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 09:14:19 PST Path: supernews.google.com!sn-xit-02!supernews.com!news.gv.tsc.tdk.com!newsfeed.berkeley.edu!ucberkeley!newsfeed.direct.ca!look.ca!nntp2.aus1.giganews.com!NetNews1!attws2!attor2!attor1!ip.att.net!news.hitter.net!news!news.crc.com!not-for-mail From: "David C. Hoos, Sr." Newsgroups: comp.lang.ada Subject: Re: Compile time executed functions Date: Wed, 28 Mar 2001 10:12:56 -0600 Organization: CRC: A wholly owned subsidiary of Thermo Electron Message-ID: <99t2ga$c7n$1@hobbes2.crc.com> References: <3AC03CCE.70E3C2D5@mida.se> <87ae67qdrv.fsf@deneb.enyo.de> <87lmprow3a.fsf@deneb.enyo.de> <874rweoo2p.fsf@deneb.enyo.de> NNTP-Posting-Host: 198.175.145.56 X-Trace: hobbes2.crc.com 985795914 12535 198.175.145.56 (28 Mar 2001 16:11:54 GMT) X-Complaints-To: abuse@crc.com NNTP-Posting-Date: 28 Mar 2001 16:11:54 GMT X-Newsreader: Microsoft Outlook Express 5.50.4133.2400 X-Mimeole: Produced By Microsoft MimeOLE V5.50.4133.2400 Xref: supernews.google.com comp.lang.ada:6164 Date: 2001-03-28T16:11:54+00:00 List-Id: 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" wrote in message news:Minw6.344$bY4.291@www.newsranger.com... > In article <874rweoo2p.fsf@deneb.enyo.de>, Florian Weimer says... > > > >Ted Dennison 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