Memory allocation purity

[Don via Digitalmars-d]

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