Persistent list

[Andrei Alexandrescu via Digitalmars-d]

I created a simple persistent list with reference counting and custom 
allocation at http://dpaste.dzfl.pl/0981640c2835. It's a good 
illustration of a number of issues. In particular, each cast must be 
properly explained.

Here's my exegesis:

* Lines 6: By construction the list doesn't work with mutable objects. 
This is because it uses sharing internally (in the classic manner of 
functional containers) to give the illusion of many copies.

* Lines 11-12: I came to terms with the notion that some types cannot be 
made immutable. We've been trying to do reference counting on immutable 
objects for a long time. It's time to acknowledge that true immutability 
(which the immutable keyword models) and reference counting don't mix. 
Const does work (more below). But overall I'm at peace with the notion 
that if you can't live without immutable, I'll refer you to the garbage 
collector.

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

* Line 35: the constness of the Node is taken away before deallocation. 
This is acceptable.

* Lines 40, 46: same matter as with the allocator - the reference count 
is a mutable part of a possibly const object.

* Line 65: deallocation again is allowed to cast things, even in safe 
code; the point here is we know we can do something the type system 
doesn't know.

* Lines 104-112: using recursion in the construction of objects with 
const parts is, I think, a major emerging idiom in D.

* Lines 141-152: I couldn't make tail() work with inout. Generally I'm 
very unhappy about inout. I don't know how to use it. Everything I read 
about it is extremely complicated compared to its power. I wish we 
removed it from the language and replaced it with an understandable idiom.

* Lines 161-185: Same problem: inout.

* Lines 191-199: Same problem: inout.

* Lines 208-259: I made inout work for getting the range of the list.

Please reply with improvements, ideas, comments, and such. Thanks!


Andrei