Timon Gehr wrote:
> On 08/21/2011 09:10 PM, Don wrote:
>> bearophile wrote:
>>> Sean Eskapp:
>>>
>>>> Oh, I see, thanks! This isn't documented in the function documentation!
>>>
>>> D purity implementation looks like a simple thing, but it's not
>>> simple, it has several parts that in the last months have be added to
>>> the language and compiler, and we are not done yet, there are few more
>>> things to add (like implicit conversion to immutable of the results of
>>> strongly pure functions). It will need several book pages to document
>>> all such necessary design details.
>>>
>>> Bye,
>>> bearophile
>>
>> It is actually very simple: a function marked as 'pure' is not allowed
>> to explicitly access any static variables.
>> Everything else is just compiler optimisation, and the programmer
>> shouldn't need to worry about it.
> 
> It can be of value to know that a function is pure as in mathematics if it is strongly pure, but can have restricted side-effects if it is weakly pure.

Well, from the compiler's point of view, it's more complicated than that. There are const-pure as well as immutable-pure functions. A const-pure function has no side-effects, but cannot be optimised as strongly as an immutable-pure function.

BTW: The whole "weak pure"/"strong pure" naming was just something I came up with, to convince Walter to relax the purity rules. I'd rather those names disappeared, they aren't very helpful.

But the basic point is, that knowing that there are no static variables is hugely significant for reasoning about code. The strong pure/weak pure distinction is not very interesting (you can distinguish them
using only the function signature).

On Mon, 22 Aug 2011 22:19:50 +0200, Don <nospam@nospam.com> wrote:

> BTW: The whole "weak pure"/"strong pure" naming was just something I came up with, to convince Walter to relax the purity rules. I'd rather those names disappeared, they aren't very helpful.

The concepts are useful, but better names might be worth it. But what
short word eloquently conveys 'accesses no mutable global state'? :p

What we call strongly pure is what in other languages is simply called
'pure', and that is likely the word that should be used for it.

Weakly pure is a somewhat different beast, and the 'best' solution would
likely be for it to be the default (But as we all know, this would
require changing the language too much. Perhaps in D3...). Noglobal
might be the best we have. My favorite thus far is 'conditionally pure'.
It conveys that the function is pure in certain circumstances, and not
in others. However, it might be somewhat diluted by the addition of pure
inference in newer versions of DMD - that definitely is conditionally
pure.

Const pure is not a concept I'm particularly familiar with. Is this the
special case of calling a conditionally pure function with only
const/immutable parameters, with arguments that are immutable in the
calling context, and that it in those cases can be considered
strongly pure?

-- 
  Simen

On 08/22/2011 10:19 PM, Don wrote:
> Timon Gehr wrote:
>> On 08/21/2011 09:10 PM, Don wrote:
>>> bearophile wrote:
>>>> Sean Eskapp:
>>>>
>>>>> Oh, I see, thanks! This isn't documented in the function
>>>>> documentation!
>>>>
>>>> D purity implementation looks like a simple thing, but it's not
>>>> simple, it has several parts that in the last months have be added to
>>>> the language and compiler, and we are not done yet, there are few more
>>>> things to add (like implicit conversion to immutable of the results of
>>>> strongly pure functions). It will need several book pages to document
>>>> all such necessary design details.
>>>>
>>>> Bye,
>>>> bearophile
>>>
>>> It is actually very simple: a function marked as 'pure' is not allowed
>>> to explicitly access any static variables.
>>> Everything else is just compiler optimisation, and the programmer
>>> shouldn't need to worry about it.
>>
>> It can be of value to know that a function is pure as in mathematics
>> if it is strongly pure, but can have restricted side-effects if it is
>> weakly pure.
>
> Well, from the compiler's point of view, it's more complicated than
> that. There are const-pure as well as immutable-pure functions. A
> const-pure function has no side-effects, but cannot be optimised as
> strongly as an immutable-pure function.

What significant optimization do immutable-pure functions benefit from that const-pure functions cannot? Is it just that the compiler cannot do CSE in some cases if there is an impure call in between two const-pure calls? (which I think would be rather insignificant)

>
> BTW: The whole "weak pure"/"strong pure" naming was just something I
> came up with, to convince Walter to relax the purity rules. I'd rather
> those names disappeared, they aren't very helpful.
>

In some contexts they are in fact useful, otherwise the compiler implementation wouldn't have any use for them.

> But the basic point is, that knowing that there are no static variables
> is hugely significant for reasoning about code.  The strong pure/weak
> pure distinction is not very interesting (you can distinguish them
> using only the function signature).

Yes, but saying 'the function is weakly pure' is shorter than saying 'the pure function signature does include mutable references', just like having a flag set to PUREweak is more efficient than examining the function signature multiple times.

On Monday, August 22, 2011 15:57 Timon Gehr wrote:
> On 08/22/2011 10:19 PM, Don wrote:
> > Timon Gehr wrote:
> >> On 08/21/2011 09:10 PM, Don wrote:
> >>> bearophile wrote:
> >>>> Sean Eskapp:
> >>>>> Oh, I see, thanks! This isn't documented in the function documentation!
> >>>> 
> >>>> D purity implementation looks like a simple thing, but it's not simple, it has several parts that in the last months have be added to the language and compiler, and we are not done yet, there are few more things to add (like implicit conversion to immutable of the results of strongly pure functions). It will need several book pages to document all such necessary design details.
> >>>> 
> >>>> Bye,
> >>>> bearophile
> >>> 
> >>> It is actually very simple: a function marked as 'pure' is not allowed
> >>> to explicitly access any static variables.
> >>> Everything else is just compiler optimisation, and the programmer
> >>> shouldn't need to worry about it.
> >> 
> >> It can be of value to know that a function is pure as in mathematics if it is strongly pure, but can have restricted side-effects if it is weakly pure.
> > 
> > Well, from the compiler's point of view, it's more complicated than that. There are const-pure as well as immutable-pure functions. A const-pure function has no side-effects, but cannot be optimised as strongly as an immutable-pure function.
> 
> What significant optimization do immutable-pure functions benefit from that const-pure functions cannot? Is it just that the compiler cannot do CSE in some cases if there is an impure call in between two const-pure calls? (which I think would be rather insignificant)

The _only_ time that subsequent calls to a pure function can be optimized out is when all of its arguments are immutable or implicitly convertible to immutable, otherwise their values could change between calls to the function. A function whose parameters are all immutable or implicitly convertible to immutable is always going to be able to be optimized that way, because you _know_ that it's arguments are immutable or implicitly convertible to immutable (they _have_ to be). In cases where a pure function whose parameters are const or implicitly convertible to immutable is passed immutable arguments, it could be optimized (though that doesn't currently happen), but if the arguments aren't immutable, then it can't be, because they could change between calls to the function.

> > BTW: The whole "weak pure"/"strong pure" naming was just something I came up with, to convince Walter to relax the purity rules. I'd rather those names disappeared, they aren't very helpful.
> 
> In some contexts they are in fact useful, otherwise the compiler implementation wouldn't have any use for them.
> 
> > But the basic point is, that knowing that there are no static variables is hugely significant for reasoning about code. The strong pure/weak pure distinction is not very interesting (you can distinguish them using only the function signature).
> 
> Yes, but saying 'the function is weakly pure' is shorter than saying 'the pure function signature does include mutable references', just like having a flag set to PUREweak is more efficient than examining the function signature multiple times.

Ultimately, whether pure functions can be optimized or not becomes an implementation detail. pure functions can't access mutable global state. That's what pure means. The compiler then does what it can to optimize pure functions. Weak and strong purity are what determine whether such optimizations can take place, but I think that Don is basically saying that that should just be an implementation detail and that what should be focused on with regards to pure functions is the fact that they can't access mutable global state.

- Jonathan M Davis

Simen Kjaeraas wrote:
> On Mon, 22 Aug 2011 22:19:50 +0200, Don <nospam@nospam.com> wrote:
> 
>> BTW: The whole "weak pure"/"strong pure" naming was just something I came up with, to convince Walter to relax the purity rules. I'd rather those names disappeared, they aren't very helpful.
> 
> The concepts are useful, but better names might be worth it. But what
> short word eloquently conveys 'accesses no mutable global state'? :p

@nostatic  ?
stateless ?

> What we call strongly pure is what in other languages is simply called
> 'pure', and that is likely the word that should be used for it.


> Weakly pure is a somewhat different beast, and the 'best' solution would
> likely be for it to be the default (But as we all know, this would
> require changing the language too much. Perhaps in D3...). Noglobal
> might be the best we have. My favorite thus far is 'conditionally pure'.
> It conveys that the function is pure in certain circumstances, and not
> in others. However, it might be somewhat diluted by the addition of pure
> inference in newer versions of DMD - that definitely is conditionally
> pure.
> 
> Const pure is not a concept I'm particularly familiar with. Is this the
> special case of calling a conditionally pure function with only
> const/immutable parameters, with arguments that are immutable in the
> calling context, and that it in those cases can be considered
> strongly pure?

No, it's where the signature contains const parameters, rather than immutable ones.
Two calls to a const-pure function, with the same parameters, may give different results. You'd need to do a deep inspection of the parameters,
to see if they changed.

Consider:

x = foo(y);
x = foo(y);
where foo is const-pure.
Perhaps y contains a pointer to x. In that case, foo could depend on x.
Or, there might be a mutable pointer to y somewhere, and x might have an opAssign which modifies y.
In each case, the second y is different to the first one.

But, if foo is immutable-pure, it will return the same value both times, so one of the calls can be optimized away.