D's treatment of values versus side-effect free nullary functions

[Andrei Alexandrescu]

Walter Bright wrote:
> Andrei Alexandrescu wrote:
>> Walter Bright wrote:
>>> Don wrote:
>>>> While running the semantic on each function body, the compiler could 
>>>> fairly easily check to see if the function is CTFEable. (The main 
>>>> complication is that it has to guess about how many iterations are 
>>>> performed in loops). Then, when a CTFEable function is called with 
>>>> compile-time constants as arguments, it could run CTFE on it, even 
>>>> if it is not mandatory.
>>>
>>> I think this is the halting problem, and is insoluble.
>>
>> On what basis?
> 
> Trying to determine by static analysis if a function would evaluate 
> within a "reasonable" amount of time, or even if it would finish at all.
> 
> So let's suppose the compiler just attempts CTFE on those functions 
> anyway, with a timeout if they take too long. Suddenly we've just thrown 
> all the compiler performance out the window.

Sorry for alerting the halting problem police. I feel "halting problem" 
is a kind of cop-out that is used instead of real analysis. Whenever a 
problem sounds difficult, "halting problem!" absolves us from looking 
into it.

As far as I can tell, CTFE-ability can be deterministically computed 
through a static analysis that goes like this:

1. Associate a 3-state Boolean tracking CTFE-ability (yes/no/dunno) with 
each function in the program.

2. Start analysis with all functions in the program in the "dunno" state.

3. Add all "dunno" functions to a worklist.

4. Pop one function off the worklist. If it uses only CTFE-able 
expressions and statements and calls only CTFE-able functions, mark it 
with "yes". If it calls at least one non-CTFE-able function mark it with 
"no".

5. Repeat from 4 until the worklist is empty.

6. Repeat from 3 until you make no progress (two successive epochs 
cannot reduce the number of "dunno" functions).

7. Mark all remaining "dunno" functions as "yes" (they all call each other).

At the end of this process you know all CTFE-able functions in the 
program. (A proof would be necessary to assess whether the fixed point 
is unique and independent of the order in which you look at functions etc.)

To assess CTFEability of one given function for minimum work, this 
should suffice:

1. Just like above, associate a 3-state Boolean tracking CTFE-ability 
(yes/no/dunno) with each function in the program, initially "dunno".

2. Put the function of interest in a worklist

3. Pick one function from the worklist and tentatively mark it as "yes".

5. Look at all functions it calls and put all "dunno" functions in the 
worklist

5. Continue from 3 until the worklist is empty.



Andrei