Using pure to create immutable

[Steven Schveighoffer]

On Thu, 22 Sep 2011 16:23:12 -0400, Jonathan M Davis <jmdavisProg at 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 at yahoo.com> wrote:
>> > On Thu, 22 Sep 2011 15:44:21 -0400, Jonathan M Davis
>> >
>> > <jmdavisProg at 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