Persistent list

[Jonathan M Davis via Digitalmars-d]

On Friday, 13 November 2015 at 23:10:04 UTC, Andrei Alexandrescu 
wrote:
> * Lines 26-29: The allocator is fundamentally a mutable part of 
> the container. This is an insufficiency of our type system - we 
> can't say "this object may be constant, but this reference is 
> to a mutable part of it". We can't explain that necessity out 
> of existence, and List is part of the proof. So we need to make 
> that cast legal.
>
> One simple solution is to simply allow the cast. One more 
> involved is to define an attribute @mutable with the following 
> rules: (a) @mutable data is not affected by const; (b) if a 
> type T contains transitively any @mutable member, immutable(T) 
> is illegal. That would allow us to not need a cast in line 28.

The problem (at least with the current cast) is that D's const is 
supposed to be physical const, not logical const, and treating 
any of its parts internally as mutable violates that. When the 
const object could actually be immutable underneath, we really 
have no choice about that, because immutable needs to be physical 
const to do what it does. With immutable out of the picture, it 
becomes a more interesting question.

As it stands, the compiler can assume that a const object doesn't 
mutate if it knows that no other references to that data could 
have mutated it. In theory that's worth something but in practice 
is probably pretty much useless, since it's likely to help only 
when pure member functions are called in succession. But if we 
allow @mutable, then we'll have to ensure that the compiler never 
does any optimizations based on const when @mutable is involved 
(and possibly make it never make optimizations based on const 
anywhere since stuff like pointers and classes are can hide the 
fact that @mutable is involved).

The bigger problem is that it undermines the guarantee that const 
objects can't be mutated via a const reference, since as soon as 
a member variable is @mutable, that's circumvented. As long as 
casting away const and mutating is still undefined behavior, then 
it's only a matter of finding @mutable members, but it basically 
means that we're allowing D's const to go from physical to const 
to logical const (where the mutation isn't even actually 
guaranteed to follow the rules of logical const, since it's the 
programmer that controls it), and that's not a small thing, 
particularly in light of how much Walter prizes the compiler 
guarantees that physical const provides (and I agree that there's 
real value there).

Now, as it stands, D's const is so restrictive that certain 
idioms are just plain impossible with it. Ref-counting is the 
prime example, and your predicament with the container highlights 
another. And aside from immutable, we _can_ choose to change how 
D's const works so that it has backdoors like @mutable. And given 
how many D programmers seem to have pretty much decided that 
const is useless and shouldn't be used precisely because it's too 
restrictive, that may be exactly what we need to do. But 
regardless, we _do_ need to do it in a way that allows const to 
work properly with immutable, and disallowing immutable with 
@mutable and ensuring that the compiler doesn't make assumptions 
about const that don't jive with @mutable when it's possible that 
@mutable is involved should then make it possible for us to make 
a change to const to make it less restrictive.

So, while I don't really like the idea of putting a backdoor in 
const, I think that it's clear that we're either going to have to 
put in that backdoor, or we're going to have to disallow idioms 
like what you're trying to do with the allocator in this 
container.

- Jonathan M Davis