From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,571930b4ff0bc1ee X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-03-28 13:22:35 PST Newsgroups: comp.lang.ada Path: supernews.google.com!sn-xit-02!supernews.com!news.gv.tsc.tdk.com!news.iac.net!news-out.cwix.com!newsfeed.cwix.com!newsfeed.icl.net!news.tele.dk!62.112.0.25!newsfeed.online.be!zur.uu.net!ash.uu.net!world!bobduff From: Robert A Duff Subject: Re: Compile time executed functions Sender: bobduff@world.std.com (Robert A Duff) Message-ID: Date: Wed, 28 Mar 2001 21:15:18 GMT References: <3AC03CCE.70E3C2D5@mida.se> <87ae67qdrv.fsf@deneb.enyo.de> <87lmprow3a.fsf@deneb.enyo.de> <874rweoo2p.fsf@deneb.enyo.de> Organization: The World Public Access UNIX, Brookline, MA X-Newsreader: Gnus v5.3/Emacs 19.34 Xref: supernews.google.com comp.lang.ada:6172 Date: 2001-03-28T21:15:18+00:00 List-Id: Ted Dennison writes: > After thinking about this some more, I'll go so far as to say that I don't think > there are *any* languages that supply this capability. That's not correct. The Bliss language has a macro facility that can use the full power of the language at compile time. Lisp macros also allow the full power of Lisp at compile time. As you point out, this means that you can have infinite loops at compile time. In practise, that's not a big deal: you deal with infinite compile-time loops the same way as run-time ones. If you think the thing is taking too long, you type control-C and investigate. Or if you're doing a batch build, you set time-outs. Or you could have the compiler count the number of iterations of each loop, and stop after "too many". (After all, a very long loop is just as bad as an infinite one.) In fact, I would argue that compile-time infinite loops are less damaging than run-time infinite loops, because a compile-time infinite loop is guaranteed to be found by the programmer, whereas a run-time loop might sneak through testing and escape to the customer. Come to think of it, can't you write infinite loops using the C macro preprocessor? Eg, a file that #include's itself? Or a macro that expands to something containing a call to itself? >... The only possible way out is to somehow put > restrictions on the routines that may be supplied to the compiler so that all > possilbe non-halting routines are disallowed. That pretty much means nothing > with a loop (except possibly a for loop) or a goto, or another subroutine call > (recursion is another type of loop, but this may be softened by building and > checking some kind of call tree at compile time instead). It's still sort of research-y, but it is possible to do much better than that. Various techniques exist for proving that more general loops terminate. Perhaps someday it will be common practise to prove termination for 99% of the loops we actually write (and mark the residue as "can't prove" or "intentionally infinite"). But this is orthogonal to the issue of compile time vs run time. If you had a fancy program prover, you would use it for both. - Bob