Re: Compile time executed functions

[Ted Dennison<dennison@telepath.com>]

In article <874rweoo2p.fsf@deneb.enyo.de>, Florian Weimer says...
>
>Ted Dennison<dennison@telepath.com> writes:
>
>> >You build the function (or a lambda expression) using the usual
>> >methods, and then call COMPILE on it.  Simple, isn't it? ;-)
>
>> But that just generates code for the function, right?
>
>Yes, but this way, values can be computed prior to run time which
>appear to be constants (even during compile time) but are in fact not.

Ahhh. But that's not what he was talking about. He wants to be able to supply
some arbitrary function (like say an integrator or a matrix math routine or a
search routine) which the compiler will then run during the compile phase, find
the value of the result (eg: 3.57) and then place that value in a constant which
he can have the compiler stick in the ROM section of the generated code. In
order to stick a value in the ROM section, it clearly cannot be computed at
runtime. It has to be calulated by the compiler at compile time and built into a
ROM section in the reulting executable.

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. If there are, there
certianly aren't many. The reason is as follows:

Let us assume there is a compiler X that allows any aribitrary routine to be
supplied which it will run during the compile phase, find the result, and store
that result value in a constant. There are two possible approaches that X can
take to support this capability. 

Approach 1 is that compiler X makes no attempt to verify that the supplied
routine is valid. In this case, it would be possible for the user to supply a
non-halting routine to the compiler (eg: an estimating integration routine that
has a bug where it never converges). Thus a compiler that takes approach 1 can
under some circumstances go into an infinte loop during compilation due to a bug
in user code, and it must be the user's responsiblily to prevent this, and to
detect the condition when it occurs (vs. a routine that just takes a long time)
and kill the compiler somehow. This must be accepted as normal operation of
compiler X(1).

Approach 2 is that compiler X does not accept non-halting routines. However,
this means compiler X(2) is magic, since the halting problem has been proven to
be unsolvable in the general case. Whatever you do, don't tick off the developer
of X(2)! :-)

I'd claim that most developers will not accept the responsibility of an X(1)
compiler, and X(2) is impossible. 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). These restrictions
would allow some simple subroutines, but nothing complicated like a
pointer-based list search or an estimating integrator, which is the kind of
stuff the original poster wanted to use.

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
          home email - mailto:dennison@telepath.com