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

[Andrei Alexandrescu]

On 07/23/2010 03:18 PM, Walter Bright wrote:
> 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?).

The halting problem describes a program along with its inputs. The art 
is to find analyses that simplify the setup a little and produce 
conservative results while also guaranteeing they will end. My analysis 
ignores the data.

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

The analysis I discussed is a flow- and path-independent analysis. It 
always terminates and produces conservative results (i.e. it associates 
one Boolean with each function, not on each tuple of a function and 
inputs. This is how the current compiler works - if you tried your 
example, it will refuse to evaluate foo during compilation.

I agree that if you want to associate CTFEability with actual inputs you 
run into the halting problem. So the trick is to evaluate CTFE in 
isolation from inputs.


Andrei