www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - forcing compile time function execution

reply Artur Skawina <art.08.09 gmail.com> writes:
Is there a way to *force* CTFE? Without using an extra wrapper like this:

auto f_impl(alias a)() { / * ... ctfeable ... */ }
auto f(alias a)() { enum ctfed = f_impl!a; return ctfed; }

A " compile" (or " ctfe" etc) function attribute would eliminate the need for
the wrapper...

artur
Dec 27 2011
next sibling parent Piotr Szturmaj <bncrbme jadamspam.pl> writes:
Artur Skawina wrote:
 Is there a way to *force* CTFE? Without using an extra wrapper like this:

 auto f_impl(alias a)() { / * ... ctfeable ... */ }
 auto f(alias a)() { enum ctfed = f_impl!a; return ctfed; }

 A " compile" (or " ctfe" etc) function attribute would eliminate the need for
the wrapper...

 artur

static x = functionToBeCTFEd(); PS. You should ask questions in D.learn :-)
Dec 27 2011
prev sibling next sibling parent reply "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
On Tuesday, 27 December 2011 at 18:00:27 UTC, Artur Skawina wrote:
 Is there a way to *force* CTFE? Without using an extra wrapper 
 like this:

 auto f_impl(alias a)() { / * ... ctfeable ... */ }
 auto f(alias a)() { enum ctfed = f_impl!a; return ctfed; }

 A " compile" (or " ctfe" etc) function attribute would 
 eliminate the need for the wrapper...

import std.math; template Now(alias e) { enum Now = e; } void main() { auto f = Now!(sin(3)); } This should probably be in Phobos somewhere :) I suggested this before, but a bug (now fixed) prevented the idea from working.
Dec 27 2011
parent reply Artur Skawina <art.08.09 gmail.com> writes:
On 12/27/11 20:18, so wrote:
 On Tue, 27 Dec 2011 21:02:49 +0200, Artur Skawina <art.08.09 gmail.com> wrote:
 
 On 12/27/11 19:29, Vladimir Panteleev wrote:
 On Tuesday, 27 December 2011 at 18:00:27 UTC, Artur Skawina wrote:
 Is there a way to *force* CTFE? Without using an extra wrapper like this:

 auto f_impl(alias a)() { / * ... ctfeable ... */ }
 auto f(alias a)() { enum ctfed = f_impl!a; return ctfed; }

 A " compile" (or " ctfe" etc) function attribute would eliminate the need for
the wrapper...


Umm, the point was to *avoid* the extra useless wrapper. The only reason for its existence (and any kind of assignment to a static/enum) is to tell the compiler to try CTFE. Without the compile time assignment, it won't try hard enough - which means that, for f_impl()s that are not simple enough, code will be silently emitted and evaluated at runtime. Even when the functions are supposed to only do *compiletime* checking. (This happens eg. when /ctfeable/ contains loops) Hence the " compile" attribute suggestion, and list selection. (I actually tried something similar to Now(), but that only obfuscates the code even more, for no gain) artur

// lib.d T fun(T); unittest { enum a = fun; } Should do the trick. No change in client code. Yes ctfe_forced might be nice but not that we lack a solution. I also like this one because it doesn't pollute the function.

Hmm, maybe i'll try an example. Let's say you want to calculate the value for use as a mask to strip off some high bits of an int. You only have the number of allowed values, which /is supposed to/ be a power of two. This is in generic, library code, so you can not assume anything more. Obviously the answer is "uint POW2MASK(uint n) {return n-1;}" But if somebody calls this with a wrong argument it will silently fail horribly. Also it is simple enough to always be fully inlined. And can then be made to work on more than just an int. And will often be used with a predefined constant 'n'. The "safe" solution for the "unknown constant case" might look like this: auto POW2MASK(alias N)() { ulong n = N; enum MSB = 1UL<<(n.sizeof*8-1); n--; while ((n&MSB)==0) n = (n<<1) + 1; if (n==n.max) return cast(typeof(N))(N-1); assert(0, N.stringof ~ " is not a power of two."); // Abort compilation. } which can be used to statically check constants, like this: private enum HASHSIZE_check_ = POW2MASK!HASHSIZE; But now that we have this function, we can also use it in place of the open coded "n-1" or the original POW2MASK() in other (template) functions to gain some extra safety for free, right? "return (result&POW2MASK!N)" etc. Wrong. The compiler will actually emit the constant-checking code, instead of just using the right constant. It will do this silently, so, unless you inspect the generated code, you might never realize this. The solution? This: // Given a constant power-of-two value (with just one bit set) return // a 'mask' that can be used to mask of any higher bits so that // the result fits into [0..N) range. // Checks (at compile time) that the integer is a usable power of two. // NOTE: // "N==0" _is_ allowed, as it can be useful; // "N==1" is not very useful (mask is zero) but is allowed too. // 'N' should probably be unsigned, but this function does not enforce // this and will return the same type as that of 'N'. // // The implementation has to be split into two functions to force // the compiler to execute the checks at compile time and not emit // any of the ctfe-only code. private auto POW2MASK_CTFE(alias N)() { ulong n = N; enum MSB = 1UL<<(n.sizeof*8-1); n--; while ((n&MSB)==0) n = (n<<1) + 1; if (n==n.max) return cast(typeof(N))(N-1); assert(0, N.stringof ~ " is not a power of two."); // Abort compilation. } auto POW2MASK(alias N)() { enum R = POW2MASK_CTFE!N; return R; } Using this version we now get 100% bit-for-bit identical executable to the "N-1" open coded one. Zero runtime cost, but the build will immediately fail if someone tries to use a non-power-of-2 value. (This has already caught at least one off-by-one bug here, btw) This is just an example, that check could be done in n different ways, some of which would probably be completely optimized out (eg switch statement). CTFE can be very useful for things like checking constant requirements (especially when you have several /dependent/ constants) in templates, but if every time it's used to gain some extra safety you have to obfuscate the code, then it becomes much less attractive. The wrapper is there *only* to force CTFE, and *has* to be there for every single function that relies on ctfe happening, and probably would be a good idea for every function that is expected to evaluate at compile time. Omitting it could mean that even if things are ok now (ie no ctfe required), later when someone changes something (like adds another check after finding a bug) the result could be an unexpected app slowdown, with absolutely no warning. If you think that that someone should realize this -- well, even then, he/she has a choice of adding the check, then renaming the function and introducing a wrapper, or deciding this is not worth the effort... I know what i would do... ;) "auto ctfe POW2MASK(alias N)() {...}" would be much more straightforward than the idiom above, wouldn't it? [1] artur [1] and i don't even like " ctfe", but " compile_time" would be too verbose...
Dec 27 2011
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 12/27/2011 10:44 PM, Artur Skawina wrote:
 On 12/27/11 20:18, so wrote:
 On Tue, 27 Dec 2011 21:02:49 +0200, Artur Skawina<art.08.09 gmail.com>  wrote:

 On 12/27/11 19:29, Vladimir Panteleev wrote:
 On Tuesday, 27 December 2011 at 18:00:27 UTC, Artur Skawina wrote:
 Is there a way to *force* CTFE? Without using an extra wrapper like this:

 auto f_impl(alias a)() { / * ... ctfeable ... */ }
 auto f(alias a)() { enum ctfed = f_impl!a; return ctfed; }

 A " compile" (or " ctfe" etc) function attribute would eliminate the need for
the wrapper...


Umm, the point was to *avoid* the extra useless wrapper. The only reason for its existence (and any kind of assignment to a static/enum) is to tell the compiler to try CTFE. Without the compile time assignment, it won't try hard enough - which means that, for f_impl()s that are not simple enough, code will be silently emitted and evaluated at runtime. Even when the functions are supposed to only do *compiletime* checking. (This happens eg. when /ctfeable/ contains loops) Hence the " compile" attribute suggestion, and list selection. (I actually tried something similar to Now(), but that only obfuscates the code even more, for no gain) artur

// lib.d T fun(T); unittest { enum a = fun; } Should do the trick. No change in client code. Yes ctfe_forced might be nice but not that we lack a solution. I also like this one because it doesn't pollute the function.

Hmm, maybe i'll try an example. Let's say you want to calculate the value for use as a mask to strip off some high bits of an int. You only have the number of allowed values, which /is supposed to/ be a power of two. This is in generic, library code, so you can not assume anything more. Obviously the answer is "uint POW2MASK(uint n) {return n-1;}" But if somebody calls this with a wrong argument it will silently fail horribly. Also it is simple enough to always be fully inlined. And can then be made to work on more than just an int. And will often be used with a predefined constant 'n'. The "safe" solution for the "unknown constant case" might look like this: auto POW2MASK(alias N)() { ulong n = N; enum MSB = 1UL<<(n.sizeof*8-1); n--; while ((n&MSB)==0) n = (n<<1) + 1; if (n==n.max) return cast(typeof(N))(N-1); assert(0, N.stringof ~ " is not a power of two."); // Abort compilation. } which can be used to statically check constants, like this: private enum HASHSIZE_check_ = POW2MASK!HASHSIZE; But now that we have this function, we can also use it in place of the open coded "n-1" or the original POW2MASK() in other (template) functions to gain some extra safety for free, right? "return (result&POW2MASK!N)" etc. Wrong. The compiler will actually emit the constant-checking code, instead of just using the right constant. It will do this silently, so, unless you inspect the generated code, you might never realize this. The solution? This: // Given a constant power-of-two value (with just one bit set) return // a 'mask' that can be used to mask of any higher bits so that // the result fits into [0..N) range. // Checks (at compile time) that the integer is a usable power of two. // NOTE: // "N==0" _is_ allowed, as it can be useful; // "N==1" is not very useful (mask is zero) but is allowed too. // 'N' should probably be unsigned, but this function does not enforce // this and will return the same type as that of 'N'. // // The implementation has to be split into two functions to force // the compiler to execute the checks at compile time and not emit // any of the ctfe-only code. private auto POW2MASK_CTFE(alias N)() { ulong n = N; enum MSB = 1UL<<(n.sizeof*8-1); n--; while ((n&MSB)==0) n = (n<<1) + 1; if (n==n.max) return cast(typeof(N))(N-1); assert(0, N.stringof ~ " is not a power of two."); // Abort compilation. } auto POW2MASK(alias N)() { enum R = POW2MASK_CTFE!N; return R; } Using this version we now get 100% bit-for-bit identical executable to the "N-1" open coded one. Zero runtime cost, but the build will immediately fail if someone tries to use a non-power-of-2 value. (This has already caught at least one off-by-one bug here, btw) This is just an example, that check could be done in n different ways, some of which would probably be completely optimized out (eg switch statement). CTFE can be very useful for things like checking constant requirements (especially when you have several /dependent/ constants) in templates, but if every time it's used to gain some extra safety you have to obfuscate the code, then it becomes much less attractive. The wrapper is there *only* to force CTFE, and *has* to be there for every single function that relies on ctfe happening, and probably would be a good idea for every function that is expected to evaluate at compile time. Omitting it could mean that even if things are ok now (ie no ctfe required), later when someone changes something (like adds another check after finding a bug) the result could be an unexpected app slowdown, with absolutely no warning. If you think that that someone should realize this -- well, even then, he/she has a choice of adding the check, then renaming the function and introducing a wrapper, or deciding this is not worth the effort... I know what i would do... ;) "auto ctfe POW2MASK(alias N)() {...}" would be much more straightforward than the idiom above, wouldn't it? [1] artur [1] and i don't even like " ctfe", but " compile_time" would be too verbose...

template POW2MASK(alias N) if(!(N&N-1)) { enum POW2MASK = N-1; } uint POW2MASK(uint n) { if(__ctfe) assert(!(n&n-1)); return n-1; } uint POW2MASK(uint n) in{assert(!(n&n-1));} body { return n-1; } I don't think your example helps your point a lot. Compiling in error checking code is a matter of debug/release mode, not a matter of compile-time vs runtime. Assertions are always checked in CTFE and always stripped from runtime release code.
Dec 27 2011
prev sibling parent Artur Skawina <art.08.09 gmail.com> writes:
On 12/27/11 23:10, Timon Gehr wrote:

 I don't think your example helps your point a lot. Compiling in error checking
code is a matter of debug/release mode, not a matter of compile-time vs
runtime. Assertions are always checked in CTFE and always stripped from runtime
release code.

I remembered about the contracts after already writing my version... But then realized it's completely irrelevant where the ctfed "code" goes - you don't want unnecessary bloat both in release *and* debug builds. And compiletime error checks is not something you want to disable in release builds. If anything you want more of them. As long as they are completely "free" runtime-wise. Which ctfe makes possible. Runtime error checking is different, yes. But anything the compiler can check for itself should never be disabled, other than maybe for *devel* builds, if it affects compile times. Nothing worse than a bug *only* in a release build.
 template POW2MASK(alias N) if(!(N&N-1)) {
     enum POW2MASK = N-1;
 }

This i didn't think of. Calling the ctfe functions from template constraints. Solves the issue at least for simple templates. I'm not sure if separating the checks from useful code will work for every case, but for the rest the wrapper might be acceptable. Thank you, artur
Dec 27 2011
prev sibling next sibling parent Artur Skawina <art.08.09 gmail.com> writes:
On 12/27/11 19:29, Vladimir Panteleev wrote:
 On Tuesday, 27 December 2011 at 18:00:27 UTC, Artur Skawina wrote:
 Is there a way to *force* CTFE? Without using an extra wrapper like this:

 auto f_impl(alias a)() { / * ... ctfeable ... */ }
 auto f(alias a)() { enum ctfed = f_impl!a; return ctfed; }

 A " compile" (or " ctfe" etc) function attribute would eliminate the need for
the wrapper...


Umm, the point was to *avoid* the extra useless wrapper. The only reason for its existence (and any kind of assignment to a static/enum) is to tell the compiler to try CTFE. Without the compile time assignment, it won't try hard enough - which means that, for f_impl()s that are not simple enough, code will be silently emitted and evaluated at runtime. Even when the functions are supposed to only do *compiletime* checking. (This happens eg. when /ctfeable/ contains loops) Hence the " compile" attribute suggestion, and list selection. (I actually tried something similar to Now(), but that only obfuscates the code even more, for no gain) artur
Dec 27 2011
prev sibling next sibling parent so <so so.so> writes:
On Tue, 27 Dec 2011 21:02:49 +0200, Artur Skawina <art.08.09 gmail.com>  
wrote:

 On 12/27/11 19:29, Vladimir Panteleev wrote:
 On Tuesday, 27 December 2011 at 18:00:27 UTC, Artur Skawina wrote:
 Is there a way to *force* CTFE? Without using an extra wrapper like  
 this:

 auto f_impl(alias a)() { / * ... ctfeable ... */ }
 auto f(alias a)() { enum ctfed = f_impl!a; return ctfed; }

 A " compile" (or " ctfe" etc) function attribute would eliminate the  
 need for the wrapper...


Umm, the point was to *avoid* the extra useless wrapper. The only reason for its existence (and any kind of assignment to a static/enum) is to tell the compiler to try CTFE. Without the compile time assignment, it won't try hard enough - which means that, for f_impl()s that are not simple enough, code will be silently emitted and evaluated at runtime. Even when the functions are supposed to only do *compiletime* checking. (This happens eg. when /ctfeable/ contains loops) Hence the " compile" attribute suggestion, and list selection. (I actually tried something similar to Now(), but that only obfuscates the code even more, for no gain) artur

// lib.d T fun(T); unittest { enum a = fun; } Should do the trick. No change in client code. Yes ctfe_forced might be nice but not that we lack a solution. I also like this one because it doesn't pollute the function.
Dec 27 2011
prev sibling next sibling parent "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
On Tuesday, 27 December 2011 at 19:03:07 UTC, Artur Skawina wrote:
 Umm, the point was to *avoid* the extra useless wrapper.

Sorry, I thought you were writing one wrapper per CTFE-able function.
 Hence the " compile" attribute suggestion, and list selection.

Presently I don't see how your suggestion justifies an addition to the language itself, given that a wrapper is easy to implement. Furthermore, it would be yet another thing that requires people to inspect referenced code to keep track of what's going on (with compile in the language, you can't inspect a function's body and know if any function call is at runtime or compile-time).
 (I actually tried something similar to Now(), but that only 
 obfuscates the code even more, for no gain)

If you don't like Now, let's go back to the per-function wrapper idea. import std.math; string makeNow(string name) { return `template `~name~`(X...) { enum `~name~` = `~name~`Impl(X); }`; } mixin(makeNow("f")); double fImpl(double f) { return sin(f); } enum sin3 = f!3;
Dec 27 2011
prev sibling next sibling parent reply Joshua Reusch <yoschi arkandos.de> writes:
Am 27.12.2011 18:59, Artur Skawina wrote:
 Is there a way to *force* CTFE? Without using an extra wrapper like this:

 auto f_impl(alias a)() { / * ... ctfeable ... */ }
 auto f(alias a)() { enum ctfed = f_impl!a; return ctfed; }

 A " compile" (or " ctfe" etc) function attribute would eliminate the need for
the wrapper...

 artur

more general: is there any reason to not evaluate a pure function with const arguments always at compile-time ?
Dec 27 2011
next sibling parent reply Joshua Reusch <yoschi arkandos.de> writes:
Am 27.12.2011 20:35, Vladimir Panteleev wrote:
 Halting problem?

Makes an not-stopping pure function really sense? If you evaluate a function creating an infinite loop at compile-time, you get for sure in this state. Then, the compiler could stop the evaluation after some time and print an error/warning or creates runtime code.
Dec 27 2011
parent reply Joshua Reusch <yoschi arkandos.de> writes:
Am 27.12.2011 20:51, schrieb Vladimir Panteleev:
 On Tuesday, 27 December 2011 at 19:46:31 UTC, Joshua Reusch wrote:
 Am 27.12.2011 20:35, Vladimir Panteleev wrote:
 Halting problem?

Makes an not-stopping pure function really sense?

No, but you don't know if the user is expecting the function to take a long time to run, or it's stuck due to a bug.

If the function gets evaluated at compile-time, also the loop/recursion conditions are known.
 If you evaluate a function creating an infinite loop at compile-time,
 you get for sure in this state. Then, the compiler could stop the
 evaluation after some time and print an error/warning or creates
 runtime code.

The problem is with "after some time". It's not possible to know when the compiler should stop. For all it knows, the user is doing some compile-time raytracing.

ok, "after some time" is really not the right approach. But as I wrote above, the compiler knows the conditions for loops. The function also is pure, so it should have the same behaviour with the same arguments. With a function calling stack it should be possible to detect infinite recursive calls.
Dec 27 2011
parent Joshua Reusch <yoschi arkandos.de> writes:
Am 27.12.2011 21:27, schrieb Vladimir Panteleev:
 On Tuesday, 27 December 2011 at 20:11:32 UTC, Joshua Reusch wrote:
 Am 27.12.2011 20:51, schrieb Vladimir Panteleev:
 On Tuesday, 27 December 2011 at 19:46:31 UTC, Joshua Reusch wrote:
 Am 27.12.2011 20:35, Vladimir Panteleev wrote:
 Halting problem?

Makes an not-stopping pure function really sense?

No, but you don't know if the user is expecting the function to take a long time to run, or it's stuck due to a bug.

If the function gets evaluated at compile-time, also the loop/recursion conditions are known.

We're back at the halting problem. There are heuristics, but you can't know for sure.

Sorry, of course... Some other attribute ( ctfe) would really be better for this...
 For example:

 for (auto i=arr.length-1; i>=0; i--)

 On 64-bits, i will be 64 bits too (because arr.length is size_t). Since
 it's unsigned, the loop will wrap, and it'll take a very long time until
 it'll reach a state it's been in before.

Joshua
Dec 27 2011
prev sibling parent Joshua Reusch <yoschi arkandos.de> writes:
Am 27.12.2011 21:03, schrieb Artur Skawina:
 On 12/27/11 20:31, Joshua Reusch wrote:
 Am 27.12.2011 18:59, Artur Skawina wrote:
 Is there a way to *force* CTFE? Without using an extra wrapper like this:

 auto f_impl(alias a)() { / * ... ctfeable ... */ }
 auto f(alias a)() { enum ctfed = f_impl!a; return ctfed; }

 A " compile" (or " ctfe" etc) function attribute would eliminate the need for
the wrapper...

 artur

more general: is there any reason to not evaluate a pure function with const arguments always at compile-time ?

"Pure" does not necessarily == cheap. There will always be a limit to the amount of transformations a compiler can do; otherwise it could in many cases just run the program instead of compiling it. :)

It did not seen an "real" program without runtime arguments yet, but the time it takes to compile could be a problem. ctfe + JIT would be nice ;)
 So there has to be some kind of heuristic, to make sure builds don't take too
long. And when the compiler gives up, it has to generate that "pure" code after
all. This is not what you want if you know that something can be reasonably
cheaply computed at compile time, but is not really needed in the resulting
program and would slow it down significantly.
 Hence " ctfe", which would have to be the equivalent of the enum-assigning
wrapper -- either the function evaluates to a constant, or the build fails.

A ctfe'd function should also be callable at runtime, but defaults to ctfe then. This could be the solution of the/my pure-always vs. only-if-needed - ctfe problem. Maybe some decorator/wrapper Syntax as in Python would also be nice ... :)
 artur

Joshua
Dec 27 2011
prev sibling next sibling parent "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
On Tuesday, 27 December 2011 at 19:31:58 UTC, Joshua Reusch wrote:
 more general: is there any reason to not evaluate a pure 
 function with const arguments always at compile-time ?

Halting problem?
Dec 27 2011
prev sibling next sibling parent "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
On Tuesday, 27 December 2011 at 19:46:31 UTC, Joshua Reusch wrote:
 Am 27.12.2011 20:35, Vladimir Panteleev wrote:
 Halting problem?

Makes an not-stopping pure function really sense?

No, but you don't know if the user is expecting the function to take a long time to run, or it's stuck due to a bug.
 If you evaluate a function creating an infinite loop at 
 compile-time, you get for sure in this state. Then, the 
 compiler could stop the evaluation after some time and print an 
 error/warning or creates runtime code.

The problem is with "after some time". It's not possible to know when the compiler should stop. For all it knows, the user is doing some compile-time raytracing.
Dec 27 2011
prev sibling next sibling parent Artur Skawina <art.08.09 gmail.com> writes:
On 12/27/11 20:31, Joshua Reusch wrote:
 Am 27.12.2011 18:59, Artur Skawina wrote:
 Is there a way to *force* CTFE? Without using an extra wrapper like this:

 auto f_impl(alias a)() { / * ... ctfeable ... */ }
 auto f(alias a)() { enum ctfed = f_impl!a; return ctfed; }

 A " compile" (or " ctfe" etc) function attribute would eliminate the need for
the wrapper...

 artur

more general: is there any reason to not evaluate a pure function with const arguments always at compile-time ?

"Pure" does not necessarily == cheap. There will always be a limit to the amount of transformations a compiler can do; otherwise it could in many cases just run the program instead of compiling it. :) So there has to be some kind of heuristic, to make sure builds don't take too long. And when the compiler gives up, it has to generate that "pure" code after all. This is not what you want if you know that something can be reasonably cheaply computed at compile time, but is not really needed in the resulting program and would slow it down significantly. Hence " ctfe", which would have to be the equivalent of the enum-assigning wrapper -- either the function evaluates to a constant, or the build fails. artur
Dec 27 2011
prev sibling parent "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
On Tuesday, 27 December 2011 at 20:11:32 UTC, Joshua Reusch wrote:
 Am 27.12.2011 20:51, schrieb Vladimir Panteleev:
 On Tuesday, 27 December 2011 at 19:46:31 UTC, Joshua Reusch 
 wrote:
 Am 27.12.2011 20:35, Vladimir Panteleev wrote:
 Halting problem?

Makes an not-stopping pure function really sense?

No, but you don't know if the user is expecting the function to take a long time to run, or it's stuck due to a bug.

If the function gets evaluated at compile-time, also the loop/recursion conditions are known.

We're back at the halting problem. There are heuristics, but you can't know for sure. For example: for (auto i=arr.length-1; i>=0; i--) On 64-bits, i will be 64 bits too (because arr.length is size_t). Since it's unsigned, the loop will wrap, and it'll take a very long time until it'll reach a state it's been in before.
Dec 27 2011