RFC on range design for D2

[Andrei Alexandrescu]

Sean Kelly wrote:
> Andrei Alexandrescu wrote:
>> Sean Kelly wrote:
>>> Andrei Alexandrescu wrote: ...
>>>> 
>>>> After much thought and discussions among Walter, Bartosz and
>>>> myself, I defined a range design and reimplemented all of
>>>> std.algorithm and much of std.stdio in terms of ranges alone.
>>> 
>>> Yup.  This is why I implemented all of Tango's algorithms 
>>> specifically for arrays from the start--slices represent a
>>> reasonable approximation of ranges, and this seems far preferable
>>> to the iterator approach of C++.  Glad to hear that this is what
>>> you've decided as well.
>> 
>> That's great to hear, but I should warn you that moving from arrays
>> to "the lowest range that will do" is not quite easy. Think of 
>> std::rotate for example.
> 
> I'll admit that I find some of the features <algorithm> provides to
> be pretty weird.  Has anyone ever actually wanted to sort something
> other than a random-access range in C++?  Or rotate one, for example?

Great questions. I don't recall having needed to sort a list lately, but 
rotate is a great function that has an undeservedly odd name. What 
rotate does is to efficiently transform this:

a, b, c, d, e, f, A, B, C, D

into this:

A, B, C, D, a, b, c, d, e, f

I use that all the time because it's really a move-to-front operation. 
In fact my algorithm2 implementation does not call it rotate anymore, it 
calls it moveToFront and allows you to move any subrange of a range to 
the front of that range efficiently. It's a useful operation in a great 
deal of lookup strategies.

> These operations are allowed, but to me they fall outside the realm
> of useful functionality.  I suppose there may be some relation here
> to Stepanov's idea of a computational basis.  Should an algorithm
> operate on a range if it cannot do so efficiently?  And even if it
> does, will anyone actually use it?

I think it all depends on what one's day-to-day work consists of. I was 
chatting to Walter about it and he confessed that, although he has a 
great deal of respect for std.algorithm, he's not using much of it. I 
told him back that I need 80% of std.algorithm on a daily basis. In fact 
that's why I wrote it - otherwise I wouldn't have had the time to put 
into it.

This is because I make next to no money so I can afford to work on basic 
research, which is "important" in a long-ranging way. Today's computing 
is quite disorganized and great energy is expended on gluing together 
various pieces, protocols, and interfaces. I've worked in that 
environment quite a lot, and dealing with glue can easily become 90% of 
a day's work, leaving only little time to get occupied with a real 
problem, such as making a computer genuinely smarter or at least more 
helpful towards its user. All too often we put a few widgets on a window 
and the actual logic driving those buttons - the "smarts", the actual 
"work" gets drowned by details taking care of making that logic stick to 
the buttons.

I mentioned in a talk once that any programmer should know how to 
multiply two matrices. Why? Because if you don't, you can't tackle a 
variety of problems that can be easily expressed in terms of matrix 
multiplication, even though they have nothing to do with algebra 
(rotating figures, machine learning, fractals, fast series...). A person 
in the audience said that she never actually needs to multiply two 
matrices, so why bother? I gave an evasive response, but the reality was 
that that was a career-limiting state of affairs for her.


Andrei