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

[Walter Bright]

Andrei Alexandrescu wrote:
> 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.

I thought that this was exactly the halting problem.


> 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.

Let's set aside for a moment the problem that CTFE can take an arbitrarily long 
time to run and that this cannot be predicted by any sort of static analysis 
(isn't this what the halting problem is?).

Consider the following function:

   int foo(int x, int y)
   {
     if (x == 3)
          return y + 1;
     printf("hello\n");
   }

Is that function CTFE'able? By your algorithm, no. But, consider the following call:

   const z = foo(3, 7);

Yes, it works at compile time. The particular path taken through the function 
must be CTFE'able, not the entire function. And the path cannot be statically 
determined without actually attempting to execute it.