Expanding the horizons of D purity

[Timon Gehr]

On 10/31/2013 09:05 PM, H. S. Teoh wrote:
>  ...
> 	// N.B. This is a (weakly) pure function.
> 	void func(scope void delegate(int) dg) pure
> 	{
> 		// N.B. This calls an *impure* delegate.
> 		dg(1);
> 	}
>
> Before you break out the pitchforks, please allow me to rationalize this
> situation.
>
> The above code is essentially equivalent to:
>
> 	void func(void *context, scope void function(void*,int) dg) pure
> 	{
> 		dg(context, 1);
> 	}
>
> That is to say, passing in a delegate is essentially equivalent to
> passing in a mutable reference to some outside state (the delegate's
> context), and a pointer to a function that possibly mutates the outside
> world through that context pointer. In a sense, this is not that much
> different from a weakly pure function that directly modifies the outside
> world via the context pointer.
> ...

Also consider the strongly pure version:

void func(scope immutable(void)* context, scope void 
function(immutable(void)*,int)pure dg) pure{
     dg(context, 1);
}

The 'immutable' on the context qualifies all data reachable from the 
context as immutable.

The 'pure' on the function pointer can be approximately understood as 
qualifying all data reachable from the function body code as immutable. 
(i.e. the referenced shared and thread local globals.)

This of course suggests that the 'essetial equivalent' of the above code is:

void func(scope void delegate(int)pure immutable dg){
     dg(1);
}

But DMD rejects this, which is blatantly wrong. It uses two different 
notions of purity for delegates obtained from member functions and for 
lambdas.

> ...
>
> Well, it certainly violates *strong* purity, no question about that. But
> consider this code:
>
> 	int stronglyPure(int x) pure
> 	{
> 		int[] scratchpad;
> 		scratchpad.length = 2;
>
> 		// This is an impure delegate because it closes over
> 		// scratchpad.
> 		auto dg = (int x) { scratchpad[x]++; };
>
> 		// Should this work?
> 		func(dg);
>
> 		return scratchpad[1];
> 	}
> ...

Yah, actually this is a weakly pure delegate. The function attributes 
for lambdas just haven't been fixed after the meaning of 'pure' has 
changed to weakly pure. I.e. I think your code should be compilable even 
if func takes a pure delegate.


To demonstrate, we can write the following functions that DMD accepts:


void func(scope void delegate(int)pure dg) pure{
     dg(1);
}

int stronglyPure(int x) pure{
     struct S{
         int[] scratchpad;
         void member(int x) pure { scratchpad[x]++; };
     }
     S s;
     s.scratchpad.length = 2;

     // this is a pure delegate, even though it does
     // (essentially) the same as yours, namely
     // it changes a location in its context
     auto dg=&s.member;

     func(dg); // works.

     return s.scratchpad[1];
}


> Think about it.  What func does via dg can only ever affect a variable
> local to stronglyPure(). It's actually impossible for stronglyPure() to
> construct a delegate that modifies a global variable, because the
> compiler will complain that referencing a global is not allowed inside a
> pure function (verified on git HEAD).

This is similar to the restriction that pure functions may not take the 
address of a global mutable variable, so it makes some sense.

> ...
>
> //
>
> Why is this important? Well, ultimately the motivation for pushing the
> envelope in this direction is due to functions of this sort:
>
> 	void toString(scope void delegate(const(char)[]) dg) {
> 		dg(...);
> 	}
>
> By allowing this function to be marked pure, we permit it to be called
> from pure code (which I proved in the above discussion as actually
> pure).

Well, "proved" is maybe a little strong. Let's say you presented a well 
reasoned argument. :o)

> Or, put another way, we permit template functions that call
> toString with a delegate that updates a local variable to be inferred as
> pure. This allows more parts of std.format to be pure, which in turn
> expands the usability of things like std.conv.to in pure code.
> Currently, to!string(3.14f) is impure due to std.format ultimately
> calling a toString function like the above, but there is absolutely no
> reason why computing the string representation of a float can't be made
> pure. Implementing this proposal would resolve this problem.
>
> Besides, expanding the scope of purity allows much more D code to be
> made pure, thus increasing purity-based optimization opportunities.
>
> So, in a nutshell, my proposal is:
>
> - Functions that, besides invoking a delegate parameter, are pure,
>    should be allowed to be marked as pure.
>
> - Template functions that, besides invoking a delegate parameter,
>    perform no impure operations should be inferred as pure.
>
> - A function that takes a delegate parameter cannot be strongly pure
>    (but can be weakly pure), unless the delegate itself is pure.

Should probably be 'pure immutable', as lined out above. Do you agree?

>    (Rationale: the delegate parameter potentially involves arbitrary
>    references to the outside world, and thus cannot be strongly pure.)
>
>
> T
>

I guess this is the way to go. I approve of this proposal.