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
