On 06/19/2015 03:21 PM, Andrei Alexandrescu wrote:
> 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?

What Scala does.

scala> class C { var x:Int=0 }
defined class C

scala> val s = (Range(0,10) map { _ => new C }).toSet
s: scala.collection.immutable.Set[C] = Set(C@f35b47c, C@741d171e, C@688a3052, C@43529d91, C@4b564e68, C@21d8ee20, C@165f3028, C@64e6bd1e, C@486a8d1c, C@28f9883c)

scala> for(x <- s) print(x.x)
0000000000
scala> for(x <- s) x.x += 1

scala> for(x <- s) print(x.x)
1111111111


Note that I cannot change the set in-place.

The memory allocated by the persistent data structure should not be exposed, but if mutable references are stored in the structure, it should be possible to mutate the data those references refer to after the references have been obtained from (rvalue) front.

If the stored data is to be further constrained, we do have type modifiers to signify it, but it is not the library's job to constrain the design space artificially.

On 06/19/2015 03:31 PM, Andrei Alexandrescu wrote:
>> 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.

I think this would be a pointless assertion though.

What makes persistent data structures useful is that they provide _value semantics_ for complex data types with _O(1)_ copies and fast updates. (COW has only the first two of those.)

Even in-place mutation should be allowed (e.g insert an element into a set, remove an element from a set), as long as value semantics is preserved. Scala also does this:

scala> var t = s
t: scala.collection.immutable.Set[C] = Set(C@f35b47c, C@741d171e, C@688a3052, C@43529d91, C@4b564e68, C@21d8ee20, C@165f3028, C@64e6bd1e, C@486a8d1c, C@28f9883c)

scala> t.size
res10: Int = 10

scala> t+=new C

scala> t
res7: scala.collection.immutable.Set[C] = Set(C@f35b47c, C@28c1b86, C@741d171e, C@688a3052, C@43529d91, C@4b564e68, C@21d8ee20, C@165f3028, C@64e6bd1e, C@486a8d1c, C@28f9883c)

scala> t.size
res10: Int = 11

scala> t+=new C

scala> t.size
res12: Int = 12

Similarly, it is no problem to allow reassigning the front of a persistent list, as long as in the background, a new node is allocated for the new head, that points to the same tail.

Reference counting is actually quite neat here, because if the reference count is 1, updates can be performed in-place transparently as an optimization.

On 06/19/2015 05:27 PM, Andrei Alexandrescu wrote:
> On 6/19/15 8:01 AM, "Ulrich =?UTF-8?B?S8O8dHRsZXIi?=
> <kuettler@gmail.com>" wrote:
>> If opAssign is allowed, a major point of functional data structures is
>> lost. Client code is so much better if rebinding is off the table.
>
> I have the same instinct but not enough rationale. What would be an
> example in favor of the argument?

I think he is just arguing for immutable by default. The obvious counter-argument is: Show me the implementation of the 'length(T)(SList!T)' function for SList!T with disabled opAssign.

On 06/19/2015 11:37 PM, Timon Gehr wrote:
> On 06/19/2015 05:27 PM, Andrei Alexandrescu wrote:
>> On 6/19/15 8:01 AM, "Ulrich =?UTF-8?B?S8O8dHRsZXIi?=
>> <kuettler@gmail.com>" wrote:
>>> If opAssign is allowed, a major point of functional data structures is
>>> lost. Client code is so much better if rebinding is off the table.
>>
>> I have the same instinct but not enough rationale. What would be an
>> example in favor of the argument?
>
> I think he is just arguing for immutable by default. The obvious
> counter-argument is: Show me the implementation of the
> 'length(T)(SList!T)' function for SList!T with disabled opAssign.

Bad example, you'd just use the range, I guess. :o)
Append?

On 6/19/15 2:44 PM, Timon Gehr wrote:
> On 06/19/2015 11:37 PM, Timon Gehr wrote:
>> On 06/19/2015 05:27 PM, Andrei Alexandrescu wrote:
>>> On 6/19/15 8:01 AM, "Ulrich =?UTF-8?B?S8O8dHRsZXIi?=
>>> <kuettler@gmail.com>" wrote:
>>>> If opAssign is allowed, a major point of functional data structures is
>>>> lost. Client code is so much better if rebinding is off the table.
>>>
>>> I have the same instinct but not enough rationale. What would be an
>>> example in favor of the argument?
>>
>> I think he is just arguing for immutable by default. The obvious
>> counter-argument is: Show me the implementation of the
>> 'length(T)(SList!T)' function for SList!T with disabled opAssign.
>
> Bad example, you'd just use the range, I guess. :o)
> Append?

Appending to a functional singly-linked list would necessitate wholesale duplication, whether or not the list has mutable elements. Indeed if the reference count is 1 for _all_ elements in the list, there's no need for copying. That takes O(n) time to evaluate, but walking through to the end of the list is needed anyway.

But that's due to the topology of the list. You can append to a slice of immutable objects no problem (we do that with strings all the time).

I still am confused as to where your vision aims; I'll reply to your other message.


Andrei

On 6/19/15 2:23 PM, Timon Gehr wrote:
> What makes persistent data structures useful is that they provide _value
> semantics_ for complex data types with _O(1)_ copies and fast updates.
> (COW has only the first two of those.)

OK, so SList!int should allow mutating individual values, and SList!(immutable int) shouldn't? Or does that apply only to objects with indirections?

Also, what bearing does this have on deciding whether an SList is rebindable or not?


Andrei

On 06/20/2015 12:24 AM, Andrei Alexandrescu wrote:
> On 6/19/15 2:44 PM, Timon Gehr wrote:
>> On 06/19/2015 11:37 PM, Timon Gehr wrote:
>>> On 06/19/2015 05:27 PM, Andrei Alexandrescu wrote:
>>>> On 6/19/15 8:01 AM, "Ulrich =?UTF-8?B?S8O8dHRsZXIi?=
>>>> <kuettler@gmail.com>" wrote:
>>>>> If opAssign is allowed, a major point of functional data structures is
>>>>> lost. Client code is so much better if rebinding is off the table.
>>>>
>>>> I have the same instinct but not enough rationale. What would be an
>>>> example in favor of the argument?
>>>
>>> I think he is just arguing for immutable by default. The obvious
>>> counter-argument is: Show me the implementation of the
>>> 'length(T)(SList!T)' function for SList!T with disabled opAssign.
>>
>> Bad example, you'd just use the range, I guess. :o)
>> Append?
>
> Appending to a functional singly-linked list would necessitate wholesale
> duplication,

Sorry, I wasn't clear enough, I meant append a list to a list, i.e. concatenation. Then you only need to duplicate the first list, and runtime is linear in the first list.

What I was getting at is that if things are not rebindable, you are left with recursive functions as the natural iteration primitive, which you have objected to in the past.

> ...
>
> I still am confused as to where your vision aims; I'll reply to your
> other message.
> ...

I am still similarly confused why non-rebindability is even considered.

On 06/20/2015 12:36 AM, Andrei Alexandrescu wrote:
> On 6/19/15 2:23 PM, Timon Gehr wrote:
>> What makes persistent data structures useful is that they provide _value
>> semantics_ for complex data types with _O(1)_ copies and fast updates.
>> (COW has only the first two of those.)
>
> OK, so SList!int should allow mutating individual values, and
> SList!(immutable int) shouldn't? Or does that apply only to objects with
> indirections?
>
> Also, what bearing does this have on deciding whether an SList is
> rebindable or not?
> ...

Rebindability is orthogonal to the functionality. They shouldn't be tied.

E.g., one should not have to jump through hoops when translating code that uses ephemeral data structures with O(N) duplications to persistent data structures with O(1) duplications.

On 06/20/2015 12:36 AM, Andrei Alexandrescu wrote:
> On 6/19/15 2:23 PM, Timon Gehr wrote:
>> What makes persistent data structures useful is that they provide _value
>> semantics_ for complex data types with _O(1)_ copies and fast updates.
>> (COW has only the first two of those.)
>
> OK, so SList!int should allow mutating individual values, and
> SList!(immutable int) shouldn't? Or does that apply only to objects with
> indirections?

Forgot to answer to this.

E.g:

struct ListInt6{int front,b,c,d,e,f; }

auto x = ListInt6(1,2,3,4,5,6);
auto y = x;
x.front = 2;
assert(x.front==2);
assert(y.front==1); // value semantics


auto x = SList!int(1,2,3,4,5,6);
auto y = x;

x.front=2;
assert(x.front==2);
assert(y.front==1); // value semantics

It is not absolutely crucial that this works, but then, why shouldn't it work? It works for structs.