On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
> On Thu, 15 May 2014 05:51:14 +0000
> via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
> 
>> Yep, purity implies memoing.
> 
> No, it doesn't. _All_ that it means when a function is pure is that it cannot access global or static variables unless they can't be changed after being initialized (e.g. they're immutable, or they're const value types), and it can't call any other functions which aren't pure. It means _nothing_ else. And it _definitely_ has nothing to do with functional purity.
> 
> Now, combined with other information, you _can_ get functional purity out it - e.g. if all the parameters to a function are immutable, then it _is_ functionally pure, and optimizations requiring functional purity can be done with that function. But by itself, pure means nothing of the sort.
> 
> So, no, purity does _not_ imply memoization.
> 
> - Jonathan M Davis
> 

Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)"

The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence.

Even other sources are consistent on this matter, and this is what purity by definition is.

On Thu, 15 May 2014 07:22:02 +0000
via Digitalmars-d <digitalmars-d@puremagic.com> wrote:

> On Thursday, 15 May 2014 at 06:59:08 UTC, Jonathan M Davis via Digitalmars-d wrote:
> > And it _definitely_ has nothing to do with functional purity.
>
> Which makes it pointless and misleading.
>
> > Now, combined with other information, you _can_ get functional
> > purity out it -
> > e.g. if all the parameters to a function are immutable, then it
> > _is_
> > functionally pure, and optimizations requiring functional
> > purity can be done
> > with that function.
>
> No, you can't say it is functionally pure if you can flip a coin with a pure function. To do that you would need a distinction between "prove pure" and "assume pure" as well as having immutable reference types that ban identity comparison.
>
> > So, no, purity does _not_ imply memoization.
>
> It should, or use a different name.

Originally, pure required that the function parameters be pure in addition to disallowing the function from accessing global or static variables or calling functions that weren't pure. It allowed for mutation within the function, and it allowed for allocation via new, but from the outside, the function _was_ functionally pure. The problem was that it was almost useless. You just couldn't do anything in a pure function that mattered most of the time. You couldn't call any other functions from the pure function unless they were pure, which meant that the arguments to them had to be immutable, which just didn't work, because while the arguments to the first function were immutable, what it had to do internally often involved operating on other variables which were created within the function which were not immutable and didn't need to be immutable, but you couldn't use them with any functions unless they were immutable thanks to the fact that all pure functions had to have immutable parameters, and pure functions could only call pure functions. It just didn't work.

So, Don introduced the idea of "weak" purity. What it comes down to is that it's an extension of the concept that mutation within a pure function is fine just so long as its arguments aren't mutated. We made it so that pure functions _didn't_ have to have immutable parameters. They just couldn't access anything that wasn't passed to them as arguments. This meant that they could only mutate what they were given and thus they didn't violate the "strong" purity of the original pure function which had immutable parameters. e.g.

string strongFunc(immutable string foo, int i) pure
{
    auto foo = str ~ " hello world ";
    weak(str, i);
    return str;
}

void weakFunc(ref string str, int i) pure
{
    foreach(j; 0 .. i)
        str ~= to!(j);
}

The strong guarantees that strongFunc has which make it functionally pure are not violated by the fact that weakFunc is _not_ functionally pure. But by marking it pure, it guarantees that it can safely be called from a strongly pure function without violating the guarantees of that strongly pure function. To do that, _all_ we need to guarantee is that the weakly pure function cannot access anything save for what's passed into it (since if it could access global variables, that would violate the guarantees of any other pure functions that called it), but we do need that guarantee. The result is that the pure attribute doesn't in and of itself mean functional purity anymore, but it _can_ be used to build a function which is functionally pure.

You could argue that a different attribute should be used other than pure to mark "weakly" pure functions, but that would just complicate things. The compiler is capable of figuring out the difference between a "weakly" pure and "strongly" pure function on its own from just the function signature just so long as "weak" purity is detectable from the function signature. So, we only need one attribute - one to mark the fact that the function can't access global, mutable state and can't call any functions that can. And we were already marking strongly pure functions with pure, so it made perfect sense to use it on weakly pure functions as well. At that point, it was just up to the compiler to detect whether the function was strongly pure or not and thus was functionally pure and could be used in optimizations.

So, sorry that it offends your sensibilities that pure by itself does not indicate functional purity, but it's a building block for functional purity, and the evolution of things made it make perfect sense to use the pure attribute for this. And even if pure _didn't_ enable functional purity, it would still be highly useful just from the fact that a pure function (be it weak or strong) cannot access global variables, and that makes it _much_ easier to reason about code, because you know that it isn't accessing anything that wasn't passed to it.

I recommend that you read this article by David Nadlinger:

http://klickverbot.at/blog/2012/05/purity-in-d/

- Jonathan M Davis

On Thu, 15 May 2014 10:14:48 +0200
luka8088 via Digitalmars-d <digitalmars-d@puremagic.com> wrote:

> On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
> > On Thu, 15 May 2014 05:51:14 +0000
> > via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
> >
> >> Yep, purity implies memoing.
> >
> > No, it doesn't. _All_ that it means when a function is pure is that it cannot access global or static variables unless they can't be changed after being initialized (e.g. they're immutable, or they're const value types), and it can't call any other functions which aren't pure. It means _nothing_ else. And it _definitely_ has nothing to do with functional purity.
> >
> > Now, combined with other information, you _can_ get functional purity out it - e.g. if all the parameters to a function are immutable, then it _is_ functionally pure, and optimizations requiring functional purity can be done with that function. But by itself, pure means nothing of the sort.
> >
> > So, no, purity does _not_ imply memoization.
> >
> > - Jonathan M Davis
> >
>
> Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)"
>
> The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence.
>
> Even other sources are consistent on this matter, and this is what purity by definition is.
>

The reread the paragraph at the top of the section of the documentation that you linked to:

"Pure functions are functions which cannot access global or static, mutable state save through their arguments. This can enable optimizations based on the fact that a pure function is guaranteed to mutate nothing which isn't passed to it, and in cases where the compiler can guarantee that a pure function cannot alter its arguments, it can enable full, functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)."

That outright says that pure only _can_ enable functional purity - in particular when the compiler is able to guarantee that the function cannot mutate its arguments. pure itself however means nothing of the sort. The fact that pure functions cannot access global state _is_ the basis for functional purity when combined with parameters that arguments cannot be mutated.

If you get hung up on what the concept of functional purity is or what you thought pure was before using D, then you're going to have a hard time understanding what pure means in D. And yes, it's a bit weird, but it comes from the practical standpoint of how to make functional purity possible without being too restrictive to be useful. So, it really doesn't matter what other sources say about what purity means. That's not what D's pure means. D's pure is just a building block for what purity normally means. It makes it so that the compiler can detect functional purity and then optimize based on it, but it doesn't in and of itself have anything to do with functional purity.

If the documentation isn't getting that across, then I guess that it isn't clear enough. But I would have thought that the part that said "and in cases where the compiler can guarantee that a pure function cannot alter its arguments, it can enable full, functional purity" would have made it clear that D's pure is _not_ functionally pure by itself. The first part of the paragraph says what pure really means: "Pure functions are functions which cannot access global or static, mutable state save through their arguments." Everything else with regards to functional purity is derived from there, but in and of itself, that's _all_ that the pure attribute in D means.

See also: http://klickverbot.at/blog/2012/05/purity-in-d/

- Jonathan M Davis

On Thursday, 15 May 2014 at 08:14:50 UTC, luka8088 wrote:
> On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
>> On Thu, 15 May 2014 05:51:14 +0000
>> via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>> 
>>> Yep, purity implies memoing.
>> 
>> No, it doesn't. _All_ that it means when a function is pure is that it cannot
>> access global or static variables unless they can't be changed after being
>> initialized (e.g. they're immutable, or they're const value types), and it
>> can't call any other functions which aren't pure. It means _nothing_ else. And
>> it _definitely_ has nothing to do with functional purity.
>> 
>> Now, combined with other information, you _can_ get functional purity out it -
>> e.g. if all the parameters to a function are immutable, then it _is_
>> functionally pure, and optimizations requiring functional purity can be done
>> with that function. But by itself, pure means nothing of the sort.
>> 
>> So, no, purity does _not_ imply memoization.
>> 
>> - Jonathan M Davis
>> 
>
> Um. Yes it does. http://dlang.org/function.html#pure-functions
> "functional purity (i.e. the guarantee that the function will always
> return the same result for the same arguments)"
>
> The fact that it should not be able to effect or be effected by the
> global state is not a basis for purity, but rather a consequence.
>
> Even other sources are consistent on this matter, and this is what
> purity by definition is.


Please note: D's 'pure' annotation does *not* mean that the function is pure. It means that it is statically verified to be OK to call it from a pure function.

The compiler determines if a function is pure, the programmer never does.

There are two things going on here, and they are quite distinct.

(1) Really the keyword should be something like '@noglobal', rather than 'pure'. It's called pure for historical reasons. To reduce confusion I'll call D's pure '@noglobal' and the functional languages pure '@memoizable'.

But it turns out that @memoizable isn't actually an interesting property, whereas '@noglobal' is.

"No global state" is a deep, transitive property of a function. "Memoizable" is a superficial supersetextra property which the compiler can trivially determine from @noglobal.

Suppose you have function f(), which calls function g().

If f does not depend on global state, then g must not depend on global state.

BUT if f() can be memoizable even if g() is not memoizable.

This approach used by D enormously increases the number of functions which can be statically proven to be pure. The nomenclature can create confusion though.


(2) Allowing GC activity inside a @noglobal function does indeed weaken our ability to memoize.

The compiler can still perform memoizing operations on most functions that return GC-allocated memory, but it's more difficult. We don't yet have data on how much of a problem this is.

An interesting side-effect of the recent addition of @nogc to the language, is that we get this ability back.

On 15.5.2014. 11:35, Jonathan M Davis via Digitalmars-d wrote:
> On Thu, 15 May 2014 10:14:48 +0200
> luka8088 via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
> 
>> On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
>>> On Thu, 15 May 2014 05:51:14 +0000
>>> via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>>>
>>>> Yep, purity implies memoing.
>>>
>>> No, it doesn't. _All_ that it means when a function is pure is that it cannot access global or static variables unless they can't be changed after being initialized (e.g. they're immutable, or they're const value types), and it can't call any other functions which aren't pure. It means _nothing_ else. And it _definitely_ has nothing to do with functional purity.
>>>
>>> Now, combined with other information, you _can_ get functional purity out it - e.g. if all the parameters to a function are immutable, then it _is_ functionally pure, and optimizations requiring functional purity can be done with that function. But by itself, pure means nothing of the sort.
>>>
>>> So, no, purity does _not_ imply memoization.
>>>
>>> - Jonathan M Davis
>>>
>>
>> Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)"
>>
>> The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence.
>>
>> Even other sources are consistent on this matter, and this is what purity by definition is.
>>
> 
> The reread the paragraph at the top of the section of the documentation that you linked to:
> 
> "Pure functions are functions which cannot access global or static, mutable state save through their arguments. This can enable optimizations based on the fact that a pure function is guaranteed to mutate nothing which isn't passed to it, and in cases where the compiler can guarantee that a pure function cannot alter its arguments, it can enable full, functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)."
> 
> That outright says that pure only _can_ enable functional purity - in particular when the compiler is able to guarantee that the function cannot mutate its arguments. pure itself however means nothing of the sort. The fact that pure functions cannot access global state _is_ the basis for functional purity when combined with parameters that arguments cannot be mutated.

I am aware of weak/strong purity. I am only talking about strong purity now.

To quote bearophile:

bool randomBit() pure nothrow @safe {
    return (new int[1].ptr) > (new int[1].ptr);
}
void main() {}

"Pure functions are functions which cannot access global or static, mutable state save through their arguments." - no objections here

"This can enable optimizations based on the fact that a pure function is guaranteed to mutate nothing which isn't passed to it, and in cases where the compiler can guarantee that a pure function cannot alter its arguments, it can enable full, functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)." - no arguments where passed to the function, it should always return the same result

> 
> If you get hung up on what the concept of functional purity is or what you thought pure was before using D, then you're going to have a hard time understanding what pure means in D. And yes, it's a bit weird, but it comes from the practical standpoint of how to make functional purity possible without being too restrictive to be useful. So, it really doesn't matter what other sources say about what purity means. That's not what D's pure means. D's pure is just a building block for what purity normally means. It makes it so that the compiler can detect functional purity and then optimize based on it, but it doesn't in and of itself have anything to do with functional purity.
> 
> If the documentation isn't getting that across, then I guess that it isn't clear enough. But I would have thought that the part that said "and in cases where the compiler can guarantee that a pure function cannot alter its arguments, it can enable full, functional purity" would have made it clear that D's pure is _not_ functionally pure by itself. The first part of the paragraph says what pure really means: "Pure functions are functions which cannot access global or static, mutable state save through their arguments." Everything else with regards to functional purity is derived from there, but in and of itself, that's _all_ that the pure attribute in D means.
> 
> See also: http://klickverbot.at/blog/2012/05/purity-in-d/
> 
> - Jonathan M Davis
> 

Yeah, it does not seem to be clear enough.

It comes down to two simple questions:
  - should you be able to make a strong pure rand() function i D?
  - if not, why?

My answer would be: no, because the result should always be the same.

Of course I could be wrong, but my understanding of it fits with what the docs say. I think that answering this questions would clarify a lot!

On Thursday, 15 May 2014 at 09:23:00 UTC, Jonathan M Davis via Digitalmars-d wrote:
> functions that weren't pure. It allowed for mutation within the function, and
> it allowed for allocation via new, but from the outside, the function _was_
> functionally pure.

If it didn't return the memory allocated with new and if the call to new resulted in an exception, yes.

> It just didn't work.

That I question. A pure function ( http://en.wikipedia.org/wiki/Pure_function ) depends on the values of the parameters, and only that. That is most useful. Those value can be very complex. You could have a pure member function look up values in a cache. Then the configuration of entire cache is the value.

You need to think about this in terms of pre/post conditions in Hoare Logic (which I am not very good at btw).


> So, Don introduced the idea of "weak" purity. What it comes down to is that
> it's an extension of the concept that mutation within a pure function is fine
> just so long as its arguments aren't mutated. We made it so that pure
> functions _didn't_ have to have immutable parameters. They just couldn't
> access anything that wasn't passed to them as arguments. This meant that they
> could only mutate what they were given and thus they didn't violate the
> "strong" purity of the original pure function which had immutable parameters.

And that's fine as long as nobody else is holding a reference to those mutable parameters. That means that you are taking version N of the mutable and returning version N+1. That's similar to

x=1
a =f(x)
x=x+1
b = f(x)

which can be rewritten as:

x0 =1
a = f(x0)
x1 = x0+1
b = f(x1)

If you think in terms of a context for purity such as a transaction then you can even allow access to globals as long as they remain constant until the transaction is committed (or you leave the context where purity is desired). Meaning, you can memoize within that context.

> functions that called it), but we do need that guarantee. The result is that
> the pure attribute doesn't in and of itself mean functional purity anymore,
> but it _can_ be used to build a function which is functionally pure.

But, that can be deduced by the compiler, so what is the point of having "pure" for "weakly pure"? Clearly you only need to specify "strongly pure"?

> So, sorry that it offends your sensibilities that pure by itself does not
> indicate functional purity, but it's a building block for functional purity,

It doesn't offend me, but it is a source of confusion and not sticking to definitions makes the language design look random.

The same thing goes for lazy parameters. Why pick Call-By-Name (Algol style) over Call-By-Need (memoing)? Call-By-Name is known to be error prone.

Actually, lazy parameters should be restricted to pure expressions… if correctness and safety is the goal.

> attribute for this. And even if pure _didn't_ enable functional purity, it
> would still be highly useful just from the fact that a pure function (be it
> weak or strong) cannot access global variables, and that makes it _much_
> easier to reason about code, because you know that it isn't accessing anything
> that wasn't passed to it.

Ok, but maybe the opposite would be better. Marking functions that access globals with @global or something. After all, most functions don't access globals.

On 15.5.2014. 11:45, Don wrote:
> On Thursday, 15 May 2014 at 08:14:50 UTC, luka8088 wrote:
>> On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
>>> On Thu, 15 May 2014 05:51:14 +0000
>>> via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>>>
>>>> Yep, purity implies memoing.
>>>
>>> No, it doesn't. _All_ that it means when a function is pure is that
>>> it cannot
>>> access global or static variables unless they can't be changed after
>>> being
>>> initialized (e.g. they're immutable, or they're const value types),
>>> and it
>>> can't call any other functions which aren't pure. It means _nothing_
>>> else. And
>>> it _definitely_ has nothing to do with functional purity.
>>>
>>> Now, combined with other information, you _can_ get functional purity
>>> out it -
>>> e.g. if all the parameters to a function are immutable, then it _is_
>>> functionally pure, and optimizations requiring functional purity can
>>> be done
>>> with that function. But by itself, pure means nothing of the sort.
>>>
>>> So, no, purity does _not_ imply memoization.
>>>
>>> - Jonathan M Davis
>>>
>>
>> Um. Yes it does. http://dlang.org/function.html#pure-functions "functional purity (i.e. the guarantee that the function will always return the same result for the same arguments)"
>>
>> The fact that it should not be able to effect or be effected by the global state is not a basis for purity, but rather a consequence.
>>
>> Even other sources are consistent on this matter, and this is what purity by definition is.
> 
> 
> Please note: D's 'pure' annotation does *not* mean that the function is pure. It means that it is statically verified to be OK to call it from a pure function.
> 
> The compiler determines if a function is pure, the programmer never does.
> 
> There are two things going on here, and they are quite distinct.
> 
> (1) Really the keyword should be something like '@noglobal', rather than 'pure'. It's called pure for historical reasons. To reduce confusion I'll call D's pure '@noglobal' and the functional languages pure '@memoizable'.
> 
> But it turns out that @memoizable isn't actually an interesting property, whereas '@noglobal' is.
> 
> "No global state" is a deep, transitive property of a function. "Memoizable" is a superficial supersetextra property which the compiler can trivially determine from @noglobal.
> 
> Suppose you have function f(), which calls function g().
> 
> If f does not depend on global state, then g must not depend on global state.
> 
> BUT if f() can be memoizable even if g() is not memoizable.
> 
> This approach used by D enormously increases the number of functions which can be statically proven to be pure. The nomenclature can create confusion though.
> 
> 
> (2) Allowing GC activity inside a @noglobal function does indeed weaken
> our ability to memoize.
> 
> The compiler can still perform memoizing operations on most functions that return GC-allocated memory, but it's more difficult. We don't yet have data on how much of a problem this is.
> 
> An interesting side-effect of the recent addition of @nogc to the language, is that we get this ability back.
> 

Yeah, I read all about weak/string purity and I do understand the background. I was talking about strong purity, maybe I should pointed that out.

So, to correct myself: As I understood strong purity implies memoization. Am I correct?

On Thursday, 15 May 2014 at 09:45:52 UTC, Don wrote:
> But it turns out that @memoizable isn't actually an interesting property, whereas '@noglobal' is.
>
> "No global state" is a deep, transitive property of a function. "Memoizable" is a superficial supersetextra property which the compiler can trivially determine from @noglobal.

Uhm. That is a pretty strong assumption. "memoizable" is very useful property when you do multihreading, transactions or anything that requires locking. And you can still access globals, you just need a guarantee that globals don't change until you are done.

Considering that > 90% of the functions I write don't do IO or globals I'd rather specify the opposite. "io", "global" whatever. That is also easy to enforce, i.e. you don't get to access IO/globals if you don't annotate the function.

On Thursday, 15 May 2014 at 10:31:47 UTC, luka8088 wrote:
> On 15.5.2014. 11:45, Don wrote:
>> On Thursday, 15 May 2014 at 08:14:50 UTC, luka8088 wrote:
>>> On 15.5.2014. 8:58, Jonathan M Davis via Digitalmars-d wrote:
>>>> On Thu, 15 May 2014 05:51:14 +0000
>>>> via Digitalmars-d <digitalmars-d@puremagic.com> wrote:
>>>>
>>>>> Yep, purity implies memoing.
>>>>
>>>> No, it doesn't. _All_ that it means when a function is pure is that
>>>> it cannot
>>>> access global or static variables unless they can't be changed after
>>>> being
>>>> initialized (e.g. they're immutable, or they're const value types),
>>>> and it
>>>> can't call any other functions which aren't pure. It means _nothing_
>>>> else. And
>>>> it _definitely_ has nothing to do with functional purity.
>>>>
>>>> Now, combined with other information, you _can_ get functional purity
>>>> out it -
>>>> e.g. if all the parameters to a function are immutable, then it _is_
>>>> functionally pure, and optimizations requiring functional purity can
>>>> be done
>>>> with that function. But by itself, pure means nothing of the sort.
>>>>
>>>> So, no, purity does _not_ imply memoization.
>>>>
>>>> - Jonathan M Davis
>>>>
>>>
>>> Um. Yes it does. http://dlang.org/function.html#pure-functions
>>> "functional purity (i.e. the guarantee that the function will always
>>> return the same result for the same arguments)"
>>>
>>> The fact that it should not be able to effect or be effected by the
>>> global state is not a basis for purity, but rather a consequence.
>>>
>>> Even other sources are consistent on this matter, and this is what
>>> purity by definition is.
>> 
>> 
>> Please note: D's 'pure' annotation does *not* mean that the function is
>> pure. It means that it is statically verified to be OK to call it from a
>> pure function.
>> 
>> The compiler determines if a function is pure, the programmer never does.
>> 
>> There are two things going on here, and they are quite distinct.
>> 
>> (1) Really the keyword should be something like '@noglobal', rather than
>> 'pure'. It's called pure for historical reasons. To reduce confusion
>> I'll call D's pure '@noglobal' and the functional languages pure
>> '@memoizable'.
>> 
>> But it turns out that @memoizable isn't actually an interesting
>> property, whereas '@noglobal' is.
>> 
>> "No global state" is a deep, transitive property of a function.
>> "Memoizable" is a superficial supersetextra property which the compiler
>> can trivially determine from @noglobal.
>> 
>> Suppose you have function f(), which calls function g().
>> 
>> If f does not depend on global state, then g must not depend on global
>> state.
>> 
>> BUT if f() can be memoizable even if g() is not memoizable.
>> 
>> This approach used by D enormously increases the number of functions
>> which can be statically proven to be pure. The nomenclature can create
>> confusion though.
>> 
>> 
>> (2) Allowing GC activity inside a @noglobal function does indeed weaken
>> our ability to memoize.
>> 
>> The compiler can still perform memoizing operations on most functions
>> that return GC-allocated memory, but it's more difficult. We don't yet
>> have data on how much of a problem this is.
>> 
>> An interesting side-effect of the recent addition of @nogc to the
>> language, is that we get this ability back.
>> 
>
> Yeah, I read all about weak/string purity and I do understand the
> background. I was talking about strong purity, maybe I should pointed
> that out.
>
> So, to correct myself: As I understood strong purity implies
> memoization. Am I correct?

Yes. 'strong pure' means pure in the way that the functional language crowd means 'pure'.
'weak pure' just means doesn't use globals.

But note that "strong purity" isn't an official concept, it was just the terminology I used when explain to Walter what I meant. I don't like the term because it's rather misleading
-- in reality you could define a whole range of purity strengths (more than just two).
The stronger the purity, the more optimizations you can apply.

On Thu, 15 May 2014 10:10:57 +0000
via Digitalmars-d <digitalmars-d@puremagic.com> wrote:

> On Thursday, 15 May 2014 at 09:23:00 UTC, Jonathan M Davis via Digitalmars-d wrote:
> > functions that weren't pure. It allowed for mutation within the
> > function, and
> > it allowed for allocation via new, but from the outside, the
> > function _was_
> > functionally pure.
>
> If it didn't return the memory allocated with new and if the call to new resulted in an exception, yes.
>
> > It just didn't work.
>
> That I question. A pure function ( http://en.wikipedia.org/wiki/Pure_function ) depends on the values of the parameters, and only that. That is most useful. Those value can be very complex. You could have a pure member function look up values in a cache. Then the configuration of entire cache is the value.
>
> You need to think about this in terms of pre/post conditions in Hoare Logic (which I am not very good at btw).
>
>
> > So, Don introduced the idea of "weak" purity. What it comes
> > down to is that
> > it's an extension of the concept that mutation within a pure
> > function is fine
> > just so long as its arguments aren't mutated. We made it so
> > that pure
> > functions _didn't_ have to have immutable parameters. They just
> > couldn't
> > access anything that wasn't passed to them as arguments. This
> > meant that they
> > could only mutate what they were given and thus they didn't
> > violate the
> > "strong" purity of the original pure function which had
> > immutable parameters.
>
> And that's fine as long as nobody else is holding a reference to those mutable parameters.

That would only matter if the compiler were trying to optimize based on pure functions with mutable parameters. It doesn't. And it would actually be very difficult for it to do so without doing full program optimization, which really doesn't work with the C linking model that D uses. The fact that we have thread-local by default helps, but it's not enough for more than very simple cases.

The compiler doesn't care about optimizing weakly pure functions. The whole purpose of weakly pure functions is to have functions which aren't functionally pure but can still be used in functions that _are_ functionally pure.

> If you think in terms of a context for purity such as a transaction then you can even allow access to globals as long as they remain constant until the transaction is committed (or you leave the context where purity is desired). Meaning, you can memoize within that context.

That doesn't work with D's model, because it doesn't have any concept of transactions like that. It also doesn't really have any concept of memoization either. The most that it does that is anything like memoizaton is optimize away multiple calls to a function within a single expression (or maybe within a statement - I don't remember which). So,

auto y = sqrt(x) * sqrt(x);

might become something more like

auto temp = sqrt(x);
y = x * x;

but after that, the result of sqrt(x) is forgotten. So, in reality, the optimization gains from strongly pure functions are pretty minimal (almost non-existent really). If we were willing to do code flow analysis, we could probably make more optimizations (assuming that the exact same function call was made several times within a single function, which isn't all that common anyway), but Walter is generally against doing code flow analysis in the compiler due to the complications that it adds. We have some, but not a lot.

The two main gains for purity are

1. being able to know for sure that a function doesn't access any global
   variables, which makes it easier to reason about the code.

2. being able to implicitly convert types to and from mutable, const, and
   immutable based on the knowledge that a particular value has to be unique.

I'd say that functional purity was really the original goal of adding pure to the language, but it's really those two effects which have given us the most benefit. #2 in particular was unexpected, and the compiler devs keep finding new places that they can take advantage of it, which makes dealing with immutable a lot more pleasant - particularly when it comes to creating immutable objects that require mutation in order to be initialized properly.

> > functions that called it), but we do need that guarantee. The
> > result is that
> > the pure attribute doesn't in and of itself mean functional
> > purity anymore,
> > but it _can_ be used to build a function which is functionally
> > pure.
>
> But, that can be deduced by the compiler, so what is the point of having "pure" for "weakly pure"? Clearly you only need to specify "strongly pure"?

It can't be deduced from the signature, and the compiler has to be able to know based only on the signature, because it doesn't necessarily have the source code for the function available. The only functions for which the compiler ever deduces anything from their bodies are templated functions, because it always has their bodies, and if it didn't do the attribute inference for you, you'd be forced to either restrict the function by marking it (or not marking it) with a particular set of attributes, or you'd have to duplicate the function for each combination of attributes that you wanted.

So, when you mark a function as pure, the compiler verifies that it's pure based on its body, but when other functions use it, all they know or care about is the signature of the function. So, it's up to the programmer to tell the compiler that a function is supposed to be pure, and it's up to the compiler to verify that, and then use that knowledge to infer other things based purely on the signature (like functional purity or the ability to implicitly convert a type to the same type but with different mutability).

> Ok, but maybe the opposite would be better. Marking functions that access globals with @global or something. After all, most functions don't access globals.

I agree that that would be great if we were starting over - just like it would be great if @safe were the default, but it's too late now. We have to make do with what we have. We can make backwards-compatible changes, but we're very much trying to minimize breaking changes at this point. We'll still make them if we really think that they're needed, but we really want to avoid it. And as nice as changing some of the attributes around would be nice, it's too big a breaking change for too little gain.

- Jonathan M Davis