In wake of a few discussion I've witnessed, I'm thinking of a last change for ranges. (In fact there's one more, but that's minor.)

The problem is that input ranges and forward ranges have the same syntactic interface, but different semantic interfaces. Consider the problem of finding the first two identical adjacent items in a range:

R adjacentFind(R)(R r)
{
    if (r,empty) return r;
    R last = r;
    r.popFront;
    for (; !r.empty && last.front != r.front; last.popFront, r.popFront)
    {
    }
    return r;
}

This will work properly on lists and vectors, but horrendously on files and sockets. This is because input ranges can't be saved for later use: incrementing r also increments popFront and essentially forces both to look at the same current value.

I'm thinking a better design is to require any range that's forward or better to define a function save(). Ranges that don't implement it are input ranges; those that do, will guarantee a brand new range is returned from save(). So then adjacentFind would look like this:

R adjacentFind(R)(R r)
{
    if (r,empty) return r;
    R last = r.save;
    r.popFront;
    for (; !r.empty && last.front != r.front; last.popFront, r.popFront)
    {
    }
    return r;
}

Obviously, when you pass a range that doesn't support save, adjacentFind will not compile, which is what we want.

Andrei

P.S. There is a way to implement adjacentFind for forward ranges by saving data instead of ranges. I've used a limited version above for illustration purposes.

On Wed, 20 May 2009 20:19:30 +0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> In wake of a few discussion I've witnessed, I'm thinking of a last change for ranges. (In fact there's one more, but that's minor.)
>
> The problem is that input ranges and forward ranges have the same syntactic interface, but different semantic interfaces. Consider the problem of finding the first two identical adjacent items in a range:
>
> R adjacentFind(R)(R r)
> {
>      if (r,empty) return r;
>      R last = r;
>      r.popFront;
>      for (; !r.empty && last.front != r.front; last.popFront, r.popFront)
>      {
>      }
>      return r;
> }
>
> This will work properly on lists and vectors, but horrendously on files and sockets. This is because input ranges can't be saved for later use: incrementing r also increments popFront and essentially forces both to look at the same current value.
>
> I'm thinking a better design is to require any range that's forward or better to define a function save(). Ranges that don't implement it are input ranges; those that do, will guarantee a brand new range is returned from save(). So then adjacentFind would look like this:
>
> R adjacentFind(R)(R r)
> {
>      if (r,empty) return r;
>      R last = r.save;
>      r.popFront;
>      for (; !r.empty && last.front != r.front; last.popFront, r.popFront)
>      {
>      }
>      return r;
> }
>
> Obviously, when you pass a range that doesn't support save, adjacentFind will not compile, which is what we want.
>
> Andrei
>
> P.S. There is a way to implement adjacentFind for forward ranges by saving data instead of ranges. I've used a limited version above for illustration purposes.

Why not r.dup?

On Wed, 20 May 2009 20:23:27 +0400, Denis Koroskin <2korden@gmail.com> wrote:

> On Wed, 20 May 2009 20:19:30 +0400, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
>
>> In wake of a few discussion I've witnessed, I'm thinking of a last change for ranges. (In fact there's one more, but that's minor.)
>>
>> The problem is that input ranges and forward ranges have the same syntactic interface, but different semantic interfaces. Consider the problem of finding the first two identical adjacent items in a range:
>>
>> R adjacentFind(R)(R r)
>> {
>>      if (r,empty) return r;
>>      R last = r;
>>      r.popFront;
>>      for (; !r.empty && last.front != r.front; last.popFront,
>> r.popFront)
>>      {
>>      }
>>      return r;
>> }
>>
>> This will work properly on lists and vectors, but horrendously on files and sockets. This is because input ranges can't be saved for later use: incrementing r also increments popFront and essentially forces both to look at the same current value.
>>
>> I'm thinking a better design is to require any range that's forward or better to define a function save(). Ranges that don't implement it are input ranges; those that do, will guarantee a brand new range is returned from save(). So then adjacentFind would look like this:
>>
>> R adjacentFind(R)(R r)
>> {
>>      if (r,empty) return r;
>>      R last = r.save;
>>      r.popFront;
>>      for (; !r.empty && last.front != r.front; last.popFront,
>> r.popFront)
>>      {
>>      }
>>      return r;
>> }
>>
>> Obviously, when you pass a range that doesn't support save, adjacentFind will not compile, which is what we want.
>>
>> Andrei
>>
>> P.S. There is a way to implement adjacentFind for forward ranges by saving data instead of ranges. I've used a limited version above for illustration purposes.
>
> Why not r.dup?

Nevermind, I don't want to turn it into a bycicle shed discussion, but .dup would be consistent with arrays.

Do you suggest that ranges now have a reference semantics? That's quite a big change, but I do believe that it's for good, because it make classes a rightful ranges citizen.

== Quote from Denis Koroskin (2korden@gmail.com)'s article
> Why not r.dup?

.dup is supposed to imply copying of the range's contents, not copying of the range's iteration state.

Andrei Alexandrescu wrote:
> In wake of a few discussion I've witnessed, I'm thinking of a last change for ranges. (In fact there's one more, but that's minor.)
> 
> The problem is that input ranges and forward ranges have the same syntactic interface, but different semantic interfaces. Consider the problem of finding the first two identical adjacent items in a range:
> 
> R adjacentFind(R)(R r)
> {
>     if (r,empty) return r;
>     R last = r;
>     r.popFront;
>     for (; !r.empty && last.front != r.front; last.popFront, r.popFront)
>     {
>     }
>     return r;
> }
> 
> This will work properly on lists and vectors, but horrendously on files and sockets. This is because input ranges can't be saved for later use: incrementing r also increments popFront and essentially forces both to look at the same current value.
> 
> I'm thinking a better design is to require any range that's forward or better to define a function save(). Ranges that don't implement it are input ranges; those that do, will guarantee a brand new range is returned from save(). So then adjacentFind would look like this:
> 
> R adjacentFind(R)(R r)
> {
>     if (r,empty) return r;
>     R last = r.save;
>     r.popFront;
>     for (; !r.empty && last.front != r.front; last.popFront, r.popFront)
>     {
>     }
>     return r;
> }
> 
> Obviously, when you pass a range that doesn't support save, adjacentFind will not compile, which is what we want.
> 
> Andrei
> 
> P.S. There is a way to implement adjacentFind for forward ranges by saving data instead of ranges. I've used a limited version above for illustration purposes.

I REALLY hope that ranges will have some room  for a "Let's have a closer look" chapter in your book.  Sometimes I found them quite hard to understand:
Björn

dsimcha wrote:
> == Quote from Denis Koroskin (2korden@gmail.com)'s article
>> Why not r.dup?
> 
> .dup is supposed to imply copying of the range's contents, not copying of the
> range's iteration state.

Yes, for arrays save() is:

T[] save(T)(T[] r) { return r; }


Andrei

On Wed, May 20, 2009 at 9:19 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

> I'm thinking a better design is to require any range that's forward or better to define a function save(). Ranges that don't implement it are input ranges; those that do, will guarantee a brand new range is returned from save(). So then adjacentFind would look like this:
>
> R adjacentFind(R)(R r)
> {
>    if (r,empty) return r;
>    R last = r.save;
>    r.popFront;
>    for (; !r.empty && last.front != r.front; last.popFront, r.popFront)
>    {
>    }
>    return r;
> }
>
> Obviously, when you pass a range that doesn't support save, adjacentFind will not compile, which is what we want.

The only other alternative that comes to mind would be forcing input ranges to hide their copy constructor, or whatever the D equivalent is, making R last = r; fail.  But that would make input ranges very difficult to use.

So, of those two options at least, requiring a .save sounds like the better choice.

The down side is you will get no error if you write the code the first way, without a .save.   I see this as turning into tip #5 in "Effective D" -- "Know when to use .save"   It would be nice if that potential mistake could be eliminated somehow.  You could perhaps require input ranges to implement transfer semantics, and have them implement a .clone for cases when you really do want to make an aliasing copy.

--bb

Bill Baxter wrote:
> On Wed, May 20, 2009 at 9:19 AM, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
> 
>> I'm thinking a better design is to require any range that's forward or
>> better to define a function save(). Ranges that don't implement it are input
>> ranges; those that do, will guarantee a brand new range is returned from
>> save(). So then adjacentFind would look like this:
>>
>> R adjacentFind(R)(R r)
>> {
>>    if (r,empty) return r;
>>    R last = r.save;
>>    r.popFront;
>>    for (; !r.empty && last.front != r.front; last.popFront, r.popFront)
>>    {
>>    }
>>    return r;
>> }
>>
>> Obviously, when you pass a range that doesn't support save, adjacentFind
>> will not compile, which is what we want.
> 
> The only other alternative that comes to mind would be forcing input
> ranges to hide their copy constructor, or whatever the D equivalent
> is, making R last = r; fail.  But that would make input ranges very
> difficult to use.

Exactly. I thought of that design, and it was difficult to even pass a range to a function.

> So, of those two options at least, requiring a .save sounds like the
> better choice.
> 
> The down side is you will get no error if you write the code the first
> way, without a .save.   I see this as turning into tip #5 in
> "Effective D" -- "Know when to use .save"   It would be nice if that
> potential mistake could be eliminated somehow.  You could perhaps
> require input ranges to implement transfer semantics, and have them
> implement a .clone for cases when you really do want to make an
> aliasing copy.

Good point. I don't have a solution for that. Giving ranges move semantics would probably make for another Effective D tip (or perhaps more... move semantics are pretty brutal).

Another partial solution is to define a different interface for input ranges, one that combines front() and popFront(). Something like popNext. That way, people who use only the primitives empty() and popNext() know they are using a forward range and with hope they'll remember they can't really save copies of it and expect them to "remember" where they are in the input.


Andrei

I feel like there are too many differences between input and forward ranges for such a minor difference. Many range functions are written assuming no side effects on the caller. This can restrict the use of helper functions. It may be best to make their usage different...

Andrei Alexandrescu Wrote:

> In wake of a few discussion I've witnessed, I'm thinking of a last change for ranges. (In fact there's one more, but that's minor.)
> 
> The problem is that input ranges and forward ranges have the same syntactic interface, but different semantic interfaces. Consider the problem of finding the first two identical adjacent items in a range:
> 
> R adjacentFind(R)(R r)
> {
>      if (r,empty) return r;
>      R last = r;
>      r.popFront;
>      for (; !r.empty && last.front != r.front; last.popFront, r.popFront)
>      {
>      }
>      return r;
> }
> 
> This will work properly on lists and vectors, but horrendously on files and sockets. This is because input ranges can't be saved for later use: incrementing r also increments popFront and essentially forces both to look at the same current value.
> 
> I'm thinking a better design is to require any range that's forward or better to define a function save(). Ranges that don't implement it are input ranges; those that do, will guarantee a brand new range is returned from save(). So then adjacentFind would look like this:
> 
> R adjacentFind(R)(R r)
> {
>      if (r,empty) return r;
>      R last = r.save;
>      r.popFront;
>      for (; !r.empty && last.front != r.front; last.popFront, r.popFront)
>      {
>      }
>      return r;
> }
> 
> Obviously, when you pass a range that doesn't support save, adjacentFind will not compile, which is what we want.
> 
> Andrei
> 
> P.S. There is a way to implement adjacentFind for forward ranges by saving data instead of ranges. I've used a limited version above for illustration purposes.

Jason House wrote:
> I feel like there are too many differences between input and forward
> ranges for such a minor difference. Many range functions are written
> assuming no side effects on the caller. This can restrict the use of
> helper functions. It may be best to make their usage different...

So how do you think we should go about it? Also don't forget that any ranges should be seamlessly and efficiently treated as input ranges.

Andrei