Persistent list

[Timon Gehr via Digitalmars-d]

On 11/14/2015 11:37 PM, Andrei Alexandrescu wrote:
> On 11/14/2015 05:04 PM, Timon Gehr wrote:
>> We have had the discussion you are asking for before, and you have
>> decided to ignore it, with the justification that this was how you
>> decided and a vague appeal to emotion. I usually don't operate under
>> the assumption that identical experiments lead to different outcomes
>> without a good reason.
>
> Yah, of course I remember that discussion. Thing is I remained
> unconvinced after said discussion.
>
> There's no technical argument being made here. It's a judgment call.
>
> Clearly allowing List!int with the same codebase as
> http://dpaste.dzfl.pl/0981640c2835 is possible, and it would allow a
> number of additional uses at the cost of somewhat murky semantics (that
> list is not a value and not a reference; defining other containers with
> similar semantics is tricky).
>
> But there's a distinct possibility: List!(immutable int) is
> indistinguishable from a value type - each value is independent from all
> others, up to taking address of elements in the list.
>
> So what we could do is define List!int to implement value semantics with
> a completely different implementation - COW.

How to implement COW without support for writing?

> That's a very appealing
> equation for the user: "List!T is always a value regardless of T."
> Optimizations apply depending on T, but that's transparent and the user
> doesn't need to care. A List!T is a value. Boom. Done.
> ...

It is awesome if List!T acts like a value type. More precisely, like a 
struct. That in particular means its elements should not always need to 
be transitively immutable.

> Per what you propose, we'd have "List!T is a Lisp-style list.  It has
> cons cells and atoms, and cons(head, list) creates a new list that
> shares its tail with list." etc.
> ...

It's not precisely what I want, but it is a way to get close. Ideal 
semantics would be that List!T is a value type with (by default, unless 
qualified immutable) mutable slots, much like what you get for structs. 
Now the problem is just that D does not support expressing this. 
Allowing mutable reference access is the next most obvious viable thing, 
but maybe we can find another way to get close to the right semantics. 
(I guess we might never support mutating method calls on elements in the 
best fashion possible though.)

> You seem to assert there's no contest, and anyone choosing (1) over (2)
> is seriously incompetent.

There's no contest because there shouldn't need to be a mandated choice. 
Categorically choosing (2) over (1) is not the right course of action 
either. (And (2) is already a suboptimal compromise!)

> I seem to think there is a real choice there,
> and I want to keep it open for the time being. Is this reasonable?
> ...

This is reasonable enough. It's not what "I've decided persistent lists 
with mutable elements just too weird to endorse" communicates though. I 
think it is clear what can be done next time (on both sides) to avoid an 
unproductive subthread like this one.

>> Maybe not, but what is? It can't be laying down a well-reasoned
>> argument, because as recent history shows it will just be ignored
>> without a reasonable justification.
>>
>> I guess one other good way to proceed would be to just not have the
>> dialog for now and instead wait until people who are actually trying
>> to use the containers start complaining in blog posts and on reddit.
>>
>> Feel free to voice any better suggestions you may have.
>
> One interesting problem Walter and I have as leaders of this community
> is to attract within the core circle people who are literally better
> than ourselves. People whom we can trust with using good judgment in
> complex situation and can lead themselves entire features and parts of
> the language (such as compiler-supported RC etc).
>
> Amaury and you (Timon) may as well be the smartest people hanging out in
> this forum. You both are also very generous with your time. I can't talk
> for Walter, but for all I can tell you two are better than I'll ever be
> at all metrics that matter to language design. The challenge, then,
> becomes in convincing you to put that good expertise and good will
> toward something positive; because, to be blunt, a large chunk of your
> and Amaury's energy is dedicated to picking fights and proving just what
> chowderheads Walter and I are for not doing as you say.
>
> I'm very happy to admit - you're a whole lot better than myself. So
> let's do something constructive.
>...

That's flattering, thanks! But it was not my intention to pick a fight. 
It is just that for my current project, persistent data structures would 
be a great option to have. However, the data structures would be  close 
to useless to me if they were to mandate transitive immutability, and 
mirroring them manually is a PITA.