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

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

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

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

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.

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

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.

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

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!

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.