digitalmars.D - forcing compile time function execution
- Artur Skawina (5/5) Dec 27 2011 Is there a way to *force* CTFE? Without using an extra wrapper like this...
- Piotr Szturmaj (3/8) Dec 27 2011 static x = functionToBeCTFEd();
- Vladimir Panteleev (12/18) Dec 27 2011 import std.math;
- Artur Skawina (5/12) Dec 27 2011 Umm, the point was to *avoid* the extra useless wrapper. The only reason...
- so (11/32) Dec 27 2011 // lib.d
- Artur Skawina (55/86) Dec 27 2011 Hmm, maybe i'll try an example.
- Timon Gehr (15/101) Dec 27 2011 template POW2MASK(alias N) if(!(N&N-1)) {
- Artur Skawina (7/11) Dec 27 2011 I remembered about the contracts after already writing my version... But...
- Vladimir Panteleev (18/22) Dec 27 2011 Sorry, I thought you were writing one wrapper per CTFE-able
- Joshua Reusch (3/8) Dec 27 2011 more general: is there any reason to not evaluate a pure function with
- Vladimir Panteleev (2/4) Dec 27 2011 Halting problem?
- Joshua Reusch (6/7) Dec 27 2011 Makes an not-stopping pure function really sense?
- Vladimir Panteleev (6/13) Dec 27 2011 No, but you don't know if the user is expecting the function to
- Joshua Reusch (8/22) Dec 27 2011 If the function gets evaluated at compile-time, also the loop/recursion
- Vladimir Panteleev (8/22) Dec 27 2011 We're back at the halting problem. There are heuristics, but you
- Joshua Reusch (4/25) Dec 27 2011 Sorry, of course... Some other attribute (@ctfe) would really be better
- Artur Skawina (5/16) Dec 27 2011 "Pure" does not necessarily == cheap. There will always be a limit to th...
- Joshua Reusch (8/24) Dec 27 2011 It did not seen an "real" program without runtime arguments yet, but the...
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
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... arturstatic x = functionToBeCTFEd(); PS. You should ask questions in D.learn :-)
Dec 27 2011
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
On 12/27/11 19:29, Vladimir Panteleev wrote:On Tuesday, 27 December 2011 at 18:00:27 UTC, Artur Skawina wrote: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) arturIs 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...
Dec 27 2011
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:// 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.On Tuesday, 27 December 2011 at 18:00:27 UTC, Artur Skawina wrote: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) arturIs 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...
Dec 27 2011
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: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...On 12/27/11 19:29, Vladimir Panteleev wrote:// 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.On Tuesday, 27 December 2011 at 18:00:27 UTC, Artur Skawina wrote: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) arturIs 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...
Dec 27 2011
On 12/27/2011 10:44 PM, Artur Skawina wrote:On 12/27/11 20:18, so wrote: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.On Tue, 27 Dec 2011 21:02:49 +0200, Artur Skawina<art.08.09 gmail.com> wrote: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...On 12/27/11 19:29, Vladimir Panteleev wrote:// 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.On Tuesday, 27 December 2011 at 18:00:27 UTC, Artur Skawina wrote: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) arturIs 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...
Dec 27 2011
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
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
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... arturmore general: is there any reason to not evaluate a pure function with const arguments always at compile-time ?
Dec 27 2011
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
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
On Tuesday, 27 December 2011 at 19:46:31 UTC, Joshua Reusch wrote:Am 27.12.2011 20:35, Vladimir Panteleev wrote: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.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.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
Am 27.12.2011 20:51, schrieb Vladimir Panteleev:On Tuesday, 27 December 2011 at 19:46:31 UTC, Joshua Reusch wrote:If the function gets evaluated at compile-time, also the loop/recursion conditions are known.Am 27.12.2011 20:35, Vladimir Panteleev wrote: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.Halting problem?Makes an not-stopping pure function really sense?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.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
On Tuesday, 27 December 2011 at 20:11:32 UTC, Joshua Reusch wrote:Am 27.12.2011 20:51, schrieb Vladimir Panteleev: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.On Tuesday, 27 December 2011 at 19:46:31 UTC, Joshua Reusch wrote:If the function gets evaluated at compile-time, also the loop/recursion conditions are known.Am 27.12.2011 20:35, Vladimir Panteleev wrote: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.Halting problem?Makes an not-stopping pure function really sense?
Dec 27 2011
Am 27.12.2011 21:27, schrieb Vladimir Panteleev:On Tuesday, 27 December 2011 at 20:11:32 UTC, Joshua Reusch wrote:Sorry, of course... Some other attribute ( ctfe) would really be better for this...Am 27.12.2011 20:51, schrieb Vladimir Panteleev:We're back at the halting problem. There are heuristics, but you can't know for sure.On Tuesday, 27 December 2011 at 19:46:31 UTC, Joshua Reusch wrote:If the function gets evaluated at compile-time, also the loop/recursion conditions are known.Am 27.12.2011 20:35, Vladimir Panteleev wrote: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.Halting problem?Makes an not-stopping pure function really sense?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
On 12/27/11 20:31, Joshua Reusch wrote:Am 27.12.2011 18:59, Artur Skawina wrote:"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. arturIs 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... arturmore general: is there any reason to not evaluate a pure function with const arguments always at compile-time ?
Dec 27 2011
Am 27.12.2011 21:03, schrieb Artur Skawina:On 12/27/11 20:31, Joshua Reusch wrote: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 ;)Am 27.12.2011 18:59, Artur Skawina wrote:"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. :)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... arturmore general: is there any reason to not evaluate a pure function with const arguments always at compile-time ?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 ... :)arturJoshua
Dec 27 2011