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

Andrei Alexandrescu (5/5) Mar 27 2013 Found this:

Iain Buclaw (5/10) Mar 27 2013 Soon, we'll hear stories of how CTFE tried to take over the
bearophile (33/35) Mar 27 2013 It seems a bug, this is a reduction:

Timon Gehr (3/8) Mar 27 2013 You might want to add it to the report, which is at:

bearophile (4/6) Mar 27 2013 I will, later.

Dicebot (6/11) Mar 27 2013 Is it really CTFE fault? So far seems more like issue of run-time
Jesse Phillips (6/11) Mar 27 2013 But, but, I can generate D code, mix it in, and run unittests on
Timon Gehr (28/33) Mar 27 2013 Attempt 1:

H. S. Teoh (8/11) Mar 27 2013 Heh, I think this one is unimplementable, as it amounts to solving the

Timon Gehr (2/8) Mar 27 2013 Actually it does not. Non-success denotes either failure or non-terminat...

H. S. Teoh (5/16) Mar 27 2013 But how do you check for non-termination?

Timon Gehr (2/16) Mar 27 2013 Why would you need to?

H. S. Teoh (6/23) Mar 27 2013 How else would you force compilation to fail in that case?

Timon Gehr (8/29) Mar 27 2013 You don't have to.

Dmitry Olshansky (6/20) Mar 27 2013 Watchdog if you need it.

Timon Gehr (5/9) Mar 27 2013 On second thought, probably loading of the value of initialized mutable
Timon Gehr (5/8) Mar 27 2013 This could easily be lifted as well by doing a more "runtime" checks (in...

H. S. Teoh (13/16) Mar 27 2013 IMO, this is a compiler bug. If the compiler can't correctly generate

deadalnix (3/12) Mar 27 2013 That work fairly well for closures and context pointer. It is a
Andrei Alexandrescu (3/8) Mar 27 2013 Then bugzillize!

Peter Alexander (4/8) Mar 27 2013 Aren't the limits just Safe D? (i.e. if it's in Safe D, it

Dmitry Olshansky (6/15) Mar 27 2013 No - one can call writeln (if one day it's marked @trusted). CTFE can

Nick Sabalausky (11/29) Mar 27 2013 ion-when-printing-result-of-std-algorithm-cartesianpr

Dmitry Olshansky (8/36) Mar 27 2013 That's far cry from full I/O ;)

Don (6/23) Mar 28 2013 Actually the relationship between CTFE and SafeD is more

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

"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

"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

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

"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

"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

"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

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

"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

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

"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

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

"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

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

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

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

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

"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

"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

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

"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

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

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=



ion-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?)

=20
 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

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

"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

D Programming

C/C++ Programming

Other

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