Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: Programming exercise/challenge Date: Sat, 02 Jan 2021 19:17:21 -0800 Organization: A noiseless patient Spider Lines: 51 Message-ID: <86pn2mso8u.fsf@linuxsc.com> References: <86wnxwkyol.fsf@linuxsc.com> <5fcbb652$0$16505$e4fe514c@textnews.kpn.nl> <86a6tvur8x.fsf@linuxsc.com> <20210102220509.a5956ea29c0c8b1e0a0d64c4@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="ba2c00f638f312455dfdd19ce649c4ad"; logging-data="885"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+aS3Z5rS2NOd9e5kqNq9ptL7fNffcahjc=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:KgVeN9TPbjp8+nnsugM+gjBWDio= sha1:vPlirkZPXaKV1FL1bMFyzvUyI3s= Xref: csiph.com comp.lang.c:158119 Richard Damon writes: > On 1/2/21 2:05 PM, Anton Shepelev wrote: > >> Bart: >> >>> Does this program rely heavily on recursion? >>> >>> Because it tends to crash across all compilers I tried, >>> including gcc -O0, on the handful of test files I used, >>> mostly in the 1000s of lines. >> >> There are two kinds of programmer: those who consider >> recursion a form of the loop and those who consider the loop >> a form of recursion. I think that the former approach is at >> discord with the philosophy of imperative procedural >> languages, where the code directly expresses actions rather >> than "declaring" them in some vague indirect way. I believe >> the original ISO C had no provision for tail-call >> optimisation, and rightly so: if you want a loop, write >> loop. > > Tail call optimization falls fulling under the AS-IF rule, If the > compiler can generate code that works as if the call was made without > actually using a call but just a jump, it can do so if it wants (but > isn't required to). Yes, and vice versa: an iterative form may be compiled as a recursive function. Of course normally this doesn't happen, but both are allowed. > It can sometimes be a bit of work to confirm that it is ok to make the > optimization, because little things like the address of any local > variable leaking out of the context invalidates it. Yes, and there are other aspects that can prevent tail call optimization, including some that are not as obvious. However, it isn't too difficult to acquire a pretty accurate sense for which tail calls will be optimized and which ones will not. > I do agree that if it is important to the program that tail call > optimization be done, then the programmer should apply the transform > themselves, and not hope that the compiler will do it. [...] Oh I would say this differently. If it is important to the program that tail call optimization be done then it is important to verify that the compiler has done it. It isn't all that hard to write a program to scan the output of gcc -S (or clang -S) to see where there are truly recursive calls left in the compiled code. As a matter of routine I verified that my decommenting program optimized away all the recursive tail calls.