On 10/08/2015 10:08 PM, Kagamin wrote:
> OK, I thought a little more and... Name: divisible range. It occurred to
> me that we only need to reverse logic of bidirectional range: while
> bidirectional range is a pair of ranges that shrink towards each other,
> divisible range is divided into two ranges that shrink away from each
> other. The C++ example implies that begin and end must be bidirectional
> iterators, but that is not really needed as they are used for bounds
> checks only, ranges have empty for that, so the divisible range can be a
> normal input range that provides access to its left part that shrinks
> from back (backward input range?) and provides access to the right part.

Isn't this the same as my suggestion?
http://forum.dlang.org/post/mv3q34$bbg$1@digitalmars.com

If not, what is the difference?

On Thursday, 8 October 2015 at 22:57:01 UTC, Timon Gehr wrote:
> Isn't this the same as my suggestion?
> http://forum.dlang.org/post/mv3q34$bbg$1@digitalmars.com
>
> If not, what is the difference?

Your range is undoable. The difference I see is that you use full (should be frontFull) and pushFront to go left, I use normal backward input range, empty and popBack - existing primitives. Also pushFront may suggest you're adding new items at the front, maybe your methods should be frontUndoEmpty and undoPopFront?

Also imagine you want to write an algorithm that iterates backwards, you must choose which set of primitives to use: back+empty+popBack or front+frontUndoEmpty+undoPopFront, and an undoable bidirectional range will support both.

On Wednesday, 7 October 2015 at 14:59:28 UTC, Trass3r wrote:
> On Tuesday, 6 October 2015 at 22:39:01 UTC, Ulrich Küttler  wrote:
>> Yes, this is an explanation. Thanks. So the argument being C++ customs. Now that you mention it, this seems to be the argument in Eric's D4128 paper, too.
>>
>> I was hoping for a somewhat deeper reasoning. Out of curiously, I am still trying to grasp all the implications. Ranges are hard.
>
> Another one is "odd number of iterators algorithms"
>
>> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4128.html#appendix-3-d-ranges-and-algorithmic-complexity
>
> D’s choice of algorithmic basis operations is inherently less efficient than C++’s.

Glad that you guys found my rationale. Yes, those are the two big reasons. Trying to express algorithms without any clear abstraction of "position within range" (independent of ranges) is hard and awkward, and occasionally causes algorithms to be less efficient.

IMO, James Touton's "position-based ranges"[1] was/is a viable design of a ranges-first interface that also had a (very weak but sufficient) notion of position. It might be a direction for D if you ever find it necessary.

It's true that the initial version of Boost.Range wasn't terribly interesting. As early as 12/2004, I was working on a set of extensions to Boost.Range that added range adaptors that chain. (See https://svn.boost.org/svn/boost/sandbox/boost/range_ex.) Lazy range operations that compose is where range-based design starts. That's as far back as I can trace my work on "real ranges". This work was eventually merged into Boost.Range as Range v2.

On Thursday, 1 October 2015 at 08:37:37 UTC, Walter Bright wrote:
> Range iteration over arrays have been around in D since the beginning and a more general proposal first appears here:
>
> http://www.digitalmars.com/d/archives//12773.html

I don't see any generic description there of what constitutes a range or how to leverage it in user code, just a discussion of the foreach language construct.

> I found a link to Thorsten's Boost range:
>
> http://www.boost.org/doc/libs/1_34_0/libs/range/doc/intro.html
> http://www.boost.org/doc/libs/1_34_0/libs/range/doc/range.html
>
> It returns an iterator, so I don't think it is what we'd consider a range to be today.
>
> Matthew's ranges had the following members:
>
>     current
>     advance
>     is_open
>
> corresponding to front, popFront, and empty.
>
> So I'd say given what I can dig up, that D's ranges were more advanced than Boost's were at the time.

Walter, you seem to suggest that Real Ranges have a popFront/front interface. Naturally by that metric C++ ranges don't count! But IMO that's not what matters. What matters is the programming model that ranges permit. Boost.Range's model where ranges are a layer over iterators can and does support that model, as my range proposal and my range_ex library from 2004 demonstrate.

To be honest, this whole conversation is kind of funny to me. It reminds me of the Bugs Bunny cartoon where Marvin the Martian plants his flag on Earth and says, "I claim this planet in the name of [Digital] Mars!" We Earthlings respectfully disagree. :-)

Eric

[^1] http://www.open-std.org/pipermail/ranges/2014-March/000499.html

On 10/10/15 12:58 AM, Eric Niebler wrote:
> To be honest, this whole conversation is kind of funny to me. It
> reminds me of the Bugs Bunny cartoon where Marvin the Martian plants
> his flag on Earth and says, "I claim this planet in the name of
> [Digital] Mars!" We Earthlings respectfully disagree. :-)

Only it's the other way around, which makes the matter quite ironic. You wrote:

> P.S. I see lots of people here assuming that C++ is playing catch-up
> to D because D has ranges and C++ doesn't yet. That is ignoring the
> long history of ranges in C++. C++ got ranges in the form of the
> Boost.Range library by Thorsten Ottoson sometime in the early 00's.
> Andrei didn't implement D's ranges until many years after. The ranges
> idea is older than dirt. It's not a D invention.

I think it would be a bit of a stretch to describe D ranges as derivative of Boost ranges.

Anyhow, it's best for us all to focus on doing good work instead of pettily fighting for irrelevant credit.


Andrei

On 10/10/15 12:58 AM, Eric Niebler wrote:
> Trying to express algorithms without any clear abstraction of "position
> within range" (independent of ranges) is hard and awkward, and
> occasionally causes algorithms to be less efficient.

I agree that ranges are a weaker basis than iterators. But it's not necessarily that a notion of position is the only way out.

Ranges can be made as strong a basis by adding the O(1) primitives r1.before(r2) and r1.after(r2) that return the prefix/suffix following r2 within r1. With those I hope to be able to show easily that algorithms needing "iterator in the middle" can be redone.

I think I need to sit down and define these primitives (albeit they aren't used that frequently) and use them in a few fundamental algorithms to just close the matter once and for all.


Andrei

On Sat, Oct 10, 2015 at 09:52:22AM +0300, Andrei Alexandrescu via Digitalmars-d wrote:
> On 10/10/15 12:58 AM, Eric Niebler wrote:
> >Trying to express algorithms without any clear abstraction of "position within range" (independent of ranges) is hard and awkward, and occasionally causes algorithms to be less efficient.
> 
> I agree that ranges are a weaker basis than iterators. But it's not necessarily that a notion of position is the only way out.
> 
> Ranges can be made as strong a basis by adding the O(1) primitives
> r1.before(r2) and r1.after(r2) that return the prefix/suffix following
> r2 within r1. With those I hope to be able to show easily that
> algorithms needing "iterator in the middle" can be redone.

I assume .before would be implemented in a specialization of forward ranges, and .after in a specialization of bidirectional ranges?


> I think I need to sit down and define these primitives (albeit they aren't used that frequently) and use them in a few fundamental algorithms to just close the matter once and for all.
[...]

It would also fix the current bug in nextPermutation that claims that it supports bidirectional ranges, when in fact it requires random access ranges, precisely because reversing the last n elements requires the "iterator in the middle" construct.


T

-- 
Gone Chopin. Bach in a minuet.

On Saturday, 10 October 2015 at 06:15:10 UTC, Andrei Alexandrescu wrote:
> On 10/10/15 12:58 AM, Eric Niebler wrote:
>> To be honest, this whole conversation is kind of funny to me. It
>> reminds me of the Bugs Bunny cartoon where Marvin the Martian plants
>> his flag on Earth and says, "I claim this planet in the name of
>> [Digital] Mars!" We Earthlings respectfully disagree. :-)
>
> Only it's the other way around, which makes the matter quite ironic. You wrote:
>
>> P.S. I see lots of people here assuming that C++ is playing catch-up
>> to D because D has ranges and C++ doesn't yet. That is ignoring the
>> long history of ranges in C++. C++ got ranges in the form of the
>> Boost.Range library by Thorsten Ottoson sometime in the early 00's.
>> Andrei didn't implement D's ranges until many years after. The ranges
>> idea is older than dirt. It's not a D invention.
>
> I think it would be a bit of a stretch to describe D ranges as derivative of Boost ranges.

If I implied that I believe that D ranges were based on Boost.Range, then I apologize. I don't believe that. I suspect (but don't know) that ranges in D were independently invented without knowledge of the long history of them in C++. Which is fine except for the claims that C++ is playing catch-up. It's not.

> Anyhow, it's best for us all to focus on doing good work instead of pettily fighting for irrelevant credit.

I only jumped in when I saw some disparagement of C++ and my work which (IMO) was both
petty and wrong. I would very much like to drop this and get back to productive work.

\e

On Sat, Oct 10, 2015 at 06:06:59PM +0000, Eric Niebler via Digitalmars-d wrote:
> On Saturday, 10 October 2015 at 06:15:10 UTC, Andrei Alexandrescu wrote:
[...]
> >Anyhow, it's best for us all to focus on doing good work instead of pettily fighting for irrelevant credit.
> 
> I only jumped in when I saw some disparagement of C++ and my work which (IMO) was both petty and wrong. I would very much like to drop this and get back to productive work.
[...]

Eric, if I came across as disparaging your work, I apologize, as that was never my intention. As the author of the article that you used as the basis for your presentation, I am very honored to have you acknowledge my work in the C++ community.

My comment about C++ playing catchup wasn't intended to be petty disparagement either, it's a reflection of my consideration that C++ has been heading in the wrong direction (IMO), and only now is "turning the ship", so to speak, toward where other languages have already gone ahead.  I'm a C++ programmer myself, and for many years have faced many problems and issues that arose from certain design decisions in C++. After discovering D and realizing that I don't *need* to deal with such issues after all, because D made different design decisions, only to learn later on that C++ is now also trying to head in the same directions, it's a bit hard not to perceive C++ as playing catch-up.


T

-- 
Gone Chopin. Bach in a minuet.

On 10/10/15 9:06 PM, Eric Niebler wrote:
> On Saturday, 10 October 2015 at 06:15:10 UTC, Andrei Alexandrescu wrote:
>> On 10/10/15 12:58 AM, Eric Niebler wrote:
>>> To be honest, this whole conversation is kind of funny to me. It
>>> reminds me of the Bugs Bunny cartoon where Marvin the Martian plants
>>> his flag on Earth and says, "I claim this planet in the name of
>>> [Digital] Mars!" We Earthlings respectfully disagree. :-)
>>
>> Only it's the other way around, which makes the matter quite ironic.
>> You wrote:
>>
>>> P.S. I see lots of people here assuming that C++ is playing catch-up
>>> to D because D has ranges and C++ doesn't yet. That is ignoring the
>>> long history of ranges in C++. C++ got ranges in the form of the
>>> Boost.Range library by Thorsten Ottoson sometime in the early 00's.
>>> Andrei didn't implement D's ranges until many years after. The ranges
>>> idea is older than dirt. It's not a D invention.
>>
>> I think it would be a bit of a stretch to describe D ranges as
>> derivative of Boost ranges.
>
> If I implied that I believe that D ranges were based on Boost.Range,
> then I apologize. I don't believe that.

Well the simple fact is then that P.S. has done an awful job at conveying your point.

> I suspect (but don't know) that
> ranges in D were independently invented without knowledge of the long
> history of them in C++.

Well that's easy to figure. "Iterators Must Go" at https://archive.org/details/AndreiAlexandrescuKeynoteBoostcon2009 starting around minute 1:01:50 mentions "Ranges are not Boost ranges. They're very different". Same talk at 1:02:34 describes how Boost and Adobe defined their own ranges ("Boost and Adobe did make an interesting step in a good direction, however things must be taken way further than that." So there was knowledge of said long history of ranges in C++. Far as I can tell "Iterators Must Go" was immediately and universally recognized as a turning point in how people approached getting work done using ranges.

(Existing work I only found out recently: Matthew Wilson did define ranges as a generalization of D slices; his work was not based on C++ idioms, and made no inroads in the C++ community. His work _is_ strongly related to today's D ranges, I ought to have found that, and it is my mistake to not have.)

> Which is fine except for the claims that C++ is
> playing catch-up. It's not.
>
>> Anyhow, it's best for us all to focus on doing good work instead of
>> pettily fighting for irrelevant credit.
>
> I only jumped in when I saw some disparagement of C++ and my work which
> (IMO) was both
> petty and wrong. I would very much like to drop this and get back to
> productive work.

Eric, I don't know about others but I respect and like your work. I appreciate its originality, too. What I see here is a simple case when someone said something wrong and got his behind appropriately handed on a dish constructed of a precious metal.


Andrei