www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.experimental.collection.functional.slist

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jun 18 2015
next sibling parent reply "JDemler" <jakob.demler stud-mail.uni-wuerzburg.de> writes:
On Thursday, 18 June 2015 at 23:32:03 UTC, 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


Before being able to compile your code i have some very basic 
questions:

1. Where can I find 'std/experimental/allocator.d'? The compiler 
seems to want it and i cannot find it in either 
https://github.com/andralex/phobos/tree/allocator/std/experimental/allocator or
https://github.com/D-Programming-Language/phobos/tree/master/std/experimental

2. What is the rationale behind a singly linked list? Or is it 
just to experiment with collections and allocators?
Jun 18 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdan.org> writes:
"JDemler" <jakob.demler stud-mail.uni-wuerzburg.de> wrote:

 On Thursday, 18 June 2015 at 23:32:03 UTC, 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


 
 Before being able to compile your code i have some very basic questions:
 
 1. Where can I find 'std/experimental/allocator.d'? The compiler seems to
 want it and i cannot find it in either
 https://github.com/andralex/phobos/tree/allocator/std/experimental/allocator or
 https://github.com/D-Programming-Language/phobos/tree/master/std/experimental


Should be around there, I'm on the phone now so can't check. It's
std/experimental/allocator/package.d


 2. What is the rationale behind a singly linked list? Or is it just to
 experiment with collections and allocators?


It's the simplest collection that's meaningful. So I chose it as proof of
concept.
Jun 18 2015
prev sibling next sibling parent reply "ZombineDev" <valid_email he.re> writes:
On Thursday, 18 June 2015 at 23:32:03 UTC, 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


It's a nice start and I like in general how easy it is to 
integrate an allocator to the design. The node ref-counting and 
disposal make this almost a classic text-book example - it's that 
easy :)

I have some comments/questions:
* I don't know if it's because this is WIP, but it also strange 
that the range has empty and popFront primitives, but the Slist 
doesn't have them.
* More over, the distinction between the SList collection and 
it's range is a bit blurry. They even have the same members. You 
have named your module
std.[..]functional.[..], which makes me wonder if you actually 
need a collection to operate with such lists. This idea reminds 
of programming lisp where operations with lists are fluid and 
everything is floating around and it just works without having to 
call collection<T>.push_back(elem); a single-time. The difference 
being that this is GC-free and with more deterministic behavior, 
but it still resembles this productivity of "just get stuff done 
and don't bother me with management".

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

* 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?
Jun 18 2015
next sibling parent "ZombineDev" <valid_email he.re> writes:
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:

 [...]


BTW, for those who want to review this, you actually don't need 
to download the forthcoming allocator modules. You can just 
replace the missing imports with this:

class IAllocator
{
	T* make(T, Args...)(Args args) { return new T(args); }
	void dispose(T)(T* toDelete) { }
}

static IAllocator theAllocator;

static this() { theAllocator = new IAllocator(); }
Jun 18 2015
prev sibling next sibling parent reply "ZombineDev" <valid_email he.re> writes:
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?
Jun 18 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.


Andrei
Jun 18 2015
next sibling parent reply "ZombineDev" <valid_email he.re> writes:
On Friday, 19 June 2015 at 02:24:35 UTC, 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:
 [..]




 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.


 Andrei


I just realized that my idea of something in between collections 
and ranges obviously comes from D's own slices/dynamic arrays :D 
(I really shouldn't be allowed to talk so late in the night :D)

So here's an idea - can we make the new functional SList (and 
probably DList) the logic counter-part of slices?

const SList!int;    // <- `const int[]` You can't mutate the 
elements,
                     // nor the topology

SList!(const(int)); // <- `const(int)[]` You can mutate the 
topology,
                     //but not the elements

ConstSList!(int);   // <- `missing head const array` You can 
mutate the elements,
                     // but not the topology

SList!(int);        // <- `int[]` Unlimited power

SList!(int) mutable_list;
mutable_list ~= 3; //change the topology in-place

const SList!(int) const_list;
const_list ~= 42; //error - can't mutate const SList
const SList!(int) concat_result = const_list ~ 42; 
//functional-style "modification"
foreach (elem; concat_result) {..} //error need mutable range, 
because of popFront()

SList!(const(int)) range = concat_result; // implicitly 
convertable
                                           // like const(int)[] <- 
const(int[])
foreach (elem; range) {..} // works


So instead of limiting the user by making `front` return const 
refs, we allow him to choose.
Jun 18 2015
parent "ZombineDev" <valid_email he.re> writes:
On Friday, 19 June 2015 at 03:10:36 UTC, ZombineDev wrote:

 [...]


In short, make SList both a range and a collection, just like the 
way arrays/slices are.
Jun 18 2015
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.)
Jun 19 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jun 19 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
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.
Jun 19 2015
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/18/15 6:07 PM, ZombineDev wrote:

 It's a nice start and I like in general how easy it is to integrate an
 allocator to the design. The node ref-counting and disposal make this
 almost a classic text-book example - it's that easy :)


Thanks for taking a look! Yah, I, too, was a tad surprised about the 
seamless dovetailing of things.


 I have some comments/questions:
 * I don't know if it's because this is WIP, but it also strange that the
 range has empty and popFront primitives, but the Slist doesn't have them.


functional.SList should have empty but not popFront. The latter is mutating.


 * More over, the distinction between the SList collection and it's range
 is a bit blurry. They even have the same members. You have named your
 module
 std.[..]functional.[..], which makes me wonder if you actually need a
 collection to operate with such lists. This idea reminds of programming
 lisp where operations with lists are fluid and everything is floating
 around and it just works without having to call
 collection<T>.push_back(elem); a single-time. The difference being that
 this is GC-free and with more deterministic behavior, but it still
 resembles this productivity of "just get stuff done and don't bother me
 with management".


Years ago when I chose the range primitives there was a choice between:

for (auto r = x[]; !r.empty; r.popFront) {
   ... use r.front ...
}

and

for (auto r = x[]; !r.empty; r = r.tail) {
   ... use r.front ...
}

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.


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


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


Andrei
Jun 18 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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".
Jun 19 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jun 19 2015
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jun 19 2015
prev sibling next sibling parent reply "Ulrich =?UTF-8?B?S8O8dHRsZXIi?= <kuettler gmail.com> writes:
On Friday, 19 June 2015 at 13:31:36 UTC, Andrei Alexandrescu 
wrote:

 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.


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. On the other hand, there is const and immutable... 
I would still prefer properly functional data structures.

In addition, is there a constructor for structural sharing, the 
complement to tail? Along those line:

this(T e, SList rhs)
{
     if (rhs.root) {
          allocator = rhs.allocator;
          root = allocator.make!Node(e, 1, rhs.root);
          ++rhs.root.count;
     }
}

This is very exciting! Properly typed efficient functional data 
structures! (In my dream, there are clojure's vector, set, map in 
D.) This is just too good.
Jun 19 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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?


 On
 the other hand, there is const and immutable... I would still prefer
 properly functional data structures.

 In addition, is there a constructor for structural sharing, the
 complement to tail? Along those line:

 this(T e, SList rhs)
 {
      if (rhs.root) {
           allocator = rhs.allocator;
           root = allocator.make!Node(e, 1, rhs.root);
           ++rhs.root.count;
      }
 }


Yah, I implemented that to be spelled as value ~ list.


 This is very exciting! Properly typed efficient functional data
 structures! (In my dream, there are clojure's vector, set, map in D.)
 This is just too good.


I can tell I'm pretty excited to hack at it.


Andrei
Jun 19 2015
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/19/15 8:27 AM, 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?


FWIW Scala's immutable containers are all assignable. -- Andrei
Jun 19 2015
parent "Ulrich =?UTF-8?B?S8O8dHRsZXIi?= <kuettler gmail.com> writes:
On Friday, 19 June 2015 at 15:55:48 UTC, Andrei Alexandrescu 
wrote:

 On 6/19/15 8:27 AM, 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?




Hard to come up with a convincing example here. Any large 
function that creates a data structure

     auto lst = SList!int(1, 2, 3);

features some non-trivial logic

     if (lst.length % 2)
     {
         lst = lst.tail();
     }

and produces whatever result

     writeln(lst);

is much simpler to reason about if the variables are all const, 
aka not assignable. The above is obviously weak. The only 
convincing argument I know of is to use a language that enforces 
immutability and experience the lift of a mental burden.

Erlang uses single assignment, a variable can only be bound once.

The obvious counter argument seems to be performance.


 FWIW Scala's immutable containers are all assignable. -- Andrei


Not knowing scala at all, to me this looks insane:

http://www.scala-lang.org/api/2.11.5/index.html#scala.collection.immutable.Vector

There is a little too much.
Jun 19 2015
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Jun 19 2015
parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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?
Jun 19 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jun 19 2015
parent Timon Gehr <timon.gehr gmx.ch> writes:
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.
Jun 19 2015
prev sibling parent reply Timon Gehr <timon.gehr gmx.ch> writes:
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.
Jun 19 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jun 19 2015
next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
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.
Jun 19 2015
prev sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
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.
Jun 19 2015
prev sibling next sibling parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
Should default construction be disabled? A default constructed 
SList doesn't have an allocator...
Jun 19 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jun 19 2015
prev sibling next sibling parent reply Ivan Timokhin <timokhin.iv gmail.com> writes:
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
Jun 19 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jun 19 2015
next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
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
Jun 19 2015
parent reply Ivan Timokhin <timokhin.iv gmail.com> writes:
On Fri, Jun 19, 2015 at 01:49:14PM +0000, Jonathan M Davis wrote:

 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


The return type was const from the beginning; see also
http://forum.dlang.org/post/mlvuh3$2du2$1 digitalmars.com
Jun 19 2015
parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Friday, 19 June 2015 at 14:19:49 UTC, Ivan Timokhin wrote:

 On Fri, Jun 19, 2015 at 01:49:14PM +0000, Jonathan M Davis 
 wrote:

 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


 The return type was const from the beginning; see also 
 http://forum.dlang.org/post/mlvuh3$2du2$1 digitalmars.com


Well, it won't work in the general case to have front returning a 
const value. There are too many types that are completely 
unusable when const. It may be that you don't want it returning 
by ref if it's not const, but const is simply way too restrictive 
to be required.

- Jonathan M Davis
Jun 19 2015
prev sibling parent reply Ivan Timokhin <timokhin.iv gmail.com> writes:
On Fri, Jun 19, 2015 at 06:36:26AM -0700, Andrei Alexandrescu wrote:

 On 6/19/15 4:51 AM, Ivan Timokhin wrote:

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


Disclaimer: my level of expertise in the field is approximately zero.

Having said that, from what I've heard, it seems that indirection and virtual
call cost can be quite noticeable with simple allocators (e.g. region
allocator). Could we have an allocator template argument that would default to
IAllocator, so that one gets all benefits of runtime binding by default, but
still can get static binding if it is required?
Jun 19 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/19/15 7:32 AM, Ivan Timokhin wrote:

 Having said that, from what I've heard, it seems that indirection and virtual
 call cost can be quite noticeable with simple allocators (e.g. region
 allocator). Could we have an allocator template argument that would default to
 IAllocator, so that one gets all benefits of runtime binding by default, but
 still can get static binding if it is required?


I think we need to pay what it takes to have a working framework. -- Andrei
Jun 19 2015
prev sibling parent reply Ivan Timokhin <timokhin.iv gmail.com> writes:
Correct me if I'm wrong, but it seems that the GC is unaware of any memory
coming from an allocator (unless it's a GCAllocator, of course), so it won't
scan it. If that's the case, that's bound to cause problems if T has
indirections.

On Thu, Jun 18, 2015 at 11:32:05PM +0000, 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
Jun 19 2015
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/19/15 1:09 PM, Ivan Timokhin wrote:

 Correct me if I'm wrong, but it seems that the GC is unaware of any memory
 coming from an allocator (unless it's a GCAllocator, of course), so it won't
 scan it. If that's the case, that's bound to cause problems if T has
 indirections.


Depends on where memory ultimately comes from. -- Andrei
Jun 19 2015