RFC on range design for D2

[Bill Baxter]

On Wed, Sep 10, 2008 at 11:57 PM, Andrei Alexandrescu
<SeeWebsiteForEmail at erdani.org> wrote:
> Bill Baxter wrote:
>>
>> On Wed, Sep 10, 2008 at 10:07 PM, Andrei Alexandrescu
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>>
>>> Bill Baxter wrote:
>>>>
>>>> But I think you and I are in agreement that it would be easier and
>>>> more natural to think of ranges as iterators augmented with
>>>> information about bounds, as opposed to a contiguous block of things
>>>> from A to B.
>>>
>>> I like that you are bringing this point up, it is interesting. Note that
>>> my
>>> API never assumes or requires that there's an actual contiguous block of
>>> things underneath. Au contraire, in the I/O case, there's only "the
>>> current
>>> element" underneath.
>>
>> Yes, I see that and think it's great.  But the point I've been trying
>> to make is that the nomenclature you are using seems to emphasize the
>> contiguous block interpretation, rather than the interpretation as a
>> cursor plus a sentinel.  The contiguous block terminology makes good
>> sense for slices, but less for things like trees and unbounded
>> generators and HMMs.
>
> I disagree that isEmpty, first, and next suggest anything near contiguous
> block. It's just list terminology. Is the list empty? Give me the first
> element of the list. Advance to the next element in the list.

However a range isn't, generally speaking, a list.  It's a way to
traverse or access data that may or may not be a list.  For something
like an unbounded generator, it is odd to speak of the "first".  Such
an object has a current value and a "next", but the value you can look
at right now is only the "first" by a bit of a terminology stretch.

I think using list terminology unnecessarily confuses the iterating
construct that does the accessing with the container being accessed.
The range is not the container.  The range consists of a place where
you are, and a termination condition.  The range is not "empty" or
"full" because it does not actually contain elements.  Sure, if you're
dead set on it, you can say that by "empty" we mean that the set of
things you would get if you called .next repeatedly is empty, but why?
 The terminology is just encouraging one to think of a range as a
container, when in fact it is not -- it is more like two goal posts.
Call it atEnd() or similar and you'll naturally encourage people to
think of ranges as references rather than containers.

Similarly, using list terminology led you to "pop".  But pop on a
range does not actually remove any content.  Pop just moves the goal
post on one end.

And then there's the various union/diff stuff, which everyone seems to
find confusing.  I think much of that confusion and mental overhead
just goes away if you think of a range as a good old iterator plus a
stopping condition.

> Names for the before and after range operations are still in the air...
>
> Are you referring to the "range" name itself?

That could be part of the reason for this tendency to try to assign
list-like names to the parts.  If it were called a "bounded iterator"
I think that would better describe the perspective I'm pushing, and
naturally lead to choices like "atEnd" instead of "isEmpty".

>> And ok, I do think your incredible shrinking bidirectional range is
>> borked.  But other than that, I'm just talking about terminology.
>
> How is it borked?

See my post to Digitalmars.D.

But upon further reflection I think it may be that it's just not what
I would call a bidirectional range.  By that I mean it's not good at
solving the problems that a bidirectional iterator in C++ is good for.
 Your bidir range may be useful (though I'm not really convinced that
very many algorithms need what it provides) --  but I think one also
needs an iterator that's good at what C++'s bidir iterators are good
at, i.e. moving the active cursor backwards or forwards.  I would call
your construct more of a "double-headed" range than a bidirectional
one.

--bb