www.digitalmars.com         C & C++   DMDScript  

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

reply Justin Johansson <no spam.com> writes:
Perhaps this is a philosophical question, like what is time, though it
is also a novice programmer question as well.  The question exactly
being:

"What is the difference between a (constant/immutable) value and the
result of calling a side-effect free function that returns the same?"

May I please petition respondents not to answer in terms of PL syntax.
That is, this question is not about optional parentheses which some
PL's use to make values and nullary function calls look syntactical
alike.

Going beyond syntax and into semantics, does the D language have
any special "opinion" or idiom relating to constant/immutable
values versus nullary function calls?

 From my observation, the Scala PL community has had similar questions
poised in the past (about the difference between val's and nullary
functions) and their answer has largely given into constraints
imposed upon Scala's implementation and semantics as are
implementable on the Java Virtual Machine (JWM).

Thanks for answers,
Justin Johansson
Jul 20 2010
next sibling parent reply Jonathan M Davis <jmdavisprog gmail.com> writes:
On Tuesday, July 20, 2010 06:36:57 Justin Johansson wrote:
 Perhaps this is a philosophical question, like what is time, though it
 is also a novice programmer question as well.  The question exactly
 being:
 
 "What is the difference between a (constant/immutable) value and the
 result of calling a side-effect free function that returns the same?"
 
 May I please petition respondents not to answer in terms of PL syntax.
 That is, this question is not about optional parentheses which some
 PL's use to make values and nullary function calls look syntactical
 alike.
 
 Going beyond syntax and into semantics, does the D language have
 any special "opinion" or idiom relating to constant/immutable
 values versus nullary function calls?
 
  From my observation, the Scala PL community has had similar questions
 poised in the past (about the difference between val's and nullary
 functions) and their answer has largely given into constraints
 imposed upon Scala's implementation and semantics as are
 implementable on the Java Virtual Machine (JWM).
 
 Thanks for answers,
 Justin Johansson

1. A const variable is a chunk of memory which can be read as a particular type but not written to in that context. Optimizations may remove it in some cases. 2. An immutable variable is a chunk of memory which can be read as a particular type and cannot be written to in any context. Optimizations may remove it in some cases (and likely more cases than with const). 3. A manifest constant using an enum is a value of a particular type which is reused throughout the code without being an addressable chunk of memory (though it may still actually have an address depending on what the compiler does - you just can't address it yourself). The value never changes and cannot be changed. 4. A pure function which takes no parameters and simply returns a value of a particular type is not a chunk of memory. It's a procedure at a certain location in memory, which is therefore addressable for the purposes of calling it (or passing it around to be called). When it is run, it produces a value, and it will always produce the same value regardless of when it is run. Optimizations may remove the call in some cases and simply re-use the result. Also, the function could be used in CTFE to produce the value at compile time and just use that value instead of calling the function at runtime. Depending on how the function is used and how much optimizing the compiler does, the function may never get called at runtime. But it is ultimately a function rather than a variable, which means that it is used as a function, including what that means for addressing it. So, there _will_ be cases where it cannot be optimized out (like if you're passing around a pointer to it and calling it through the pointer). It is _not_ a variable. It may get optimized to the point that it's as efficient as a variable, but then again, it might not be. And there are cases where it acts very much like the function that it is. - Jonathan M Davis
Jul 20 2010
next sibling parent Justin Johansson <no spam.com> writes:
Jonathan M Davis wrote:
 On Tuesday, July 20, 2010 06:36:57 Justin Johansson wrote:
 Perhaps this is a philosophical question, like what is time, though it
 is also a novice programmer question as well.  The question exactly
 being:

 "What is the difference between a (constant/immutable) value and the
 result of calling a side-effect free function that returns the same?"

 May I please petition respondents not to answer in terms of PL syntax.
 That is, this question is not about optional parentheses which some
 PL's use to make values and nullary function calls look syntactical
 alike.

 Going beyond syntax and into semantics, does the D language have
 any special "opinion" or idiom relating to constant/immutable
 values versus nullary function calls?

  From my observation, the Scala PL community has had similar questions
 poised in the past (about the difference between val's and nullary
 functions) and their answer has largely given into constraints
 imposed upon Scala's implementation and semantics as are
 implementable on the Java Virtual Machine (JWM).

 Thanks for answers,
 Justin Johansson

1. A const variable is a chunk of memory which can be read as a particular type but not written to in that context. Optimizations may remove it in some cases. 2. An immutable variable is a chunk of memory which can be read as a particular type and cannot be written to in any context. Optimizations may remove it in some cases (and likely more cases than with const). 3. A manifest constant using an enum is a value of a particular type which is reused throughout the code without being an addressable chunk of memory (though it may still actually have an address depending on what the compiler does - you just can't address it yourself). The value never changes and cannot be changed. 4. A pure function which takes no parameters and simply returns a value of a particular type is not a chunk of memory. It's a procedure at a certain location in memory, which is therefore addressable for the purposes of calling it (or passing it around to be called). When it is run, it produces a value, and it will always produce the same value regardless of when it is run. Optimizations may remove the call in some cases and simply re-use the result. Also, the function could be used in CTFE to produce the value at compile time and just use that value instead of calling the function at runtime. Depending on how the function is used and how much optimizing the compiler does, the function may never get called at runtime. But it is ultimately a function rather than a variable, which means that it is used as a function, including what that means for addressing it. So, there _will_ be cases where it cannot be optimized out (like if you're passing around a pointer to it and calling it through the pointer). It is _not_ a variable. It may get optimized to the point that it's as efficient as a variable, but then again, it might not be. And there are cases where it acts very much like the function that it is. - Jonathan M Davis

Thanks for your time in constructing this well-written, well-considered and detailed answer :-) Justin
Jul 20 2010
prev sibling parent reply Justin Johansson <no spam.com> writes:
Jonathan M Davis wrote:
 Also, the 
 function could be used in CTFE to produce the value at compile time and just
use 
 that value instead of calling the function at runtime. Depending on how the 
 function is used and how much optimizing the compiler does, the function may 
 never get called at runtime.

Thanks again. This bit of insight into CTFE was particularly useful to me. :-)
Jul 20 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:
 However, what can be used in CTFE is currently rather limited.

Currently its main limitation is the amount of memory it burns. I think Don will eventually remove this problem too, even if this requires a half rewrite of the whole thing :-)
 You also generally have to force the issue a 
 bit by using it in places where the value _must_ be known at compile-time
(such 
 as enum values, member variable initializations, etc.). I'm not sure that CTFE 
 gets done at this point if it doesn't need to be.

Currently CTFE is performed only where explicitly asked for. DMD doesn't currently perform partial compilation (except the kind of manual compilation done with constant template arguments).
 So, how much CTFE does for you depends on the current state of the compiler
(and 
 likely whether you compiling with optimizations turned on), but it definitely
has 
 the capacity to run functions - especially pure ones - at compile time such
that 
 they may never get called at runtime.

As far as I know, currently optimization level doesn't influence CTFE. Bye, bearophile
Jul 20 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:
 But theoretically, it 
 could be used for optimizations just like inlining (particularly with pure 
 functions), and that being the case, it probably will at some point.

Pure functions go well with CTFE because they don't use global state, but you can run code at compile time only if all the arguments are known at compile time :-) If some of their arguments are known at compile time and some of them are not known, and you want to optimize better, then you need partial compilation, that is a bit hard to implement, probably makes the compiler slow and complex. So for a practical form of manual partial compilation practical time ago I have proposed something similar to GCC __builtin_constant_p (http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html#index-g_t_005f_005fbuiltin_005 constant_005fp-2392 ), that is syntax sugar that you can use inside functions to turn them into templates (I don't know if you can also have a single entry point to keep the possibility of taking their address). You can use a static if with such __trait(isCTAgument, foo), to tell if each function argument as foo is known at compile time, and do something with it if it is. This is like defining those arguments as CT template arguments, that later the optimizer can optimize better (and perform the partial compilation). Bye, bearophile
Jul 20 2010
next sibling parent reply Don <nospam nospam.com> writes:
Jonathan M Davis wrote:
 On Tuesday, July 20, 2010 17:24:33 bearophile wrote:
 Jonathan M Davis:
 But theoretically, it
 could be used for optimizations just like inlining (particularly with
 pure functions), and that being the case, it probably will at some
 point.

you can run code at compile time only if all the arguments are known at compile time :-) If some of their arguments are known at compile time and some of them are not known, and you want to optimize better, then you need partial compilation, that is a bit hard to implement, probably makes the compiler slow and complex. So for a practical form of manual partial compilation practical time ago I have proposed something similar to GCC __builtin_constant_p (http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html#index-g_t _005f_005fbuiltin_005fconstant_005fp-2392 ), that is syntax sugar that you can use inside functions to turn them into templates (I don't know if you can also have a single entry point to keep the possibility of taking their address). You can use a static if with such __trait(isCTAgument, foo), to tell if each function argument as foo is known at compile time, and do something with it if it is. This is like defining those arguments as CT template arguments, that later the optimizer can optimize better (and perform the partial compilation). Bye, bearophile

Partial compilation would indeed be a big step forward, but it would certainly be a lot of work. Just being able to have functions run with CTFE which could be fully run with CTFE would lead to some nice optimizations. Certainly, that would need to be achieved before we could look at having partial compilation. Still, partial compilation would certainly be cool if we ever reached that point. - Jonathan M Davis

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. Incidentally, having the function being marked as 'pure' doesn't really help at all for determining if it is CTFEable.
Jul 21 2010
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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. This is why the language does CTFE in well-defined circumstances and the CTFE must succeed else a compilation time error. I'm not seeing CTFE as a credible optimization tool, either, as none of my programs would benefit at all from it. For example, what's a text editor going to precompute?
Jul 21 2010
next sibling parent reply Don <nospam nospam.com> writes:
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.

In general, yes. But some quite useful instances are trivial.
 
 This is why the language does CTFE in well-defined circumstances and the 
 CTFE must succeed else a compilation time error.

 
 I'm not seeing CTFE as a credible optimization tool, either, as none of 
 my programs would benefit at all from it. For example, what's a text 
 editor going to precompute?

All it would be, would be moving parts of the optimization step from the back-end into the front-end. In theory, it wouldn't gain you anything. In practice, there may be some optimisations which are easier to do in the front-end than the back-end. An existing example of this is with: if(false) { xxx; } where the entire xxx clause is dropped immediately, and not sent to the backend at all. It don't think this has any practical consequences, it's merely an extra bit of freedom for compiler writers to implement optimisation.
Jul 21 2010
parent Don <nospam nospam.com> writes:
Fawzi Mohamed wrote:
 
 On 21-lug-10, at 11:37, Don 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.


In general, yes. But some quite useful instances are trivial.
 This is why the language does CTFE in well-defined circumstances and 
 the CTFE must succeed else a compilation time error.

 I'm not seeing CTFE as a credible optimization tool, either, as none 
 of my programs would benefit at all from it. For example, what's a 
 text editor going to precompute?

All it would be, would be moving parts of the optimization step from the back-end into the front-end. In theory, it wouldn't gain you anything. In practice, there may be some optimisations which are easier to do in the front-end than the back-end. An existing example of this is with: if(false) { xxx; } where the entire xxx clause is dropped immediately, and not sent to the backend at all. It don't think this has any practical consequences, it's merely an extra bit of freedom for compiler writers to implement optimisation.

Yes, but normally I dislike too much *unpredictable* magic. yes you can try to evaluate some functions at compile time, but which ones? You try for like 1s and if the calculation does not complete postpone it to the runtime? This then becomes Haskell like in the sense that some small changes to the source give large changes to the runtime, in a way that is not clearly seen from the source code.

There is absolutely no difference between this and the optimiser.
 
 I am with Walter on this, one thing should be either compile time or 
 runtime, and a programmer should be able to tell which is which.
 

Jul 21 2010
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Walter Bright:
 I'm not seeing CTFE as a credible optimization tool, either, as none of my
 programs would benefit at all from it. For example, what's a text editor going
 to precompute?

The manual partial compilation I have explained is useful for numerical code. The example where I have seen improvements was a convolution with small mask. When the mask was known at compile time the compiler has able to speed up code almost twice. Partial compilation can be useful, but it's hard to implement, so I have suggested a practical way to implement it manually, with some syntax sugar. Bye, bearophile
Jul 21 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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? Andrei
Jul 21 2010
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Jul 23 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jul 23 2010
parent reply Walter Bright <newshound2 digitalmars.com> writes:
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.
Jul 23 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jul 23 2010
parent reply Walter Bright <newshound2 digitalmars.com> writes:
Andrei Alexandrescu wrote:
 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.

That's because there's an unrelated bug in it :-( Here's the corrected example: import std.c.stdio; int foo(int x, int y) { if (x == 3) return y + 1; printf("hello\n"); return 0; } const z = foo(3, 7); The compiler does not work as you suggest it does.
Jul 24 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Walter Bright wrote:
 Andrei Alexandrescu wrote:
 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.

That's because there's an unrelated bug in it :-( Here's the corrected example: import std.c.stdio; int foo(int x, int y) { if (x == 3) return y + 1; printf("hello\n"); return 0; } const z = foo(3, 7); The compiler does not work as you suggest it does.

That's actually good, meaning that the compiler can and will, when pressed, forge forward with CTFE even if unsure. The analysis I suggested would allow the compiler to automatically CTFE certain functions in confidence that they are, in fact, CTFE-able. Andrei
Jul 24 2010
prev sibling parent reply "Jim Balter" <Jim Balter.name> writes:
"Walter Bright" <newshound2 digitalmars.com> wrote in message 
news:i2cteh$ufq$1 digitalmars.com...
 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.

A common misconception, but not so. The halting problem is to find an algorithm that will, for every possible function and data as input, correctly determine whether the function will terminate. Turing proved that such an algorithm is impossible, but that's irrelevant to any practical problem. Not only isn't it necessary to guarantee that the functions you decide not to attempt CTFE on really don't terminate, but no function in any real program looks anthing like the arcane function that Turing proved will baffle your algorithm. -- jqb
 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.

Jul 24 2010
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 24/07/10 12:43 PM, Jim Balter wrote:
 I thought that this was exactly the halting problem.

A common misconception, but not so. The halting problem is to find an algorithm that will, for every possible function and data as input, correctly determine whether the function will terminate. Turing proved that such an algorithm is impossible, but that's irrelevant to any practical problem. Not only isn't it necessary to guarantee that the functions you decide not to attempt CTFE on really don't terminate, but no function in any real program looks anthing like the arcane function that Turing proved will baffle your algorithm.

Walter is right. Yes, Turing did prove it using an unrealistic example, but the only reason he did so was to keep the proof simple. There are plenty of practical examples of functions which are difficult (or impossible) to determine whether or not they terminate. In particular, any recursion or unconstrained loops make it very difficult to prove termination, and there's plenty of practical examples of those e.g. quicksort.
Jul 24 2010
parent reply "Jim Balter" <Jim Balter.name> writes:
"Peter Alexander" <peter.alexander.au gmail.com> wrote in message 
news:i2er6d$1jkv$1 digitalmars.com...
 On 24/07/10 12:43 PM, Jim Balter wrote:
 I thought that this was exactly the halting problem.

A common misconception, but not so. The halting problem is to find an algorithm that will, for every possible function and data as input, correctly determine whether the function will terminate. Turing proved that such an algorithm is impossible, but that's irrelevant to any practical problem. Not only isn't it necessary to guarantee that the functions you decide not to attempt CTFE on really don't terminate, but no function in any real program looks anthing like the arcane function that Turing proved will baffle your algorithm.

Walter is right.

No, he's not, and I explained why, and you have failed to rebut anything I wrote.
 Yes, Turing did prove it using an unrealistic example, but the only reason 
 he did so was to keep the proof simple.

You have no absolutely no idea what you're talking about; Turing's proof is reductio ad absurdum based on a diagonalization argument -- the constructed undeterminable function is dependent on the algorithm purported to be able to decide it. See http://en.wikipedia.org/wiki/Halting_problem
 There are plenty of practical examples of functions which are difficult 
 (or impossible) to determine whether or not they terminate.

The halting problem proof isn't about "diffiicult", only "impossible", and you have failed to provide a function and a proof that it is *impossible* to determine whether it terminates.
 In particular, any recursion or unconstrained loops make it very difficult 
 to prove termination, and there's plenty of practical examples of those 
 e.g. quicksort.

Again, difficulty is not an issue, *impossibility* is -- *that* is what the halting problem is, and if you don't understand that then you don't understand the issue *at all*.
Jul 24 2010
parent reply "Jim Balter" <Jim Balter.name> writes:
"Jim Balter" <Jim Balter.name> wrote in message 
news:i2fkp7$2if$1 digitalmars.com...
 "Peter Alexander" <peter.alexander.au gmail.com> wrote in message 
 news:i2er6d$1jkv$1 digitalmars.com...
 On 24/07/10 12:43 PM, Jim Balter wrote:
 I thought that this was exactly the halting problem.

A common misconception, but not so. The halting problem is to find an algorithm that will, for every possible function and data as input, correctly determine whether the function will terminate. Turing proved that such an algorithm is impossible, but that's irrelevant to any practical problem. Not only isn't it necessary to guarantee that the functions you decide not to attempt CTFE on really don't terminate, but no function in any real program looks anthing like the arcane function that Turing proved will baffle your algorithm.

Walter is right.

No, he's not, and I explained why, and you have failed to rebut anything I wrote.
 Yes, Turing did prove it using an unrealistic example, but the only 
 reason he did so was to keep the proof simple.

You have no absolutely no idea what you're talking about; Turing's proof is reductio ad absurdum based on a diagonalization argument -- the constructed undeterminable function is dependent on the algorithm purported to be able to decide it. See http://en.wikipedia.org/wiki/Halting_problem
 There are plenty of practical examples of functions which are difficult 
 (or impossible) to determine whether or not they terminate.

The halting problem proof isn't about "diffiicult", only "impossible", and you have failed to provide a function and a proof that it is *impossible* to determine whether it terminates.
 In particular, any recursion or unconstrained loops make it very 
 difficult to prove termination, and there's plenty of practical examples 
 of those e.g. quicksort.

Again, difficulty is not an issue, *impossibility* is -- *that* is what the halting problem is, and if you don't understand that then you don't understand the issue *at all*.

P.S. The point about difficulty goes to why this is not a matter of the halting problem. Even if the halting problem were decidable, that would not help us in the slightest because we are trying to solve a *practical* problem. Even if you could prove, for every given function, whether it would halt on all inputs, that wouldn't tell you which ones to perform CTFE on -- we want CTFE to terminate before the programmer dies of old age. The halting problem is strictly a matter of theory; it's ironic to see someone who has designed a programming language based on *pragmatic* rather than theoretical considerations to invoke it.
Jul 24 2010
parent reply Rainer Deyke <rainerd eldwood.com> writes:
On 7/24/2010 15:34, Jim Balter wrote:
 The point about difficulty goes to why this is not a matter of the
 halting problem. Even if the halting problem were decidable, that would
 not help us in the slightest because we are trying to solve a
 *practical* problem. Even if you could prove, for every given function,
 whether it would halt on all inputs, that wouldn't tell you which ones
 to perform CTFE on -- we want CTFE to terminate before the programmer
 dies of old age. The halting problem is strictly a matter of theory;
 it's ironic to see someone who has designed a programming language based
 on *pragmatic* rather than theoretical considerations to invoke it.

That's exactly backwards. It's better to catch errors at compile time than at run time. A program that fails to terminate and fails to perform I/O is a faulty program. (A function that performs I/O is obviously not a candidate for CTFE.) I'd rather catch the faulty program by having the compiler lock up at compile time than by having the compiled program lock up after deployment. Testing whether the program terminates at compile time by attempting to execute the program at compile time is a feature, not a bug. -- Rainer Deyke - rainerd eldwood.com
Jul 24 2010
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Rainer Deyke:
 (A function that performs I/O is
 obviously not a candidate for CTFE.)

I don't fully agree, see this enhancement request of mine: http://d.puremagic.com/issues/show_bug.cgi?id=3952 Bye, bearophile
Jul 24 2010
parent "Jim Balter" <Jim Balter.name> writes:
"bearophile" <bearophileHUGS lycos.com> wrote in message 
news:i2g42t$10ce$1 digitalmars.com...
 Rainer Deyke:
 (A function that performs I/O is
 obviously not a candidate for CTFE.)

I don't fully agree, see this enhancement request of mine: http://d.puremagic.com/issues/show_bug.cgi?id=3952 Bye, bearophile

"performs I/O" refers to the semantics of the running program; the I/O is done at the time the function is invoked. I/O done by pragma(msg, ...) or ctputs is performed by the compiler, not by the function. Obviously, as Rainer said, no CTFE function can perform I/O since that I/O would never get performed by the running program. Also, I think computing compile-time messages is an abuse of CTFE -- it certainly isn't its intended purpose.
Jul 25 2010
prev sibling parent reply "Jim Balter" <Jim Balter.name> writes:
"Rainer Deyke" <rainerd eldwood.com> wrote in message 
news:i2g3oo$von$1 digitalmars.com...
 On 7/24/2010 15:34, Jim Balter wrote:
 The point about difficulty goes to why this is not a matter of the
 halting problem. Even if the halting problem were decidable, that would
 not help us in the slightest because we are trying to solve a
 *practical* problem. Even if you could prove, for every given function,
 whether it would halt on all inputs, that wouldn't tell you which ones
 to perform CTFE on -- we want CTFE to terminate before the programmer
 dies of old age. The halting problem is strictly a matter of theory;
 it's ironic to see someone who has designed a programming language based
 on *pragmatic* rather than theoretical considerations to invoke it.

That's exactly backwards. It's better to catch errors at compile time than at run time. A program that fails to terminate and fails to perform I/O is a faulty program. (A function that performs I/O is obviously not a candidate for CTFE.) I'd rather catch the faulty program by having the compiler lock up at compile time than by having the compiled program lock up after deployment. Testing whether the program terminates at compile time by attempting to execute the program at compile time is a feature, not a bug.

You have a good point, and that point would imply that whether a function would terminate, or how long it would take in general, isn't relevant to the decision of whether CTFE should be done. But there are (at least) two problems: 1) you can't be certain that the code will be run at run time at all -- in generic code you could easily have function invocations with constant values that would fail in various ways but the function is never run with those values because of prior tests. But CTFE wouldn't be nearly as useful if it is performed only for code that you can be certain will run. If you can't be certain, then you need a conservative approach, and you must not report errors that might never occur at run time; if you can be certain, then you could forge ahead at compile time no matter how long the computation would take. But: 2) You do not have the debug facilities at compile time that you have at run time. If the program stalls at run time, you can attach a debugger to it and find out what it's doing. But if CTFE is running at compile time and the compiler stalls, you don't know why ... unless the compiler has a mechanism such that you can interrupt it and it can report an execution trace of the CTFE code. That still is not enough -- you really need full debug capabilites to trace the code, all available at compile time. That's just too much.
 -- 
 Rainer Deyke - rainerd eldwood.com 

Jul 25 2010
next sibling parent Don <nospam nospam.com> writes:
Jim Balter wrote:
 
 "Rainer Deyke" <rainerd eldwood.com> wrote in message 
 news:i2g3oo$von$1 digitalmars.com...
 On 7/24/2010 15:34, Jim Balter wrote:
 The point about difficulty goes to why this is not a matter of the
 halting problem. Even if the halting problem were decidable, that would
 not help us in the slightest because we are trying to solve a
 *practical* problem. Even if you could prove, for every given function,
 whether it would halt on all inputs, that wouldn't tell you which ones
 to perform CTFE on -- we want CTFE to terminate before the programmer
 dies of old age. The halting problem is strictly a matter of theory;
 it's ironic to see someone who has designed a programming language based
 on *pragmatic* rather than theoretical considerations to invoke it.

That's exactly backwards. It's better to catch errors at compile time than at run time. A program that fails to terminate and fails to perform I/O is a faulty program. (A function that performs I/O is obviously not a candidate for CTFE.) I'd rather catch the faulty program by having the compiler lock up at compile time than by having the compiled program lock up after deployment. Testing whether the program terminates at compile time by attempting to execute the program at compile time is a feature, not a bug.

You have a good point, and that point would imply that whether a function would terminate, or how long it would take in general, isn't relevant to the decision of whether CTFE should be done. But there are (at least) two problems: 1) you can't be certain that the code will be run at run time at all -- in generic code you could easily have function invocations with constant values that would fail in various ways but the function is never run with those values because of prior tests. But CTFE wouldn't be nearly as useful if it is performed only for code that you can be certain will run. If you can't be certain, then you need a conservative approach, and you must not report errors that might never occur at run time; if you can be certain, then you could forge ahead at compile time no matter how long the computation would take. But: 2) You do not have the debug facilities at compile time that you have at run time. If the program stalls at run time, you can attach a debugger to it and find out what it's doing. But if CTFE is running at compile time and the compiler stalls, you don't know why ... unless the compiler has a mechanism such that you can interrupt it and it can report an execution trace of the CTFE code. That still is not enough -- you really need full debug capabilites to trace the code, all available at compile time. That's just too much.

The D plugin for Eclipse included a compile-time debugger (!)
Jul 25 2010
prev sibling parent reply Rainer Deyke <rainerd eldwood.com> writes:
On 7/25/2010 13:41, Jim Balter wrote:
 But there are
 (at least) two problems: 1) you can't be certain that the code will be
 run at run time at all -- in generic code you could easily have function
 invocations with constant values that would fail in various ways but the
 function is never run with those values because of prior tests.

That's a good point - but at the same time, I'm having trouble thinking of any sensible example where this would be an issue. It would require at all of the following factors: - The function itself is a candidate for CTFE. - The arguments to the function can be evaluated at compile time, but are not simple constants (i.e. they depend on template parameters). - The code that calls the function depends on run-time parameters. - The function is never called with parameters that prevent it from terminating, but the compiler is unable to determine that this is the case. Something like this would work, I guess, but it's horribly contrived: int terminate_if_nonzero(int i) { return (i != 0) ? i : terminate_if_nonzero(i); } void f(int i)(bool call_it) { if (call_it) terminate_if_nonzero(i); } bool get_input_and_return_false() { // This function is not a CTFE candidate because it performs I/O. read_input(); return false; } void main() { f!(0)(get_input_and_return_false()); } -- Rainer Deyke - rainerd eldwood.com
Jul 26 2010
parent reply "Jim Balter" <Jim Balter.name> writes:
"Rainer Deyke" <rainerd eldwood.com> wrote in message 
news:i2jeja$1lha$1 digitalmars.com...
 On 7/25/2010 13:41, Jim Balter wrote:
 But there are
 (at least) two problems: 1) you can't be certain that the code will be
 run at run time at all -- in generic code you could easily have function
 invocations with constant values that would fail in various ways but the
 function is never run with those values because of prior tests.

That's a good point - but at the same time, I'm having trouble thinking of any sensible example where this would be an issue.

Consider some code that calls a pure function that uses a low-overhead exponential algorithm when the parameter is small, and otherwise calls a pure function that uses a high-overhead linear algorithm. The calling code happens not to be CTFEable and thus the test, even though it only depends on a constant, is not computed at compile time. The compiler sees two calls, one to each of the two functions, with the same parameter passed to each, but only one of the two will actually be called at run time. Trying to evaluate the low-overhead exponential algorithm with large parameters at compile time would be a lose without a timeout to terminate the attempt. It might be best if the compiler only attempts CTFE if the code explicitly requests it.
 It would require
 at all of the following factors:
  - The function itself is a candidate for CTFE.
  - The arguments to the function can be evaluated at compile time, but
 are not simple constants (i.e. they depend on template parameters).
  - The code that calls the function depends on run-time parameters.
  - The function is never called with parameters that prevent it from
 terminating, but the compiler is unable to determine that this is the 
 case.

 Something like this would work, I guess, but it's horribly contrived:

 int terminate_if_nonzero(int i) {
  return (i != 0) ? i : terminate_if_nonzero(i);
 }

 void f(int i)(bool call_it) {
  if (call_it) terminate_if_nonzero(i);
 }

 bool get_input_and_return_false() {
  // This function is not a CTFE candidate because it performs I/O.
  read_input();
  return false;
 }

 void main() {
  f!(0)(get_input_and_return_false());
 }


 -- 
 Rainer Deyke - rainerd eldwood.com 

Jul 26 2010
parent reply Rainer Deyke <rainerd eldwood.com> writes:
On 7/26/2010 18:30, Jim Balter wrote:
 Consider some code that calls a pure function that uses a low-overhead
 exponential algorithm when the parameter is small, and otherwise calls a
 pure function that uses a high-overhead linear algorithm. The calling
 code happens not to be CTFEable and thus the test, even though it only
 depends on a constant, is not computed at compile time. The compiler
 sees two calls, one to each of the two functions, with the same
 parameter passed to each, but only one of the two will actually be
 called at run time. Trying to evaluate the low-overhead exponential
 algorithm with large parameters at compile time would be a lose without
 a timeout to terminate the attempt. It might be best if the compiler
 only attempts CTFE if the code explicitly requests it.

It seems to me that you're describing something like this: if (x < some_limit) { return some_function(x); } else { return some_other_function(x); } This does not pose a problem, assuming 'some_limit' is a compile-time constant. If 'x' is known at compile, the test can be performed at compile time. If 'x' is not known at compile time, neither of the function invocations can be evaluated at compile time. The problem does exist in this code: if (complex_predicate(x)) { return some_function(x); } else { return some_other_function(x); } ...but only if 'complex_predicate' is not a candidate for CTFE but the other functions are. (This can happen if 'complex_predicate' performs any type of output, including debug logging, so the scenario is not entirely unlikely.) Actually I'm not entirely sure if CTFE is even necessary for producing optimal code. The optimizations enabled by CTFE seem like a subset of those enabled by aggressive inlining combined with other common optimizations. -- Rainer Deyke - rainerd eldwood.com
Jul 26 2010
parent Don <nospam nospam.com> writes:
Rainer Deyke wrote:
 On 7/26/2010 18:30, Jim Balter wrote:
 Consider some code that calls a pure function that uses a low-overhead
 exponential algorithm when the parameter is small, and otherwise calls a
 pure function that uses a high-overhead linear algorithm. The calling
 code happens not to be CTFEable and thus the test, even though it only
 depends on a constant, is not computed at compile time. The compiler
 sees two calls, one to each of the two functions, with the same
 parameter passed to each, but only one of the two will actually be
 called at run time. Trying to evaluate the low-overhead exponential
 algorithm with large parameters at compile time would be a lose without
 a timeout to terminate the attempt. It might be best if the compiler
 only attempts CTFE if the code explicitly requests it.

It seems to me that you're describing something like this: if (x < some_limit) { return some_function(x); } else { return some_other_function(x); } This does not pose a problem, assuming 'some_limit' is a compile-time constant. If 'x' is known at compile, the test can be performed at compile time. If 'x' is not known at compile time, neither of the function invocations can be evaluated at compile time. The problem does exist in this code: if (complex_predicate(x)) { return some_function(x); } else { return some_other_function(x); } ...but only if 'complex_predicate' is not a candidate for CTFE but the other functions are. (This can happen if 'complex_predicate' performs any type of output, including debug logging, so the scenario is not entirely unlikely.) Actually I'm not entirely sure if CTFE is even necessary for producing optimal code. The optimizations enabled by CTFE seem like a subset of those enabled by aggressive inlining combined with other common optimizations.

I think that's probably true. If the inliner is in the front-end (as is currently the case in DMD, but not DMC), then CTFE can produce better code. If functions can be inlined *after* optimisation, CTFE may be a more efficient way to perform certain optimisations, but otherwise it's probably not much of a win. From the programmer's point of view, it makes no difference whether it is done or not.
Jul 29 2010
prev sibling parent reply Don <nospam nospam.com> writes:
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.

But it doesn't need to perfectly solve the complete halting problem. It can be of benefit if it just identifies some functions which can be trivially shown to halt, and ignores any which it is unsure about. For example, a function which contains no loops and no recursive calls is always CTFEable. Admittedly, that probably doesn't include many functions which wouldn't be inlined anyway. But still, while checking for which functions are inlinable, the compiler could check for 'trivially CTFEable' at the same time. If a CTFEable call is made to an inlinable function, it's probably quicker to CTFE it rather than inline + optimize. Assuming of course that we have a fast implementation of CTFE. I completely agree that there will always be opportunities for CTFE which will be missed unless you allow the compile time to become arbitrarily long.
Jul 23 2010
next sibling parent reply div0 <div0 users.sourceforge.net> writes:
On 23/07/2010 21:54, Don wrote:
 I completely agree that there will always be opportunities for CTFE
 which will be missed unless you allow the compile time to become
 arbitrarily long.

Which is why ultimately it should be up to the programmer to decide. There should be a way to force the compiler to try CTFE, unless it can absolutely prove the function is not CTFE. -- My enormous talent is exceeded only by my outrageous laziness. http://www.ssTk.co.uk
Jul 23 2010
parent reply "Jim Balter" <Jim Balter.name> writes:
"div0" <div0 users.sourceforge.net> wrote in message 
news:i2d2ek$179m$1 digitalmars.com...
 On 23/07/2010 21:54, Don wrote:
 I completely agree that there will always be opportunities for CTFE
 which will be missed unless you allow the compile time to become
 arbitrarily long.

Which is why ultimately it should be up to the programmer to decide. There should be a way to force the compiler to try CTFE, unless it can absolutely prove the function is not CTFE.

That's what command line optimzation options are for.
 -- 
 My enormous talent is exceeded only by my outrageous laziness.
 http://www.ssTk.co.uk 

Jul 24 2010
parent reply div0 <div0 users.sourceforge.net> writes:
On 24/07/2010 12:46, Jim Balter wrote:
 "div0" <div0 users.sourceforge.net> wrote in message
 news:i2d2ek$179m$1 digitalmars.com...
 On 23/07/2010 21:54, Don wrote:
 I completely agree that there will always be opportunities for CTFE
 which will be missed unless you allow the compile time to become
 arbitrarily long.

Which is why ultimately it should be up to the programmer to decide. There should be a way to force the compiler to try CTFE, unless it can absolutely prove the function is not CTFE.

That's what command line optimzation options are for.

No they aren't. command line options apply to the entire module(s) not to specific invocations of a function. -- My enormous talent is exceeded only by my outrageous laziness. http://www.ssTk.co.uk
Jul 24 2010
parent bearophile <bearophileHUGS lycos.com> writes:
div0:
 No they aren't.
 command line options apply to the entire module(s) not to specific 
 invocations of a function.

In both GNU C and CLisp you can add annotations to change the optimization level on a function by function basis: http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html#index-g_t_0040code_007boptimize_007d-function-attribute-2419 Bye, bearophile
Jul 24 2010
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 07/23/2010 03:54 PM, Don 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.

But it doesn't need to perfectly solve the complete halting problem. It can be of benefit if it just identifies some functions which can be trivially shown to halt, and ignores any which it is unsure about. For example, a function which contains no loops and no recursive calls is always CTFEable. Admittedly, that probably doesn't include many functions which wouldn't be inlined anyway. But still, while checking for which functions are inlinable, the compiler could check for 'trivially CTFEable' at the same time. If a CTFEable call is made to an inlinable function, it's probably quicker to CTFE it rather than inline + optimize. Assuming of course that we have a fast implementation of CTFE. I completely agree that there will always be opportunities for CTFE which will be missed unless you allow the compile time to become arbitrarily long.

By the way, remember you asked at some point what removeAny in std.container is good for? CTFEability analysis could use such a primitive... Andrei
Jul 23 2010
prev sibling next sibling parent Don <nospam nospam.com> writes:
Jonathan M Davis wrote:
 On Wednesday 21 July 2010 00:09:05 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.

 Incidentally, having the function being marked as 'pure' doesn't really
 help at all for determining if it is CTFEable.

Hmm. As I understood it, it did. But I guess that if it did, the compiler could technically determine whether a function was actually pure anyway by looking at its body. All the pure attribute would do is save it the trouble. So, the pure attribute wouldn't do much in that sense except save the compiler some computation. I can certainly see why being pure wouldn't be enough to be CTFEable (since pure doesn't guarantee anything about whether it's parameters are know at compile time), but I would have thought that the lack of global state would be required - at least the lack of global state which isn't known at compile time - for it to be CTFEable, in which case the pureness would help.

The check for no globals is common to both CTFE and pure, but it's pretty trivial. There are functions which are pure but not CTFEable, eg CTFE requires source code to be available, pure does not. More interestingly, there are many functions which are CTFEable which are not pure. It's OK for a CTFE function to modify values which are reachable through its parameters. So although CTFEable and pure have significant overlap, neither one is a subset of the other.
 
 In any case, I'd obviously have to study it up a bit more to understand
exactly 
 what's required for CTFEability. I have some idea, but obviously not enough.
 
 - Jonathan M Davis

Jul 21 2010
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Don wrote:
 Jonathan M Davis wrote:
 On Tuesday, July 20, 2010 17:24:33 bearophile wrote:
 Jonathan M Davis:
 But theoretically, it
 could be used for optimizations just like inlining (particularly with
 pure functions), and that being the case, it probably will at some
 point.

but you can run code at compile time only if all the arguments are known at compile time :-) If some of their arguments are known at compile time and some of them are not known, and you want to optimize better, then you need partial compilation, that is a bit hard to implement, probably makes the compiler slow and complex. So for a practical form of manual partial compilation practical time ago I have proposed something similar to GCC __builtin_constant_p (http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html#index-g_t _005f_005fbuiltin_005fconstant_005fp-2392 ), that is syntax sugar that you can use inside functions to turn them into templates (I don't know if you can also have a single entry point to keep the possibility of taking their address). You can use a static if with such __trait(isCTAgument, foo), to tell if each function argument as foo is known at compile time, and do something with it if it is. This is like defining those arguments as CT template arguments, that later the optimizer can optimize better (and perform the partial compilation). Bye, bearophile

Partial compilation would indeed be a big step forward, but it would certainly be a lot of work. Just being able to have functions run with CTFE which could be fully run with CTFE would lead to some nice optimizations. Certainly, that would need to be achieved before we could look at having partial compilation. Still, partial compilation would certainly be cool if we ever reached that point. - Jonathan M Davis

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

I don' think that's easy. The compiler would need to do a fixed-point iteration on the transitive closure of the functions called by the analyzed function. Andrei
Jul 21 2010
prev sibling parent Fawzi Mohamed <fawzi gmx.ch> writes:
On 21-lug-10, at 11:37, Don 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.


In general, yes. But some quite useful instances are trivial.
 This is why the language does CTFE in well-defined circumstances  
 and the CTFE must succeed else a compilation time error.

 I'm not seeing CTFE as a credible optimization tool, either, as  
 none of my programs would benefit at all from it. For example,  
 what's a text editor going to precompute?

All it would be, would be moving parts of the optimization step from the back-end into the front-end. In theory, it wouldn't gain you anything. In practice, there may be some optimisations which are easier to do in the front-end than the back-end. An existing example of this is with: if(false) { xxx; } where the entire xxx clause is dropped immediately, and not sent to the backend at all. It don't think this has any practical consequences, it's merely an extra bit of freedom for compiler writers to implement optimisation.

Yes, but normally I dislike too much *unpredictable* magic. yes you can try to evaluate some functions at compile time, but which ones? You try for like 1s and if the calculation does not complete postpone it to the runtime? This then becomes Haskell like in the sense that some small changes to the source give large changes to the runtime, in a way that is not clearly seen from the source code. I am with Walter on this, one thing should be either compile time or runtime, and a programmer should be able to tell which is which.
Jul 21 2010
prev sibling next sibling parent Jonathan M Davis <jmdavisprog gmail.com> writes:
On Tuesday, July 20, 2010 14:28:16 Justin Johansson wrote:
 Jonathan M Davis wrote:
 Also, the
 function could be used in CTFE to produce the value at compile time and
 just use that value instead of calling the function at runtime.
 Depending on how the function is used and how much optimizing the
 compiler does, the function may never get called at runtime.

Thanks again. This bit of insight into CTFE was particularly useful to me. :-)

Glad to be of help. I would point out though that CTFE is its infancy at this point. I believe that the goal is to have the entirety of SafeD work with CTFE and likely use it in optimizations quite a bit. However, what can be used in CTFE is currently rather limited. You also generally have to force the issue a bit by using it in places where the value _must_ be known at compile-time (such as enum values, member variable initializations, etc.). I'm not sure that CTFE gets done at this point if it doesn't need to be. It's certainly a goal though for it to be much more expansive. And pure functions are a prime candidate for CTFE since they don't rely on global state at all (pure functions with no parameters even more so since there's never a case where you don't know one or more of their parameters at compile time). So, how much CTFE does for you depends on the current state of the compiler (and likely whether you compiling with optimizations turned on), but it definitely has the capacity to run functions - especially pure ones - at compile time such that they may never get called at runtime. - Jonathan M Davis
Jul 20 2010
prev sibling next sibling parent Jonathan M Davis <jmdavisprog gmail.com> writes:
On Tuesday, July 20, 2010 15:49:56 bearophile wrote:
 
 As far as I know, currently optimization level doesn't influence CTFE.

Well, like I said. It depends on what exactly the compiler does, and as far as I know, it only does CTFE when it has to for initialization. But theoretically, it could be used for optimizations just like inlining (particularly with pure functions), and that being the case, it probably will at some point. Not knowing exactly what it does right now, I don't _know_ that it doesn't do that right now, but I would expect that you're right and it doesn't currently use CTFE for optimizations. Hopefully that will eventually happen though. - Jonathan M Davis
Jul 20 2010
prev sibling next sibling parent Jonathan M Davis <jmdavisprog gmail.com> writes:
On Tuesday, July 20, 2010 17:24:33 bearophile wrote:
 Jonathan M Davis:
 But theoretically, it
 could be used for optimizations just like inlining (particularly with
 pure functions), and that being the case, it probably will at some
 point.

Pure functions go well with CTFE because they don't use global state, but you can run code at compile time only if all the arguments are known at compile time :-) If some of their arguments are known at compile time and some of them are not known, and you want to optimize better, then you need partial compilation, that is a bit hard to implement, probably makes the compiler slow and complex. So for a practical form of manual partial compilation practical time ago I have proposed something similar to GCC __builtin_constant_p (http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html#index-g_t _005f_005fbuiltin_005fconstant_005fp-2392 ), that is syntax sugar that you can use inside functions to turn them into templates (I don't know if you can also have a single entry point to keep the possibility of taking their address). You can use a static if with such __trait(isCTAgument, foo), to tell if each function argument as foo is known at compile time, and do something with it if it is. This is like defining those arguments as CT template arguments, that later the optimizer can optimize better (and perform the partial compilation). Bye, bearophile

Partial compilation would indeed be a big step forward, but it would certainly be a lot of work. Just being able to have functions run with CTFE which could be fully run with CTFE would lead to some nice optimizations. Certainly, that would need to be achieved before we could look at having partial compilation. Still, partial compilation would certainly be cool if we ever reached that point. - Jonathan M Davis
Jul 20 2010
prev sibling next sibling parent reply Jonathan M Davis <jmdavisprog gmail.com> writes:
On Wednesday 21 July 2010 00:09:05 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.
 
 Incidentally, having the function being marked as 'pure' doesn't really
 help at all for determining if it is CTFEable.

Hmm. As I understood it, it did. But I guess that if it did, the compiler could technically determine whether a function was actually pure anyway by looking at its body. All the pure attribute would do is save it the trouble. So, the pure attribute wouldn't do much in that sense except save the compiler some computation. I can certainly see why being pure wouldn't be enough to be CTFEable (since pure doesn't guarantee anything about whether it's parameters are know at compile time), but I would have thought that the lack of global state would be required - at least the lack of global state which isn't known at compile time - for it to be CTFEable, in which case the pureness would help. In any case, I'd obviously have to study it up a bit more to understand exactly what's required for CTFEability. I have some idea, but obviously not enough. - Jonathan M Davis
Jul 21 2010
parent reply "Jim Balter" <Jim Balter.name> writes:
"Jonathan M Davis" <jmdavisprog gmail.com> wrote in message 
news:mailman.435.1279700666.24349.digitalmars-d puremagic.com...
 On Wednesday 21 July 2010 00:09:05 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.

 Incidentally, having the function being marked as 'pure' doesn't really
 help at all for determining if it is CTFEable.

Hmm. As I understood it, it did.

You understood right.
 But I guess that if it did, the compiler could
 technically determine whether a function was actually pure anyway by 
 looking at
 its body. All the pure attribute would do is save it the trouble. So, the 
 pure
 attribute wouldn't do much in that sense except save the compiler some
 computation.

pure functions must halt, so the attribute let's you tell the compiler something that it could only figure out with difficulty, if at all.
 I can certainly see why being pure wouldn't be enough to be CTFEable 
 (since pure
 doesn't guarantee anything about whether it's parameters are know at 
 compile
 time), but I would have thought that the lack of global state would be 
 required
 - at least the lack of global state which isn't known at compile time - 
 for it
 to be CTFEable, in which case the pureness would help.

 In any case, I'd obviously have to study it up a bit more to understand 
 exactly
 what's required for CTFEability. I have some idea, but obviously not 
 enough.

 - Jonathan M Davis 

Jul 24 2010
parent reply Don <nospam nospam.com> writes:
Jim Balter wrote:
 
 "Jonathan M Davis" <jmdavisprog gmail.com> wrote in message 
 news:mailman.435.1279700666.24349.digitalmars-d puremagic.com...
 On Wednesday 21 July 2010 00:09:05 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.

 Incidentally, having the function being marked as 'pure' doesn't really
 help at all for determining if it is CTFEable.

Hmm. As I understood it, it did.

You understood right.
 But I guess that if it did, the compiler could
 technically determine whether a function was actually pure anyway by 
 looking at
 its body. All the pure attribute would do is save it the trouble. So, 
 the pure
 attribute wouldn't do much in that sense except save the compiler some
 computation.

pure functions must halt, so the attribute let's you tell the compiler something that it could only figure out with difficulty, if at all.

Being marked as 'pure' is no guarantee that the function will terminate.
Jul 24 2010
next sibling parent "Jim Balter" <Jim Balter.name> writes:
"Don" <nospam nospam.com> wrote in message 
news:i2ffm7$2qf3$1 digitalmars.com...
 Jim Balter wrote:
 "Jonathan M Davis" <jmdavisprog gmail.com> wrote in message 
 news:mailman.435.1279700666.24349.digitalmars-d puremagic.com...
 On Wednesday 21 July 2010 00:09:05 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.

 Incidentally, having the function being marked as 'pure' doesn't really
 help at all for determining if it is CTFEable.

Hmm. As I understood it, it did.

You understood right.
 But I guess that if it did, the compiler could
 technically determine whether a function was actually pure anyway by 
 looking at
 its body. All the pure attribute would do is save it the trouble. So, 
 the pure
 attribute wouldn't do much in that sense except save the compiler some
 computation.

pure functions must halt, so the attribute let's you tell the compiler something that it could only figure out with difficulty, if at all.

Being marked as 'pure' is no guarantee that the function will terminate.

A pure function has no side effects; one that doesn't terminate produces no return value either (throwing an exception is a form of termination). Thus a pure function that doesn't terminate is a bug. It would be perfectly reasonable for a compiler to assume that a pure function does terminate but to put a time limit on how long it spends evaluating it -- which it should do anyway, since even provably terminating functions can take longer than the time to the heat death of the universe to complete ... as I noted before, the halting problem isn't relevant in practice, because even if it were solvable, there are no time constraints on the solution.
Jul 24 2010
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Don wrote:
 Being marked as 'pure' is no guarantee that the function will terminate.

Right, and the compiler makes no attempt to check this, either.
Jul 24 2010
parent reply "Jim Balter" <Jim Balter.name> writes:
"Walter Bright" <newshound2 digitalmars.com> wrote in message 
news:i2flvi$4io$1 digitalmars.com...
 Don wrote:
 Being marked as 'pure' is no guarantee that the function will terminate.

Right, and the compiler makes no attempt to check this, either.

Of course the compiler makes no attempt to check -- that *would* be the halting problem, but there's no reason for a compiler to attempt such a check even if it could be done. Pure functions invoked on constant values are excellent candidates for CTFE because they have no side effects and are computable at compile time -- if they terminate. But pure functions that don't terminate are almost entirely pointless; the only non-pointless example I can think of is a kernel''s idle process on machines without an interruptable halt instruction. Even if there were useful non-terminating pure functions, intentionally putting the keyword "pure" on a function that doesn't terminate is doable but dumb. Of course, unintentionally doing so is a mistake. But dumbth and mistakes do happen, so the compiler can guard against taking forever -- or too long, period (Ackermann's Function is a famous example of a pure function that takes astronomically long to compute even on small input values -- good luck on writing a compiler that can detect such functions) -- by setting a timer. If the timer goes off before the computation completes, the compiler should abandon CTFE and print a warning message (unless suppressed by a pragma), since the function is most likely buggy (this satisfies Rainer Deyke's point that errors, including run-on functions, should be detected at compile time rather than waiting for runtime).
Jul 25 2010
parent reply Don <nospam nospam.com> writes:
Jim Balter wrote:
 "Walter Bright" <newshound2 digitalmars.com> wrote in message 
 news:i2flvi$4io$1 digitalmars.com...
 Don wrote:
 Being marked as 'pure' is no guarantee that the function will terminate.

Right, and the compiler makes no attempt to check this, either.

Of course the compiler makes no attempt to check -- that *would* be the halting problem, but there's no reason for a compiler to attempt such a check even if it could be done. Pure functions invoked on constant values are excellent candidates for CTFE because they have no side effects and are computable at compile time -- if they terminate. But pure functions that don't terminate are almost entirely pointless;

It's a bug. the only non-pointless example I can think of
 is a kernel''s idle process on machines without an interruptable halt 
 instruction. Even if there were useful non-terminating pure functions, 
 intentionally putting the keyword "pure" on a function that doesn't 
 terminate is doable but dumb. Of course, unintentionally doing so is a 
 mistake. But dumbth and mistakes do happen, so the compiler can guard 
 against taking forever -- or too long, period (Ackermann's Function is a 
 famous example of a pure function that takes astronomically long to 
 compute even on small input values -- good luck on writing a compiler 
 that can detect such functions) -- by setting a timer. If the timer goes 
 off before the computation completes, the compiler should abandon CTFE 
 and print a warning message (unless suppressed by a pragma), since the 
 function is most likely buggy (this satisfies Rainer Deyke's point that 
 errors, including run-on functions, should be detected at compile time 
 rather than waiting for runtime).

I don't think you can say that it's "most likely buggy". A function to calculate pi, for example, is a pure function that may take days to run.
Jul 25 2010
parent "Jim Balter" <Jim Balter.name> writes:
"Don" <nospam nospam.com> wrote in message 
news:i2ice7$2i7r$1 digitalmars.com...
 Jim Balter wrote:
 "Walter Bright" <newshound2 digitalmars.com> wrote in message 
 news:i2flvi$4io$1 digitalmars.com...
 Don wrote:
 Being marked as 'pure' is no guarantee that the function will 
 terminate.

Right, and the compiler makes no attempt to check this, either.

Of course the compiler makes no attempt to check -- that *would* be the halting problem, but there's no reason for a compiler to attempt such a check even if it could be done. Pure functions invoked on constant values are excellent candidates for CTFE because they have no side effects and are computable at compile time -- if they terminate. But pure functions that don't terminate are almost entirely pointless;

It's a bug.

Yes, that was my point (I gave below the sole exception I'm aware of). That's why the fact that the pure keyword doesn't *guarantee* that the function terminates is irrelevant. In fact, the language could specify that a function marked "pure" must terminate and say that it's an error (which may or may not be detected by the compiler) if it does not.
 the only non-pointless example I can think of
 is a kernel''s idle process on machines without an interruptable halt 
 instruction. Even if there were useful non-terminating pure functions, 
 intentionally putting the keyword "pure" on a function that doesn't 
 terminate is doable but dumb. Of course, unintentionally doing so is a 
 mistake. But dumbth and mistakes do happen, so the compiler can guard 
 against taking forever -- or too long, period (Ackermann's Function is a 
 famous example of a pure function that takes astronomically long to 
 compute even on small input values -- good luck on writing a compiler 
 that can detect such functions) -- by setting a timer. If the timer goes 
 off before the computation completes, the compiler should abandon CTFE 
 and print a warning message (unless suppressed by a pragma), since the 
 function is most likely buggy (this satisfies Rainer Deyke's point that 
 errors, including run-on functions, should be detected at compile time 
 rather than waiting for runtime).

I don't think you can say that it's "most likely buggy". A function to calculate pi, for example, is a pure function that may take days to run.

I just mentioned Ackermann's function above, so obviously I am aware that pure functions *can* take a very long time -- and that's a case where an exact result can be computed in a finite amount of time, unlike a complete decimal expansion of pi. However, in the real world, it's quite unlikely that a pi calculator would be a pure function operating entirely on constant values (required for CTFE) that takes days to run -- in reality, the number of iterations or significant digits is variable, intermediate results are printed or stored (possibly memoized), short-lived pure functions are invoked by non-pure frameworks, multiple threads coordinate the work, etc. I DO think I can say that long-running pure functions are *most likely* buggy, which is not contradicted by anecdotal counterexamples. But such a Bayesian debate is not worth our time having; as I mentioned elsewhere, there could be a noctfe pragma for functions the programmer does not want the compiler to attempt to compute, and one could also leave it up to the programmer to specify whether they want to be warned about attempts to compute pure functions that take longer than some threshold to compute -- which would satisfy Rainer Deyke's desire to learn about (possible) bugs at compile time rather than waiting for run time.
Jul 26 2010
prev sibling parent BCS <none anon.com> writes:
Hello Justin,

 "What is the difference between a (constant/immutable) value and the
 result of calling a side-effect free function that returns the same?"

A const value can't be changed from the current context but could be changed via another alias or inside a non side effect free function or via one of those in another thread. An immutable value can't change, end of story. The value a side-effect free function returns can change as soon as anything changes, a local var (via nested functions) global var or anything addressable through them. The function most closely resembles the const var. -- ... <IXOYE><
Jul 21 2010