The docs currently state that:
---
Pure functions are functions that produce the same result for the same arguments. To that end, a pure function:

    * has parameters that are all immutable or are implicitly convertible to immutable
    * does not read or write any global mutable state
---

This is extremely restrictive, and not currently enforced.
Two specific limitations:
- a 'pure' member function doesn't really make sense (could only be called on an immutable class)
- a pure function cannot have 'out' parameters.

In a discussion on D.learn, Steven Schveighoffer noted that it's only shared variables which make things complicated.
The limitations exist because 'pure' is used to mean both 'no hidden state' AND 'cachable'. But 'cachable' is really only an implementation detail.

PROPOSAL:
Drop the first requirement. Only one requirement is necessary:

A pure function does not read or write any global mutable state.

If a pure function has parameters that are all immutable or are implicitly convertible to immutable, then the compiler is permitted to cache the results.

This is possible because the first rule (all immutable parameters) is trivial, and can be checked from the function declaration (in fact, you can check it just from the mangled function name). The second rule (no globals) is viral, and requires inspection of the function body, and the function bodies of every function called by that function.

Actually, a clever compiler could even cache the results of pure functions which have parameters which don't implicitly cast to immutable.

I haven't found anything in TDPL which mentions the "only immutable parameters" rule. Relaxing that rule would allow much larger functions to be cached. The more important benefit (IMHO) of pure, that it makes it easier to reason about code, would be dramatically extended.

== Quote from Don (nospam@nospam.com)'s article
> The docs currently state that:
> ---
> Pure functions are functions that produce the same result for the same
> arguments. To that end, a pure function:
>      * has parameters that are all immutable or are implicitly
> convertible to immutable
>      * does not read or write any global mutable state
> ---
> This is extremely restrictive, and not currently enforced.
> Two specific limitations:
> - a 'pure' member function doesn't really make sense (could only be
> called on an immutable class)
> - a pure function cannot have 'out' parameters.
> In a discussion on D.learn, Steven Schveighoffer noted that it's only
> shared variables which make things complicated.
> The limitations exist because 'pure' is used to mean both 'no hidden
> state' AND 'cachable'. But 'cachable' is really only an implementation
> detail.
> PROPOSAL:
> Drop the first requirement. Only one requirement is necessary:
> A pure function does not read or write any global mutable state.
> If a pure function has parameters that are all immutable or are
> implicitly convertible to immutable, then the compiler is permitted to
> cache the results.
> This is possible because the first rule (all immutable parameters) is
> trivial, and can be checked from the function declaration (in fact, you
> can check it just from the mangled function name). The second rule (no
> globals) is viral, and requires inspection of the function body, and the
> function bodies of every function called by that function.
> Actually, a clever compiler could even cache the results of pure
> functions which have parameters which don't implicitly cast to immutable.
> I haven't found anything in TDPL which mentions the "only immutable
> parameters" rule. Relaxing that rule would allow much larger functions
> to be cached. The more important benefit (IMHO) of pure, that it makes
> it easier to reason about code, would be dramatically extended.

Two things:

1.  The documentation that says that the parameters need to be convertible to immutable is outdated.  This was changed a while ago to only requiring const.

2.  If you mean that the parameters don't have to be const either, i.e. you can
freely mutate state on the heap, i.e. of a ref parameter, or stuff that's
reachable from a pointer or reference, then pure offers almost no useful guarantees.

On Tue, 21 Sep 2010 22:21:39 -0400, Don <nospam@nospam.com> wrote:

> The docs currently state that:
> ---
> Pure functions are functions that produce the same result for the same arguments. To that end, a pure function:
>
>      * has parameters that are all immutable or are implicitly convertible to immutable
>      * does not read or write any global mutable state
> ---
>
> This is extremely restrictive, and not currently enforced.
> Two specific limitations:
> - a 'pure' member function doesn't really make sense (could only be called on an immutable class)
> - a pure function cannot have 'out' parameters.
>
> In a discussion on D.learn, Steven Schveighoffer noted that it's only shared variables which make things complicated.
> The limitations exist because 'pure' is used to mean both 'no hidden state' AND 'cachable'. But 'cachable' is really only an implementation detail.
>
> PROPOSAL:
> Drop the first requirement. Only one requirement is necessary:
>
> A pure function does not read or write any global mutable state.
>
> If a pure function has parameters that are all immutable or are implicitly convertible to immutable, then the compiler is permitted to cache the results.
>
> This is possible because the first rule (all immutable parameters) is trivial, and can be checked from the function declaration (in fact, you can check it just from the mangled function name). The second rule (no globals) is viral, and requires inspection of the function body, and the function bodies of every function called by that function.
>
> Actually, a clever compiler could even cache the results of pure functions which have parameters which don't implicitly cast to immutable.
>
> I haven't found anything in TDPL which mentions the "only immutable parameters" rule. Relaxing that rule would allow much larger functions to be cached. The more important benefit (IMHO) of pure, that it makes it easier to reason about code, would be dramatically extended.

One of the major benefits of functional languages (a.k.a pure functions) is that you can automatically parallelize them (i.e. via a task based runtime) in addition to caching the result. I really don't want to lose that guarantee. However, I do see your point. One of the benefits of D's pure functions is the ability to use procedural code inside them; however the "does not read or write any global mutable state" prevents pure functions from calling impure functions/members on their internal (impure) variables. So removing the concurrency safety from pure would greatly expand the number of pure functions, however, automatic parallelism would be lost. I don't view this as an acceptable reduction in pure's power, particularly given that Dave's std.parallelism module is currently under review.

With regard to an alternative, I think two levels of pure have been identified as being useful and synergistic to each other. I think this could either manifest itself as pure + scope(pure) or as a new 'task' type + pure. Anyways, that's my two cents worth.

Wed, 22 Sep 2010 04:21:39 +0200, Don wrote:

> The docs currently state that:
> ---
> Pure functions are functions that produce the same result for the same arguments. To that end, a pure function:
> 
>      * has parameters that are all immutable or are implicitly
> convertible to immutable
>      * does not read or write any global mutable state
> ---
> 
> This is extremely restrictive, and not currently enforced. Two specific
> limitations:
> - a 'pure' member function doesn't really make sense (could only be
> called on an immutable class)
> - a pure function cannot have 'out' parameters.
> 
> In a discussion on D.learn, Steven Schveighoffer noted that it's only shared variables which make things complicated. The limitations exist because 'pure' is used to mean both 'no hidden state' AND 'cachable'. But 'cachable' is really only an implementation detail.
> 
> PROPOSAL:
> Drop the first requirement. Only one requirement is necessary:
> 
> A pure function does not read or write any global mutable state.

A purely functional language provides referential transparency: the same arguments applied to the function always return the same result.

Technically this is feasible, but I don't think that it's a good idea to surprise user with impurity of pure function.

> This is extremely restrictive, and not currently enforced.
> Two specific limitations:
> - a 'pure' member function doesn't really make sense (could only be
> called on an immutable class)
> - a pure function cannot have 'out' parameters.

If you can't use purity, don't use it, impure functions work just fine.

Don wrote:

> The docs currently state that:
> ---
> Pure functions are functions that produce the same result for the same arguments. To that end, a pure function:
> 
>      * has parameters that are all immutable or are implicitly
> convertible to immutable
>      * does not read or write any global mutable state
> ---
> 
> This is extremely restrictive, and not currently enforced.
> Two specific limitations:
> - a 'pure' member function doesn't really make sense (could only be
> called on an immutable class)
> - a pure function cannot have 'out' parameters.

Would it be possible to make an exception for out parameters? After all they can
be considered part of the output, and as input are always initialized to the
same value. The result of a function can be defined as the tuple of its return
value and all out parameters.

> In a discussion on D.learn, Steven Schveighoffer noted that it's only
> shared variables which make things complicated.
> The limitations exist because 'pure' is used to mean both 'no hidden
> state' AND 'cachable'. But 'cachable' is really only an implementation
> detail.
> 
> PROPOSAL:
> Drop the first requirement. Only one requirement is necessary:
> 
> A pure function does not read or write any global mutable state.
> 
> If a pure function has parameters that are all immutable or are implicitly convertible to immutable, then the compiler is permitted to cache the results.

If pure functions are allowed to mutate their input parameters, do we not lose referential transparency?

a = pureFun(input);
b = pureFun(input);

assert( a == b );

Or am I misunderstanding your proposal?

Don wrote:
> The docs currently state that:

> PROPOSAL:
> Drop the first requirement. Only one requirement is necessary:
> 
> A pure function does not read or write any global mutable state.
> 

Wow. It seems that not one person who has responded so far has understood this proposal! I'll try again. Under this proposal:

If you see a function which has mutable parameters, but is marked as 'pure', you can only conclude that it doesn't use global variables. That's not much use on it's own. Let's call this a 'weakly-pure' function.

However, if you see a function maked as 'pure', which also has only immutable parameters, you have the same guarantee which 'pure' gives us as the moment. Let's call this a 'strongly-pure' function.

The benefit of the relaxed rule is that a strongly-pure function can call a weakly-pure functions, while remaining strongly-pure.
This allows very many more functions to become strongly pure.

The point of the proposal is *not* to provide the weak guarantee. It is to provide the strong guarantee in more situations.

On 09/22/2010 10:13 AM, Don wrote:
> Don wrote:
>> The docs currently state that:
>
>> PROPOSAL:
>> Drop the first requirement. Only one requirement is necessary:
>>
>> A pure function does not read or write any global mutable state.
>>
>
> Wow. It seems that not one person who has responded so far has
> understood this proposal! I'll try again. Under this proposal:
>
> If you see a function which has mutable parameters, but is marked as
> 'pure', you can only conclude that it doesn't use global variables.
> That's not much use on it's own. Let's call this a 'weakly-pure' function.
>
> However, if you see a function maked as 'pure', which also has only
> immutable parameters, you have the same guarantee which 'pure' gives us
> as the moment. Let's call this a 'strongly-pure' function.
>
> The benefit of the relaxed rule is that a strongly-pure function can
> call a weakly-pure functions, while remaining strongly-pure.
> This allows very many more functions to become strongly pure.
>
> The point of the proposal is *not* to provide the weak guarantee. It is
> to provide the strong guarantee in more situations.

Will this allow member functions to be weakly pure? As in, only touches its own state.

Because that would be useful.

Pelle wrote:
> On 09/22/2010 10:13 AM, Don wrote:
>> Don wrote:
>>> The docs currently state that:
>>
>>> PROPOSAL:
>>> Drop the first requirement. Only one requirement is necessary:
>>>
>>> A pure function does not read or write any global mutable state.
>>>
>>
>> Wow. It seems that not one person who has responded so far has
>> understood this proposal! I'll try again. Under this proposal:
>>
>> If you see a function which has mutable parameters, but is marked as
>> 'pure', you can only conclude that it doesn't use global variables.
>> That's not much use on it's own. Let's call this a 'weakly-pure' function.
>>
>> However, if you see a function maked as 'pure', which also has only
>> immutable parameters, you have the same guarantee which 'pure' gives us
>> as the moment. Let's call this a 'strongly-pure' function.
>>
>> The benefit of the relaxed rule is that a strongly-pure function can
>> call a weakly-pure functions, while remaining strongly-pure.
>> This allows very many more functions to become strongly pure.
>>
>> The point of the proposal is *not* to provide the weak guarantee. It is
>> to provide the strong guarantee in more situations.
> 
> Will this allow member functions to be weakly pure? As in, only touches its own state.
> 
> Because that would be useful.
Yes.

On 2010-09-21 22:21:39 -0400, Don <nospam@nospam.com> said:

> PROPOSAL:
> Drop the first requirement. Only one requirement is necessary:
> 
> A pure function does not read or write any global mutable state.
> 
> If a pure function has parameters that are all immutable or are implicitly convertible to immutable, then the compiler is permitted to cache the results.

This is what I was advocating a long time ago when pure came out.

The current rule prevent you from doing any serious work from inside a pure function. Inside a pure function you can only call a pure function, you can't even call functions that take mutable references to local variables. This makes it impossible to use generic algorithms, such as sort, to manipulate local mutable data, even when those algorithms have no need for a global state.

So I certainly support this change.

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/