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

On 11/13/2015 03:10 PM, Andrei Alexandrescu wrote:

> at http://dpaste.dzfl.pl/0981640c2835

> * Lines 11-12: I came to terms with the notion that some types cannot be
> made immutable.

Could constructor qualifiers help in such cases? I would like to hear war stories and experiences from others who used that feature before:

The spec:

  http://dlang.org/struct.html#struct-constructor

My rewording:


http://ddili.org/ders/d.en/special_functions.html#ix_special_functions.constructor%20qualifier

DIP53:

  http://wiki.dlang.org/DIP53

Ali

On 11/13/15 6:10 PM, Andrei Alexandrescu wrote:
> 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 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.

This seems to work for me:

        inout(List) tail() inout
	{
		assert(root);
		auto n = root.next;
		incRef(n);
		return inout(List)(n, allocator);
	}


>
> * Lines 161-185: Same problem: inout.

	inout(List) opBinaryRight(string op)(T head) inout
		if (op == "~")
	{
		auto allocator = either(allocator, theAllocator);
        import std.conv : emplace;
        void[] buf = allocator.allocate(Node.sizeof);
        auto n = emplace!(const Node)(buf, head, root, 1);
        incRef(root);
		return inout(List)(n, allocator);
    }

>
> * Lines 191-199: Same problem: inout.

Should work now that inout is valid on both the others


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

inout not necessary here, you can use const. If inout doesn't apply to the return value, I believe it devolves to straight const (not sure though).

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

Just note: anything inout is treated like it's const. You can't modify ANYTHING inside it. And since nothing casts to or from inout, when you return something that's composed via inout, it has to be done in a functional way (i.e. constructed and returned).

Here is an updated paste with inout functions:

http://dpaste.dzfl.pl/3fbc786a50c1

Two unrelated notes:

1. I've been writing swift code for the last couple weeks, and goddamn if it hasn't ruined my ability to type semicolons at the end of lines
2. I thought there was a way to clone dpastes? I had to make a new paste and then copy all the code.

-Steve

On 11/14/2015 12:10 AM, Andrei Alexandrescu wrote:
>
> * Lines 6: By construction the list doesn't work with mutable objects.

=(

On Friday, 13 November 2015 at 23:10:04 UTC, Andrei Alexandrescu wrote:
> * 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.

External reference counting should work fine with immutable, i.e. RefCounted!(immutable T).

Hmm. We can't have immutability and ref counting.
Lets just say, the only time ref counting should come into effect is IF it has been removed from the list. This way the list should consider it 'owned' by it.

This is where I say, immutability by itself isn't the problem. The problem is we are unable to attribute new behavior to another type without effecting the type system directly.

If we can add new behavior without effecting the payloads immutability, we can add e.g. ref counting as needed.

This is where my 'managed memory'[0] idea is coming into play.
In essence, managed memory would allow a mutable addition to any given heap allocated type (not including pointers).

So sure the payload is attributed as being immutable, but ref counting can still go on safely!

Of course this is a major addition and is no where near ready for DIP status, but hey, maybe a solution?

[0] http://wiki.dlang.org/User:Alphaglosined/ManagedMemory

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

On 14-Nov-2015 02:10, Andrei Alexandrescu wrote:
> 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:
[snip]
> * 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.

Just don't make it const (see your point at 11-12). I have a feeling that ref-count and allocator are in the same mold - fields that must mutate.

So I imagine const/immutable for complex types will only work like this:

struct Layout{
   immutable Core core; //all constness ends here
   // accounting fields
   uint refCount;
   UAllocator alloc;
// ... any tracing and/or stats fit this definition
}

I totally do not understand the whole knee-jerk reaction of "everything must be const because it looks good in my code" and bug reports a-la:

const obj = SomeComplexTypeFromStd(....); // doesn't compile!

Well some types can't be transitively const (w/o sacrificing functionality/performance). Low-level immutable is a tool to create high-level immutable constructs IMHO.

It might make sense to re-purpose final storage class to be write-once a-la Java, because this is what folks expect when writing `immutable/const x = ...;` everywhere possible.

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

I can't agree more. Every time dealing with inout when I finally think I grok how it works the next instant I see that it doesn't do what I expect.

For me inout inevitably stops at the boundary of being unnable to have List!(inout(T)) and the like.


-- 
Dmitry Olshansky

On 11/13/2015 06:26 PM, Ali Çehreli wrote:
> On 11/13/2015 03:10 PM, Andrei Alexandrescu wrote:
>
>  > at http://dpaste.dzfl.pl/0981640c2835
>
>  > * Lines 11-12: I came to terms with the notion that some types cannot be
>  > made immutable.
>
> Could constructor qualifiers help in such cases? I would like to hear
> war stories and experiences from others who used that feature before:
>
> The spec:
>
>    http://dlang.org/struct.html#struct-constructor
>
> My rewording:
>
>
> http://ddili.org/ders/d.en/special_functions.html#ix_special_functions.constructor%20qualifier
>
>
> DIP53:
>
>    http://wiki.dlang.org/DIP53
>
> Ali

Great writeup. Constructor qualifiers are part of the larger discussion about collections, but in this case it's a deeper matter.

The code uses non-atomic ++ and -- for the refcount exactly because an immutable List cannot be constructed, so it's not shared among threads.


Andrei

On 11/13/2015 06:36 PM, Steven Schveighoffer wrote:
> On 11/13/15 6:10 PM, Andrei Alexandrescu wrote:
>> 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 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.
>
> This seems to work for me:
>
>          inout(List) tail() inout
>      {
>          assert(root);
>          auto n = root.next;
>          incRef(n);
>          return inout(List)(n, allocator);
>      }

That doesn't work for me with my unittests, I get:

persistent_list.d(154): Error: None of the overloads of '__ctor' are callable using a inout object, candidates are:
persistent_list.d(93): persistent_list.List!(immutable(int)).List.this(const(Node*) n, IAllocator a)
persistent_list.d(264): Error: template instance persistent_list.List!(immutable(int)) error instantiating

154 is the last line in the function above.


Andrei