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