www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - CTFE is getting too powerful :o)

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Found this: 
http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr

Soon we'll need to clearly define the limits of CTFE, and what happens 
when it fails.


Andrei
Mar 27 2013
next sibling parent "Iain Buclaw" <ibuclaw ubuntu.com> writes:
On Wednesday, 27 March 2013 at 14:48:32 UTC, Andrei Alexandrescu 
wrote:
 Found this: 
 http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr

 Soon we'll need to clearly define the limits of CTFE, and what 
 happens when it fails.


 Andrei

Soon, we'll hear stories of how CTFE tried to take over the world... http://bit.ly/13x3E96
Mar 27 2013
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Andrei Alexandrescu:

 Soon we'll need to clearly define the limits of CTFE, and what 
 happens when it fails.

It seems a bug, this is a reduction: struct MapResult(alias fun) { int[] _input; property bool empty() { return _input.length == 0; } void popFront() { _input = _input[1 .. $]; } property auto ref front() { return fun(1); } } auto map(alias fun)(int[] r) { return MapResult!(fun)(r); } auto foo(int[] r) { return map!(x => r)([1]); } enum r1 = [1]; version (stat) { auto result = foo(r1); } void main() { version (stat) { } else { auto result = foo(r1); } foreach (t; result) {} } Bye, bearophile
Mar 27 2013
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 03/27/2013 04:44 PM, bearophile wrote:
 Andrei Alexandrescu:

 Soon we'll need to clearly define the limits of CTFE, and what happens
 when it fails.

It seems a bug, this is a reduction: ...

You might want to add it to the report, which is at: http://d.puremagic.com/issues/show_bug.cgi?id=9822
Mar 27 2013
prev sibling next sibling parent "Dicebot" <m.strashun gmail.com> writes:
On Wednesday, 27 March 2013 at 14:48:32 UTC, Andrei Alexandrescu 
wrote:
 Found this: 
 http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr

 Soon we'll need to clearly define the limits of CTFE, and what 
 happens when it fails.


 Andrei

Is it really CTFE fault? So far seems more like issue of run-time data vs compile-time data, interconnection of which is (probably) not defined. CTFE has actually done an awesome job and managed to compute cartesianProduct :) Erm, pretended to do so at least.
Mar 27 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Timon Gehr:

 You might want to add it to the report, which is at:
 http://d.puremagic.com/issues/show_bug.cgi?id=9822

I will, later. Bye, bearophile
Mar 27 2013
prev sibling next sibling parent "Jesse Phillips" <Jessekphillips+D gmail.com> writes:
On Wednesday, 27 March 2013 at 14:48:32 UTC, Andrei Alexandrescu 
wrote:
 Found this: 
 http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr

 Soon we'll need to clearly define the limits of CTFE, and what 
 happens when it fails.


 Andrei

But, but, I can generate D code, mix it in, and run unittests on the generated code!!!! All at compile time! While everyone is concerning themselves with Go's lack of generics, D is running circles around everyone.
Mar 27 2013
prev sibling next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 03/27/2013 03:48 PM, Andrei Alexandrescu wrote:
 Found this:
 http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr


 Soon we'll need to clearly define the limits of CTFE, and what happens
 when it fails.
 ...

Attempt 1: CTFE may compute the result of an arbitrary D expression according to the usual language semantics, provided that: - D source code is available at all definitions of called functions. - No mutable variables/fields are loaded or stored that were not allocated during the same CTFE execution. - Only type casts are evaluated whose kind may not harm type safety. - No function enclosing the evaluated expression is called during evaluation. We might also want: - No stack references are accessed after the declaring function has returned. - There is no reliance on the indeterminism inherent in array appends. But they are quite hard to check efficiently. If CTFE does not terminate, compilation is not allowed to succeed. If CTFE fails because the above criteria are not met, the evaluated expression is in error. There are further funny complications, but those should be addressed in a general way as they are not exclusive to CTFE. Eg: class A{ auto foo(){ return "A"; } } class B{ auto foo(){ return "B"; } } template ID(alias a){ alias a ID; } template P(C){ alias ID!(mixin((new C()).foo())) P; } class C : P!C{ } // error class D : P!D{ override foo(){ return "A"; } } // ok static assert(is(D:A));
Mar 27 2013
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 03/27/2013 06:20 PM, H. S. Teoh wrote:
 On Wed, Mar 27, 2013 at 05:55:54PM +0100, Timon Gehr wrote:
 [...]
 If CTFE does not terminate, compilation is not allowed to succeed.

Heh, I think this one is unimplementable, as it amounts to solving the halting problem. :) ...

Actually it does not. Non-success denotes either failure or non-termination.
Mar 27 2013
next sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
On 03/27/2013 06:50 PM, H. S. Teoh wrote:
 On Wed, Mar 27, 2013 at 06:29:59PM +0100, Timon Gehr wrote:
 On 03/27/2013 06:20 PM, H. S. Teoh wrote:
 On Wed, Mar 27, 2013 at 05:55:54PM +0100, Timon Gehr wrote:
 [...]
 If CTFE does not terminate, compilation is not allowed to succeed.

Heh, I think this one is unimplementable, as it amounts to solving the halting problem. :) ...

Actually it does not. Non-success denotes either failure or non-termination.

But how do you check for non-termination? T

Why would you need to?
Mar 27 2013
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 03/27/2013 10:37 PM, H. S. Teoh wrote:
 On Wed, Mar 27, 2013 at 10:19:12PM +0100, Timon Gehr wrote:
 On 03/27/2013 06:50 PM, H. S. Teoh wrote:
 On Wed, Mar 27, 2013 at 06:29:59PM +0100, Timon Gehr wrote:
 On 03/27/2013 06:20 PM, H. S. Teoh wrote:
 On Wed, Mar 27, 2013 at 05:55:54PM +0100, Timon Gehr wrote:
 [...]
 If CTFE does not terminate, compilation is not allowed to succeed.

Heh, I think this one is unimplementable, as it amounts to solving the halting problem. :) ...

Actually it does not. Non-success denotes either failure or non-termination.

But how do you check for non-termination?


 Why would you need to?

How else would you force compilation to fail in that case? T

You don't have to. "If CTFE does not terminate, compilation is not allowed to succeed." && "Non-success denotes either failure or non-termination." ==> "If CTFE does not terminate, compilation should either fail or not terminate."
Mar 27 2013
prev sibling parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
27-Mar-2013 21:50, H. S. Teoh пишет:
 On Wed, Mar 27, 2013 at 06:29:59PM +0100, Timon Gehr wrote:
 On 03/27/2013 06:20 PM, H. S. Teoh wrote:
 On Wed, Mar 27, 2013 at 05:55:54PM +0100, Timon Gehr wrote:
 [...]
 If CTFE does not terminate, compilation is not allowed to succeed.

Heh, I think this one is unimplementable, as it amounts to solving the halting problem. :) ...

Actually it does not. Non-success denotes either failure or non-termination.

But how do you check for non-termination?

Watchdog if you need it. Going by no reasonable program written in D can compile longer <insert your time to get some coffee>.
 T

-- Dmitry Olshansky
Mar 27 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 27, 2013 at 06:29:59PM +0100, Timon Gehr wrote:
 On 03/27/2013 06:20 PM, H. S. Teoh wrote:
On Wed, Mar 27, 2013 at 05:55:54PM +0100, Timon Gehr wrote:
[...]
If CTFE does not terminate, compilation is not allowed to succeed.

Heh, I think this one is unimplementable, as it amounts to solving the halting problem. :) ...

Actually it does not. Non-success denotes either failure or non-termination.

But how do you check for non-termination? T -- If creativity is stifled by rigid discipline, then it is not true creativity.
Mar 27 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 27, 2013 at 10:19:12PM +0100, Timon Gehr wrote:
 On 03/27/2013 06:50 PM, H. S. Teoh wrote:
On Wed, Mar 27, 2013 at 06:29:59PM +0100, Timon Gehr wrote:
On 03/27/2013 06:20 PM, H. S. Teoh wrote:
On Wed, Mar 27, 2013 at 05:55:54PM +0100, Timon Gehr wrote:
[...]
If CTFE does not terminate, compilation is not allowed to succeed.

Heh, I think this one is unimplementable, as it amounts to solving the halting problem. :) ...

Actually it does not. Non-success denotes either failure or non-termination.

But how do you check for non-termination?


 
 Why would you need to?

How else would you force compilation to fail in that case? T -- In order to understand recursion you must first understand recursion.
Mar 27 2013
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 03/27/2013 05:55 PM, Timon Gehr wrote:
 ...

   - No mutable variables/fields are loaded or stored that were not
     allocated during the same CTFE execution.
...

On second thought, probably loading of the value of initialized mutable static variables should be allowed, so that it is easy to assemble mutable object graphs at compile time. (it would still not be allowed to modify the fields of referenced objects.)
Mar 27 2013
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
On 03/27/2013 05:55 PM, Timon Gehr wrote:
 ...

   - Only type casts are evaluated whose kind may not harm type safety.
 ...

This could easily be lifted as well by doing a more "runtime" checks (in such a way that there is no additional overhead for the interpreter except when there is an out-of-bounds access, which would terminate CTFE anyway and in the final sanity check when the resulting value is returned.)
Mar 27 2013
prev sibling next sibling parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 27, 2013 at 10:48:31AM -0400, Andrei Alexandrescu wrote:
 Found this: http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr

IMO, this is a compiler bug. If the compiler can't correctly generate code for something, it shouldn't just keep quiet and generate wrong code.
 Soon we'll need to clearly define the limits of CTFE, and what happens
 when it fails.

IMO, CTFE should be allowed to do the maximum of what's possible during compile-time, regardless of current implementation limitations. Placing arbitrary limits on it will hurt in the long run, I think. Of course, defining absolute limits for it makes sense if said limits are theoretical limits of compile-time evaluation. :) T -- No! I'm not in denial!
Mar 27 2013
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/27/13 1:17 PM, H. S. Teoh wrote:
 On Wed, Mar 27, 2013 at 10:48:31AM -0400, Andrei Alexandrescu wrote:
 Found this: http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr

IMO, this is a compiler bug. If the compiler can't correctly generate code for something, it shouldn't just keep quiet and generate wrong code.

Then bugzillize! Andrei
Mar 27 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Wed, Mar 27, 2013 at 05:55:54PM +0100, Timon Gehr wrote:
[...]
 If CTFE does not terminate, compilation is not allowed to succeed.

Heh, I think this one is unimplementable, as it amounts to solving the halting problem. :)
 If CTFE fails because the above criteria are not met, the evaluated
 expression is in error.

Makes sense. T -- Obviously, some things aren't very obvious.
Mar 27 2013
prev sibling next sibling parent "deadalnix" <deadalnix gmail.com> writes:
On Wednesday, 27 March 2013 at 17:19:40 UTC, H. S. Teoh wrote:
 On Wed, Mar 27, 2013 at 10:48:31AM -0400, Andrei Alexandrescu 
 wrote:
 Found this: 
 http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr

IMO, this is a compiler bug. If the compiler can't correctly generate code for something, it shouldn't just keep quiet and generate wrong code.

That work fairly well for closures and context pointer. It is a proven strategy.
Mar 27 2013
prev sibling next sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Wednesday, 27 March 2013 at 14:48:32 UTC, Andrei Alexandrescu 
wrote:
 Found this: 
 http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr

 Soon we'll need to clearly define the limits of CTFE, and what 
 happens when it fails.

Aren't the limits just Safe D? (i.e. if it's in Safe D, it compiles, anything more is implementation defined?)
Mar 27 2013
parent reply Dmitry Olshansky <dmitry.olsh gmail.com> writes:
27-Mar-2013 23:14, Peter Alexander пишет:
 On Wednesday, 27 March 2013 at 14:48:32 UTC, Andrei Alexandrescu wrote:
 Found this:
 http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr


 Soon we'll need to clearly define the limits of CTFE, and what happens
 when it fails.

Aren't the limits just Safe D? (i.e. if it's in Safe D, it compiles, anything more is implementation defined?)

No - one can call writeln (if one day it's marked trusted). CTFE can never do such a thing. Plus no access to globals etc. in general sense no side effects. -- Dmitry Olshansky
Mar 27 2013
parent Dmitry Olshansky <dmitry.olsh gmail.com> writes:
27-Mar-2013 23:50, Nick Sabalausky пишет:
 On Wed, 27 Mar 2013 23:43:07 +0400
 Dmitry Olshansky <dmitry.olsh gmail.com> wrote:

 27-Mar-2013 23:14, Peter Alexander пишет:
 On Wednesday, 27 March 2013 at 14:48:32 UTC, Andrei Alexandrescu
 wrote:
 Found this:
 http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr


 Soon we'll need to clearly define the limits of CTFE, and what
 happens when it fails.

Aren't the limits just Safe D? (i.e. if it's in Safe D, it compiles, anything more is implementation defined?)

No - one can call writeln (if one day it's marked trusted). CTFE can never do such a thing.

There's (thankfully) already a ctfeWriteln (or something like that). So about all that needs to happen for writeln to work in CTFE is for it to start with: if(__ctfe) { ctfeWriteln(...); return; } Or something like that.

That's far cry from full I/O ;) In fact I believe we might need more general set of "built-in" functions for CTFE. The goal is to define as small set as possible covering as many good use-cases as possible. And you still can't read/write to TLS global from CTFE for obvious reasons.
 Plus no access to globals etc. in general
 sense no side effects.


-- Dmitry Olshansky
Mar 27 2013
prev sibling next sibling parent Nick Sabalausky <SeeWebsiteToContactMe semitwist.com> writes:
On Wed, 27 Mar 2013 23:43:07 +0400
Dmitry Olshansky <dmitry.olsh gmail.com> wrote:

 27-Mar-2013 23:14, Peter Alexander =D0=BF=D0=B8=D1=88=D0=B5=D1=82:
 On Wednesday, 27 March 2013 at 14:48:32 UTC, Andrei Alexandrescu
 wrote:
 Found this:
 http://stackoverflow.com/questions/15652718/object-error-access-violat=



 Soon we'll need to clearly define the limits of CTFE, and what
 happens when it fails.

Aren't the limits just Safe D? (i.e. if it's in Safe D, it compiles, anything more is implementation defined?)

No - one can call writeln (if one day it's marked trusted). CTFE can=20 never do such a thing.

There's (thankfully) already a ctfeWriteln (or something like that). So about all that needs to happen for writeln to work in CTFE is for it to start with: if(__ctfe) { ctfeWriteln(...); return; } Or something like that.
 Plus no access to globals etc. in general
 sense no side effects.
=20

Mar 27 2013
prev sibling parent "Don" <turnyourkidsintocash nospam.com> writes:
On Wednesday, 27 March 2013 at 19:43:13 UTC, Dmitry Olshansky 
wrote:
 27-Mar-2013 23:14, Peter Alexander пишет:
 On Wednesday, 27 March 2013 at 14:48:32 UTC, Andrei 
 Alexandrescu wrote:
 Found this:
 http://stackoverflow.com/questions/15652718/object-error-access-violation-when-printing-result-of-std-algorithm-cartesianpr


 Soon we'll need to clearly define the limits of CTFE, and 
 what happens
 when it fails.

Aren't the limits just Safe D? (i.e. if it's in Safe D, it compiles, anything more is implementation defined?)

No - one can call writeln (if one day it's marked trusted). CTFE can never do such a thing. Plus no access to globals etc. in general sense no side effects.

Actually the relationship between CTFE and SafeD is more interesting than that. CTFE can also do some things which safe D cannot, eg pointer arithmetic. Neither is a pure subset of the other.
Mar 28 2013