Persistent list

[Steven Schveighoffer via Digitalmars-d]

On 11/16/15 3:48 PM, Andrei Alexandrescu wrote:

>
> I think the main problem is the difficulty of getting from "I want to
> make this method work with mutable and nonconst data" to "I have a
> working solution using inout".

Again, it's not that hard. I have had little trouble with using it 
instead of const where it is appropriate. There are a couple rough 
edges, but you haven't hit them yet.

>
> The semantics is complex and difficult. Error messages are horrifying.
> Even explaining code that works is hard. Once a solution works, trying
> to change it in meaningful ways again makes the code not work, and again
> with uninformative error messages. So there's resistance to changing
> working code.

I just did the naive thing and slapped inout on your functions. This is 
what I got:

persistent_list2.d(146): Error: cannot implicitly convert expression (( 
List!(immutable(int)) __slList1681 = List(null, null);
  , __slList1681).this(n, this.allocator())) of type 
List!(immutable(int)) to inout(List!(immutable(int)))

WTF!

This is not how it used to be. What the hell is __slList1681? And what 
is List(null, null)?

This has to be some sort of lowering that was added to the compiler, I 
have never seen such horrible messages for inout. How it should look:

Error: cannot implicitly convert expression List(n, allocator) of type 
List!(immutable(int)) to inout(List!(immutable(int)))

Note, this is not an inout problem. If I put immutable(List) as the 
return type, I get:

persistent_list2.d(146): Error: cannot implicitly convert expression (( 
List!(immutable(int)) __slList1681 = List(null, null);
  , __slList1681).this(n, this.allocator())) of type 
List!(immutable(int)) to immutable(List!(immutable(int)))

We can and should fix this. I'll file an issue if none has been filed.

> At the same time, we have a wonderful language ready to help with
> features that didn't exist when we introduced inout. Search
> http://dpaste.dzfl.pl/52a3013efe34 for QList - it's restricted properly,
> works very well, and is easy to explain.

Actually, it's not easier to explain or maintain, and the solution 
existed before inout was introduced (in fact one of the reasons *to* use 
inout was to avoid QList-like solutions).

Example:

static QList cons(QList)(T head, auto ref QList lst)
     if (is(Unqual!QList == List))

Tell me how cons guarantees not to modify lst? Is it convention or 
compiler guarantees? find the bug:

static QList cons(QList)(T head, auto ref QList lst)
     if (is(Unqual!QList == List))
{
List result;
result._allocator = either(lst.allocator, theAllocator);
import std.conv : emplace;
void[] buf = result.allocator.allocate(Node.sizeof);
auto n = emplace!(const Node)(buf, head, lst.root, 1);
incRef(lst.root);
result.root = n;
static if(!is(QList == const)) lst.root = lst.root.next;
return result;
}

The point of const is to provide a mechanism to those reading the 
signature to say "this function will NOT change the parameter, and the 
compiler guarantees it."

I remember reading originally why Walter put const into the language -- 
because C++ developers who used const extensively to provide guarantees 
simply wouldn't use D if it didn't provide a mechanism to do this. I 
don't recall the exact wording, but I'm sure it's somewhere in the ng.

The point of inout was to provide what const does, but allow you to hook 
the output const flavor to the input const flavor. That's all.

> Walter and I think inout didn't turn out well. It became a little
> monster mastering a swamp. Template solutions can drain that swamp, make
> the monster disappear, and build nice things on that field.

I disagree, and appeals to authority is not very convincing, no matter 
how colorful. I think inout works great for what it's good at. It has 
some finishing to do, but the concept is sound and works fine. It's a 
perfect fit for containers in general. In this particular case it's not 
necessary.

We absolutely should fix the error messages, they are not very helpful.

> I think we should slowly marginalize inout - discourage it from new
> code, document and publicize better alternatives, the works.

Because we have a poor error message? I can assure you this is not 
endemic to inout.

>> In this case, it appears to work only because of your cast of _allocator
>> to mutable whenever you access it via allocator. Other than that, the
>> only other member is the node pointer, which is const. Effectively, A
>> list's data is always const, so there is no reason to make the struct
>> itself const.
>
> Plenty of reason. The list may be member in an object. Also, if you
> don't have const List you can't compose List with itself.

Huh? Mutable List casts to const List just fine. If I always return a 
mutable List from a composing operation, then it works for const List as 
well (both as the receiver of the return value and as the parameter).

What I meant to say is that a const(List) isn't particularly needed to 
guard the List's data. That is already const.

-Steve