The discussion on Reddit brought to my attention that pure functions can return and assign to an immutable.

http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutability_in_d/c2lsgek

I am trying to modify the example request to make use of this, but have failed.

http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutability_in_d/c2lrfpm

test.d(4): Error: cannot implicitly convert expression (makeFromArray([1,2,3]))
of type test.List!(int).List to immutable(List)

Is this a bug? I can't identify where this issue would lie (works with inheritance and templating).

void main() {
   immutable a = makeFromArray([1,2,3]);
}
private abstract class List(T) {
   abstract bool isEmpty () const;
   abstract T head () const;
   abstract const(List!T) tail () const;


}
private final class Cons(T): List!T {
   immutable T head_;
   Cons!T tail_; // not immutable here for a reason

   this(T h, Cons!T t) { head_ = h; tail_ = t; }

   override bool isEmpty() const { return false; }
   override T head () const { return head_; }
   override const(Cons!T) tail () const { return tail_; }
}

List!T makeFromArray(T)(T[] array) pure {
   if (array.length == 0) { return null; }

   auto result = new Cons!T(array[0], null);
   auto end = result;

   for (int i = 1; i < array.length; ++i) {
      end.tail_ = new Cons!T(array[i], null);
      end = end.tail_;
   }

   return result;
}

On 22.09.2011 22:53, Jesse Phillips wrote:
> The discussion on Reddit brought to my attention that pure functions can return and assign to an immutable.
>
> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutability_in_d/c2lsgek
>
> I am trying to modify the example request to make use of this, but have failed.
>
> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutability_in_d/c2lrfpm
>
> test.d(4): Error: cannot implicitly convert expression (makeFromArray([1,2,3]))
> of type test.List!(int).List to immutable(List)
>
> Is this a bug? I can't identify where this issue would lie (works with inheritance and templating).
>

Maybe:
-------------------------<<<<<<<<<<
 List!T makeFromArray(T)(immutable T[] array) pure {
>     if (array.length == 0) { return null; }
>
>     auto result = new Cons!T(array[0], null);
>     auto end = result;
>
>     for (int i = 1; i<  array.length; ++i) {
>        end.tail_ = new Cons!T(array[i], null);
>        end = end.tail_;
>     }
>
>     return result;
> }
>

If I'm not mistaken only strongly pure functions are working.

-- 
Dmitry Olshansky

On Thursday, September 22, 2011 23:36:40 Dmitry Olshansky wrote:
> On 22.09.2011 22:53, Jesse Phillips wrote:
> > The discussion on Reddit brought to my attention that pure functions can return and assign to an immutable.
> > 
> > http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutabil ity_in_d/c2lsgek
> > 
> > I am trying to modify the example request to make use of this, but have failed.
> > 
> > http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutabil ity_in_d/c2lrfpm
> > 
> > test.d(4): Error: cannot implicitly convert expression
> > (makeFromArray([1,2,3])) of type test.List!(int).List to
> > immutable(List)
> > 
> > Is this a bug? I can't identify where this issue would lie (works with
> > inheritance and templating).
> Maybe:
> -------------------------<<<<<<<<<<
>   List!T makeFromArray(T)(immutable T[] array) pure {
> 
> >     if (array.length == 0) { return null; }
> > 
> >     auto result = new Cons!T(array[0], null);
> >     auto end = result;
> > 
> >     for (int i = 1; i<  array.length; ++i) {
> > 
> >        end.tail_ = new Cons!T(array[i], null);
> >        end = end.tail_;
> > 
> >     }
> > 
> >     return result;
> > 
> > }
> 
> If I'm not mistaken only strongly pure functions are working.h

Which would make sense. The only reason that it can implicitly cast to immutable is because it _knows_ that there are no other mutable references to that data, and for it to be able to know that, the function must be strongly pure.

- Jonathan M Davis

On Thu, 22 Sep 2011 15:44:21 -0400, Jonathan M Davis <jmdavisProg@gmx.com> wrote:

> On Thursday, September 22, 2011 23:36:40 Dmitry Olshansky wrote:
>> On 22.09.2011 22:53, Jesse Phillips wrote:
>> > The discussion on Reddit brought to my attention that pure functions  
>> can
>> > return and assign to an immutable.
>> >
>> >  
>> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutabil
>> > ity_in_d/c2lsgek
>> >
>> > I am trying to modify the example request to make use of this, but  
>> have
>> > failed.
>> >
>> >  
>> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutabil
>> > ity_in_d/c2lrfpm
>> >
>> > test.d(4): Error: cannot implicitly convert expression
>> > (makeFromArray([1,2,3])) of type test.List!(int).List to
>> > immutable(List)
>> >
>> > Is this a bug? I can't identify where this issue would lie (works with
>> > inheritance and templating).
>> Maybe:
>> -------------------------<<<<<<<<<<
>>   List!T makeFromArray(T)(immutable T[] array) pure {
>>
>> >     if (array.length == 0) { return null; }
>> >
>> >     auto result = new Cons!T(array[0], null);
>> >     auto end = result;
>> >
>> >     for (int i = 1; i<  array.length; ++i) {
>> >
>> >        end.tail_ = new Cons!T(array[i], null);
>> >        end = end.tail_;
>> >
>> >     }
>> >
>> >     return result;
>> >
>> > }
>>
>> If I'm not mistaken only strongly pure functions are working.h
>
> Which would make sense. The only reason that it can implicitly cast to
> immutable is because it _knows_ that there are no other mutable references to
> that data, and for it to be able to know that, the function must be strongly
> pure.

Technically, something like this could be cast to immutable:

T[] foo(const(T)[] arg) pure

Since it can be proven that the result is new data.

So it doesn't *need* to be strong-pure.

-Steve

On Thu, 22 Sep 2011 16:09:29 -0400, Steven Schveighoffer <schveiguy@yahoo.com> wrote:

> On Thu, 22 Sep 2011 15:44:21 -0400, Jonathan M Davis <jmdavisProg@gmx.com> wrote:
>
>> On Thursday, September 22, 2011 23:36:40 Dmitry Olshansky wrote:
>>> On 22.09.2011 22:53, Jesse Phillips wrote:
>>> > The discussion on Reddit brought to my attention that pure functions  
>>> can
>>> > return and assign to an immutable.
>>> >
>>> >  
>>> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutabil
>>> > ity_in_d/c2lsgek
>>> >
>>> > I am trying to modify the example request to make use of this, but  
>>> have
>>> > failed.
>>> >
>>> >  
>>> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutabil
>>> > ity_in_d/c2lrfpm
>>> >
>>> > test.d(4): Error: cannot implicitly convert expression
>>> > (makeFromArray([1,2,3])) of type test.List!(int).List to
>>> > immutable(List)
>>> >
>>> > Is this a bug? I can't identify where this issue would lie (works  
>>> with
>>> > inheritance and templating).
>>> Maybe:
>>> -------------------------<<<<<<<<<<
>>>   List!T makeFromArray(T)(immutable T[] array) pure {
>>>
>>> >     if (array.length == 0) { return null; }
>>> >
>>> >     auto result = new Cons!T(array[0], null);
>>> >     auto end = result;
>>> >
>>> >     for (int i = 1; i<  array.length; ++i) {
>>> >
>>> >        end.tail_ = new Cons!T(array[i], null);
>>> >        end = end.tail_;
>>> >
>>> >     }
>>> >
>>> >     return result;
>>> >
>>> > }
>>>
>>> If I'm not mistaken only strongly pure functions are working.h
>>
>> Which would make sense. The only reason that it can implicitly cast to
>> immutable is because it _knows_ that there are no other mutable references to
>> that data, and for it to be able to know that, the function must be strongly
>> pure.
>
> Technically, something like this could be cast to immutable:
>
> T[] foo(const(T)[] arg) pure
>
> Since it can be proven that the result is new data.
>
> So it doesn't *need* to be strong-pure.

And actually, just making the argument immutable doesn't make it strong-pure, the result has to be too.

So I don't think it has to do with strong-purity at all.

-Steve

On Thursday, September 22, 2011 16:09:29 Steven Schveighoffer wrote:
> On Thu, 22 Sep 2011 15:44:21 -0400, Jonathan M Davis <jmdavisProg@gmx.com>
> 
> wrote:
> > On Thursday, September 22, 2011 23:36:40 Dmitry Olshansky wrote:
> >> On 22.09.2011 22:53, Jesse Phillips wrote:
> >> > The discussion on Reddit brought to my attention that pure functions
> >> 
> >> can
> >> 
> >> > return and assign to an immutable.
> >> 
> >> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutab il
> >> 
> >> > ity_in_d/c2lsgek
> >> > 
> >> > I am trying to modify the example request to make use of this, but
> >> 
> >> have
> >> 
> >> > failed.
> >> 
> >> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immutab il
> >> 
> >> > ity_in_d/c2lrfpm
> >> > 
> >> > test.d(4): Error: cannot implicitly convert expression
> >> > (makeFromArray([1,2,3])) of type test.List!(int).List to
> >> > immutable(List)
> >> > 
> >> > Is this a bug? I can't identify where this issue would lie (works
> >> > with
> >> > inheritance and templating).
> >> 
> >> Maybe:
> >> -------------------------<<<<<<<<<<
> >> 
> >>   List!T makeFromArray(T)(immutable T[] array) pure {
> >> 
> >> >     if (array.length == 0) { return null; }
> >> > 
> >> >     auto result = new Cons!T(array[0], null);
> >> >     auto end = result;
> >> > 
> >> >     for (int i = 1; i<  array.length; ++i) {
> >> > 
> >> >        end.tail_ = new Cons!T(array[i], null);
> >> >        end = end.tail_;
> >> > 
> >> >     }
> >> > 
> >> >     return result;
> >> > 
> >> > }
> >> 
> >> If I'm not mistaken only strongly pure functions are working.h
> > 
> > Which would make sense. The only reason that it can implicitly cast to
> > immutable is because it _knows_ that there are no other mutable
> > references to
> > that data, and for it to be able to know that, the function must be
> > strongly
> > pure.
> 
> Technically, something like this could be cast to immutable:
> 
> T[] foo(const(T)[] arg) pure
> 
> Since it can be proven that the result is new data.
> 
> So it doesn't *need* to be strong-pure.

Yes, you can always cast to immutable, but unless the compiler can _prove_ that the return value can be safely cast to immutable, it won't do it implicitly, and the function needs to be strongly pure to do that.

Now, if the compiler were improved to consider that function strongly pure when it's passed an immutable argument, then it would work in that case, but until that happens, it can't do that, and even then, it would only work if the argument passed to it were immutable rather than mutable or const.

- Jonathan M Davis

On Thursday, September 22, 2011 16:11:05 Steven Schveighoffer wrote:
> On Thu, 22 Sep 2011 16:09:29 -0400, Steven Schveighoffer
> 
> <schveiguy@yahoo.com> wrote:
> > On Thu, 22 Sep 2011 15:44:21 -0400, Jonathan M Davis
> > 
> > <jmdavisProg@gmx.com> wrote:
> >> On Thursday, September 22, 2011 23:36:40 Dmitry Olshansky wrote:
> >>> On 22.09.2011 22:53, Jesse Phillips wrote:
> >>> > The discussion on Reddit brought to my attention that pure functions
> >>> 
> >>> can
> >>> 
> >>> > return and assign to an immutable.
> >>> 
> >>> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immut abil>>>
> >>> > ity_in_d/c2lsgek
> >>> > 
> >>> > I am trying to modify the example request to make use of this, but
> >>> 
> >>> have
> >>> 
> >>> > failed.
> >>> 
> >>> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immut abil>>>
> >>> > ity_in_d/c2lrfpm
> >>> > 
> >>> > test.d(4): Error: cannot implicitly convert expression
> >>> > (makeFromArray([1,2,3])) of type test.List!(int).List to
> >>> > immutable(List)
> >>> > 
> >>> > Is this a bug? I can't identify where this issue would lie (works
> >>> 
> >>> with
> >>> 
> >>> > inheritance and templating).
> >>> 
> >>> Maybe:
> >>> -------------------------<<<<<<<<<<
> >>> 
> >>>   List!T makeFromArray(T)(immutable T[] array) pure {
> >>> 
> >>> >     if (array.length == 0) { return null; }
> >>> > 
> >>> >     auto result = new Cons!T(array[0], null);
> >>> >     auto end = result;
> >>> > 
> >>> >     for (int i = 1; i<  array.length; ++i) {
> >>> > 
> >>> >        end.tail_ = new Cons!T(array[i], null);
> >>> >        end = end.tail_;
> >>> > 
> >>> >     }
> >>> > 
> >>> >     return result;
> >>> > 
> >>> > }
> >>> 
> >>> If I'm not mistaken only strongly pure functions are working.h
> >> 
> >> Which would make sense. The only reason that it can implicitly cast to
> >> immutable is because it _knows_ that there are no other mutable
> >> references to
> >> that data, and for it to be able to know that, the function must be
> >> strongly
> >> pure.
> > 
> > Technically, something like this could be cast to immutable:
> > 
> > T[] foo(const(T)[] arg) pure
> > 
> > Since it can be proven that the result is new data.
> > 
> > So it doesn't *need* to be strong-pure.
> 
> And actually, just making the argument immutable doesn't make it strong-pure, the result has to be too.
> 
> So I don't think it has to do with strong-purity at all.

??? Functions are pure, not variables or return values. The entire reason that the compiler can implicitly cast the return value to immutable is because it _knows_ that there are no mutable references to that data, and it can only make that guarantee if the function is strongly pure. So, if a function is strongly pure, the implicit cast to immutable can be made, and if it's not, then it can't be.

For a function to be strongly pure, it cannot access any globally mutable state, all functions that it calls must be pure, and all of its parameters must either be immutable or implicitly convertible to immutable (so that the complire can guarantee that they'll never change). So, it's guaranteed that the return value of a strongly pure function is either immutable or it was allocated within that strongly pure function (or within a function that it called) and that there are no other references to that data, so then it's guaranteed that the return value can be safely cast to immutable. const doesn't enter into it (unless the compiler is improved to consider a pure function with const parameters strongly pure when it's passed immutable arguments), and there is no concept of the return value being pure or not. So, I'm not quite sure what you're thinking here.

- Jonathan M Davis

On Thu, 22 Sep 2011 16:15:20 -0400, Jonathan M Davis <jmdavisProg@gmx.com> wrote:

> On Thursday, September 22, 2011 16:09:29 Steven Schveighoffer wrote:
>>
>> Technically, something like this could be cast to immutable:
>>
>> T[] foo(const(T)[] arg) pure
>>
>> Since it can be proven that the result is new data.
>>
>> So it doesn't *need* to be strong-pure.
>
> Yes, you can always cast to immutable

I meant implicitly cast, sorry.  I should be able to do this:

T[] foo(const(T)[] arg) pure {...}

immutable x = foo(y);

> but unless the compiler can _prove_
> that the return value can be safely cast to immutable, it won't do it
> implicitly, and the function needs to be strongly pure to do that.

It doesn't.  In fact, the result of a strongly-pure function *cannot* be cast away from immutable implicitly:

immutable(int)[] strongpure(immutable(int)[] arg) pure { return arg[0..5];}

immutable(int)[] y = [1,2,3,4,5,6,7,8,9];
int[] x = strongpure(y); // error!

This function is not strong pure:

int[] weakpure(immutable(int)[] arg) pure {...}

because it cannot be optimized away.  Subsequent calls to weakpure do *not* return the same value, each one returns a new piece of data.

Yet because we know it returns a new piece of data, the result should be implicitly castable to immutable:

immutable(int)[] y = [1,2,3,4,5,6,7,8,9];
immutable(int)[] x = weakpure(y); // should be fine

-Steve

On Thu, 22 Sep 2011 16:23:12 -0400, Jonathan M Davis <jmdavisProg@gmx.com> wrote:

> On Thursday, September 22, 2011 16:11:05 Steven Schveighoffer wrote:
>> On Thu, 22 Sep 2011 16:09:29 -0400, Steven Schveighoffer
>>
>> <schveiguy@yahoo.com> wrote:
>> > On Thu, 22 Sep 2011 15:44:21 -0400, Jonathan M Davis
>> >
>> > <jmdavisProg@gmx.com> wrote:
>> >> On Thursday, September 22, 2011 23:36:40 Dmitry Olshansky wrote:
>> >>> On 22.09.2011 22:53, Jesse Phillips wrote:
>> >>> > The discussion on Reddit brought to my attention that pure
>> >>> > functions
>> >>>
>> >>> can
>> >>>
>> >>> > return and assign to an immutable.
>> >>>
>> >>> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immut
>> >>> abil>>>
>> >>> > ity_in_d/c2lsgek
>> >>> >
>> >>> > I am trying to modify the example request to make use of this,
>> >>> > but
>> >>>
>> >>> have
>> >>>
>> >>> > failed.
>> >>>
>> >>> http://www.reddit.com/r/programming/comments/knn5p/thoughts_on_immut
>> >>> abil>>>
>> >>> > ity_in_d/c2lrfpm
>> >>> >
>> >>> > test.d(4): Error: cannot implicitly convert expression
>> >>> > (makeFromArray([1,2,3])) of type test.List!(int).List to
>> >>> > immutable(List)
>> >>> >
>> >>> > Is this a bug? I can't identify where this issue would lie
>> >>> > (works
>> >>>
>> >>> with
>> >>>
>> >>> > inheritance and templating).
>> >>>
>> >>> Maybe:
>> >>> -------------------------<<<<<<<<<<
>> >>>
>> >>>   List!T makeFromArray(T)(immutable T[] array) pure {
>> >>>
>> >>> >     if (array.length == 0) { return null; }
>> >>> >
>> >>> >     auto result = new Cons!T(array[0], null);
>> >>> >     auto end = result;
>> >>> >
>> >>> >     for (int i = 1; i<  array.length; ++i) {
>> >>> >
>> >>> >        end.tail_ = new Cons!T(array[i], null);
>> >>> >        end = end.tail_;
>> >>> >
>> >>> >     }
>> >>> >
>> >>> >     return result;
>> >>> >
>> >>> > }
>> >>>
>> >>> If I'm not mistaken only strongly pure functions are working.h
>> >>
>> >> Which would make sense. The only reason that it can implicitly cast  
>> to
>> >> immutable is because it _knows_ that there are no other mutable
>> >> references to
>> >> that data, and for it to be able to know that, the function must be
>> >> strongly
>> >> pure.
>> >
>> > Technically, something like this could be cast to immutable:
>> >
>> > T[] foo(const(T)[] arg) pure
>> >
>> > Since it can be proven that the result is new data.
>> >
>> > So it doesn't *need* to be strong-pure.
>>
>> And actually, just making the argument immutable doesn't make it
>> strong-pure, the result has to be too.
>>
>> So I don't think it has to do with strong-purity at all.
>
> ??? Functions are pure, not variables or return values. The entire reason that
> the compiler can implicitly cast the return value to immutable is because it
> _knows_ that there are no mutable references to that data, and it can only
> make that guarantee if the function is strongly pure.  So, if a function is
> strongly pure, the implicit cast to immutable can be made, and if it's not,
> then it can't be.
>
> For a function to be strongly pure, it cannot access any globally mutable
> state, all functions that it calls must be pure, and all of its parameters
> must either be immutable or implicitly convertible to immutable (so that the
> complire can guarantee that they'll never change).

The definition of strong-pure is a pure function where pure optimizations can be made.  In order for that to work, The return value must also be immutable or implicitly castable to immutable.

Consider:

char[] foo(string s) pure { return s.dup;} // strong pure?

auto x = foo("hello");
auto y = foo("hello");

If foo was considered strong-pure, then couldn't the compiler rewrite the second line to be auto y = x ?  But let's mess it up:

auto x = foo("hello");
x[0] = 'm';
auto y = foo("hello");

The compiler *must* call both foo calls, it can't optimize any away.

Contrast this with a true strong-pure function which returns string, the compiler *can* safely remove the second call.

This is different from a pure function "where it's guaranteed the result is new data".  That is the condition for which you should be allowed to implicitly cast.  Uniqueness is the property we are looking for, and the only way to guarantee it is with a pure function that returns a type that cannot be a subset of any parameter.

-Steve

On Thursday, September 22, 2011 13:25 Steven Schveighoffer wrote:
> On Thu, 22 Sep 2011 16:15:20 -0400, Jonathan M Davis <jmdavisProg@gmx.com>
> 
> wrote:
> > On Thursday, September 22, 2011 16:09:29 Steven Schveighoffer wrote:
> >> Technically, something like this could be cast to immutable:
> >> 
> >> T[] foo(const(T)[] arg) pure
> >> 
> >> Since it can be proven that the result is new data.
> >> 
> >> So it doesn't *need* to be strong-pure.
> > 
> > Yes, you can always cast to immutable
> 
> I meant implicitly cast, sorry. I should be able to do this:
> 
> T[] foo(const(T)[] arg) pure {...}
> 
> immutable x = foo(y);
> 
> > but unless the compiler can _prove_
> > that the return value can be safely cast to immutable, it won't do it
> > implicitly, and the function needs to be strongly pure to do that.
> 
> It doesn't. In fact, the result of a strongly-pure function *cannot* be cast away from immutable implicitly:

Casting away immutability was never the issue. I don't believe that that can _ever_ be done implicitly, regardless of purity. It's casting _to_ immutable that's the issue.

> immutable(int)[] strongpure(immutable(int)[] arg) pure { return arg[0..5];}
> 
> immutable(int)[] y = [1,2,3,4,5,6,7,8,9];
> int[] x = strongpure(y); // error!
> 
> This function is not strong pure:
> 
> int[] weakpure(immutable(int)[] arg) pure {...}
> 
> because it cannot be optimized away. Subsequent calls to weakpure do *not* return the same value, each one returns a new piece of data.
> 
> Yet because we know it returns a new piece of data, the result should be implicitly castable to immutable:
> 
> immutable(int)[] y = [1,2,3,4,5,6,7,8,9];
> immutable(int)[] x = weakpure(y); // should be fine

Okay. I think that the problem here is that everything that I've been saying has everything to do with the parameters and arguments and _nothing_ to do with the return value. You make a valid point in your other post that a function returning a mutable value can't be considered strongly pure. However, if you ignore the return value in what I was saying about strongly pure before, everything holds for being able to implicitly cast to immutable. The issue is that a function which returns a mutable value can't quite be strongly pure, which I misjudged, so terming them strongly pure as I was is incorrect. However, I would point out that a function which returns a const value can still be strongly pure as long as all of its parameters are all immutable or implicitly convertible to immutable, since then the compiler can guarantee that the return value can't be changed without subverting the type system.

In any case, in order for a function to be able to have its return value implicitly value implicitly cast to immutable, it must pure and all of its arguments must be immutable or implicitly convertible to immutable (or - if the compiler is ever improved to treat pure functions with const parameters and immutable arguments the same way - the requirement would be that the function must be pure and all of its _arguments_ must be immutable or implicitly convertible to immutable). So, we have a new distinguish to make with regards to purity - whether the return value can be implicitly cast to immutable or not - and we don't have a name for that. And unlike strong purity vs weak purity, programmers actually have to understand the distinction if they're going to take advantage of it.

- Jonathan M Davis