output ranges: by ref or by value?

[Andrei Alexandrescu]

Steven Schveighoffer wrote:
> On Sun, 03 Jan 2010 00:49:08 -0500, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org> wrote:
> 
>> Steven Schveighoffer wrote:
>>> My theory is, given this list of ranges, if you pair them with an 
>>> algorithm that requires save capability, you wouldn't want to use 
>>> that algorithm on it anyways (kinda like the consume example).
>>
>> Why gratuitously limit the design? You're asking to replace this:
>>
>> R save() { return this; }
>>
>> with:
>>
>> enum thisIsAForwardRange = true;
>>
>> Is there a reason? The former leaves in flexibility. The latter 
>> doesn't, for no good reason.
> 
> Well, one thing you could do is:
> 
> enum thisIsAnInputRange = true;
> 
> and then no special implementation is needed for normal forward ranges.  
> the other point is there is no special treatment needed inside 
> algorithms -- the risk of forgetting to use save at the right points of 
> the algorithm is higher than forgetting to say isForwardRange!(R) at the 
> beginning of the function.

isForwardRange will be defined to yield true if and only if the range 
defines save. But I see you point - user code only asserts 
isForwardRange and then does not bother to use save(), just copies stuff 
around in confidence that copying does the right thing.

Thanks for this insight. I don't see how to reconcile that with class 
ranges and covariance.

> Not having opSlice be part of the interface itself does not preclude it 
> from implementing opSlice, and does not preclude using ranges of it in 
> std.algorithm.  If I'm not mistaken, all functions in std.algorithm rely 
> on compile time interfaces.  opApply allows for full input range 
> functionality for things like copying and outputting where templates may 
> not be desired.

The point is how much container-independent code can someone write by 
using the Container interface. If all you have is a Container, you can't 
use it with any range algorithm.

>>> BTW, the primitives in dcollections are:
>>>  clear(); // clear all elements
>>> remove(V v); // remove an element
>>
>> Search and remove? That's an odd primitive. Why wouldn't you offer an 
>> interface for iteration that allows an algorithm for search, and a 
>> primitive for positioned removal?
> 
> Search and positioned removal are also a primitives, but not defined on 
> the interface.  remove was a primitive on Tango's containers, and 
> dcollections was originally meant to be a replacement for Tango's 
> containers.
> 
> I think the point is, if you have an interface reference, what would be 
> the minimum functionality needed so that you could use a container 
> without knowing its implementation.

Yes, and I think remove(V v) does not belong to the minimum 
functionality. It combines two functions (search and remove) and raises 
questions such as what happens to duplicate elements.

>>> contains(V v); // returns whether an element is contained in the 
>>> colleciton
>>
>> I don't think this belongs to primitives. It's O(n) for many 
>> containers and again it's a generic algorithm, not a member.
> 
> Again, it's part of the minimal usable interface.  It's not a generic 
> algorithm, because some containers can implement this more efficiently.

But this is exactly what I believe to be a mistake: you are abstracting 
away algorithmic complexity.

> Plus, to use the generic algorithms, you would need to use interfaces as 
> ranges which I think are completely useless.

Why?

>>> length(); // the length of the collection
>>
>> That's not a primitive either. std.algorithm.walkLength is. For me, 
>> all sorts of red flags and alarm buzzers go off when primitives are 
>> guaranteed that can't be implemented efficiently but by a subset of 
>> containers. You can't discount complexity as a implementation detail.
> 
> All current dcollection containers have O(1) length.

Some containers can't define O(1) length conveniently.

>>> dup(); // duplicate the collection
>>> opApply(int delegate(ref V v) dg); // iterate the collection
>>> opApply(int delegate(ref bool doPurge, ref V v) dg); // purge the 
>>> collection
>>>  That means it covers only empty in your list of must-have functions 
>>> (via length() == 0).
>>
>> How do you implement length() for a singly-linked list? Is empty() 
>> going to take O(n)?
> 
> first, dcollections' list implementation is doubly linked because all 
> collections are forward and backward iterable.
> 
> second, even for singly linked lists, you can have either O(1) length or 
> O(1) splicing (consuming a link list range into another linked list).  
> Dcollections' default link list implementation uses O(1) length since I 
> think splicing is a specialized requirement.

Right. The question is how much pressure Container is putting on the 
implementation. I'd rather leave it to the list implementation to decide 
to store the length or not.

>>> Add is not a primitive because the Map collections shouldn't assign 
>>> some random key to the new element.  removeAny is defined only on 
>>> sets and multisets, but I'm not sure that it couldn't be moved to 
>>> Collection, in fact, I'll probably do that.
>>
>> add is a primitive that takes Tuple!(K, V) as the element type.
> 
> How do you define that on Container(V)?  on Map(K, V), set(K k, V v) is 
> an interface method.

Map!(K, V) has Tuple!(K, V) as its element type.

> what you can do is define Map(K, V) as inheriting Container(Tuple!(K, 
> V)), but then trying to use the container functions are very 
> cumbersome.  In dcollections, Map(K, V) inherits Collection(V).
> 
>>
>>> Note that it's missing begin and end which are defined on every 
>>> single container type (i.e. the equivalent of the all-elements 
>>> range).  This is because those primitives return a struct that is 
>>> different for every container type.
>>
>> So you can't write container-independent iteration code unless you use 
>> opApply, in which case composition becomes tenuous.
> 
> No, you can easily write container-independent iteration as long as you 
> have the implementation.

In this context: container-independent = using the Container interface. 
This is the whole purpose of creating a container hierarchy. If the 
container design fosters knowing the implementation, maybe a class 
hierarchy is not the right choice in the first place.

> If you use interfaces you can write opApply wrappers to do different 
> things.  I'm not sure what you mean by composition.

For example, compose ranges a la retro or take.

>>> It also surpasses opSlice via opApply, since all an input range can 
>>> do anyways is iterate.  In fact, opApply is more powerful because you 
>>> can change elements and remove elements (via purging).  Plus it's 
>>> more efficient than a range-via-interface.
>>
>> An input range is a subset of other (more powerful) ranges. It's also 
>> much more flexible. I agree that calling range primitives via 
>> interfaces can become an efficiency liability.
> 
> How is it more flexible?  You can't replace data, and you can't remove 
> data while iterating, both of which are possible with dcollection's 
> primitives.  If you have a Container(E) which defines InputRange!E 
> opSlice, how do you get at the more defined range definition?  casting?

You can replace data by assigning to range's elements. Removal is done 
via positioned remove (which I think needs to be a primitive).

>>>>> I see a range as being useful for iteration or algorithms, but not 
>>>>> for general use.  A great example is AAs.  Would you say that an AA 
>>>>> *is* a range or should *provide* a range?  If it is a range, does 
>>>>> that mean you remove elements as you call popFront?  Does that make 
>>>>> any sense?  If it doesn't, then what happens if you add elements 
>>>>> through another alias to that AA?
>>>>
>>>> An AA provides several ranges - among which byKey and byValue.
>>>  I misunderstood your statement "[a container hierarchy] does need 
>>> range interfaces."  I thought you meant containers themselves need to 
>>> implement the range interface, I see now that isn't the case, so my bad.
>>
>> Yah, they'd offer it as a result of opSlice(). Covariant return types 
>> will ensure there's no virtual call when you know what container you 
>> operate on.
> 
> Not having opSlice on the interface guarantees you never have a virtual 
> call for iteration :)  opApply mitigates the virtual call on the interface.

And takes away the ability to compose ranges and to use algorithms with 
the container.

>> Above all: the primitive set for a container must be a small set of 
>> functions that (a) can be implemented by all containers within 
>> reasonable efficiency bounds, and (b) are container-specific, not 
>> generic. IMHO any container design that defines a search(Element) as a 
>> primitive is misguided. Searching is not a container primitive - it's 
>> an algorithm. Only more specialized containers (e.g. trees, hashes 
>> etc.) can afford to define search(Element) as a primitive. Linear 
>> search is a generic algorithm that works the same for everyone. It 
>> does not belong as a method of any container.
> 
> If the minimal container design isn't usable without std.algorithm, then 
> I don't think it's worth having interfaces.

Why?

I think the other way: if the minimal container design is unusable with 
std.algorithm, the design took a wrong turn somewhere.

> If you need std.algorithm, 
> you need the full implementation of the container because it's a 
> compile-time interface.

How did you reach that conclusion? std.algorithm uses a syntactic 
interface that is obeyed by interfaces too. There's no problem.

> Interface ranges are something that should be 
> avoided, it's like having a programming language where everything has to 
> be a class.

I disagree. The negation of an implementation dogma can be just as 
limiting as the dogma. The way I see it, a design defines some 
desiderata. Then it does whatever it takes to fulfill them.

If one desideratum is to use a class hierachy to write 
container-independent code, then interface ranges naturally follow. 
There's no ifs and buts about it.

> What you are saying seems completely incorrect to me: "since not all 
> containers can implement fast search, I'm going to guarantee that *all* 
> containers use a linear search via their interface.

This is a misunderstanding. In the STL linear containers don't define 
find(), but associative containers do. That is the correct design.

> *AND* I want to 
> make each loop in the search algorithm call 3 virtual functions!"

Not necessarily. This happens only if you use the Container interface to 
write container-independent code. It is the cost it takes for the design 
to fulfill its desiderata.

> How 
> is that better than a search function that guarantees linear performance 
> but gives the option of being as fast as possible with no loop virtual 
> calls?

It is better because it doesn't write off search complexity as an 
implementation detail. "Linear or better" is not a good guarantee. A 
good guarantee is "From this node of the hierarchy down, this primitive 
is defined to guarantee O(log n) search". Linear search is a generic 
algorithm and does not belong to any container.


Andrei