I think this is a good discovery. Currently a pure function can have lazy parameters and it is treated as a weakly pure function.

pure int foo(lazy int x) { return x; }  // OK

We can think the lazy parameter is a limited case of scope delegate parameter.

And more, I discovered that the purity may be stronger depends on the given delegate purity.

void func(scope void delegate(int) dg) pure;

void main() {
    int num;

    // the function call has weak purity
    func((x){ num = x;});

    // the function call has strong purity
    func((x){ ; });
}

Kenji Hara



2013/11/1 H. S. Teoh <hsteoh@quickfur.ath.cx>

> [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 11/01/2013 02:36 PM, Kenji Hara wrote:
> I think this is a good discovery. Currently a pure function can have
> lazy parameters and it is treated as a weakly pure function.
>
> pure int foo(lazy int x) { return x; }  // OK
>
> We can think the lazy parameter is a limited case of scope delegate
> parameter.
>...

They are. I think it would be quite strange to treat them differently.

> And more, I discovered that the purity may be stronger depends on the
> given delegate purity.
>
> void func(scope void delegate(int) dg) pure;
>
> void main() {
>      int num;
>
>      // the function call has weak purity
>      func((x){ num = x;});
>
>      // the function call has strong purity
>      func((x){ ; });
> }
>
> Kenji Hara
>

Yes. Furthermore, the first delegate should have inferred type 'void delegate(int x)pure nothrow @safe' and the second delegate should have inferred type 'void delegate(int x)pure immutable nothrow @safe'.

2013/11/1 Timon Gehr <timon.gehr@gmx.ch>

> On 11/01/2013 02:36 PM, Kenji Hara wrote:
>
>> I think this is a good discovery. Currently a pure function can have lazy parameters and it is treated as a weakly pure function.
>>
>> pure int foo(lazy int x) { return x; }  // OK
>>
>> We can think the lazy parameter is a limited case of scope delegate
>> parameter.
>> ...
>>
>
> They are. I think it would be quite strange to treat them differently.


I've also felt same thing about it. The proposal will generalize the language rule.


>  And more, I discovered that the purity may be stronger depends on the
>> given delegate purity.
>>
>> void func(scope void delegate(int) dg) pure;
>>
>> void main() {
>>      int num;
>>
>>      // the function call has weak purity
>>      func((x){ num = x;});
>>
>>      // the function call has strong purity
>>      func((x){ ; });
>> }
>>
>> Kenji Hara
>>
>>
> Yes. Furthermore, the first delegate should have inferred type 'void delegate(int x)pure nothrow @safe' and the second delegate should have inferred type 'void delegate(int x)pure immutable nothrow @safe'.
>

The first delegate should not become pure. So it would become 'void delegate(int)nothrow @safe'. I agree with the second inference result.

Kenji Hara

On 11/01/2013 03:21 PM, Kenji Hara wrote:
> 2013/11/1 Timon Gehr <timon.gehr@gmx.ch <mailto:timon.gehr@gmx.ch>>
>
>     On 11/01/2013 02:36 PM, Kenji Hara wrote:
>
>         I think this is a good discovery. Currently a pure function can have
>         lazy parameters and it is treated as a weakly pure function.
>
>         pure int foo(lazy int x) { return x; }  // OK
>
>         We can think the lazy parameter is a limited case of scope delegate
>         parameter.
>         ...
>
>
>     They are. I think it would be quite strange to treat them differently.
>
>
> I've also felt same thing about it. The proposal will generalize the
> language rule.
>
>         And more, I discovered that the purity may be stronger depends
>         on the
>         given delegate purity.
>
>         void func(scope void delegate(int) dg) pure;
>
>         void main() {
>               int num;
>
>               // the function call has weak purity
>               func((x){ num = x;});
>
>               // the function call has strong purity
>               func((x){ ; });
>         }
>
>         Kenji Hara
>
>
>     Yes. Furthermore, the first delegate should have inferred type 'void
>     delegate(int x)pure nothrow @safe' and the second delegate should
>     have inferred type 'void delegate(int x)pure immutable nothrow @safe'.
>
>
> The first delegate should not become pure.

Why not? It is weakly pure, like the following:

void main(){
    struct S{
        int num;
        void member(int x)pure{ num = x; } // pure
    }
    S s;
    func(&s.member); // weakly pure function call
}


> So it would become 'void
> delegate(int)nothrow @safe'. I agree with the second inference result.
>
> Kenji Hara

2013/11/1 Timon Gehr <timon.gehr@gmx.ch>

> On 11/01/2013 03:21 PM, Kenji Hara wrote:
>
>>
>> The first delegate should not become pure.
>>
>
> Why not? It is weakly pure, like the following:
>
> void main(){
>     struct S{
>         int num;
>         void member(int x)pure{ num = x; } // pure
>     }
>     S s;
>     func(&s.member); // weakly pure function call
>
> }
>

Hmm, looks reasonable. Thanks for the good point out.

Kenji Hara

On Fri, Nov 01, 2013 at 08:59:29PM +0400, Denis Shelomovskij wrote:
> 01.11.2013 0:05, H. S. Teoh пишет:
[...]
> >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.
[...]

No, that's not good enough. What if you need to pass an impure delegate to toString()? Sure, std.format can be made to use only pure delegates, but you can't predict other code that needs to use toString. Forcing toString to take only pure delegates makes it unusable with output ranges that need to perform impure operations. With my proposal, toString will work with *both* pure and impure delegates -- basically, the pure qualifier becomes a dependent purity ("purity of this function depends on the delegate parameter, body of function is pure besides the invocation of the delegate").


T

-- 
Кто везде - тот нигде.

On Fri, Nov 01, 2013 at 12:26:43AM +0100, 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 unless you pass them explicitly, do not touch anything static, etc . . .

This still holds. Passing a delegate that closes over shared data is equal to passing in a reference to that data as argument. It's compatible with the current definition of weak purity.


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

There is also the case where you want toString() to work for *both* pure and impure code. By allowing it to call any delegate, we're essentially saying "the body of this function is pure, depending on the purity of the call to the delegate". So you can pass in a completely impure delegate and it will behave like an impure function, but the trick here is that (1) impure delegates cannot be created within strongly pure functions (i.e., delegates that cause side-effects to appear outside the strongly pure function), and (2) all delegates created within strongly pure functions will only produce pure behaviour with the function that invokes the delegate. IOW, when called from pure code, the function is actually pure, even if it's impure when called from impure code.


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

I'm not sure what inout has to do with purity. It's another can o' worms that I'm avoiding to open, at the moment. :P


T

-- 
Your inconsistency is the only consistent thing about you! -- KD

On Thu, Oct 31, 2013 at 10:10:03PM +0100, Timon Gehr wrote:
> On 10/31/2013 09:05 PM, H. S. Teoh wrote:
[...]
> >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?
[...]

Yes, you're right. If the delegate can't modify anything externally, then the function can be made strongly pure.


T

-- 
One reason that few people are aware there are programs running the internet is that they never crash in any significant way: the free software underlying the internet is reliable to the point of invisibility. -- Glyn Moody, from the article "Giving it all away"

On Friday, 1 November 2013 at 17:21:07 UTC, H. S. Teoh wrote:
>> 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.
>
> I'm not sure what inout has to do with purity. It's another can o' worms
> that I'm avoiding to open, at the moment. :P
>

That is the same problem. You won't understand it unless you open the can of worms.

01.11.2013 21:12, H. S. Teoh пишет:
> On Fri, Nov 01, 2013 at 08:59:29PM +0400, Denis Shelomovskij wrote:
>> 01.11.2013 0:05, H. S. Teoh пишет:
> [...]
>>> 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.
> [...]
>
> No, that's not good enough. What if you need to pass an impure delegate
> to toString()? Sure, std.format can be made to use only pure delegates,
> but you can't predict other code that needs to use toString. Forcing
> toString to take only pure delegates makes it unusable with output
> ranges that need to perform impure operations. With my proposal,
> toString will work with *both* pure and impure delegates -- basically,
> the pure qualifier becomes a dependent purity ("purity of this function
> depends on the delegate parameter, body of function is pure besides the
> invocation of the delegate").
>
>
> T
>

I'd say `@safe`, `pure`, and `nothrow` are in the same boat here and the solution should work for them all. Probably we will need a delegate attributes wildcard. Something like this:
---
// a single wildcard for all:
void f(void delegate() @attr_wildcard del) @attr_wildcard;
---
or better:
---
// `f` is `@safe`, it also `pure` and `nothrow` if `del` is:
void f(void delegate() @safe pure? nothrow? del) @safe pure? nothrow?;
---

Also, do you disagree with the proposal in Issue 11412 [1]?

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

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