Memory allocation purity

[Peter Alexander via Digitalmars-d]

On Friday, 16 May 2014 at 00:27:34 UTC, Andrei Alexandrescu wrote:
> On 5/15/14, 2:52 PM, Timon Gehr wrote:
>> On 05/15/2014 08:03 PM, Andrei Alexandrescu wrote:
>>>>>
>>>>> Purity of allocation is frequently assumed by functional 
>>>>> languages
>>>>
>>>> Examples?
>>>
>>> cons 1 2 is equal to cons 1 2
>>> ...
>>
>> I don't see anything whose specification would need to mention
>> 'allocation'.
>
> That's the point. There's no specification of allocation - the 
> evaluator may create two lists or reuse the same, and it's all 
> transparent.
>
>>>>> because without it it would be difficult to get much work 
>>>>> done.
>>>>
>>>> Why?
>>>
>>> It's rather obvious. You've got to have the ability to create 
>>> new values
>>> in a pure functional programming language.
>>
>> This kind of operational reasoning is not essential. Of 
>> course, in
>> practice you want to evaluate expressions, but the resulting 
>> programs
>> are of the same kind as those of a non-pure language, and can 
>> do the
>> same kind of operations. There is not really a distinction to 
>> be made at
>> that level of abstraction.
>
> I'm afraid I got lost here.

I believe Timon's point is that allocation is an implementation 
detail, just like the existence of registers, memory caches, and 
the stack. Those things need not exist to perform the computation 
and as a result there is no need to assume anything about their 
purity (as far as the language is concerned, they don't exist).

D dropped the ball (perhaps) by making memory allocation real. If 
'new' was just defined to create a new object without specifying 
(directly or indirectly) that it lived in memory and had an 
address that could be compared then the allocation of memory 
would be an implementation detail invisible to the language, and 
that would allow "true" purity, and the optimisation 
opportunities that come with it.