Memory allocation purity

[Jonathan M Davis via Digitalmars-d]

On Thu, 15 May 2014 07:22:02 +0000
via Digitalmars-d <digitalmars-d at 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