RFC on range design for D2

[Sean Kelly]

Andrei Alexandrescu wrote:
> 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.

Ah, so it's a bit like partition and select.  I use the two of those 
constantly, but haven't ever had a need for rotate.  Odd, I suppose, 
since they're so similar.

> 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.

Exactly.  I implemented Tango's Array module for the same reason.  Other 
than rotate and stable_sort, I think the module has everything from 
<algorithm>, plus some added bits.

> 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've never worked in that environment, but I would think that even such 
positions require the use of algorithms.  If not, then I wouldn't 
consider them to be software engineering positions.  As for research-- 
I'd say that's a fairly broad category.  My first salaried position was 
in R&D for a switched long-distance carrier, for example, but that's 
applied research as opposed to academic research, which I believe you're 
describing.  I think there are benefits to each, but the overlap is what 
truly interests me.

> 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.

Yup.  This is a lot like the argument for Calculus in a CS curriculum. 
Entry-level software positions rarely require such things and yet I've 
been surprised at how many times they have proven useful over the years, 
simply for general problem-solving.  And there's certainly no debate 
about Linear Algebra--they may as well rename it "math for computer 
programming."


Sean