Memory allocation purity

[luka8088 via Digitalmars-d]

On 15.5.2014. 12:48, Don wrote:
> 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.
> 

Ok. Now it is much clearer, thanks.