Memory allocation purity

[Don via Digitalmars-d]

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