Revised RFC on range design for D2

[Andrei Alexandrescu]

Sergey Gromov wrote:
> Andrei Alexandrescu <SeeWebsiteForEmail at erdani.org> wrote:
>> In wake of the many excellent comments and suggestions made here, I made 
>> one more pass through the draft proposal for ranges.
>>
>> http://ssli.ee.washington.edu/~aalexand/d/tmp/std_range.html
>>
>> There are some comments in red illustrating some uncertainties (not 
>> all), and the names of the primitives have been updated. Bicycle shed 
>> galore! But don't forget to comment on the reactor as well :o).
> 
> I've got a heap of virtual sticky notes all over my monitor while 
> reading the edited version, so here they are.
> 
> *)
> done/next/head thing got even more confusing.  Range is not a process, 
> you cannot be done with it.  If you call a spade a spade, then done() is 
> actually a safe, guarded prefetch, head is, well, sort of what it claims 
> to be, and next() just relaxes done's guard.

The art is to find something that's reasonably evocative without being 
too long. I doubt safeGuardedPrefetch will fare very well, although I 
agree it's very precise. Inevitably a shorter word will also be less 
precise.

> The look ahead/fetch next approach was much more intuitive.  I don't 
> understand why you dropped it.  I remember you saying that Bill 
> convinced you it was wrong but I either missed the arguments themselves 
> or hadn't understood them.
> 
> *)
> How do you enforce noncopyable/release semantics over a range?  I don't 
> think D got any means for that.  Also if an input range is a class 
> passed by reference, will you allow it?

Walter is working on adding that feature now.

> *)
> before() is valid for a single-linked list, forward iterators should 
> support it.

This is subtle. Consider a singly-linked list that uses a Node* as a 
range. Condition for termination is p.next == null.

Now to build list.before(another) you'd have to express a fragment of a 
list, so the one-Node* representation is insufficient. You have to 
return a range with TWO Node* objects, one pointing to the beginning and 
the other to the end of the fragment.

That can be done, but it also means that the before operation is not 
closed under your Range type. You'd have to return a different Range 
type, a fatter one.

Or we could impose that all lists use fat ranges to start with. But I 
don't want that. I hate people discussing, "Oh you want a list? use 
std.slist, it's cool. But beware, if you want a really fast list you 
better do it yourself." This is a no-go because whenever you're in the 
mood of using a singly-linked list, it being lightweight is invariably 
the main concern.

So I want to write a singly-linked list that is as fast as the classic 
singly-linked list implemented by hand from first principles. If we fail 
to do so, we can as well go home. If we want to achieve that, we need to 
model the slist fundamentals properly. Part of that proper modeling is 
that slist is not closed under the "before" operation.

> *)
> You've replaced tail with toe because people may think tail could 
> contain many elements.  But it doesn't pair well with head, and besides, 
> if I split a list in the middle I'd call the halves a head and a tail 
> which form a logical pair.  Maybe you consider tip-toe, or top-toe, from 
> the top of my head? ;)

Head to toe is culturally appealing for English speakers. But tip to toe 
is also cool. Nice tip, thanks. :o)

> *)
> A typo: in Output range sample:
> 	for (; !src.done; src.head)
> should be
> 	for (; !src.done; src.next)

Fixed, thanks.

> *)
> next() is specified to return a value, but reduce() is not.  This is 
> probably a typo.  I'd prefer them both be implemented as (done(), head) 
> and (reduce(), toe) respectively, but I don't know what your intention 
> was.

Neither of next and retreat should return a value. In wake of 
constructors/destructors, we shouldn't return by-value lightly.

> *)
> Still uncertain support for shrink-on-read, no support for shrink-on-
> write and slicing forward and bidirectional ranges.  Are they going into 
> a library?

Yes, excellent point. The document on ranges tells what they must 
define. The standard library can and will define convenience functions 
using those primitives. This is appealing because there will be many 
range implementations and you don't want to burden everyone with 
implementing a ton of non-orthogonal stuff.


Andrei