Re: Compile time executed functions

["David C. Hoos, Sr." <david.c.hoos.sr@ada95.com>]

Just to set the record straight -- the original poster's example was a CRC
lookup table -- not something that would involve the halting problem.

I had the same problem years ago when writing JOVIAL for the
AC-130 gunship.  We had to do a number of diagnostic tasks in the
idle task -- one of which was to do a CRC check on the text and constant
data areas of memory, to make sure they hadn't changed.

My solution to the table generation problem was to write a standalone
program that generated the table and wrote it to a file in JOVIAL
source code format, to be included in the source to be compiled.


"Ted Dennison" <dennison@telepath.com> wrote in message
news:Minw6.344$bY4.291@www.newsranger.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