[I actually came up with this idea last week, but decided to postpone bringing it up until all the furor about Andrei's new allocator design has settled a little. ;-)]

One of the neatest things about purity in D is that traditionally impure operations like mutation and assignment can be allowed inside a pure function, as long as the effect is invisible to the outside world. This, of course, describes strong purity. Weak purity takes it one step further, by allowing mutation of outside state via references to mutable data passed in as function arguments.

I'd like to propose extending the scope of weak purity one step further: allow weakly-pure functions to call (not necessarily pure) delegates passed as a parameter. That is, the following code should work:

	// 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.

But, I hear you cry, if func calls an *impure function* via a function pointer, doesn't that already violate purity??!

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];
	}

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). Any delegate that stronglyPure()
can construct, can only ever affect its local state. The only way you
could sneak an impure delegate into func() is if stronglyPure() itself
takes an impure delegate as parameter -- but if it does so, then it is
no longer strongly pure.

IOW, if stronglyPure() is truly strongly pure, then it is actually
impossible for the call to func() to have any effect outside of
stronglyPure()'s local scope, no matter what kind of delegate
stronglyPure() passes to func(). So such a call should be permitted!

Now let's consider the case where we pass a delegate to func() that
*does* modify global state:

	int global_state;
	void main() {
		func((int x) { global_state = x; });
	}

In this case, func being marked pure doesn't really cause any issues: main() itself is already impure because it is constructing a delegate that closes over a global variable, so the fact that the actual change comes from calling func no longer matters. It's always OK for impure code to call pure code, after all. It's no different from this:

	void weaklyPure(int* x) pure {
		*x = 1;	// OK
	}

	int global_state;
	void main() {
		weaklyPure(&global_state);
	}

That is to say, as long as the code that calls func() is marked pure,
then the behaviour of func() is guaranteed never to affect anything
outside the local scope of the caller (and whatever the caller can reach
via mutable reference parameters). That is, it is (at least) weakly
pure. If the caller is strongly pure (no mutable indirections in
parameters -- and this includes delegates), then func() is guaranteed to
never cause side-effects outside its caller. Therefore, it should be
permissible to mark func() as pure.

//

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). 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.
  (Rationale: the delegate parameter potentially involves arbitrary
  references to the outside world, and thus cannot be strongly pure.)


T

-- 
Gone Chopin. Bach in a minuet.

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.

On 10/31/2013 10:10 PM, Timon Gehr wrote:
>
> 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.

(Actually DMD 2.063+ accept the declaration but disallow calling it with a lambda function, but this is a minor change.)

I think you take it the wrong way. Weak purity have some guarantee in itself, like you know it won't reach shared data unless you pass them explicitly, do not touch anything static, etc . . .

You are basically addressing 2 more general problems here. Both are real and larger than the case you are considering.

The first one is delegate purity and context type qualifier. As you mention, a delegate's context is simply some extra data that get passed to the delegate as ARGUMENT. So the delegate must be able to mutate this while being pure.

That is the first thing : pure delegate must be able to mutate their context.

The second one is the inout problem. Qualifier in output may reflect the one in inputs. inout solve this for some type qualifiers, but sometime is ambiguous and does nothing for the problem at large.

On 11/01/2013 12:26 AM, deadalnix wrote:
> I think you take it the wrong way. Weak purity have some guarantee in
> itself, like you know it won't reach shared data

I assume you mean mutable shared data.

> unless you pass them explicitly, do not touch anything static,

Unless you pass it in explicitly.

> etc . . .

Consider this:

shared static int x;

auto bar(){
    class S{
	shared(int)* p;
	this(shared(int)* p){ this.p=p; }
        int member(int y)pure{
            return *p=y;
        }
    }
    auto s=new S(&x);
    return &s.member;
}

/+
auto bar_prime(){ // does the same thing. (but is rejected by DMD)
    return (y)pure=x=y;
}+/

auto foo(int delegate(int)pure dg, int x)pure{
    return dg(x);
}

void main(){
    auto a=bar(); // note: a is pure
    assert(x==0);
    foo(a,2); // note: foo is weakly pure
    assert(x==2);
    foo(a,3);
    assert(x==3);
}

On 11/01/2013 12:45 PM, Timon Gehr wrote:
>      auto a=bar(); // note: a is pure

(as in 'weakly pure'.)

On Friday, 1 November 2013 at 11:45:23 UTC, Timon Gehr wrote:
>
>     return (y)pure=x=y;

Drifting off topic a little, but how does this expression work?  I can't recall having seen the (y)pure thing before.

-Wyatt

On 11/01/2013 01:43 PM, Wyatt wrote:
> On Friday, 1 November 2013 at 11:45:23 UTC, Timon Gehr wrote:
>>
>>     return (y)pure=x=y;
>
> Drifting off topic a little, but how does this expression work? I can't
> recall having seen the (y)pure thing before.
>
> -Wyatt

It is in a comment. The exact expression wouldn't compile in this context, (one reason is that I have sloppily left out the parameter type, the other is that the body is not considered pure.)

I assume your question extends to the following case which is valid D code?

auto foo(){ return (int y)pure=>2; }

All function attributes (except ref, which I think is a bug in the design and/or implementation) can be specified after any parameter list. This includes function literal parameter lists (except for the single-identifier case).

(y)pure=>2 is a valid template function literal:

auto foo(alias a)(){ return a(3); }
static assert(foo!((y)pure=>2)()==2);
//                 ^~~~~~~~~~

(Typically pure is left out here, except for emphasis, because it is inferred anyway, so one would rather use y=>2.)

01.11.2013 0:05, H. S. Teoh пишет:
> [I actually came up with this idea last week, but decided to postpone
> bringing it up until all the furor about Andrei's new allocator design
> has settled a little. ;-)]
>
> One of the neatest things about purity in D is that traditionally impure
> operations like mutation and assignment can be allowed inside a pure
> function, as long as the effect is invisible to the outside world. This,
> of course, describes strong purity. Weak purity takes it one step
> further, by allowing mutation of outside state via references to mutable
> data passed in as function arguments.
>
> I'd like to propose extending the scope of weak purity one step further:
> allow weakly-pure functions to call (not necessarily pure) delegates
> passed as a parameter. That is, the following code should work:
>
> 	// 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.
>
> But, I hear you cry, if func calls an *impure function* via a function
> pointer, doesn't that already violate purity??!
>
> 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];
> 	}
>
> 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). Any delegate that stronglyPure()
> can construct, can only ever affect its local state. The only way you
> could sneak an impure delegate into func() is if stronglyPure() itself
> takes an impure delegate as parameter -- but if it does so, then it is
> no longer strongly pure.
>
> IOW, if stronglyPure() is truly strongly pure, then it is actually
> impossible for the call to func() to have any effect outside of
> stronglyPure()'s local scope, no matter what kind of delegate
> stronglyPure() passes to func(). So such a call should be permitted!
>
> Now let's consider the case where we pass a delegate to func() that
> *does* modify global state:
>
> 	int global_state;
> 	void main() {
> 		func((int x) { global_state = x; });
> 	}
>
> In this case, func being marked pure doesn't really cause any issues:
> main() itself is already impure because it is constructing a delegate
> that closes over a global variable, so the fact that the actual change
> comes from calling func no longer matters. It's always OK for impure
> code to call pure code, after all. It's no different from this:
>
> 	void weaklyPure(int* x) pure {
> 		*x = 1;	// OK
> 	}
>
> 	int global_state;
> 	void main() {
> 		weaklyPure(&global_state);
> 	}
>
> That is to say, as long as the code that calls func() is marked pure,
> then the behaviour of func() is guaranteed never to affect anything
> outside the local scope of the caller (and whatever the caller can reach
> via mutable reference parameters). That is, it is (at least) weakly
> pure. If the caller is strongly pure (no mutable indirections in
> parameters -- and this includes delegates), then func() is guaranteed to
> never cause side-effects outside its caller. Therefore, it should be
> permissible to mark func() as pure.
>
> //
>
> 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). 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.
>    (Rationale: the delegate parameter potentially involves arbitrary
>    references to the outside world, and thus cannot be strongly pure.)
>
>
> T
>

The code you like to make working looks good but I'm against the language change. I'd say the issue is nested pure functions aren't allowed to access outer function variables. Filed as Issue 11412.

The fact inpure `lazy` expressions are accepted is filed as Issue 11411 [2].

[1] http://d.puremagic.com/issues/show_bug.cgi?id=11412
[2] http://d.puremagic.com/issues/show_bug.cgi?id=11411

-- 
Денис В. Шеломовский
Denis V. Shelomovskij

01.11.2013 0:05, H. S. Teoh пишет:
> I'd like to propose extending the scope of weak purity one step further:
> allow weakly-pure functions to call (not necessarily pure) delegates
> passed as a parameter.

Unacceptable. It will break strongly purity. Your mistake is strongly pure function can easily get an impure delegate:
---
int i;

struct S
{ void g() { ++i; } }

void impureCaller(scope void delegate() del) pure
{ del(); }

void f() pure // strongly pure, will modify `i`
{
    S s;
    impureCaller(&s.g);
}
---

So issues 11469 [1] & 11412 [2] are the only way I see to solve our problems.

[1] http://d.puremagic.com/issues/show_bug.cgi?id=11469
[2] http://d.puremagic.com/issues/show_bug.cgi?id=11412

-- 
Денис В. Шеломовский
Denis V. Shelomovskij