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

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?

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

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.

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

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

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.

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

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

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