View mode: basic / threaded / horizontal-split · Log in · Help
March 24, 2012
Making sense of ranges
The documentation for std.range states

http://dlang.org/phobos/std_range.html
"This module defines the notion of range (by the membership tests isInputRange, 
isForwardRange, isBidirectionalRange, isRandomAccessRange), range capability tests (such 
as hasLength or hasSlicing), and a few useful range incarnations."

But that intro doesn't describe what a range actually is.

Here's what I've made out so far:

- Ranges are basically a generalised API for accessing a container or stream that is 
linear in logical structure and can have any element type.

- What is a range and what isn't is determined by compile-time duck typing - testing 
whether it implements certain methods.

- A range over a finite data structure is essentially equivalent to a start/end iterator 
pair as used by various C++ STL functions.

- Where a function in std.range is described as iterating through ranges in a particular 
way, what this function does is to return a range that delivers the resulting sequence.

Have I got all this right?


Things I'm confused by:

- One of the expansions of put is
    r.front = e; r.popFront();

What has putting something at the front of a range and then popping it to do with 
outputting to the range?

- Why is a range that can save checkpoints called a "forward" range?


Stewart.
March 24, 2012
Re: Making sense of ranges
On 03/24/2012 11:19 AM, Stewart Gordon wrote:
> The documentation for std.range states
>
> http://dlang.org/phobos/std_range.html
> "This module defines the notion of range (by the membership tests
> isInputRange, isForwardRange, isBidirectionalRange,
> isRandomAccessRange), range capability tests (such as hasLength or
> hasSlicing), and a few useful range incarnations."
>
> But that intro doesn't describe what a range actually is.

Apparently the library relies on the definition elsewhere. [1]

> Here's what I've made out so far:
>
> - Ranges are basically a generalised API for accessing a container or
> stream that is linear in logical structure and can have any element type.

Yes. Some ranges can also provide random access.

> - What is a range and what isn't is determined by compile-time duck
> typing - testing whether it implements certain methods.

Yes.

> - A range over a finite data structure is essentially equivalent to a
> start/end iterator pair as used by various C++ STL functions.

Yes.

> - Where a function in std.range is described as iterating through ranges
> in a particular way, what this function does is to return a range that
> delivers the resulting sequence.

Yes. Almost always lazily.

> Have I got all this right?

Yes.

> Things I'm confused by:
>
> - One of the expansions of put is
> r.front = e; r.popFront();
>
> What has putting something at the front of a range and then popping it
> to do with outputting to the range?

Iterating an output range is also by popFront(). So what it says is, put 
this element to the output range and advance the range. There is a 
gotcha about this when the output range is a slice: Whatever is just put 
into the range is popped right away! :) [2]

> - Why is a range that can save checkpoints called a "forward" range?

I agree. Here is my guess: The name of the ForwardRange comes from the 
fact that it is not double-ended. It can go only in one direction.

> Stewart.

Ali

[1] http://www.informit.com/articles/printerfriendly.aspx?p=1407357

[2] http://ddili.org/ders/d.en/ranges.html
March 24, 2012
Re: Making sense of ranges
On 24.03.2012 22:19, Stewart Gordon wrote:
> The documentation for std.range states
>
> http://dlang.org/phobos/std_range.html
> "This module defines the notion of range (by the membership tests
> isInputRange, isForwardRange, isBidirectionalRange,
> isRandomAccessRange), range capability tests (such as hasLength or
> hasSlicing), and a few useful range incarnations."
>
> But that intro doesn't describe what a range actually is.
>
> Here's what I've made out so far:
>
> - Ranges are basically a generalised API for accessing a container or
> stream that is linear in logical structure and can have any element type.
>
> - What is a range and what isn't is determined by compile-time duck
> typing - testing whether it implements certain methods.
>
> - A range over a finite data structure is essentially equivalent to a
> start/end iterator pair as used by various C++ STL functions.
>
> - Where a function in std.range is described as iterating through ranges
> in a particular way, what this function does is to return a range that
> delivers the resulting sequence.
>
> Have I got all this right?
>

More or less fine.

>
> Things I'm confused by:
>
> - One of the expansions of put is
> r.front = e; r.popFront();

Strange looking this one, but it allows, for instance, to output things 
to a container that defines range over it's elements.
>
> What has putting something at the front of a range and then popping it
> to do with outputting to the range?
>
> - Why is a range that can save checkpoints called a "forward" range?
>

It's not truly checkpoints, but rather the whole state can copied.
I believe, in some use cases checkpoints can be much smaller then the 
whole state, and we haven't got a checkpoint range yet. Could be a nice 
addition if proposal is sound.


-- 
Dmitry Olshansky
March 24, 2012
Re: Making sense of ranges
On 24/03/2012 18:57, Ali Çehreli wrote:
<snip>
> Iterating an output range is also by popFront(). So what it says is, put this element to
> the output range and advance the range. There is a gotcha about this when the output range
> is a slice: Whatever is just put into the range is popped right away! :) [2]

I'm beginning to get it now: the purpose of an output range is to put new data into the 
underlying container.  So once you've put something in, the remaining range is what's left 
to be populated.  I had been thinking of outputting in terms of appending to the range, 
hence the confusion.

>> - Why is a range that can save checkpoints called a "forward" range?
>
> I agree. Here is my guess: The name of the ForwardRange comes from the fact that it is not
> double-ended. It can go only in one direction.
<snip>

Bidirectional ranges are forward ranges as well.

But I've just had a look at STL iterators, and it seems that the range category hierarchy 
has been lifted from that.  There, a "forward" iterator combines the functionality of an 
input iterator and an output iterator, hence it's your basic iterator that can move 
forwards and do what it likes with the data it walks over.  (It would seem that it's only 
an "output" iterator in that * returns an lvalue, which may or may not be actually 
assignable depending on the constancy of the element type.)

In D ranges, OTOH, the only thing that distinguishes a forward range from a general input 
range is the presence of a save method to make a copy of it.  Doesn't seem to have 
anything to do with either the "forward" name or the C++ origin thereof....

Something else I'm finding puzzling is moveFront, moveAt and moveBack.  Is D trying to be 
C++11 or something?  Move semantics don't seem to me to be useful in a language with GC.

Stewart.
March 24, 2012
Re: Making sense of ranges
On 03/25/2012 12:07 AM, Stewart Gordon wrote:
> On 24/03/2012 18:57, Ali Çehreli wrote:
> <snip>
>> Iterating an output range is also by popFront(). So what it says is,
>> put this element to
>> the output range and advance the range. There is a gotcha about this
>> when the output range
>> is a slice: Whatever is just put into the range is popped right away!
>> :) [2]
>
> I'm beginning to get it now: the purpose of an output range is to put
> new data into the underlying container. So once you've put something in,
> the remaining range is what's left to be populated. I had been thinking
> of outputting in terms of appending to the range, hence the confusion.
>
>>> - Why is a range that can save checkpoints called a "forward" range?
>>
>> I agree. Here is my guess: The name of the ForwardRange comes from the
>> fact that it is not
>> double-ended. It can go only in one direction.
> <snip>
>
> Bidirectional ranges are forward ranges as well.
>
> But I've just had a look at STL iterators, and it seems that the range
> category hierarchy has been lifted from that. There, a "forward"
> iterator combines the functionality of an input iterator and an output
> iterator, hence it's your basic iterator that can move forwards and do
> what it likes with the data it walks over. (It would seem that it's only
> an "output" iterator in that * returns an lvalue, which may or may not
> be actually assignable depending on the constancy of the element type.)
>
> In D ranges, OTOH, the only thing that distinguishes a forward range
> from a general input range is the presence of a save method to make a
> copy of it. Doesn't seem to have anything to do with either the
> "forward" name or the C++ origin thereof....
>
> Something else I'm finding puzzling is moveFront, moveAt and moveBack.
> Is D trying to be C++11 or something? Move semantics don't seem to me to
> be useful in a language with GC.
>
> Stewart.

The fact that the language has GC does not imply everything should go on 
the GC heap.
March 25, 2012
Re: Making sense of ranges
On 03/24/2012 04:07 PM, Stewart Gordon wrote:
> On 24/03/2012 18:57, Ali Çehreli wrote:
> <snip>
>> Iterating an output range is also by popFront(). So what it says is,
>> put this element to
>> the output range and advance the range. There is a gotcha about this
>> when the output range
>> is a slice: Whatever is just put into the range is popped right away!
>> :) [2]
>
> I'm beginning to get it now: the purpose of an output range is to put
> new data into the underlying container. So once you've put something in,
> the remaining range is what's left to be populated. I had been thinking
> of outputting in terms of appending to the range, hence the confusion.
>
>>> - Why is a range that can save checkpoints called a "forward" range?
>>
>> I agree. Here is my guess: The name of the ForwardRange comes from the
>> fact that it is not
>> double-ended. It can go only in one direction.
> <snip>
>
> Bidirectional ranges are forward ranges as well.
>
> But I've just had a look at STL iterators, and it seems that the range
> category hierarchy has been lifted from that. There, a "forward"
> iterator combines the functionality of an input iterator and an output
> iterator, hence it's your basic iterator that can move forwards and do
> what it likes with the data it walks over. (It would seem that it's only
> an "output" iterator in that * returns an lvalue, which may or may not
> be actually assignable depending on the constancy of the element type.)
>
> In D ranges, OTOH, the only thing that distinguishes a forward range
> from a general input range is the presence of a save method to make a
> copy of it.

I looked for rationale on Andrei's article. There is this bit about STL 
forward iterators:

<quote>
Input and forward iterators are syntactically identical but subtly 
different semantically—copying a forward iterator saves iteration state, 
but copying an input iterator just creates a new view of the same 
iteration state.
</quote>

I guess that's why 'save' is explicit on ForwardRange.

Ali

> Doesn't seem to have anything to do with either the
> "forward" name or the C++ origin thereof....
>
> Something else I'm finding puzzling is moveFront, moveAt and moveBack.
> Is D trying to be C++11 or something? Move semantics don't seem to me to
> be useful in a language with GC.
>
> Stewart.
March 25, 2012
Re: Making sense of ranges
On Saturday, March 24, 2012 18:14:46 Ali Çehreli wrote:
> I looked for rationale on Andrei's article. There is this bit about STL
> forward iterators:
> 
> <quote>
> Input and forward iterators are syntactically identical but subtly
> different semantically—copying a forward iterator saves iteration state,
> but copying an input iterator just creates a new view of the same
> iteration state.
> </quote>
> 
> I guess that's why 'save' is explicit on ForwardRange.

Yes. If a range is a reference type rather than a value type or a dynamic 
array, then you _must_ have save in order to get a copy of its current 
state. However, since most ranges are either dynamic arrays or value types, 
functions are often written without using save like they should and would 
end up consuming a forward range if it's a reference type (e.g. a class). 
But save was created primarily to make it possible to have classes which are 
ranges rather than relying on assignment making a copy (and not all structs 
are value types, so save can be required for them as well).

- Jonathan M Davis
March 26, 2012
Rewrite of std.range docs (Was: Re: Making sense of ranges)
On Sat, Mar 24, 2012 at 06:19:32PM +0000, Stewart Gordon wrote:
> The documentation for std.range states
> 
> http://dlang.org/phobos/std_range.html
> "This module defines the notion of range (by the membership tests
> isInputRange, isForwardRange, isBidirectionalRange,
> isRandomAccessRange), range capability tests (such as hasLength or
> hasSlicing), and a few useful range incarnations."
> 
> But that intro doesn't describe what a range actually is.
[...]

In a previous post long lost inside a rather large thread some time ago,
I proposed a rewrite of the docs of std.range to make it clearer, at
least on a basic level, what a range is, why we should care, and what
the module offers.

This thread has further convinced me that std.range's docs *need* this
rewrite. So here's my first attempt at it:

	https://github.com/quickfur/phobos/tree/stdrange_docs

It's not complete yet; I still have a few more range-creation templates
to cover, and then list the auxiliary functions, etc., before it's ready
for merging into Phobos. But I thought I should put it up for review
here first, in case people have some comments/suggestions or further
things that should be put into the docs. Better to put it all in a
single pull request than waste the Phobos maintainers' time with
multiple updates to the docs.

So, comments, suggestions, flames, etc., are hereby solicited. :-)


T

-- 
If lightning were to ever strike an orchestra, it'd always hit the conductor first.
March 26, 2012
Re: Making sense of ranges
On Sat, 24 Mar 2012 19:07:01 -0400, Stewart Gordon <smjg_1998@yahoo.com>  
wrote:

> On 24/03/2012 18:57, Ali Çehreli wrote:
> <snip>
>> Iterating an output range is also by popFront(). So what it says is,  
>> put this element to
>> the output range and advance the range. There is a gotcha about this  
>> when the output range
>> is a slice: Whatever is just put into the range is popped right away!  
>> :) [2]
>
> I'm beginning to get it now: the purpose of an output range is to put  
> new data into the underlying container.  So once you've put something  
> in, the remaining range is what's left to be populated.  I had been  
> thinking of outputting in terms of appending to the range, hence the  
> confusion.

The output range is almost an entirely orthogonal concept to an input  
range.  It basically defines a way to output elements.

How an output range directs its elements is up to the output range.  It  
may append, it may overwrite, it may prepend, it can do anything it wants.

The only commonality is that a *writable* input range can also be an  
output range (writable meaning r.front = x works).

-Steve
March 27, 2012
Re: Rewrite of std.range docs (Was: Re: Making sense of ranges)
On Monday, 26 March 2012 at 00:50:32 UTC, H. S. Teoh wrote:

> This thread has further convinced me that std.range's docs 
> *need* this
> rewrite. So here's my first attempt at it:
>
> 	https://github.com/quickfur/phobos/tree/stdrange_docs

I find that opening to be much better. Look forward to the 
improvement.
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home