On 06/19/2015 04:24 AM, Andrei Alexandrescu wrote:
> On 6/18/15 6:26 PM, ZombineDev wrote:
>> On Friday, 19 June 2015 at 01:07:10 UTC, ZombineDev wrote:
>>> On Thursday, 18 June 2015 at 23:32:03 UTC, Andrei Alexandrescu wrote:
>>> [..]
>>
>> I also noticed that the `front` primitive returns only `const ref`
>> (instead of `inout ref`). Is this because the user should regard the
>> SList as immutable - i.e. if you want to change an element, you have to
>> make the modification in a copy of the list, instead of doing it inplace?
>
> Yah, traditionally functional data structures don't allow their clients
> to mutate the data AND the topology of the container. So front() returns
> a non-mutable ref.
>
> It might be interesting to explore containers that allow mutation of
> data but not of topology. We may collectively think of a few
> applications of that. For now I went the traditional route.
> ...

That's not the issue. The data held by the structure shouldn't be mutated, since it is persistent. Returning const(T) means that the data that the return value refers to may not be mutated. This is crippling.

BTW: sharing of structure between instances is the main motivation for persistent data structures. opAssign shouldn't move.
(opAssign should never move, assignment is not the same as a move.)

On 06/19/2015 04:21 AM, Andrei Alexandrescu wrote:
> ...
> functional.SList should have empty but not popFront. The latter is
> mutating.
> ...
> The first won, partly because it's easier to implement efficiently. So
> now we have this one mutating operation that we need to mind. Because of
> it, we'll need functional containers to be distinct from their ranges.
> ...

This is one reason why I dislike the term "functional" in this context, it implies unnecessary baggage. popFront does not affect any other references to the same data, so why is there any problem with it?

>> * It's strange that the copy-constructor `this(this)` has reference
>> semantics (it adds reference to the list) and the assign-operator
>> (opAssign) has move semantics (it steals the contents of the victim on
>> assignment).
>> Edit: actually because Slist is a struct this line doesn't do anything
>> to the moved from list: http://dpaste.dzfl.pl/06e24fecd2da#line-93 ,
>> though to the comment in the function is a bit disorienting.
>
> Yah, there's a little trick there that deserves an explanation -
> opAssign takes a SList by value, so the reference counting has already
> occurred at the caller side. So there's no extra need to do that, just
> move from it and leave it empty.
> ...

Oh. Well, disregard my comment about the moving, got distracted by the comment as well. BTW: opAssign does not copy the allocator.

>> * In a couple of places like this:
>> http://dpaste.dzfl.pl/06e24fecd2da#line-181
>> you assert that the list is non-empty. Why don't you instead use in
>> contracts?
>
> Well, it's briefer...
>...

And "wrong".

Should default construction be disabled? A default constructed SList doesn't have an allocator...

A couple of thoughts:

1. It seems that an allocator is a public field of SList. Should it be so? What happens if someone changes an allocator while the list holds nodes allocated with the old one?

2. Only dynamic allocator customisation is supported (unlike C++ containers). Is
this deliberate?

3. Shouldn't `front` functions be const?

On Thu, Jun 18, 2015 at 04:32:05PM -0700, Andrei Alexandrescu wrote:
> First pass illustrating the basic data layout:
> 
> http://dpaste.dzfl.pl/0d4a589ad6f5
> 
> Code is obviously barebones but passes tests and works with allocators.
> 
> Notes:
> 
> * I managed to not store one allocator per node, but there's one allocator per range. That's needed if we want "orphan ranges" to work, i.e. ranges that survive the list they came from. This is a clasic convenience vs. efficiency thing.
> 
> * There's a refcount per node because any given node may belong to multiple lists.
> 
> * Refcounting is interesting because many nodes are only used by the previous node. So destroying a list is... funny. Never saw or wrote code like this previously. See nukeTransitively.
> 
> All in all things seem convex. Please destroy appropriately.
> 
> 
> Thanks,
> 
> Andrei

On 6/19/15 2:28 AM, Timon Gehr wrote:
> That's not the issue. The data held by the structure shouldn't be
> mutated, since it is persistent. Returning const(T) means that the data
> that the return value refers to may not be mutated. This is crippling.

I don't understand. So what should be done here?

> BTW: sharing of structure between instances is the main motivation for
> persistent data structures. opAssign shouldn't move.
> (opAssign should never move, assignment is not the same as a move.)

This is a confusion - opAssign doesn't really move. (It moves from an rvalue.) Try it out - it does what one would expect it to do.


Andrei

On 6/19/15 2:36 AM, Timon Gehr wrote:
> On 06/19/2015 04:21 AM, Andrei Alexandrescu wrote:
>> ...
>> functional.SList should have empty but not popFront. The latter is
>> mutating.
>> ...
>> The first won, partly because it's easier to implement efficiently. So
>> now we have this one mutating operation that we need to mind. Because of
>> it, we'll need functional containers to be distinct from their ranges.
>> ...
>
> This is one reason why I dislike the term "functional" in this context,
> it implies unnecessary baggage. popFront does not affect any other
> references to the same data, so why is there any problem with it?

Well this is a good discussion to have: should we allow rebinding (i.e. assignment) of functional data structures or not?

For a good part of the day I've had this:

@disable void opAssign(SList);

i.e. once an SList is constructed, it'll always contain the same data. If you need a modified list, you create another one. This is how traditionally matters are handled in functional programming.

Later in the day I relaxed matters so assignment is allowed, provided that other variables referring to (parts of) the same list are left untouched. So I defined opAssign. With that, there's a possibility to write r = r.tail, which is the moral equivalent of popFront.

So yes, if opAssign is allowed, popFront may be allowed as well. Some may say it's another step on a slippery slope though.

> comment as well. BTW: opAssign does not copy the allocator.

Fixed, thanks.


Andrei

On 6/19/15 4:06 AM, "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm@gmx.net>" wrote:
> Should default construction be disabled? A default constructed SList
> doesn't have an allocator...

I think that should be fine - an empty list doesn't need one, either. -- Andrei

On 6/19/15 4:51 AM, Ivan Timokhin wrote:
> A couple of thoughts:
>
> 1. It seems that an allocator is a public field of SList. Should it be so? What
> happens if someone changes an allocator while the list holds nodes allocated
> with the old one?

Good point. Made private.

> 2. Only dynamic allocator customisation is supported (unlike C++ containers). Is
> this deliberate?

Yes; I think C++'s approach to allocators didn't go over well, and part of the problem (though not all) is that allocators are associated with the type they allocate.

> 3. Shouldn't `front` functions be const?

Good point. Made const.


Andrei

On 6/19/15 6:31 AM, Andrei Alexandrescu wrote:
> @disable void opAssign(SList);
>
> i.e. once an SList is constructed, it'll always contain the same data.
> If you need a modified list, you create another one.

Eh, I was unclear here. What I meant:

i.e. once a variable of type SList is constructed, it'll always contain the same data. If you need a modified list, you create another variable.


Andrei

On Friday, 19 June 2015 at 13:36:22 UTC, Andrei Alexandrescu wrote:
>> 3. Shouldn't `front` functions be const?
>
> Good point. Made const.

That's not necessarily a good idea. What if the element type can't even be used when it's const? inout might work in that case, but in general, you have to be _very_ careful with slapping const on generic code.

- Jonathan M Davis