Store mutable indirections in immutable data with this one weird trick!

[Paul Backus]

On Saturday, 13 November 2021 at 13:11:05 UTC, Timon Gehr wrote:
> On 13.11.21 13:42, Paul Backus wrote:
>> 
>> I guess this is what we get for trying to make memory 
>> allocation count as "pure."
>
> How else are you going to represent your values? I really don't 
> get this trend of questioning whether memory allocation should 
> be `pure`. I think it may be caused by thinking at the wrong 
> level of abstraction.

In a language where valid programs cannot distinguish between 
different pointers to the same value, or observe the side effects 
of memory allocation, it is natural to define `pure` such that it 
allows memory allocation.

D is not that kind of language. A valid D program can very easily 
distinguish between different pointers to the same value, and 
observe the side effects of memory allocation. In a language like 
D, defining `pure` such that it allows memory allocation means 
that (a) you can't, in general, assume a strongly-pure function 
has no observable side effects and is referentially transparent 
[1], which makes `pure` less useful for static analysis and 
optimization; and (b) some functions that do have no observable 
side effects and are referentially transparent nevertheless 
cannot be `pure`, which is weird and unintuitive.

[1] Actually, the spec says that the compiler is allowed to 
assume referential transparency anyway, which turns this from an 
unfortunate limitation into a loaded foot-gun.