www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Ranges

reply Steve Teale <steve.teale britseyeview.com> writes:
I shall start this again from scratch. Please excuse me for being thick about
it. I have tried before in more direct questions to Andrei, but in the end all
I got was a snotty email telling me not to be a nuisance and RTFD.
Unfortunately, the relevant documentation seems to have disappeared.

In range.d, in the context of isInputRange, it says:

"Returns $(D true) if $(D R) is an input range. An input range must
define the primitives $(D empty), $(D popFront), and $(D front). The
following code should compile for any input range ..."

template isInputRange(R)
{
    enum bool isInputRange = is(typeof(
    {
        R r;             // can define a range object
        if (r.empty) {}  // can test for empty
        r.popFront;          // can invoke next
        auto h = r.front; // can get the front of the range
    }()));
}

I can not possibly be the only D enthusiast who finds this completely
incomprehensible. What is a range? Is it a template interface, or is it just a
trick of template syntax that supports the old assertion that "nobody really
understands templates".

If ranges are to be a feature of the D language, then they should probably be
supported at language level rather than by some trick that has been discovered
by experimenting with how far you can push templates.

Also, it would be very useful to have some indication of what you might use
them for. I occasionally had to resort to STL iterators because I wanted to use
'map'. I agree that the syntax sucked, but nobody is telling me how ranges help.

I realize that some people with an IQ of 580 will find my questions naive and
misguided - not to mention impertinent, but it seems to me that one of the
responsibilities of being a leader is to explain to less gifted followers what
the fuck is going on. Or maybe I've got it wrong - if you're that bright (sorry
Walter - not you) then perhaps it's just a big ego trip.
Jun 18 2009
next sibling parent Ary Borenszweig <ary esperanto.org.ar> writes:
Steve Teale wrote:
 I shall start this again from scratch. Please excuse me for being thick about
it. I have tried before in more direct questions to Andrei, but in the end all
I got was a snotty email telling me not to be a nuisance and RTFD.
Unfortunately, the relevant documentation seems to have disappeared.
 
 In range.d, in the context of isInputRange, it says:
 
 "Returns $(D true) if $(D R) is an input range. An input range must
 define the primitives $(D empty), $(D popFront), and $(D front). The
 following code should compile for any input range ..."
 
 template isInputRange(R)
 {
     enum bool isInputRange = is(typeof(
     {
         R r;             // can define a range object
         if (r.empty) {}  // can test for empty
         r.popFront;          // can invoke next
         auto h = r.front; // can get the front of the range
     }()));
 }
 
 I can not possibly be the only D enthusiast who finds this completely
incomprehensible. What is a range? Is it a template interface, or is it just a
trick of template syntax that supports the old assertion that "nobody really
understands templates".
 
 If ranges are to be a feature of the D language, then they should probably be
supported at language level rather than by some trick that has been discovered
by experimenting with how far you can push templates.
 
 Also, it would be very useful to have some indication of what you might use
them for. I occasionally had to resort to STL iterators because I wanted to use
'map'. I agree that the syntax sucked, but nobody is telling me how ranges help.
 
 I realize that some people with an IQ of 580 will find my questions naive and
misguided - not to mention impertinent, but it seems to me that one of the
responsibilities of being a leader is to explain to less gifted followers what
the fuck is going on. Or maybe I've got it wrong - if you're that bright (sorry
Walter - not you) then perhaps it's just a big ego trip.

It's called "duck typing". http://en.wikipedia.org/wiki/Duck_typing "an object's current set of methods and properties determines the valid semantics, rather than its inheritance from a particular class or implementation of a specific interface" So you don't say something is a range by looking if it implements some Range interface, but rather if it has some methods in it.
Jun 18 2009
prev sibling next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Steve Teale (steve.teale britseyeview.com)'s article
 I shall start this again from scratch. Please excuse me for being thick about

got was a snotty email telling me not to be a nuisance and RTFD. Unfortunately, the relevant documentation seems to have disappeared.
 In range.d, in the context of isInputRange, it says:
 "Returns $(D true) if $(D R) is an input range. An input range must
 define the primitives $(D empty), $(D popFront), and $(D front). The
 following code should compile for any input range ..."
 template isInputRange(R)
 {
     enum bool isInputRange = is(typeof(
     {
         R r;             // can define a range object
         if (r.empty) {}  // can test for empty
         r.popFront;          // can invoke next
         auto h = r.front; // can get the front of the range
     }()));
 }
 I can not possibly be the only D enthusiast who finds this completely

trick of template syntax that supports the old assertion that "nobody really understands templates".
 If ranges are to be a feature of the D language, then they should probably be

experimenting with how far you can push templates.
 Also, it would be very useful to have some indication of what you might use
them

I agree that the syntax sucked, but nobody is telling me how ranges help.
 I realize that some people with an IQ of 580 will find my questions naive and

responsibilities of being a leader is to explain to less gifted followers what the fuck is going on. Or maybe I've got it wrong - if you're that bright (sorry Walter - not you) then perhaps it's just a big ego trip. Ranges are just pretty much an implicit compile-time interface. As Ary put it, compile time duck typing is a pretty accurate description. Basically, a range doesn't have to *be* a specific *type*, it just has to support certain specific *operations*, namely front, popFront, and empty. As long as it *has* these operations, and they compile and return what they're supposed to (ElementType!(T) for front(), void for popFront() and bool for empty), it doesn't matter what type it *is*. I guess the best way to think of it is that ranges are simply a convention used in Phobos about how to define iteration over user-defined types. If you stick to this convention, then all the range templates people write implicitly know what to do with your type even if they know nothing about the specifics of it. Ranges are really just a form of iterators that's given sane syntax (unlike C++) and relies on this compile-time duck typing instead of virtual functions and class-based interfaces (unlike Java and C#). However, in terms of use cases, they are the same except that ranges can be used where both efficiency and readability count. (C++ neglects readability, Java/C# neglect efficiency.) Really, they are nothing more than a way of encapsulating (at compile time, but not necessarily at runtime) iteration over user-defined types so that generic code can be written to work on these types. I suspect that your lack of understanding of ranges stems from lack of understanding of templates, since you mention that "noone understands templates" and once you get templates, ranges are ridiculously simple. If that's the case, then your best bet is probably to learn a little more about templates (which are so fundamental to what makes D special IMHO that I would say that, for all practical purposes, if you don't understand templates you don't understand D) and then try to understand ranges again.
Jun 18 2009
next sibling parent reply Derek Parnell <derek psych.ward> writes:
Steve Teale (steve.teale britseyeview.com) wrote:
 What is a range? 


In my case, I understand templates but that in itself doesn't help me understand Andrei's concept of ranges. Just using English as a guide doesn't really help either because a "range" is not an "iterator" in English. So I'd describe a range more along the lines of ... A Range is a data construct that has a set of zero or more discrete elements and can be used to iterate over its elements. There are a few varieties of ranges: InputRange, OutputRange, ForwardRange, BidirectionalRange and RandomAccessRange. InputRange ---------- With this range, iteration can only occur in one direction, from first to last element. As a minimum requirement it must implement methods that ... 1) Provide a function that returns if there are any elements (remaining) to iterator over. That function must be called 'empty()'. 2) Provide a function that returns the current first element in the set. Calling this when 'empty()' returns true will throw an exception. That function must be called 'front()'. 3) Provide a function that moves an internal 'cursor' to the element following the current first element in the set, such that it becomes the new current first element. Calling this when 'empty()' returns true will throw an exception. That function must be called 'popFront()'. (I assume that the initial call to front() before calling popFront() will return the absolute first element in the set, but this doesn't seem to be documented.) OutputRange ----------- This is an InputRange with the extra capability of being able to add elements to the range. In addition to the InputRange methods, it must also provide a method that adds a new element to the range, such that it becomes the current element. That method must be called 'put(E)' where 'E' is the new element. ForwardRange ------------ This is an InputRange with the extra capability of being able checkpoint the current first 'cursor' position simply by copying the range. When you copy an plain InputRange the copied range starts again from the absolute first element, but a copied ForwardRange starts at whatever was the current first element in the source range. (I'm not sure why Birectional ranges are not allowed to be checkpointed) BidirectionalRange ------------------ This is a ForwardRange that also allows iteration in the opposite direction. In addition to the ForwardRange methods it must also ... 1) Provide a function that returns the current last element in the set. Calling this when 'empty()' returns true will throw an exception. This must be called 'back()'. 2) Provide a function that moves an internal 'cursor' to the element that precedes the current last element in the set, such that it becomes the new current last element. Calling this when 'empty()' returns true will throw an exception. That function must be called 'popBack()'. (I assume that the initial call to back() before calling popBack() will return the absolute last element in the set, but this doesn't seem to be documented.) RandomAccessRange ----------------- This is either a BidirectionalRange or any Range in which 'empty()' always returns false (an infinite range). It must provide a method that will return the Nth element of the set. That function must be called 'opIndex(N)' where 'N' is a non-negative integer that represents a zero-based index into the set. Thus opIndex(0) returns the first element, opIndex(1) returns the 2nd element, etc ... (I assume that for finite Ranges if 'N' is not a valid index that the Range will throw an exception, but this doesn't seem to be documented.) Now I admit that these are not method names I would have choosen, as I would have preferred names more like ... isEmpty(), getFront(), moveForwards(), getBack(), moveBackwards(), getElement(N), addElement(E), but the bikeshed gods have more wisdom than me ... and not that I'm complaining of course. -- Derek Parnell Melbourne, Australia skype: derek.j.parnell
Jun 18 2009
next sibling parent Yigal Chripun <yigal100 gmail.com> writes:
Kristian Kilpi wrote:
 On Fri, 19 Jun 2009 03:13:11 +0300, Derek Parnell <derek psych.ward> wrote:
 Steve Teale (steve.teale britseyeview.com) wrote:
 Now I admit that these are not method names I would have choosen, as I
 would have preferred names more like ... isEmpty(), getFront(),
 moveForwards(), getBack(), moveBackwards(), getElement(N), addElement(E),
 but the bikeshed gods have more wisdom than me ... and not that I'm
 complaining of course.

I agree. Well, even if the names of the Range methods are a bit 'odd' for me, I guess they are ok... except for empty(). If I have a container that I wan't to use as a Range, I can't use empty() to empty the container (i.e. remove all the elements from it). :( And yes, *I* am complaining here. ;) I'm accustomed to use isXyz() for checking something and xyz() for doing something (e.g. isEmpty() + empty()). What function name should I use for emptying the container then? removeAllElements(), makeEmpty(), or maybe even emptyThisContainer()...? :P Hmm, should the Range methods use some special naming convention? E.g. rangeFront(), rangePopFront()...?

while I agree with the general point about the naming convention, I don't see how is this a problem here since a range should be a distinct type from the container. that means that you have for instance: class Tree { void empty(); ... TreeRange preOrder(); TreeRange inOrder(); TreeRange postOrder(); } struct TreeRange { bool empty(); ... } tree.empty(); // will empty the tree auto range = tree.inOrder(); ... while (!range.empty()) { // will check if the range is empty // do stuff } this might be confusing but not impossible.
Jun 19 2009
prev sibling parent Max Samukha <outer space.com> writes:
On Fri, 19 Jun 2009 11:49:06 +0300, "Kristian Kilpi"
<kjkilpi gmail.com> wrote:

On Fri, 19 Jun 2009 03:13:11 +0300, Derek Parnell <derek psych.ward> wrote:
 Steve Teale (steve.teale britseyeview.com) wrote:
 Now I admit that these are not method names I would have choosen, as I
 would have preferred names more like ... isEmpty(), getFront(),
 moveForwards(), getBack(), moveBackwards(), getElement(N), addElement(E),
 but the bikeshed gods have more wisdom than me ... and not that I'm
 complaining of course.

I agree. Well, even if the names of the Range methods are a bit 'odd' for me, I guess they are ok... except for empty(). If I have a container that I wan't to use as a Range, I can't use empty() to empty the container (i.e. remove all the elements from it). :( And yes, *I* am complaining here. ;) I'm accustomed to use isXyz() for checking something and xyz() for doing something (e.g. isEmpty() + empty()). What function name should I use for emptying the container then? removeAllElements(), makeEmpty(), or maybe even emptyThisContainer()...? :P

clear() is used quite often. You could use the likes of erase() or purge(). But, as Yigal already said, ranges and containers they crawl over are usually distinct types, so this shouldn't be a big problem.
Hmm, should the Range methods use some special naming convention? E.g.  
rangeFront(), rangePopFront()...?

Jun 19 2009
prev sibling next sibling parent reply "Lionello Lunesu" <lionello lunesu.remove.com> writes:
"dsimcha" <dsimcha yahoo.com> wrote in message 
news:h1e6qp$umo$1 digitalmars.com...
 Ranges are really just a form of iterators that's given sane syntax 
 (unlike C++)
 and relies on this compile-time duck typing instead of virtual functions 
 and
 class-based interfaces (unlike Java and C#).

Actually, C# doesn't care for the interfaces. They are just there to help you implement a compatible iterator. C#'s foreach will accept any type with "T GetEnumerator()", where type T in turn implements "bool MoveNext()" and "S Current { get; }". L.
Jun 18 2009
parent reply Ary Borenszweig <ary esperanto.org.ar> writes:
Lionello Lunesu wrote:
 
 "dsimcha" <dsimcha yahoo.com> wrote in message 
 news:h1e6qp$umo$1 digitalmars.com...
 Ranges are really just a form of iterators that's given sane syntax 
 (unlike C++)
 and relies on this compile-time duck typing instead of virtual 
 functions and
 class-based interfaces (unlike Java and C#).

Actually, C# doesn't care for the interfaces. They are just there to help you implement a compatible iterator. C#'s foreach will accept any type with "T GetEnumerator()", where type T in turn implements "bool MoveNext()" and "S Current { get; }".

Wow. :-) You always learn something new... Thanks, Lionello!
Jun 19 2009
parent Lionello Lunesu <lio lunesu.remove.com> writes:
Ary Borenszweig wrote:
 Lionello Lunesu wrote:
 "dsimcha" <dsimcha yahoo.com> wrote in message 
 news:h1e6qp$umo$1 digitalmars.com...
 Ranges are really just a form of iterators that's given sane syntax 
 (unlike C++)
 and relies on this compile-time duck typing instead of virtual 
 functions and
 class-based interfaces (unlike Java and C#).

Actually, C# doesn't care for the interfaces. They are just there to help you implement a compatible iterator. C#'s foreach will accept any type with "T GetEnumerator()", where type T in turn implements "bool MoveNext()" and "S Current { get; }".

Wow. :-) You always learn something new... Thanks, Lionello!

Hehe, you're welcome! L. By the way, using 'duck typing' (instead of implementing IEnumerator/IEnumerable) is the fastest way to iterate in C#, since it won't emit virtual calls and try-finally-Dispose. :)
Jun 20 2009
prev sibling next sibling parent reply BLS <windevguy hotmail.de> writes:
dsimcha wrote:

 Ranges are just pretty much an implicit compile-time interface.  As Ary put it,
 compile time duck typing is a pretty accurate description.  Basically, a range
 doesn't have to *be* a specific *type*, it just has to support certain specific
 *operations*, namely front, popFront, and empty.  As long as it *has* these
 operations, and they compile and return what they're supposed to
(ElementType!(T)
 for front(), void for popFront() and bool for empty), it doesn't matter what
type
 it *is*.

What I don't get is how this (definition) may work on tree based structures. To me it seems that ranges work fine on "linear" data types (whatever) lists, but well, as said I don't get it. :(
Jun 19 2009
parent reply Yigal Chripun <yigal100 gmail.com> writes:
BLS wrote:
 dsimcha wrote:
 
 Ranges are just pretty much an implicit compile-time interface.  As 
 Ary put it,
 compile time duck typing is a pretty accurate description.  Basically, 
 a range
 doesn't have to *be* a specific *type*, it just has to support certain 
 specific
 *operations*, namely front, popFront, and empty.  As long as it *has* 
 these
 operations, and they compile and return what they're supposed to 
 (ElementType!(T)
 for front(), void for popFront() and bool for empty), it doesn't 
 matter what type
 it *is*.

What I don't get is how this (definition) may work on tree based structures. To me it seems that ranges work fine on "linear" data types (whatever) lists, but well, as said I don't get it. :(

as I understand this, A range is alway some linear (iteration) order of the elements. so a tree structure can provide: tree.preOrder() tree.inOrder() tree.postOrder() which return three different ranges representing these orderings of the tree elements. a sub-tree will be of type tree itself and has nothing to do with ranges. you can of course combine the two, e.g.: AVLtree.left.right.left.postOrder; for linear structures. e.g. an array these two operations are the same. int[100] arr; auto slice = arr[40, 50]; slice is both a sub-array and a range of that sub-array.
Jun 19 2009
next sibling parent BLS <windevguy hotmail.de> writes:
Yigal Chripun wrote:
 BLS wrote:
 dsimcha wrote:

 Ranges are just pretty much an implicit compile-time interface.  As 
 Ary put it,
 compile time duck typing is a pretty accurate description.  
 Basically, a range
 doesn't have to *be* a specific *type*, it just has to support 
 certain specific
 *operations*, namely front, popFront, and empty.  As long as it *has* 
 these
 operations, and they compile and return what they're supposed to 
 (ElementType!(T)
 for front(), void for popFront() and bool for empty), it doesn't 
 matter what type
 it *is*.

What I don't get is how this (definition) may work on tree based structures. To me it seems that ranges work fine on "linear" data types (whatever) lists, but well, as said I don't get it. :(

as I understand this, A range is alway some linear (iteration) order of the elements. so a tree structure can provide: tree.preOrder() tree.inOrder() tree.postOrder() which return three different ranges representing these orderings of the tree elements. a sub-tree will be of type tree itself and has nothing to do with ranges. you can of course combine the two, e.g.: AVLtree.left.right.left.postOrder; for linear structures. e.g. an array these two operations are the same. int[100] arr; auto slice = arr[40, 50]; slice is both a sub-array and a range of that sub-array.

Thanks, Yes that makes sense.
Jun 19 2009
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Yigal Chripun:

 so a tree structure can provide:
 tree.preOrder()
 tree.inOrder()
 tree.postOrder()
 which return three different ranges representing these orderings of the 
 tree elements.

This is right, and in some situations it may even be possible to provide a generic scan: tree.scan(ScanType.PREORDER) tree.scan(ScanType.LIMITEDDEPHT) etc. But from my first experiments with the range protocol I have seen that the "pushing" style of opApply (and the syntactically nicer yield in Python and C#) sometimes leads to simpler to write iteration code. For example defining a opApply that scans a tree by pre-order is very easy, you just put the yield (or the equivalent machinery of opApply) where you want to process a leaf of the tree. But when you use the range protocol you have to split that code in parts and you must manage the state yourself manually. This can sometimes be tricky and maybe even bug-prone. ------------------------------- Kristian Kilpi:
Hmm, should the Range methods use some special naming convention? E.g.
rangeFront(), rangePopFront()...?<

Time ago I have suggested something like opFront, opEmpty, etc, like the normal D operators. ------------------------------- Yigal Chripun:
while I agree with the general point about the naming convention, I don't see
how is this a problem here since a range should be a distinct type from the
container.<

Is this always true? In a simple data structure I may want to conflate the iteration protocol with the data structure itself, for example for an array type. Is this a bad/wrong design? Bye, bearophile
Jun 19 2009
parent reply Yigal Chripun <yigal100 gmail.com> writes:
bearophile wrote:
 Yigal Chripun:
 
 so a tree structure can provide:
 tree.preOrder()
 tree.inOrder()
 tree.postOrder()
 which return three different ranges representing these orderings of the 
 tree elements.

This is right, and in some situations it may even be possible to provide a generic scan: tree.scan(ScanType.PREORDER) tree.scan(ScanType.LIMITEDDEPHT) etc.

I thought about using an enum as well, but am unsure what's simpler in this case. I'm not in love with D's enum construct.
 But from my first experiments with the range protocol I have seen that the
"pushing" style of opApply (and the syntactically nicer yield in Python and C#)
sometimes leads to simpler to write iteration code.
 For example defining a opApply that scans a tree by pre-order is very easy,
you just put the yield (or the equivalent machinery of opApply) where you want
to process a leaf of the tree. But when you use the range protocol you have to
split that code in parts and you must manage the state yourself manually. This
can sometimes be tricky and maybe even bug-prone.

what you talk about above is the tradeoff between client iteration (C++ iterators) vs. container iteration (functional each method). being a Python programmer you prefer the second but both have pros and cons. you can always combine both (coroutines/fibers/etc..) but that has a performance cost. all the above have their benefits and you should use what's appropriate for the task at hand, instead of religiously committing yourself to just one. the benefit of client side iteration like with ranges is that client code gets fine grained control over the iteration process. personally, I think opApply should be removed. it provides "push" style iteration which should be provided as a "each" method of the container. the "pull" style of ranges should be used with client side looping.
 
 -------------------------------
 
 Kristian Kilpi:
 
 Hmm, should the Range methods use some special naming convention? E.g.
rangeFront(), rangePopFront()...?<

Time ago I have suggested something like opFront, opEmpty, etc, like the normal D operators. ------------------------------- Yigal Chripun:
 while I agree with the general point about the naming convention, I don't see
how is this a problem here since a range should be a distinct type from the
container.<

Is this always true? In a simple data structure I may want to conflate the iteration protocol with the data structure itself, for example for an array type. Is this a bad/wrong design?

I mentioned arrays in my original post as an exception but I feel that in general it shouldn't be conflated in order to get a cleaner design. where else would it make sense to you to conflate the two except arrays and maybe linked-lists? I think this separation of concerns is a good thing.
 
 Bye,
 bearophile

Jun 19 2009
next sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Yigal Chripun:

personally, I think opApply should be removed. it provides "push" style
iteration which should be provided as a "each" method of the container. the
"pull" style of ranges should be used with client side looping.<

I don't understand what do you mean. Can you show me how you would like to replace the purpose of opApply, maybe with an example? Bye, bearophile
Jun 19 2009
parent reply Yigal Chripun <yigal100 gmail.com> writes:
bearophile wrote:
 Yigal Chripun:
 
 personally, I think opApply should be removed. it provides "push" style
iteration which should be provided as a "each" method of the container. the
"pull" style of ranges should be used with client side looping.<

I don't understand what do you mean. Can you show me how you would like to replace the purpose of opApply, maybe with an example? Bye, bearophile

auto c = new Container(Type)(); .. 1. Container implements iteration, "yields" items in sequence c.each( (Type obj) { ... } ); 2. client code implements iteration, pulls container for items auto r = c.getRange(); // name isn't important, just the semantics while (!r.empty) { // do stuff with current item if (some_external_condition) break; }
Jun 19 2009
parent Robert Fraser <fraserofthenight gmail.com> writes:
Yigal Chripun wrote:
 1. Container implements iteration, "yields" items in sequence
 c.each( (Type obj) { ... } );

So this is just a different bikeshed for opApply?
Jun 19 2009
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Yigal Chripun (yigal100 gmail.com)'s article
 personally, I think opApply should be removed. it provides "push" style
 iteration which should be provided as a "each" method of the container.
 the "pull" style of ranges should be used with client side looping.

But the beauty of a lot of this stuff is that the syntax of iteration stays the same no matter how it works under the hood (builtins, ranges, opApply). This is important for both generic programming and programmer convenience.
Jun 19 2009
parent reply Yigal Chripun <yigal100 gmail.com> writes:
dsimcha wrote:
 == Quote from Yigal Chripun (yigal100 gmail.com)'s article
 personally, I think opApply should be removed. it provides "push" style
 iteration which should be provided as a "each" method of the container.
 the "pull" style of ranges should be used with client side looping.

But the beauty of a lot of this stuff is that the syntax of iteration stays the same no matter how it works under the hood (builtins, ranges, opApply). This is important for both generic programming and programmer convenience.

I'm not sure I follow this. if you just want to do something with all elements than you're right but if you want to do something more complex where you need to use the range interface yourself than you can't use the foreach loop.
Jun 19 2009
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Yigal Chripun (yigal100 gmail.com)'s article
 dsimcha wrote:
 == Quote from Yigal Chripun (yigal100 gmail.com)'s article
 personally, I think opApply should be removed. it provides "push" style
 iteration which should be provided as a "each" method of the container.
 the "pull" style of ranges should be used with client side looping.

But the beauty of a lot of this stuff is that the syntax of iteration stays the same no matter how it works under the hood (builtins, ranges, opApply). This is important for both generic programming and programmer convenience.

if you just want to do something with all elements than you're right but if you want to do something more complex where you need to use the range interface yourself than you can't use the foreach loop.

Yes, but a large portion of the time, iterating over all elements is all you need. For example, if I want to write a generic function to find the mean and standard deviation of some object, I just need to be able to loop over it once. I don't care if it uses a range, builtin arrays, builtin associative arrays, opApply, or pixie dust and magic. The way this is done should be dead simple and consistent regardless of how it works under the hood. Of course if you need to do something more complicated you may need to care about the details, but it's very often the case that you don't.
Jun 19 2009
parent reply Yigal Chripun <yigal100 gmail.com> writes:
dsimcha wrote:
 == Quote from Yigal Chripun (yigal100 gmail.com)'s article
 dsimcha wrote:
 == Quote from Yigal Chripun (yigal100 gmail.com)'s article
 personally, I think opApply should be removed. it provides "push" style
 iteration which should be provided as a "each" method of the container.
 the "pull" style of ranges should be used with client side looping.

same no matter how it works under the hood (builtins, ranges, opApply). This is important for both generic programming and programmer convenience.

if you just want to do something with all elements than you're right but if you want to do something more complex where you need to use the range interface yourself than you can't use the foreach loop.

Yes, but a large portion of the time, iterating over all elements is all you need. For example, if I want to write a generic function to find the mean and standard deviation of some object, I just need to be able to loop over it once. I don't care if it uses a range, builtin arrays, builtin associative arrays, opApply, or pixie dust and magic. The way this is done should be dead simple and consistent regardless of how it works under the hood. Of course if you need to do something more complicated you may need to care about the details, but it's very often the case that you don't.

OK, that does makes sense. i thought that ranged are for those complicated situations but at a second thought there is no reason to have this limit. the one consist way to iterate over the elements regardless of what's under the hood is the foreach loop so my question than is what is/should be the priorities between the different iteration modes? if I have a container that provides both a range and opApply, which would be used by the compiler in the foreach loop?
Jun 20 2009
parent dsimcha <dsimcha yahoo.com> writes:
== Quote from Yigal Chripun (yigal100 gmail.com)'s article
 dsimcha wrote:
 == Quote from Yigal Chripun (yigal100 gmail.com)'s article
 dsimcha wrote:
 == Quote from Yigal Chripun (yigal100 gmail.com)'s article
 personally, I think opApply should be removed. it provides "push" style
 iteration which should be provided as a "each" method of the container.
 the "pull" style of ranges should be used with client side looping.

same no matter how it works under the hood (builtins, ranges, opApply). This is important for both generic programming and programmer convenience.

if you just want to do something with all elements than you're right but if you want to do something more complex where you need to use the range interface yourself than you can't use the foreach loop.

Yes, but a large portion of the time, iterating over all elements is all you need. For example, if I want to write a generic function to find the mean and standard deviation of some object, I just need to be able to loop over it once. I don't care if it uses a range, builtin arrays, builtin associative arrays, opApply, or pixie dust and magic. The way this is done should be dead simple and consistent regardless of how it works under the hood. Of course if you need to do something more complicated you may need to care about the details, but it's very often the case that you don't.

complicated situations but at a second thought there is no reason to have this limit. the one consist way to iterate over the elements regardless of what's under the hood is the foreach loop so my question than is what is/should be the priorities between the different iteration modes? if I have a container that provides both a range and opApply, which would be used by the compiler in the foreach loop?

My vote would be for opApply. Of course there is no perfect answer and the compiler will have to guess which one you mean, but I think opApply is about always the right guess. Ranges are the more flexible interface from the client's perspective, so the fact that you took the time and effort to write an opApply must mean that you want to use it when the client doesn't need that flexibility. As a concrete example, let's say you are iterating over a binary tree. This can be done with ranges, but only with an explicit stack. With opApply, you have control over the call stack and can just use recursion. Therefore, one might want to design two methods of iterating over a tree: An opApply method that uses recursion and a range method that uses an explicit stack but is more flexible for the client.
Jun 20 2009
prev sibling next sibling parent "Kristian Kilpi" <kjkilpi gmail.com> writes:
On Fri, 19 Jun 2009 03:13:11 +0300, Derek Parnell <derek psych.ward> wrote:
 Steve Teale (steve.teale britseyeview.com) wrote:
 Now I admit that these are not method names I would have choosen, as I
 would have preferred names more like ... isEmpty(), getFront(),
 moveForwards(), getBack(), moveBackwards(), getElement(N), addElement(E),
 but the bikeshed gods have more wisdom than me ... and not that I'm
 complaining of course.

I agree. Well, even if the names of the Range methods are a bit 'odd' for me, I guess they are ok... except for empty(). If I have a container that I wan't to use as a Range, I can't use empty() to empty the container (i.e. remove all the elements from it). :( And yes, *I* am complaining here. ;) I'm accustomed to use isXyz() for checking something and xyz() for doing something (e.g. isEmpty() + empty()). What function name should I use for emptying the container then? removeAllElements(), makeEmpty(), or maybe even emptyThisContainer()...? :P Hmm, should the Range methods use some special naming convention? E.g. rangeFront(), rangePopFront()...?
Jun 19 2009
prev sibling parent Tim Matthews <tim.matthews7 gmail.com> writes:
dsimcha wrote:

 
 I suspect that your lack of understanding of ranges stems from lack of
 understanding of templates, since you mention that "noone understands
templates"
 and once you get templates, ranges are ridiculously simple.  If that's the
case,
 then your best bet is probably to learn a little more about templates (which
are
 so fundamental to what makes D special IMHO that I would say that, for all
 practical purposes, if you don't understand templates you don't understand D)
and
 then try to understand ranges again.

I think steve understands templates and he was actually re-quoting the quotes from the digitalmars d docs: http://digitalmars.com/d/2.0/template.html I think that I can safely say that nobody understands template mechanics. -- Richard Deyman http://digitalmars.com/d/2.0/templates-revisited.html "What I am going to tell you about is what we teach our programming students in the third or fourth year of graduate school... It is my task to convince you not to turn away because you don't understand it. You see my programming students don't understand it... That is because I don't understand it. Nobody does." -- Richard Deeman Also I hope this quote summarizes some of the viewpoints of ranges implemented through templates: "If a nuke had a single big red button as a detonator, then you have a lot of power and that is very easy to use. Doesn't necessarily make it the right weapon for the job though."
Jun 19 2009
prev sibling parent reply Robert Fraser <fraserofthenight gmail.com> writes:
Steve Teale wrote:
 template isInputRange(R)
 {
     enum bool isInputRange = is(typeof(
     {
         R r;             // can define a range object
         if (r.empty) {}  // can test for empty
         r.popFront;          // can invoke next
         auto h = r.front; // can get the front of the range
     }()));
 }
 
 I can not possibly be the only D enthusiast who finds this completely
incomprehensible. 

Yeah, that one is a bit tricky, and what makes it worse is that it seems officially sanctioned by Walter/Andrei as the "right way" to check if a type supports some operations. Basically, if you have: is(typeof({ }())); this means "if I made a function containing , would that function compile?". It's a hack which stems from the way the is expression works.
 What is a range?

As others have mentioned, it's just a struct (or other type) that happens to support certain operations.
Jun 18 2009
parent reply grauzone <none example.net> writes:
Robert Fraser wrote:
 Yeah, that one is a bit tricky, and what makes it worse is that it seems 
 officially sanctioned by Walter/Andrei as the "right way" to check if a 
 type supports some operations. Basically, if you have:

Oh, finally someone who shares my concerns! I fear the alternatives would require to much thought and implementation/testing work, so that our gurus prefer the current approach, despite that the semantic of the code depends on silent compilation failures. (Just like SFINAE, maybe even worse.)
 is(typeof({     }()));
 
 this means "if I made a function containing    , would that function 
 compile?". It's a hack which stems from the way the is expression works.

Your example doesn't compile right now. But if you use a string mixin, the code doesn't even have to be syntactically/lexically valid: is(typeof({ mixin(" "); }))
Jun 18 2009
parent reply robert fraser <fraserofthenight gmail.com> writes:
grauzone Wrote:
 Your example doesn't compile right now. 

The " " was meant as an example to be replaced with any code. Yeah, you probably knew that.
 But if you use a string mixin, 
 the code doesn't even have to be syntactically/lexically valid:
 
 is(typeof({ mixin("   "); }))

True -- both these features (string mixins and is-expressions) are rife with pitfalls. But they're both very useful features (if you get rid of string mixins, 25% of my code will stop compiling...). Silent compilation is dangerous indeed, but also very powerful. I was just suggesting we need a better syntax, but I realized we have one: __traits(compiles). Why Andrei isn't using this is the real mystery.
Jun 18 2009
parent reply bearophile <bearophileHUGS lycos.com> writes:
Steve Teale:

I realize that some people with an IQ of 580 will find my questions naive and
misguided - not to mention impertinent, but it seems to me that one of the
responsibilities of being a leader is to explain to less gifted followers what
the fuck is going on.<

If you read the book by Andrei you will probably find enough explanations. But we can also write a Wiki page (see at end of this post). --------------------- Robert Fraser:
 I was just suggesting we need a better syntax, but I realized we have one:
__traits(compiles).<

__traits() isn't a good looking syntax, and its semantic looks almost like a random conflation/accretion of too many different things (and some of them can be done better in other ways). For example in my dlibs I have templates for the following purposes (and most of them are present in Tango too): isAssociativeArray isFloating isIntegral isStaticArray isUnsigned So instead of writing: __traits(isStaticArray, x) I write in D1: IsStaticArray!(x) In D2 you can write: IsStaticArray!x That looks better than the traits. (The syntax of is() too looks like an accretion of mixed things).
Why Andrei isn't using this is the real mystery.<

Maybe he agrees with me that __traits is not nice looking :-) Those underscores make it look like a temporary functionality. is(typeof()) has purposes similar to __traits(compiles, ). Having two syntaxes to do the same thing may be bad. Let's try using traits as you suggest. This it he original written by Steve Teale (copied from elsewhere): template isInputRange(R) { enum bool isInputRange = is(typeof( { R r; // can define a range object if (r.empty) {} // can test for empty r.popFront; // can invoke next auto h = r.front; // can get the front of the range }())); } This may be the traits version (there is no () after the {} after the "compiles"): template isInputRange(R) { enum bool isInputRange = __traits(compiles, { R r; // can define a range object if (r.empty) {} // can test for empty r.popFront; // can invoke next auto h = r.front; // can get the front of the range }); } I don't know if this is correct, but if it's correct, is it better looking? It looks almost the same to me. Both traits() and is() need a more clean and logic redesign, to move elsewhere some of their purposes, and to avoid duplication in their purposes. Andrei has shown to be able to improve the API of the regex module, so maybe he can find a better design for is() and traits(). If types become first-class at compile time, of type "type", then you can remove some purposes from is() too, you can do: type t1 = int; type t2 = float; static if (t1 != t2) {... Instead of: alias int t1; alias float t2; static if (!is(t1 == t2)) {... -------------------------- Derek Parnell: Thank you Derek Parnell for your nice summary about ranges: with to your post my understanding of this topic has gone from 10% to 15% :-) There are things I don't understand from what you have written:
OutputRange - This is an InputRange with the extra capability of being able to
add elements to the range. In addition to the InputRange methods, it must also
provide a method that adds a new element to the range, such that it becomes the
current element. That method must be called 'put(E)' where 'E' is the new
element.<

I guess a single linked list can be seen as an OutputRange then. You can add an item where you are and scan it forward (unfortunately linked listes today are dead, they are never an efficient solution on modern CPUs) In what othr situations you may use/need an OutputRange? In a file, as in a stack, you can only add in a very specific point (the end, in files, or replace the current item).
ForwardRange - This is an InputRange with the extra capability of being able
checkpoint the current first 'cursor' position simply by copying the range.
When you copy an plain InputRange the copied range starts again from the
absolute first element, but a copied ForwardRange starts at whatever was the
current first element in the source range.<

I don't understand and I don't know what checkpointing may mean there. I suggest to explain those things better, and then add 3 or more examples (very different from each other, complete, real-world and ready-to-be-copied-pasted-and-run, like you can find in every page of Borland Delphi documentation) for each kind of range. And then to put the page on the D Wiki :-)
Now I admit that these are not method names I would have choosen, as I would
have preferred names more like<

Andrei has shown that inventing very good names for those methods isn't easy... And putting lot of uppercase letters in the middle of those names isn't nice, nor handy, and it's visually noisy. Bye, bearophile
Jun 18 2009
next sibling parent Derek Parnell <derek psych.ward> writes:
On Thu, 18 Jun 2009 21:00:08 -0400, bearophile wrote:

 Thank you Derek Parnell for your nice summary about ranges:
 with to your post my understanding of this topic has gone
 from 10% to 15% :-)

LOL ... glad to have helped a tiny bit.
 There are things I don't understand from what you have written:
 
OutputRange ...


I haven't got a clue. I'm only trying to put into simpler words what I read in the official documentation.
ForwardRange ...

I don't understand and I don't know what checkpointing may mean there.

It's just a way to save your place in an iteration so that presumably you can come back to that spot later on.
 I suggest to explain those things better, and then add 3 or more examples
 (very different from each other, complete, real-world and
 ready-to-be-copied-pasted-and-run, like you can find in every page of
 Borland Delphi documentation) for each kind of range. And then to put
 the page on the D Wiki :-)

That would be nice. Hmmm... I'll see if I can do something ...
Now I admit that these are not method names I would have choosen ...

Andrei has shown that inventing very good names for those methods isn't easy...

Yes, he certainly has.
 And putting lot of uppercase letters in the middle of those names
 isn't nice, nor handy, and it's visually noisy.

Eye-of-the-beholder situation. Whether one uses "getelement", "get_element", "GetElement", "Get_Element", "getElement", "GETELEMENT", "element.get", ... is beside the point. What I was trying to show was that the current names do not intuitively tell me what is the purpose of the methods. Does 'empty()' return a Boolean that tells me if the set is empty or not, or does it return an empty set, or does it cause the set to become empty, ??? A method name that consists of a single word that can be interpreted as an adjective or a verb or a noun, etc, is ambiguous, IMO. That is why in imperative languages I prefer to see method names that reduce the potential for ambiguous interpretations by using the form <verb>[<adjective>]<noun> is_empty get_front add_element get_background_color etc ... Of course, if an unambiguous name exists it should be used, and there are also abbreviations that can be employed. But anyhow, I digress as this is just a personal style issue and not worth discussing at this point. -- Derek Parnell Melbourne, Australia skype: derek.j.parnell
Jun 18 2009
prev sibling next sibling parent reply Robert Fraser <fraserofthenight gmail.com> writes:
bearophile wrote:
 template isInputRange(R) {
     enum bool isInputRange = __traits(compiles, {
         R r;              // can define a range object
         if (r.empty) {}   // can test for empty
         r.popFront;       // can invoke next
         auto h = r.front; // can get the front of the range
     });
 }
 
 I don't know if this is correct, but if it's correct, is it better looking? It
looks almost the same to me.

Eh, it has the word "compiles" in it... You're right, though, it's not great.
 I guess a single linked list can be seen as an OutputRange then. You can add
an item where you are and scan it forward (unfortunately linked listes today
are dead, they are never an efficient solution on modern CPUs)

LinkedList!(T) is basically useless. But how many times have you used a structure with a "next" and/or "previous" pointer? How about separate chaining in hash tables? "parent" pointers (forms a linked list up to the root for trees, also applies to GUI widgets, French fries, directory hierarchies, etc.)? Linked lists are *everywhere*, they're just generally implicit in some structure and not very long.
 In what othr situations you may use/need an OutputRange? In a file, as in a
stack, you can only add in a very specific point (the end, in files, or replace
the current item). 

I think an OutputRange doesn't have to be an InputRange. It just needs put().
Jun 18 2009
parent Derek Parnell <derek psych.ward> writes:
On Thu, 18 Jun 2009 19:07:06 -0700, Robert Fraser wrote:

 I think an OutputRange doesn't have to be an InputRange. It just needs 
 put().

You're right. I misread the documentation on that one. -- Derek Parnell Melbourne, Australia skype: derek.j.parnell
Jun 18 2009
prev sibling parent Yigal Chripun <yigal100 gmail.com> writes:
bearophile wrote:
 Steve Teale:
 
 I realize that some people with an IQ of 580 will find my questions naive and
misguided - not to mention impertinent, but it seems to me that one of the
responsibilities of being a leader is to explain to less gifted followers what
the fuck is going on.<

If you read the book by Andrei you will probably find enough explanations. But we can also write a Wiki page (see at end of this post). --------------------- Robert Fraser:
 I was just suggesting we need a better syntax, but I realized we have one:
__traits(compiles).<

__traits() isn't a good looking syntax, and its semantic looks almost like a random conflation/accretion of too many different things (and some of them can be done better in other ways). For example in my dlibs I have templates for the following purposes (and most of them are present in Tango too): isAssociativeArray isFloating isIntegral isStaticArray isUnsigned So instead of writing: __traits(isStaticArray, x) I write in D1: IsStaticArray!(x) In D2 you can write: IsStaticArray!x That looks better than the traits. (The syntax of is() too looks like an accretion of mixed things).
 Why Andrei isn't using this is the real mystery.<

Maybe he agrees with me that __traits is not nice looking :-) Those underscores make it look like a temporary functionality. is(typeof()) has purposes similar to __traits(compiles, ). Having two syntaxes to do the same thing may be bad. Let's try using traits as you suggest. This it he original written by Steve Teale (copied from elsewhere): template isInputRange(R) { enum bool isInputRange = is(typeof( { R r; // can define a range object if (r.empty) {} // can test for empty r.popFront; // can invoke next auto h = r.front; // can get the front of the range }())); } This may be the traits version (there is no () after the {} after the "compiles"): template isInputRange(R) { enum bool isInputRange = __traits(compiles, { R r; // can define a range object if (r.empty) {} // can test for empty r.popFront; // can invoke next auto h = r.front; // can get the front of the range }); } I don't know if this is correct, but if it's correct, is it better looking? It looks almost the same to me. Both traits() and is() need a more clean and logic redesign, to move elsewhere some of their purposes, and to avoid duplication in their purposes. Andrei has shown to be able to improve the API of the regex module, so maybe he can find a better design for is() and traits(). If types become first-class at compile time, of type "type", then you can remove some purposes from is() too, you can do: type t1 = int; type t2 = float; static if (t1 != t2) {... Instead of: alias int t1; alias float t2; static if (!is(t1 == t2)) {... -------------------------- Derek Parnell: Thank you Derek Parnell for your nice summary about ranges: with to your post my understanding of this topic has gone from 10% to 15% :-) There are things I don't understand from what you have written:
 OutputRange - This is an InputRange with the extra capability of being able to
add elements to the range. In addition to the InputRange methods, it must also
provide a method that adds a new element to the range, such that it becomes the
current element. That method must be called 'put(E)' where 'E' is the new
element.<

I guess a single linked list can be seen as an OutputRange then. You can add an item where you are and scan it forward (unfortunately linked listes today are dead, they are never an efficient solution on modern CPUs) In what othr situations you may use/need an OutputRange? In a file, as in a stack, you can only add in a very specific point (the end, in files, or replace the current item).
 ForwardRange - This is an InputRange with the extra capability of being able
checkpoint the current first 'cursor' position simply by copying the range.
When you copy an plain InputRange the copied range starts again from the
absolute first element, but a copied ForwardRange starts at whatever was the
current first element in the source range.<

I don't understand and I don't know what checkpointing may mean there. I suggest to explain those things better, and then add 3 or more examples (very different from each other, complete, real-world and ready-to-be-copied-pasted-and-run, like you can find in every page of Borland Delphi documentation) for each kind of range. And then to put the page on the D Wiki :-)
 Now I admit that these are not method names I would have choosen, as I would
have preferred names more like<

Andrei has shown that inventing very good names for those methods isn't easy... And putting lot of uppercase letters in the middle of those names isn't nice, nor handy, and it's visually noisy. Bye, bearophile

we all know that D's compile-time features are a complete mess. also, duck-typing IMHO has no place in a statically typed language, that's just inconsistent for the language as a whole and confusing for the users.
Jun 19 2009