Re: Compile time executed functions

[Robert A Duff <bobduff@world.std.com>]

Ted Dennison<dennison@telepath.com> 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