www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - DMD 0.170 release

reply Walter Bright <newshound digitalmars.com> writes:
Added foreach_reverse, which addresses a serious shortcoming.

http://www.digitalmars.com/d/changelog.html
Oct 17 2006
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.
 
 http://www.digitalmars.com/d/changelog.html

Lots of background for the foreach improvements in: http://www.digitalmars.com/d/archives/digitalmars/D/17320.html
Oct 17 2006
next sibling parent reply Ary Manzana <asterite gmail.com> writes:
Walter Bright wrote:
 Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

Lots of background for the foreach improvements in: http://www.digitalmars.com/d/archives/digitalmars/D/17320.html

What about trees? Now I want foreach_inorder, foreach_preorder and foreach_postorder. :-) What about classes having a function that returns the "opApply" needed? Something like this: --- class Tree { int delegate(int delegate(inout int)) inorder() { return delegate int(int delegate(inout uint) dg) { // inorder traversal }; } int delegate(int delegate(inout int)) preorder() { return delegate int(int delegate(inout int) dg) { // preorder traversal }; } int delegate(int delegate(inout int)) postorder() { return delegate int(int delegate(inout int) dg) { // postorder traversal }; } // This still works, it is the default traversal int opApply(int delegate(inout int) dg) { // default traversal } } void main() { Tree t = giveMeSomeTree(); foreach(int i : t.inorder) { // something } foreach(int i : t.preorder) { // something } foreach(int i : t.postorder) { // something } foreach(int i : t) { // something } } --- Could something like this be done? I think it has the clearest syntax: no new keywords needed and very flexible. The compiler should check that the right side of the foreach is an array, or a class or struct having opApply, or a delegate of the singature I mentioned before. Ary
Oct 17 2006
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Ary Manzana wrote:
 Walter Bright wrote:
 Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

Lots of background for the foreach improvements in: http://www.digitalmars.com/d/archives/digitalmars/D/17320.html

What about trees? Now I want foreach_inorder, foreach_preorder and foreach_postorder. :-)

You know I was thinking about this a bit last night, but couldn't come up with a good syntax. But the basic idea was that since "for each" doesn't imply an order in which elements will be visited, perhaps the order could somehow be specified separately from the 'foreach' symbol. However, for classes an obvious alternative would be to use proxy objects, similar to iterators, that expose the correct algorithm in their opApply.
 What about classes having a function that returns the "opApply" needed? 
 Something like this:
 
 ---
 class Tree {
     
     int delegate(int delegate(inout int)) inorder() {
         return delegate int(int delegate(inout uint) dg) {
             // inorder traversal
         };
     }
 
         int delegate(int delegate(inout int)) preorder() {
         return delegate int(int delegate(inout int) dg) {
             // preorder traversal
         };
     }
 
         int delegate(int delegate(inout int)) postorder() {
         return delegate int(int delegate(inout int) dg) {
             // postorder traversal
         };
     }
 
     // This still works, it is the default traversal
         int opApply(int delegate(inout int) dg) {
         // default traversal
     }
     
 }
 
 void main() {
     Tree t = giveMeSomeTree();
     
     foreach(int i : t.inorder) {
         // something
         }
 
     foreach(int i : t.preorder) {
         // something
         }
 
     foreach(int i : t.postorder) {
         // something
         }
 
     foreach(int i : t) {
         // something
         }
 
 }
 ---
 
 Could something like this be done? I think it has the clearest syntax: 
 no new keywords needed and very flexible. The compiler should check that 
 the right side of the foreach is an array, or a class or struct having 
 opApply, or a delegate of the singature I mentioned before.

Yeah, something like that :-) Sean
Oct 17 2006
parent reply John Reimer <terminal.node gmail.com> writes:
Well, I feel a little naggy again so take this with as much salt as
you think it warrants.  But I'm beyond really getting worked up
about the D sega anymore; it mostly won't matter or doesn't matter
to me... much.  Committee or not, Walter seems to make language
design an ... um... interesting pasttime: his decisions are
sometimes excellent, sometimes spontaneous and abrupt, sometimes
unwarranted.  Why leave to a committee what one designer can
accomplish with flourish. ;D

I have to agree with Sean and Ary.  My own opinion: I don't really
understand why "foreach_reverse" was, once again, just tossed into
the language with (what seems to be) a minimum of discussion?  Or
should I really be surprised anymore -- this is becoming a regular
habit of his now, and I begin to wonder what's motivating him...
maybe a 1.0 version?  Yet, I do recall that Walter was getting
itchy fingers when he realized that a reverse iterator was
necessary to make D competitive with C++ (?).  And here we have it,
another quick addition of an ugly syntax, a tacky looking keyword
that is as lovely as a bandaid bridging a broken bone.

I thought D was about clean design. Isn't the trick for fixing this
less about adding another keyword and more about thinking through a
solution that's widely applicable.  Does "foreach_reverse" really
qualify as orthogonal?  If we look at other languages (especially
functional varieties) adding a keyword for each new traversal
syntax doesn't appear to be the order of the day.  If I recall
correctly it's more about properties and modifiers of the
list/expressions themselves (not sure if that was worded clearly).
Cannot foreach be extended in the same manner... "foreach" appears
to fit its purpose well. As Sean indicated: "that foreach doesn't
imply an order in which elements will be visited".  I'm sure the
keyword can be reused in the fashion of reversal as well.

Well, will you look at that.  Isn't that irony?  We got our rolls
reversed, I think.  I used to be Walter that was hesitant to add
keywords to the language.  Go figure! :D

-JJR
Oct 17 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
John Reimer wrote:
 I have to agree with Sean and Ary.  My own opinion: I don't really
 understand why "foreach_reverse" was, once again, just tossed into
 the language with (what seems to be) a minimum of discussion?

There was quite a bit of discussion. The thread was a bit old, but that doesn't make it less relevant: http://www.digitalmars.com/d/archives/digitalmars/D/17320.html
 Well, will you look at that.  Isn't that irony?  We got our rolls
 reversed, I think.  I used to be Walter that was hesitant to add
 keywords to the language.  Go figure! :D

I was reluctant to do it for a long time for that reason. It's just that no better solution emerged.
Oct 17 2006
next sibling parent reply John Reimer <terminal.node gmail.com> writes:
Walter said:
" There was quite a bit of discussion. The thread was a bit old, bt
that doesn't make it less relevant: "

Ah, ok.  I stand corrected on that aspect of my critique.

-JJR
Oct 17 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
John Reimer wrote:
 Ah, ok.  I stand corrected on that aspect of my critique.

I'll give some more lame justifications: There's been some talk about Boost recently in the n.g. (here and in comp.lang.c++) about if what Boost does is really worth it, or if it's just a lot of show-how-clever-I-am falderol. The general idea among the Boost people is that if there's any way possible it could be done in a library, rather than the core, then that's the way it should be done. I don't agree with that idea. I think Boost stretches C++ past the breaking point, and rather than showing how powerful C++ is, shows instead that the C++ core lacks power. Some of the shortcoming workarounds in Boost are just incredible, in the dogged persistence of their inventors to somehow make them work. Even so, the Boost results still wind up with serious holes in them. If some crucial features are added to the core language, then much of Boost either becomes irrelevant, or at least becomes far simpler and straightforward to implement. So let's take a simple example, not from Boost, but from its earlier incarnation STL. STL has an algorithms section, and one of those is for_each. A glaring shortcoming of for_each is you have to supply a function pointer to it - you cannot just supply a statement in { }. With foreach as a supported core language statement, it can be made to work in the general case, and it can be made to generate relevant error messages when used incorrectly. foreach is so darned useful, it seems a shame to have to do it with clumsy, limited hacks like std::for_each. STL generalizes iteration across a collection using a special iterator type. One needs to be created for each collection class. The iterators are then used in the implementation of STL algorithms. There are 3 kinds of iterators: forward, reverse, and random access. There's a serious problem with iterators, though - they require the collection to be accessible in a serialized way, when many data structures (such as binary trees) are not easily traversed that way (recursive descent for them). So I've been interested in having D algorithms and collections not need iterator types at all. I've been experimenting with doing STL's algorithms in D, and it became clear that to make them complete, reverse iteration was necessary. foreach handles forward iteration, and opIndex handles random access. Various ways of doing reverse traversal without core support always seemed to involve creating dummy classes and other hackish stuff. Promoting it to a supported statement makes it pretty clean for the user to understand and use. Essentially, I think foreach_reverse is the missing piece to be able to implement all of STL's algorithms code for D.
Oct 17 2006
next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Walter Bright wrote:
 John Reimer wrote:
 Ah, ok.  I stand corrected on that aspect of my critique.

I'll give some more lame justifications: ... So I've been interested in having D algorithms and collections not need iterator types at all. I've been experimenting with doing STL's algorithms in D, and it became clear that to make them complete, reverse iteration was necessary. foreach handles forward iteration, and opIndex handles random access. Various ways of doing reverse traversal without core support always seemed to involve creating dummy classes and other hackish stuff. Promoting it to a supported statement makes it pretty clean for the user to understand and use. Essentially, I think foreach_reverse is the missing piece to be able to implement all of STL's algorithms code for D.

I don't see how it helps. If you can already do: foreach(T item; &collection.reversed()) { } isn't that alone enough to be able to implement all of STL's algorithms without adding a "foreach_reverse"? In fact I'd argue that adding foreach_reverse does nothing more to make STL algorithms implementable. If I'm trying to implement something like std::copy, how is foreach_reverse going to help me do that generically? Users can't pass 'foreach_reverse' in as an argument if they want to make a backwards copy of something. But they can certainly pass &collection.reversed() in as one. And -- wouldn't it be nice if the original designer of the class forgot to write a reversed(), if I could write one and do foreach(T item; reversed(collection)) { } (without dummy classes and hackish stuff being required). :-) --bb
Oct 17 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Bill Baxter wrote:
 I don't see how it helps.  If you can already do:
    foreach(T item; &collection.reversed()) { }

That doesn't work for arrays.
Oct 17 2006
next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Walter Bright wrote:
 Bill Baxter wrote:
 I don't see how it helps.  If you can already do:
    foreach(T item; &collection.reversed()) { }

That doesn't work for arrays.

I see. I didn't realize the compiler special-cased arrays with foreach. I see that also extends to every built-in behavior that can be mimicked by operator overloading. That's disappointing. It would be much more consistent if something[4] could *always* be substituted with something.opIndex(4). Or if foreach(a; something) could *always* be substituted with foreach(a; &something.opApply). That doesn't mean that arrays have to be classes, just that it has to look like one to the user. Same way they now have .length, but that doesn't mean they are classes/structs. You can still use whatever optimizations or special cases you want in the compiler to speed it up. Hmmm. Well anyway, even if array.reversed() isn't going to work, I still think foreach(T item; reversed(collection)) { } could be the solution. In any case you've got to have a reasonable story for how to handle specific iteration strategies being bolted on after the fact. I.e. I've got a BorgCollection class and I want an iterator that returns only the borg's which are of type KlingonBorg. Unfortunately the BorgCollection designer didn't foresee this need. There should be a reasonable way for me to write a klingonBorgIter function so I can say foreach(KlingonBorg b; klingonBorgIter(borg_collection)) { } I can do that now. Tom S showed how. But you say that requires "dummy classes and hackish stuff" and so is not good enough as a solution for the core iteration implementation. So *make* it good enough! Figure out how to make it work, then apply that one technique mercilessly and consistently everywhere. --bb
Oct 17 2006
prev sibling next sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Walter Bright wrote:
 Bill Baxter wrote:
 I don't see how it helps.  If you can already do:
    foreach(T item; &collection.reversed()) { }

That doesn't work for arrays.

In what way does it not work? I have been doing: foreach(x; "abcd".reverseView()) writef("%s",x); prints "dcba" For any type of built in array for a very long time (long before 0.170), and it certainly seems to work for me. I also do things like: foreach(x; "aBcDeF".select(&isLowerCase)) writef("%s",x); prints "ace" Making custom foreachable iterators is not a problem in D. It is custom single-step iterators that I havn't found a neat solution for yet. I.e., as Sean says, being able to iterate through two containers sequentially. The above versions do use a (as you call it) "dummy" struct that contains an opApply. If function-escaping delegates were implemented, I don't think even the "dummy" struct would be needed, but I don't agree that having a struct ReverseIterator(T:T[]) {... mixin opApplyImpl; } is that much of a hack. /Oskar
Oct 18 2006
next sibling parent reply Bill Baxter <wbaxter gmail.com> writes:
Oskar Linde wrote:
 Walter Bright wrote:
 
 Bill Baxter wrote:

 I don't see how it helps.  If you can already do:
    foreach(T item; &collection.reversed()) { }

That doesn't work for arrays.

In what way does it not work? I have been doing: foreach(x; "abcd".reverseView()) writef("%s",x); prints "dcba" For any type of built in array for a very long time (long before 0.170), and it certainly seems to work for me.

How do you do that? I just get : undefined identifier reverseView : function expected before (), not reverseView of type int : cannot infer type for x
Oct 18 2006
parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Bill Baxter wrote:
 Oskar Linde wrote:
 Walter Bright wrote:

 Bill Baxter wrote:

 I don't see how it helps.  If you can already do:
    foreach(T item; &collection.reversed()) { }

That doesn't work for arrays.

In what way does it not work? I have been doing: foreach(x; "abcd".reverseView()) writef("%s",x); prints "dcba" For any type of built in array for a very long time (long before 0.170), and it certainly seems to work for me.

How do you do that? I just get : undefined identifier reverseView : function expected before (), not reverseView of type int : cannot infer type for x

Sorry. I wasn't very clear on this in my post. Here is a simple implementation that runs: struct ReverseIterator(T:T[]) { T[] array; int opApply(int delegate(inout T) dg) { for (int i = array.length-1; i >= 0; i--) { if (auto status = dg(array[i])) return status; } return 0; } } ReverseIterator!(Array) reverseView(Array)(Array array) { ReverseIterator!(Array) iter; // = {array} => ICE iter.array = array; return iter; } import std.stdio; void main() { foreach(x; "abcd".reverseView()) writef("%s",x); }
Oct 18 2006
parent Bill Baxter <wbaxter gmail.com> writes:
Oskar Linde wrote:
 Bill Baxter wrote:
 
 Oskar Linde wrote:

 Walter Bright wrote:

 Bill Baxter wrote:

foreach(x; "abcd".reverseView()) writef("%s",x); prints "dcba" For any type of built in array for a very long time (long before 0.170), and it certainly seems to work for me.

How do you do that? I just get : undefined identifier reverseView : function expected before (), not reverseView of type int : cannot infer type for x

Sorry. I wasn't very clear on this in my post. Here is a simple implementation that runs: ...

Ok, I see. Yeh, I just yesterday learned about this trick of defining methods for array classes (after I sent the message). It's very well hidden in the spec. ;-) Thanks for taking the time to make that example. --bb
Oct 18 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Oskar Linde wrote:
 Walter Bright wrote:
 Bill Baxter wrote:
 I don't see how it helps.  If you can already do:
    foreach(T item; &collection.reversed()) { }

That doesn't work for arrays.

In what way does it not work? I have been doing: foreach(x; "abcd".reverseView()) writef("%s",x); prints "dcba"

Try that, along with foreach_reverse, and look at the generated code.
Oct 18 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
Walter Bright wrote:
 Oskar Linde wrote:
 
 Walter Bright wrote:

 Bill Baxter wrote:

 I don't see how it helps.  If you can already do:
    foreach(T item; &collection.reversed()) { }

That doesn't work for arrays.

In what way does it not work? I have been doing: foreach(x; "abcd".reverseView()) writef("%s",x); prints "dcba"

Try that, along with foreach_reverse, and look at the generated code.

Hmm. So that's the main issue then, is it? To have a reverse iteration on arrays that's as close to a hand-written for-loop as possible? If you could only think of some way to automatically optimize that case to generate the same code... Is it totally hopeless? --bb
Oct 18 2006
parent Walter Bright <newshound digitalmars.com> writes:
Bill Baxter wrote:
 Hmm.  So that's the main issue then, is it?  To have a reverse iteration 
 on arrays that's as close to a hand-written for-loop as possible?

The major issue is that foreach will usually be used on arrays, and it had better produce good code for them, or else people will eshew it and stick with for.
 If you could only think of some way to automatically optimize that case 
 to generate the same code...  Is it totally hopeless?

Trying to recognize it out of an opApply is rather difficult.
Oct 18 2006
prev sibling parent reply Ary Manzana <asterite gmail.com> writes:
Walter Bright wrote:
 Bill Baxter wrote:
 I don't see how it helps.  If you can already do:
    foreach(T item; &collection.reversed()) { }

That doesn't work for arrays.

Is "foreach_reverse" just there for arrays? To me it dosen't bother to have a new keyword, but if it just exists to do: for(int i = array.length - ; i >= 0; i--) { // ... } then it is realy superflous. "foreach_reversed" just is useful for two things: arrays and lists. For arrays you can always type the code above. For lists, give them a "reversed" method that accepts a delegate, as I wrote. For other types the "foreach" dosen't guarantee the order! (map, tree, set, etc.) So "for(;;)" appears 5% of the time, convert it to "forever". :-) I repeat: is "foreach_reverse" just there for arrays?
Oct 18 2006
parent Bill Baxter <wbaxter gmail.com> writes:
Ary Manzana wrote:
 Walter Bright wrote:
 
 Bill Baxter wrote:

 I don't see how it helps.  If you can already do:
    foreach(T item; &collection.reversed()) { }

That doesn't work for arrays.

Is "foreach_reverse" just there for arrays? To me it dosen't bother to have a new keyword, but if it just exists to do: for(int i = array.length - ; i >= 0; i--) { // ... } then it is realy superflous. "foreach_reversed" just is useful for two things: arrays and lists. For arrays you can always type the code above. For lists, give them a "reversed" method that accepts a delegate, as I wrote. For other types the "foreach" dosen't guarantee the order! (map, tree, set, etc.) So "for(;;)" appears 5% of the time, convert it to "forever". :-) I repeat: is "foreach_reverse" just there for arrays?

No, it at least works for arrays and any class with an "opApplyReverse" method, and for any delegate you feel like passing in. Thus you can even do something nonsensical like: foreach_reverse(int i; &aggregate.opApply()) { } And use foreach_reverse to iterate forwards over aggregate. The only thing foreach_reverse gets you is the ability to magically call the magic method "opApplyReverse" on an object that has it. Otherwise foreach_reverse is pretty much identical to foreach. Oh, and I guess you get the ability to iterate backwards over the built-in types, too, which don't actually have opApply/opApplyReverse methods, but I think their lack of those methods is a missed opportunity. If they just had opApply (or acted like they did) then there wouldn't be any need to make special case rules for them in the language. So basically, without foreach_reverse you can set it up so you can do reverse iteration with something like: foreach(int i; &aggregate.reversed()) or foreach(int i; reversed(aggregate)) With it, you get to say foreach_reverse(int i; aggregate) which actually is equivalent to foreach_reverse(int i; &aggregate.opApplyReverse()) which is also equivalent to foreach(int i; &aggregate.opApplyReverse()) Basically foreach_reverse is 99% identical to foreach, but whereas foreach has a secret pact with all classes to call their opApply method, foreach_reverse has a secret pact to call opApplyReverse. In all other respects they are identical. Really either one can be made to iterate any direction and any way you wish. foreach can iterate backwards if you want, and foreach_reverse can iterate forwards. It is pretty much the antithesis of orthogonality to have multiple, very similar constructs offeing very nearly identical functionality. And meanwhile poor old 'static' is made to do the jobs of twenty big men because we can't afford another keyword to lighten his workload. Yet foreach_reverse gets a seat at the big boys' table just for knowing how to call opApplyReverse()? Doesn't seem reasonable to me. But it could be worse. At least foreach_reverse doesn't steal your socks or eat babies. He is pretty easy to ignore if you don't like him. --bb
Oct 18 2006
prev sibling next sibling parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 
 So I've been interested in having D algorithms and collections not need 
 iterator types at all. I've been experimenting with doing STL's 
 algorithms in D, and it became clear that to make them complete, reverse 
 iteration was necessary. foreach handles forward iteration, and opIndex 
 handles random access. Various ways of doing reverse traversal without 
 core support always seemed to involve creating dummy classes and other 
 hackish stuff. Promoting it to a supported statement makes it pretty 
 clean for the user to understand and use.
 
 Essentially, I think foreach_reverse is the missing piece to be able to 
 implement all of STL's algorithms code for D.

I think I agree, but for the sake of argument, how would D handle 'find' operations on sequences that don't support opIndex? At some point, a generalizable bookmark is almost necessary for a faithful implementation of some C++ algorithms. Also, many of these algorithms also require iteration across two sequences simultaneously, which doesn't map very cleanly into foreach. Consider a substring-style find operation (std::search), for example, where both the pattern and target types do not support opIndex or opSlice. I might argue that it's a bit silly or unrealistic to desire such an operation, but the C++ algorithm library does support it. Sean
Oct 17 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:
 I think I agree, but for the sake of argument, how would D handle 'find' 
  operations on sequences that don't support opIndex?  At some point, a 
 generalizable bookmark is almost necessary for a faithful implementation 
 of some C++ algorithms.  Also, many of these algorithms also require 
 iteration across two sequences simultaneously, which doesn't map very 
 cleanly into foreach.  Consider a substring-style find operation 
 (std::search), for example, where both the pattern and target types do 
 not support opIndex or opSlice.  I might argue that it's a bit silly or 
 unrealistic to desire such an operation, but the C++ algorithm library 
 does support it.

I think the target types will have to support opIndex or opSlice.
Oct 17 2006
parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 Sean Kelly wrote:
 I think I agree, but for the sake of argument, how would D handle 
 'find'  operations on sequences that don't support opIndex?  At some 
 point, a generalizable bookmark is almost necessary for a faithful 
 implementation of some C++ algorithms.  Also, many of these algorithms 
 also require iteration across two sequences simultaneously, which 
 doesn't map very cleanly into foreach.  Consider a substring-style 
 find operation (std::search), for example, where both the pattern and 
 target types do not support opIndex or opSlice.  I might argue that 
 it's a bit silly or unrealistic to desire such an operation, but the 
 C++ algorithm library does support it.

I think the target types will have to support opIndex or opSlice.

Forgive me for resurrecting a horribly battered equine, but I was thinking about this a bit tonight and I've decided that foreach, foreach_reverse, and array operations are not a sufficient general substitute for C++ iterators. For example, let's say I want to compute the set union of two sorted ranges, one of size M, the other of size N. By iterating across the two ranges simultaneously is is easy to see that the complexity for the operation will be max(M,N). In C++ this is easily accomplished using forward iterators, and the ranges can be anything from arrays to SQL result sets. In D however, there is no way to iterate across multiple ranges simultaneously using foreach, so opIndex must be used instead. With containers that have a constant-time lookup cost this isn't a big deal, but what if these containers are binary trees? The complexity for such an operation would be M(log(M)) + N(log(N)). From this it seems clear that foreach is not sufficiently adaptable to meet the needs of all sequential algorithms and opIndex is not a reasonable substitute for all cases where foreach may not be used. What alternatives do we have? So far, iterator variants are all I've been able to come up with. Sean
Nov 02 2006
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:
 Forgive me for resurrecting a horribly battered equine, but I was 
 thinking about this a bit tonight and I've decided that foreach, 
 foreach_reverse, and array operations are not a sufficient general 
 substitute for C++ iterators.
 
 For example, let's say I want to compute the set union of two sorted 
 ranges, one of size M, the other of size N.  By iterating across the two 
 ranges simultaneously is is easy to see that the complexity for the 
 operation will be max(M,N).  In C++ this is easily accomplished using 
 forward iterators, and the ranges can be anything from arrays to SQL 
 result sets.
 
 In D however, there is no way to iterate across multiple ranges 
 simultaneously using foreach, so opIndex must be used instead.  With 
 containers that have a constant-time lookup cost this isn't a big deal, 
 but what if these containers are binary trees?  The complexity for such 
 an operation would be M(log(M)) + N(log(N)).
 
  From this it seems clear that foreach is not sufficiently adaptable to 
 meet the needs of all sequential algorithms and opIndex is not a 
 reasonable substitute for all cases where foreach may not be used.  What 
 alternatives do we have?  So far, iterator variants are all I've been 
 able to come up with.

You are correct in regards to looping across multiple aggregates simultaneously. On the other hand, C++ iterators aren't a general substitute for opApply. For example, it is not at all easy to turn a recursive data structure (i.e. binary tree) into a linearized iterator.
Nov 02 2006
next sibling parent Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 Sean Kelly wrote:
 Forgive me for resurrecting a horribly battered equine, but I was 
 thinking about this a bit tonight and I've decided that foreach, 
 foreach_reverse, and array operations are not a sufficient general 
 substitute for C++ iterators.

 For example, let's say I want to compute the set union of two sorted 
 ranges, one of size M, the other of size N.  By iterating across the 
 two ranges simultaneously is is easy to see that the complexity for 
 the operation will be max(M,N).  In C++ this is easily accomplished 
 using forward iterators, and the ranges can be anything from arrays to 
 SQL result sets.

 In D however, there is no way to iterate across multiple ranges 
 simultaneously using foreach, so opIndex must be used instead.  With 
 containers that have a constant-time lookup cost this isn't a big 
 deal, but what if these containers are binary trees?  The complexity 
 for such an operation would be M(log(M)) + N(log(N)).

  From this it seems clear that foreach is not sufficiently adaptable 
 to meet the needs of all sequential algorithms and opIndex is not a 
 reasonable substitute for all cases where foreach may not be used.  
 What alternatives do we have?  So far, iterator variants are all I've 
 been able to come up with.

You are correct in regards to looping across multiple aggregates simultaneously. On the other hand, C++ iterators aren't a general substitute for opApply. For example, it is not at all easy to turn a recursive data structure (i.e. binary tree) into a linearized iterator.

Agreed. I think both approaches have merit. I suppose I was merely hoping that foreach would work for everything. Sean
Nov 02 2006
prev sibling parent reply Georg Wrede <georg.wrede nospam.org> writes:
Walter Bright wrote:
 Sean Kelly wrote:
 
 Forgive me for resurrecting a horribly battered equine, but I was 
 thinking about this a bit tonight and I've decided that foreach, 
 foreach_reverse, and array operations are not a sufficient general 
 substitute for C++ iterators.

 For example, let's say I want to compute the set union of two sorted 
 ranges, one of size M, the other of size N.  By iterating across the 
 two ranges simultaneously is is easy to see that the complexity for 
 the operation will be max(M,N).  In C++ this is easily accomplished 
 using forward iterators, and the ranges can be anything from arrays to 
 SQL result sets.

 In D however, there is no way to iterate across multiple ranges 
 simultaneously using foreach, so opIndex must be used instead.  With 
 containers that have a constant-time lookup cost this isn't a big 
 deal, but what if these containers are binary trees?  The complexity 
 for such an operation would be M(log(M)) + N(log(N)).

  From this it seems clear that foreach is not sufficiently adaptable 
 to meet the needs of all sequential algorithms and opIndex is not a 
 reasonable substitute for all cases where foreach may not be used.  
 What alternatives do we have?  So far, iterator variants are all I've 
 been able to come up with.

You are correct in regards to looping across multiple aggregates simultaneously. On the other hand, C++ iterators aren't a general substitute for opApply. For example, it is not at all easy to turn a recursive data structure (i.e. binary tree) into a linearized iterator.

If I'm not missing the essence here, there are several kinds of iterators, and not every data structure should try to provide all of these. For example, an iterator into a tree structure might be breadth-first or depth-first, but one wouldn't expect a linearized (if I understand the term in this context at all) iterator to exist. Conversely, an array is hardly thinkable without a linear iterator. What Stepanov explained to me at length (back when I was studying CS and there was not a single book published on the STL) was that the different containers all have their specific sets of "natural" iterators, and that only where it is convenient or at all implementable, other iterators may exist to them. And that it's not like you have a container and then need a certain iterator to it, but that you choose the container based on what kind of iterators you need in the first place. Then it's about the iterator just being a way to reach every item exactly once. And if you don't seem to get them in the order you want, then you sort the items, say into a list. (Or rethink the problem.) Back to foreach: it's syntactically a very convenient way to go through a trivial collection (i.e. an array or a list). But for non-trivial containers (or data structures), foreach simply is insufficient. You need an iterator. Iterators were invented for the very purpose of walking through a black-box container, if you will. I'd almost say that container-specific iterators are the only way to guarantee the lowest complexity walk-through of an arbitrary black-box container. That said, it is of course customary to provide "wrong" iterators to containers (where at all possible, as conveniences), for example a random access iterator to a linked list. But then the user should stay aware that using such is only for the cases where the choice of container has already been evaluated to be optimal, and where one only occasionally needs to access some of the items in a specific way. In other words, where this need is seldom enough to not warrant a temporary copy (or linking) of the items into a more suitable container. One could of course have foreach actually employ iterators. This gives the ease of coding with foreach combined with the flexiblity, decoupling and orthogonality offered by iterators. But, as in the previous post, even this becomes cumbersome when we're iterating over more than one container simultaneously, especially when they're of different sizes or iterating in non-lockstep. --- In general, the essence and elegance of the STL has not been too prevalent in D libraries or algorithms. With the current expressive power of D, one might expect to soon start seeing some of this.
Nov 03 2006
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Georg Wrede wrote:
 Walter Bright wrote:
 On the other hand, C++ iterators aren't a general substitute for 
 opApply. For example, it is not at all easy to turn a recursive data 
 structure (i.e. binary tree) into a linearized iterator.

If I'm not missing the essence here, there are several kinds of iterators, and not every data structure should try to provide all of these. For example, an iterator into a tree structure might be breadth-first or depth-first, but one wouldn't expect a linearized (if I understand the term in this context at all) iterator to exist. Conversely, an array is hardly thinkable without a linear iterator.

Given the structure: class Node { Node left; Node right; ...data... } how do you iterate that with an iterator? This is what I mean by 'linearizing' it. The STL sidesteps the problem by avoiding providing such a container.
Nov 03 2006
next sibling parent Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 Georg Wrede wrote:
 Walter Bright wrote:
 On the other hand, C++ iterators aren't a general substitute for 
 opApply. For example, it is not at all easy to turn a recursive data 
 structure (i.e. binary tree) into a linearized iterator.

If I'm not missing the essence here, there are several kinds of iterators, and not every data structure should try to provide all of these. For example, an iterator into a tree structure might be breadth-first or depth-first, but one wouldn't expect a linearized (if I understand the term in this context at all) iterator to exist. Conversely, an array is hardly thinkable without a linear iterator.

Given the structure: class Node { Node left; Node right; ...data... } how do you iterate that with an iterator? This is what I mean by 'linearizing' it. The STL sidesteps the problem by avoiding providing such a container.

The problem isn't so much "how" (it's really not terribly difficult) as that the memory requirements and copy semantics for such an iterator could be quite high, and the STL assumes iterators are comparable to pointers in terms of how they may be manipulated. Sean
Nov 04 2006
prev sibling parent Georg Wrede <georg.wrede nospam.org> writes:
Walter Bright wrote:
 Georg Wrede wrote:
 
 Walter Bright wrote:

 On the other hand, C++ iterators aren't a general substitute for 
 opApply. For example, it is not at all easy to turn a recursive data 
 structure (i.e. binary tree) into a linearized iterator.

If I'm not missing the essence here, there are several kinds of iterators, and not every data structure should try to provide all of these. For example, an iterator into a tree structure might be breadth-first or depth-first, but one wouldn't expect a linearized (if I understand the term in this context at all) iterator to exist. Conversely, an array is hardly thinkable without a linear iterator.

Given the structure: class Node { Node left; Node right; ...data... } how do you iterate that with an iterator? This is what I mean by 'linearizing' it. The STL sidesteps the problem by avoiding providing such a container.

You're right. This pointer-to-array semantics kept the iterators primitive, I'd almost forgotten how primitive. So, to traverse the example, one obviously needs an iterator with more state than just the current node. In practice this state would be stored in a private, persistent LIFO.
Nov 05 2006
prev sibling parent Sean Kelly <sean f4.ca> writes:
Georg Wrede wrote:
 
 Back to foreach: it's syntactically a very convenient way to go through 
 a trivial collection (i.e. an array or a list). But for non-trivial 
 containers (or data structures), foreach simply is insufficient. You 
 need an iterator.

Assuming you simply want to visit every element once then I think foreach is fine. In fact, it's generally simpler than implementing an iterator, given an arbitrary container type. Where foreach falls down is if you want to stop after N iterations and resume later. It's possible, but doing so resembles implementing random access iterators for a linked list.
 Iterators were invented for the very purpose of
 walking through a black-box container, if you will. I'd almost say that 
 container-specific iterators are the only way to guarantee the lowest 
 complexity walk-through of an arbitrary black-box container.

I think iterators are intended to represent an arbitrary position in a sequence and present a means for visiting the remaining elements. It's the "arbitrary position" part that foreach can't do.
 One could of course have foreach actually employ iterators. This gives 
 the ease of coding with foreach combined with the flexiblity, decoupling 
 and orthogonality offered by iterators.

Yup, and this is what C++ does with its for_each, transform, and other algorithms.
 But, as in the previous post, even this becomes cumbersome when we're 
 iterating over more than one container simultaneously, especially when 
 they're of different sizes or iterating in non-lockstep.

It's not terribly difficult--just a for loop with two or more iterators and conditions--but I would like to believe that this can be simplified.
 In general, the essence and elegance of the STL has not been too 
 prevalent in D libraries or algorithms. With the current expressive 
 power of D, one might expect to soon start seeing some of this.

I agree. Currently, I've implemented basically all of the C++ algorithm library plus a few additional functions, but only for arrays. Without iterators, I simply don't see the point in extending many of the algorithms to support other container types. opIndex simply doesn't apply well to most other container types. Sean
Nov 04 2006
prev sibling next sibling parent reply Bill Baxter <wbaxter gmail.com> writes:
Sean Kelly wrote:
 Walter Bright wrote:
 
 Sean Kelly wrote:

 I think I agree, but for the sake of argument, how would D handle 
 'find'  operations on sequences that don't support opIndex?  At some 
 point, a generalizable bookmark is almost necessary for a faithful 
 implementation of some C++ algorithms.  Also, many of these 
 algorithms also require iteration across two sequences 
 simultaneously, which doesn't map very cleanly into foreach.  
 Consider a substring-style find operation (std::search), for example, 
 where both the pattern and target types do not support opIndex or 
 opSlice.  I might argue that it's a bit silly or unrealistic to 
 desire such an operation, but the C++ algorithm library does support it.

I think the target types will have to support opIndex or opSlice.

Forgive me for resurrecting a horribly battered equine, but I was thinking about this a bit tonight and I've decided that foreach, foreach_reverse, and array operations are not a sufficient general substitute for C++ iterators. For example, let's say I want to compute the set union of two sorted ranges, one of size M, the other of size N. By iterating across the two ranges simultaneously is is easy to see that the complexity for the operation will be max(M,N). In C++ this is easily accomplished using forward iterators, and the ranges can be anything from arrays to SQL result sets. In D however, there is no way to iterate across multiple ranges simultaneously using foreach, so opIndex must be used instead. With containers that have a constant-time lookup cost this isn't a big deal, but what if these containers are binary trees? The complexity for such an operation would be M(log(M)) + N(log(N)). From this it seems clear that foreach is not sufficiently adaptable to meet the needs of all sequential algorithms and opIndex is not a reasonable substitute for all cases where foreach may not be used. What alternatives do we have? So far, iterator variants are all I've been able to come up with.

It would be sufficient if D had coroutines and opApply were implemented using them. The problem is that once you call an opApply function right now, it has to run to completion. The only way I can see to have multiple opApply style iterators going simultaneously if you could truly suspend execution of one opApply temporarily and run another one for an iteration. In other words, if you're going to use the stack and function state to store iterator state, then the only way to have multiple iterators in different states simultaneously is to be able to have multiple stacks active simultaneously, aka coroutines. --bb
Nov 02 2006
parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Bill Baxter wrote:
 Sean Kelly wrote:
 
 Walter Bright wrote:

 Sean Kelly wrote:

 I think I agree, but for the sake of argument, how would D handle 
 'find'  operations on sequences that don't support opIndex?  At some 
 point, a generalizable bookmark is almost necessary for a faithful 
 implementation of some C++ algorithms.  Also, many of these 
 algorithms also require iteration across two sequences 
 simultaneously, which doesn't map very cleanly into foreach.  
 Consider a substring-style find operation (std::search), for 
 example, where both the pattern and target types do not support 
 opIndex or opSlice.  I might argue that it's a bit silly or 
 unrealistic to desire such an operation, but the C++ algorithm 
 library does support it.

I think the target types will have to support opIndex or opSlice.

Forgive me for resurrecting a horribly battered equine, but I was thinking about this a bit tonight and I've decided that foreach, foreach_reverse, and array operations are not a sufficient general substitute for C++ iterators. For example, let's say I want to compute the set union of two sorted ranges, one of size M, the other of size N. By iterating across the two ranges simultaneously is is easy to see that the complexity for the operation will be max(M,N). In C++ this is easily accomplished using forward iterators, and the ranges can be anything from arrays to SQL result sets. In D however, there is no way to iterate across multiple ranges simultaneously using foreach, so opIndex must be used instead. With containers that have a constant-time lookup cost this isn't a big deal, but what if these containers are binary trees? The complexity for such an operation would be M(log(M)) + N(log(N)). From this it seems clear that foreach is not sufficiently adaptable to meet the needs of all sequential algorithms and opIndex is not a reasonable substitute for all cases where foreach may not be used. What alternatives do we have? So far, iterator variants are all I've been able to come up with.

It would be sufficient if D had coroutines and opApply were implemented using them. The problem is that once you call an opApply function right now, it has to run to completion. The only way I can see to have multiple opApply style iterators going simultaneously if you could truly suspend execution of one opApply temporarily and run another one for an iteration. In other words, if you're going to use the stack and function state to store iterator state, then the only way to have multiple iterators in different states simultaneously is to be able to have multiple stacks active simultaneously, aka coroutines. --bb

Just a thought I had. Would it be possible to emulate this behavior with delegate-as-aggregate? What I'm thinking of (and bear in mind I just rolled out of bed, so I'm at quarter-speed right now ;)) is pass foreach a "driver" delegate that then calls step iterator delegates you've provided. The driver and step iterators would be responsible for maintaining state, and would probably need a reset case (at least the iterators). -- Chris Nicholson-Sauls
Nov 03 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
Chris Nicholson-Sauls wrote:
 Bill Baxter wrote:
 
 Sean Kelly wrote:

 Walter Bright wrote:

 Sean Kelly wrote:

 I think I agree, but for the sake of argument, how would D handle 
 'find'  operations on sequences that don't support opIndex?  At 
 some point, a generalizable bookmark is almost necessary for a 
 faithful implementation of some C++ algorithms.  Also, many of 
 these algorithms also require iteration across two sequences 
 simultaneously, which doesn't map very cleanly into foreach.  
 Consider a substring-style find operation (std::search), for 
 example, where both the pattern and target types do not support 
 opIndex or opSlice.  I might argue that it's a bit silly or 
 unrealistic to desire such an operation, but the C++ algorithm 
 library does support it.

I think the target types will have to support opIndex or opSlice.

Forgive me for resurrecting a horribly battered equine, but I was thinking about this a bit tonight and I've decided that foreach, foreach_reverse, and array operations are not a sufficient general substitute for C++ iterators. For example, let's say I want to compute the set union of two sorted ranges, one of size M, the other of size N. By iterating across the two ranges simultaneously is is easy to see that the complexity for the operation will be max(M,N). In C++ this is easily accomplished using forward iterators, and the ranges can be anything from arrays to SQL result sets. In D however, there is no way to iterate across multiple ranges simultaneously using foreach, so opIndex must be used instead. With containers that have a constant-time lookup cost this isn't a big deal, but what if these containers are binary trees? The complexity for such an operation would be M(log(M)) + N(log(N)). From this it seems clear that foreach is not sufficiently adaptable to meet the needs of all sequential algorithms and opIndex is not a reasonable substitute for all cases where foreach may not be used. What alternatives do we have? So far, iterator variants are all I've been able to come up with.

It would be sufficient if D had coroutines and opApply were implemented using them. The problem is that once you call an opApply function right now, it has to run to completion. The only way I can see to have multiple opApply style iterators going simultaneously if you could truly suspend execution of one opApply temporarily and run another one for an iteration. In other words, if you're going to use the stack and function state to store iterator state, then the only way to have multiple iterators in different states simultaneously is to be able to have multiple stacks active simultaneously, aka coroutines. --bb

Just a thought I had. Would it be possible to emulate this behavior with delegate-as-aggregate? What I'm thinking of (and bear in mind I just rolled out of bed, so I'm at quarter-speed right now ;)) is pass foreach a "driver" delegate that then calls step iterator delegates you've provided. The driver and step iterators would be responsible for maintaining state, and would probably need a reset case (at least the iterators). -- Chris Nicholson-Sauls

I was tinkering around with that. But the problem is that any time you call an opApply you end up inside a function that basically does something like: for (i=0; i<length; i++) { ret = loop_body_dg(my_ith_item[i]); } There's no way I can see to stop that juggernaut before it's done, short of having it return, and if it returns then it'll lose its state. Conceptually what you need is a 'yield' that keeps the current stack frame alive, but returns to the caller. Then you could implement something like a zip() who's opApply calls the opApply's of each of its arguments, which in turn just run one iteration and each yield one value back to the zip(). Zip then packages up the results from one iteration of each of its args into a tuple and yields that back to the foreach block. --bb
Nov 03 2006
parent reply Benji Smith <dlanguage benjismith.net> writes:
Bill Baxter wrote:
 There's no way I can see to stop that juggernaut before it's done, short 
 of having it return, and if it returns then it'll lose its state. 
 Conceptually what you need is a 'yield' that keeps the current stack 
 frame alive, but returns to the caller.

But then your object can only have one iterator at a time, and what if you want to have multiple simultaneous iterators for any given object? The 'yield' keyword can only keep track of state for a single iterator, so this kind of code would fail: foreach (Item outerItem; collection) { foreach (Item innerItem; collection) { doSomething(outerItem, innerItem); } } This should be semantically identical to: for (int i = 0; i < collection.length; i++) { Item outerItem = collection[i]; for (int j = 0; j < collection.length; j++) { Item innerItem = collection[j]; doSomething(outerItem, innerItem); } } But in the 'foreach' example, the 'yield' implementation would get confused (as would the opApply method). If iteration was implemented with iterators (instead of with operator overloading and delegates), and if iterators were implemented as nested classes within the container class definitions, then iterators could access the elements directly, while still keeping their own state information. (Such as a pointer to the next iterable tree-node, in a InOrderTraversalIterator. Or whatever.) For example: class ArrayList { private Item[] items; private Iterable getForwardIterator() { ... } class ForwardIterator : Iterable { private Item* nextItem; // Keeps track of state public bool hasNext() { ... } public Item next() { ... } } } And then I'd iterate through my items like this: foreach (Item outerItem; collection.getForwardIterator()) { foreach (Item innerItem; collection.getForwardIterator()) { doSomething(outerItem, innerItem); } } In most cases, if your iterator can keep track of its own state, and if the iterator is a nested class with access to all of its containing class's members, then the 'yield' keyword is unnecessary. (The most compelling argument for 'yield' is not for the implementation of iterators, but for building generators.) But please, please reconsider the foreach * foreach_reverse implementations. Forcing a collection class to be aware of its own iterables is fugly as can be. --benji
Nov 03 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
Benji Smith wrote:
 Bill Baxter wrote:
 
 There's no way I can see to stop that juggernaut before it's done, 
 short of having it return, and if it returns then it'll lose its 
 state. Conceptually what you need is a 'yield' that keeps the current 
 stack frame alive, but returns to the caller.

But then your object can only have one iterator at a time, and what if you want to have multiple simultaneous iterators for any given object? The 'yield' keyword can only keep track of state for a single iterator, so this kind of code would fail: foreach (Item outerItem; collection) { foreach (Item innerItem; collection) { doSomething(outerItem, innerItem); } }

No it wouldn't. Not if you had support for real coroutines. That's the whole point of coroutines. You can have multiple stack frames active at the same time. Each stack frame for the opApply's in the above case would have its own local iterator state. Now whether or not coroutines are realistically implementable in a systems programming language like D is beyond me. Stackless Python folks did it, but perhaps they're taking advantage of the fact that users of interpreted code are a bit more forgiving about runtime overhead, and the fact that the interpreter has its own notion of the stack that doesn't depend on low-level processor details like EAX registers etc. But technically I don't see any roadblocks. I mean I read somewhere that coroutines are an old assembly programming trick, so the hardware is certainly capable of supporting the paradigm at the low level. It's basically just a jmp plus a manipulation of the stack pointer when it comes right down to it. --bb
Nov 03 2006
next sibling parent Kirk McDonald <kirklin.mcdonald gmail.com> writes:
Bill Baxter wrote:
 Benji Smith wrote:
 Bill Baxter wrote:

 There's no way I can see to stop that juggernaut before it's done, 
 short of having it return, and if it returns then it'll lose its 
 state. Conceptually what you need is a 'yield' that keeps the current 
 stack frame alive, but returns to the caller.

But then your object can only have one iterator at a time, and what if you want to have multiple simultaneous iterators for any given object? The 'yield' keyword can only keep track of state for a single iterator, so this kind of code would fail: foreach (Item outerItem; collection) { foreach (Item innerItem; collection) { doSomething(outerItem, innerItem); } }

No it wouldn't. Not if you had support for real coroutines. That's the whole point of coroutines. You can have multiple stack frames active at the same time. Each stack frame for the opApply's in the above case would have its own local iterator state. Now whether or not coroutines are realistically implementable in a systems programming language like D is beyond me. Stackless Python folks did it, but perhaps they're taking advantage of the fact that users of interpreted code are a bit more forgiving about runtime overhead, and the fact that the interpreter has its own notion of the stack that doesn't depend on low-level processor details like EAX registers etc. But technically I don't see any roadblocks. I mean I read somewhere that coroutines are an old assembly programming trick, so the hardware is certainly capable of supporting the paradigm at the low level. It's basically just a jmp plus a manipulation of the stack pointer when it comes right down to it. --bb

I would direct your attention to StackThreads: http://assertfalse.com/articles/stFAQ.shtml Pyd uses this nifty package to wrap a class's opApply function with Python's iteration interface. (Which uses iterator objects with a .next() method.) The magic may be found in this bit of code: http://www.dsource.org/projects/pyd/browser/trunk/infrastructure/pyd/iteration.d -- Kirk McDonald Pyd: Wrapping Python with D http://pyd.dsource.org
Nov 03 2006
prev sibling parent Walter Bright <newshound digitalmars.com> writes:
Bill Baxter wrote:
 Now whether or not coroutines are realistically implementable in a 
 systems programming language like D is beyond me.  Stackless Python 
 folks did it, but perhaps they're taking advantage of the fact that 
 users of interpreted code are a bit more forgiving about runtime 
 overhead, and the fact that the interpreter has its own notion of the 
 stack that doesn't depend on low-level processor details like EAX 
 registers etc.  But technically I don't see any roadblocks.  I mean I 
 read somewhere that coroutines are an old assembly programming trick, so 
 the hardware is certainly capable of supporting the paradigm at the low 
 level.  It's basically just a jmp plus a manipulation of the stack 
 pointer when it comes right down to it.

It's not so easy to implement in the general case (asm code takes advantage of special, easy cases). To make it work, you need to allocate the stack frame of the coroutine on the heap. Not impossible, but a lot of work involved.
Nov 03 2006
prev sibling next sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Sean Kelly wrote:

  From this it seems clear that foreach is not sufficiently adaptable to 
 meet the needs of all sequential algorithms and opIndex is not a 
 reasonable substitute for all cases where foreach may not be used.  What 
 alternatives do we have?  So far, iterator variants are all I've been 
 able to come up with.

I agree, and I have been saying this countless times. :) Why don't we come up with a standard iterator concept for D? For a forward iterator, C++ has: *i i++ / ++i i != end In the post "Iterators (Was: Re: Lazy eval -- an example issue)" in digitalmars.D ( news://news.digitalmars.com:119/ecmvec$ksl$1 digitaldaemon.com ) I suggested a simple java-style variant: *i.next() i.hasNext() A generic opApply could then be implemented as: template opApplyMixin() { int opApply(int delegate(inout ValueType v) dg) { ValueType *t; while(hasNext()) { t = next(); if (auto status = dg(*t)) return status; } return 0; } } And a simple array iterator wrapper (Could of course be more efficiently implemented): struct ArrayForwardIterator(T) { T[] arr; alias T ValueType; T* next() { arr = arr[1..$]; return arr.ptr-1; } bool hasNext() { return arr.length > 0; } mixin opApplyMixin; } If pointers should be avoided, and since D doesn't have an opDeref, but has lhs/rhs overloads for indexing, another iterator variant could be to use i[] i[]= for rhs, and lhs iterator dereferencing. i++ / ++i could be used instead of .next() if it is any clearer, and so on... It doesn't really matter what convention we pick. For better rather than worse, D doesn't allow us to do as C++ does, make iterators interchangeable with pointers. We may as well pick anything we like as long as the compiler is able to make reasonable efficient code out of it. As I said in the above referenced post, I have been toying with making a template iterator/array algorithm library. I've got a quite substantial proof of concept working, but have not had much time lately. I do love discussions about this though. :) /Oskar
Nov 03 2006
next sibling parent reply Bill Baxter <wbaxter gmail.com> writes:
Oskar Linde wrote:
 Sean Kelly wrote:
 
  From this it seems clear that foreach is not sufficiently adaptable 
 to meet the needs of all sequential algorithms and opIndex is not a 
 reasonable substitute for all cases where foreach may not be used.  
 What alternatives do we have?  So far, iterator variants are all I've 
 been able to come up with.

I agree, and I have been saying this countless times. :) Why don't we come up with a standard iterator concept for D? For a forward iterator, C++ has: *i i++ / ++i i != end

One big concern I have with the current iterators is that the approach supported for the general case is deemed too inefficient for built-in arrays. So arrays are special-cased by the compiler in the foreach logic to become more like a simple for loop. But I want that speed for foreach-ing my own classes too! Why should I be satisfied with less that peak performance for *my* classes if it's not considered good enough for built-in classes? I have to pay this penalty even if my class is a simple wrapper around an array, that say does nothing more than add an opAdd so I can add two arrays together. Plain old C++-style iterators don't have that problem. For simple cases iter++ bascially compiles down to be equivalent to pointer manipulation. --bb
Nov 03 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
You're right about that being a problem with opApply.
Nov 03 2006
parent reply Oskar Linde <olREM OVEnada.kth.se> writes:
Walter Bright wrote:

 You're right about that being a problem with opApply.

Does it have to be? If the body of the opApply is available to the compiler and the delegate parameter is a compile time constant (as it is in the normal foreach case), does anything prevent the compiler from inlining the opApply together with the delegate body? Would there still be a speed hit if this was done? I have many cases that would gain a lot if the compiler inlined functions taking compile time known delegates together with the delegate call. I hope there is nothing fundamental preventing this from happening. /Oskar
Nov 04 2006
parent Walter Bright <newshound digitalmars.com> writes:
Oskar Linde wrote:
 Walter Bright wrote:
 
 You're right about that being a problem with opApply.

Does it have to be? If the body of the opApply is available to the compiler and the delegate parameter is a compile time constant (as it is in the normal foreach case), does anything prevent the compiler from inlining the opApply together with the delegate body? Would there still be a speed hit if this was done? I have many cases that would gain a lot if the compiler inlined functions taking compile time known delegates together with the delegate call. I hope there is nothing fundamental preventing this from happening.

The compiler doesn't inline functions that have loops in them. This isn't a fault in D, but a structural limitation in the way the dmd compiler works. I find opApply particularly slick for things like recursive directory traversals, associative array walking, etc. But for ordinary linear collection types, it is hard to generate code as good from it as pointer stepping.
Nov 04 2006
prev sibling parent reply Sean Kelly <sean f4.ca> writes:
Oskar Linde wrote:
 Sean Kelly wrote:
 
  From this it seems clear that foreach is not sufficiently adaptable 
 to meet the needs of all sequential algorithms and opIndex is not a 
 reasonable substitute for all cases where foreach may not be used.  
 What alternatives do we have?  So far, iterator variants are all I've 
 been able to come up with.

I agree, and I have been saying this countless times. :) Why don't we come up with a standard iterator concept for D? For a forward iterator, C++ has: *i i++ / ++i i != end In the post "Iterators (Was: Re: Lazy eval -- an example issue)" in digitalmars.D ( news://news.digitalmars.com:119/ecmvec$ksl$1 digitaldaemon.com ) I suggested a simple java-style variant: *i.next() i.hasNext()

I think a Java style iterator is the way to go for D. Personally, I basically never find a need for bidirectional iterators, and I only use random access iterators with vectors, which correspond to D's built-in dynamic arrays. Also, a single iterator that knows when it's reached the end of the sequence better suits being used with foreach than the pointer-style iterators of C++. About the only thing I don't like about Java iterators is how they work ;-) Only being able to access the referenced data by calling next() is a bit irritating. That said, it does eliminate the need for iterators to potentially cache the current value when iterating across sequences that don't inherently store data, such as an input stream. Still, I think it's useful to have in an iterator, so perhaps something roughly like this: interface Iterator(T) { T val(); T next(); bool hasNext(); } interface WriteIterator(T) : Iterator(T) { T val( T n ); }
 A generic opApply could then be implemented as:
 
 template opApplyMixin() {
   int opApply(int delegate(inout ValueType v) dg) {
     ValueType *t;
     while(hasNext()) {
       t = next();
       if (auto status = dg(*t))
         return status;
     }
     return 0;
   }
 }
 
 And a simple array iterator wrapper (Could of course be more efficiently 
 implemented):
 
 struct ArrayForwardIterator(T) {
   T[] arr;
   alias T ValueType;
 
   T* next() { arr = arr[1..$]; return arr.ptr-1; }
   bool hasNext() { return arr.length > 0; }
   mixin opApplyMixin;
 }

Looks good.
 If pointers should be avoided, and since D doesn't have an opDeref, but 
 has lhs/rhs overloads for indexing, another iterator variant could be to 
 use
 
 i[]
 i[]=
 
 for rhs, and lhs iterator dereferencing.

I prefer the 'val' approach. It seems a bit more meaningful than something with operators.
 i++ / ++i could be used instead of .next() if it is any clearer, and so 
 on...

I'm not sure how I feel about using structs for iterators (instead of classes). With classes, we can retain some semblance of control over copy semantics, but we can't with structs. And I'm not entirely sure I think we should be able to copy iterators at will--consider Walter's case of an iterator for a traditional binary tree, for example. Also, using structs forces user code to either be hard-coded to work with a specific iterator type or to use templates. And I'll admit I do sort of like the idea of: void myFunction( Iterator!(int) x ) {} being possible.
 It doesn't really matter what convention we pick. For better rather than 
 worse, D doesn't allow us to do as C++ does, make iterators 
 interchangeable with pointers. We may as well pick anything we like as 
 long as the compiler is able to make reasonable efficient code out of it.

Agreed.
 As I said in the above referenced post, I have been toying with making a 
 template iterator/array algorithm library. I've got a quite substantial 
 proof of concept working, but have not had much time lately. I do love 
 discussions about this though. :)

I've been focusing on arrays thus far, but am getting to the point where I'd like to extend some algorithms to work for user-defined containers as well. And that obviously requires a decent convention for how iterators should be implemented. Also, I'll admit that I really enjoy algorithm talk as well :-) Sean
Nov 04 2006
parent reply Sean Kelly <sean f4.ca> writes:
Sean Kelly wrote:
 Still, I think it's useful to have in an 
 iterator, so perhaps something roughly like this:
 
 interface Iterator(T)
 {
     T val();
     T next();
     bool hasNext();
 }

Err... this doesn't work for an iterator returned for an empty container. Perhaps: interface Iterator(T) { T val(); T next(); bool atEnd(); } Anyway, you get the idea. Sean
Nov 04 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
Sean Kelly wrote:
 Sean Kelly wrote:
 
 Still, I think it's useful to have in an iterator, so perhaps 
 something roughly like this:

 interface Iterator(T)
 {
     T val();
     T next();
     bool hasNext();
 }

Err... this doesn't work for an iterator returned for an empty container.

It's fine if you define the behavior to be that you have to call next() once to get the first value. So for iteration idiom becomes: T v; while(c.hasNext()) ) { }
Nov 05 2006
next sibling parent reply Bill Baxter <wbaxter gmail.com> writes:
Bill Baxter wrote:
 Sean Kelly wrote:
 
 Sean Kelly wrote:

 Still, I think it's useful to have in an iterator, so perhaps 
 something roughly like this:

 interface Iterator(T)
 {
     T val();
     T next();
     bool hasNext();
 }

Err... this doesn't work for an iterator returned for an empty container.

It's fine if you define the behavior to be that you have to call next() once to get the first value. So for iteration idiom becomes: T v; while(c.hasNext()) ) { }

...another victem of Ctrl+Enter.... while(c.hasNext()) { T v = c.next(); } I think an alias for T also needs to be a part of the definition of the iterator. Like alias T value_type. Also would do you do a mutating iteration over collections of basic value types (eg floats), structs, and classes? I.e. if you want to do something like: while(c.hasNext()) { T v = c.next(); v += 2; } where T could be float, struct, or class. Ok, class case is fine, but the other two aren't clear to me. Mutable iterator over structs could maybe return a pointer to each struct. Basic value type, I'm not sure. Just woke up though... maybe it's obvious and my head just isn't working yet. --bb
Nov 05 2006
parent Sean Kelly <sean f4.ca> writes:
Bill Baxter wrote:
 Bill Baxter wrote:
 Sean Kelly wrote:

 Sean Kelly wrote:

 Still, I think it's useful to have in an iterator, so perhaps 
 something roughly like this:

 interface Iterator(T)
 {
     T val();
     T next();
     bool hasNext();
 }

Err... this doesn't work for an iterator returned for an empty container.

It's fine if you define the behavior to be that you have to call next() once to get the first value. So for iteration idiom becomes: T v; while(c.hasNext()) ) { }

....another victem of Ctrl+Enter.... while(c.hasNext()) { T v = c.next(); } I think an alias for T also needs to be a part of the definition of the iterator. Like alias T value_type.

I don't think it's necessary, but it may be convenient. For example, this should work: typeof(c.next()); but that obviously requires an instance of the iterator. And it's perhaps a bit confusing.
 Also would do you do a mutating iteration over collections of basic 
 value types (eg floats), structs, and classes?  I.e. if you want to do 
 something like:
 
 while(c.hasNext())
 {
    T v = c.next();
    v += 2;
 }
 where T could be float, struct, or class.  Ok, class case is fine, but 
 the other two aren't clear to me.  Mutable iterator over structs could 
 maybe return a pointer to each struct.  Basic value type, I'm not sure. 
  Just woke up though... maybe it's obvious and my head just isn't 
 working yet.

Yeah, perhaps returning a pointer is better. The lack of reference types in D can make things like this a bit awkward.
Nov 05 2006
prev sibling parent reply Sean Kelly <sean f4.ca> writes:
Bill Baxter wrote:
 Sean Kelly wrote:
 Sean Kelly wrote:

 Still, I think it's useful to have in an iterator, so perhaps 
 something roughly like this:

 interface Iterator(T)
 {
     T val();
     T next();
     bool hasNext();
 }

Err... this doesn't work for an iterator returned for an empty container.

It's fine if you define the behavior to be that you have to call next() once to get the first value. So for iteration idiom becomes: T v; while(c.hasNext()) ) { }

Yup, but this seems confusing with the presence of val() methods.
Nov 05 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
Sean Kelly wrote:
 Bill Baxter wrote:
 
 Sean Kelly wrote:

 Sean Kelly wrote:

 Still, I think it's useful to have in an iterator, so perhaps 
 something roughly like this:

 interface Iterator(T)
 {
     T val();
     T next();
     bool hasNext();
 }

Err... this doesn't work for an iterator returned for an empty container.

It's fine if you define the behavior to be that you have to call next() once to get the first value. So for iteration idiom becomes: T v; while(c.hasNext()) ) { }

Yup, but this seems confusing with the presence of val() methods.

I'm not sold on val() yet. :-) --bb
Nov 05 2006
parent David Gileadi <foo bar.com> writes:
Bill Baxter wrote:
 Sean Kelly wrote:
 Bill Baxter wrote:

 Sean Kelly wrote:

 Sean Kelly wrote:

 Still, I think it's useful to have in an iterator, so perhaps 
 something roughly like this:

 interface Iterator(T)
 {
     T val();
     T next();
     bool hasNext();
 }

Err... this doesn't work for an iterator returned for an empty container.

It's fine if you define the behavior to be that you have to call next() once to get the first value. So for iteration idiom becomes: T v; while(c.hasNext()) ) { }

Yup, but this seems confusing with the presence of val() methods.

I'm not sold on val() yet. :-) --bb

For what it's worth, C# implements it like this: public interface IEnumerator { public bool MoveNext(); public object Current { get; } public void Reset(); } It seems that MoveNext() must be called before Current becomes valid (assuming that there are any items in the collection). If Current is accessed without having an object to return, it throws an exception. So a while loop might look like: while (e.MoveNext()) { object obj = e.Current; Console.WriteLine(obj); } C#'s foreach loop also works with IEnumerator, as: foreach (object obj in c) { Console.WriteLine(obj); } where c is an object that implements the IEnumerable interface, which has a single GetEnumerator() method. I'm not suggesting that D do the same thing as C#, but I thought that some of the above might be relevant to this discussion. -Dave
Nov 06 2006
prev sibling parent reply BCS <BCS pathlink.com> writes:
Sean Kelly wrote:
 Walter Bright wrote:
 
 Sean Kelly wrote:

 I think I agree, but for the sake of argument, how would D handle 
 'find'  operations on sequences that don't support opIndex?  At some 
 point, a generalizable bookmark is almost necessary for a faithful 
 implementation of some C++ algorithms.  Also, many of these 
 algorithms also require iteration across two sequences 
 simultaneously, which doesn't map very cleanly into foreach.  
 Consider a substring-style find operation (std::search), for example, 
 where both the pattern and target types do not support opIndex or 
 opSlice.  I might argue that it's a bit silly or unrealistic to 
 desire such an operation, but the C++ algorithm library does support it.

I think the target types will have to support opIndex or opSlice.

Forgive me for resurrecting a horribly battered equine, but I was thinking about this a bit tonight and I've decided that foreach, foreach_reverse, and array operations are not a sufficient general substitute for C++ iterators. For example, let's say I want to compute the set union of two sorted ranges, one of size M, the other of size N. By iterating across the two ranges simultaneously is is easy to see that the complexity for the operation will be max(M,N). In C++ this is easily accomplished using forward iterators, and the ranges can be anything from arrays to SQL result sets. In D however, there is no way to iterate across multiple ranges simultaneously using foreach, so opIndex must be used instead. With containers that have a constant-time lookup cost this isn't a big deal, but what if these containers are binary trees? The complexity for such an operation would be M(log(M)) + N(log(N)). From this it seems clear that foreach is not sufficiently adaptable to meet the needs of all sequential algorithms and opIndex is not a reasonable substitute for all cases where foreach may not be used. What alternatives do we have? So far, iterator variants are all I've been able to come up with. Sean

I have created a monster!!! // a class that can iterate over it's contents and another // iterator's contents in order class Foo { // return an iterator int delegate(int delegate(inout U)) opApplyWith(int delegate(inout U) t) { // make a class to form delegate auto ret = new class { // context int delegate(inout U) t; // iterator int ret(int delegate(inout U) dg) { int i=0; // loop on other foreach(inout U u, t) { // sub loop on self while(i<sortedUs.length && sortedUs[i] < u) if(int r = dg(sortedUs[i++])) return r; if(int r = dg(u)) return r; } } }; // set context ret.t = t; // return it return &ret.ret; } // loop on self only int opApply(int delegate(inout U) dg) { foreach(inout U u, sortedUs) { if(int r = dg(sortedUs[i++])) return r; } } // data for class U[] sortedUs; } // use it. int main() { Foo f1, f2; foreach(U u; f1.opApplyWith(&f2.opApply)) { use(u); } }
Nov 06 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
BCS wrote:

 I have created a monster!!!

Sure! Why not? opApplyWith is surely no less useful than opApplyReverse. ;-) Oh, but we probably need opApplyWithReverse now too. :-) --bb
Nov 06 2006
parent BCS <BCS pathlink.com> writes:
Bill Baxter wrote:
 BCS wrote:
 
 I have created a monster!!!

Sure! Why not? opApplyWith is surely no less useful than opApplyReverse. ;-) Oh, but we probably need opApplyWithReverse now too. :-) --bb

Ahh. Err. I wasn't suggesting that foreach_with() be added, it just looked like a good name. I could have named it "Bob" and it would still do what I was intending but then no one would known right off what it is supposed to do. The though is that making some sort of delegate/thunk/closure as an iterator can provide a lot of different iteration type patterns.
Nov 06 2006
prev sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Walter Bright wrote:
 John Reimer wrote:
 Ah, ok.  I stand corrected on that aspect of my critique.

I'll give some more lame justifications: There's been some talk about Boost recently in the n.g. (here and in comp.lang.c++) about if what Boost does is really worth it, or if it's just a lot of show-how-clever-I-am falderol. The general idea among the Boost people is that if there's any way possible it could be done in a library, rather than the core, then that's the way it should be done. I don't agree with that idea. I think Boost stretches C++ past the breaking point, and rather than showing how powerful C++ is, shows instead that the C++ core lacks power. Some of the shortcoming workarounds in Boost are just incredible, in the dogged persistence of their inventors to somehow make them work. Even so, the Boost results still wind up with serious holes in them.

I fully agree.
 If some crucial features are added to the core language, then much of 
 Boost either becomes irrelevant, or at least becomes far simpler and 
 straightforward to implement.

Exactly. Making improvements to the language that generalizes common idioms, tremendously shrinks library code or gives additional expressive power is good. But foreach_reverse does not generalize anything or give any additional expressive power. With the boost analogy, it would just replace one single algorithm with a built in equivalent, not reduce the amount of scaffolding all the rest of boost needs. One example of a generalizing addition is Tomasz' suggestion for trailing delegates. It generalizes foreach, foreach_reverse and even the while-loop. Such an addition would not only make libraries simpler and more powerful. It could also simplify the core language. What is design if not the pursuit of simplicity? /Oskar
Oct 18 2006
next sibling parent Lars Ivar Igesund <larsivar igesund.net> writes:
Oskar Linde wrote:

 Walter Bright wrote:
 John Reimer wrote:
 Ah, ok.  I stand corrected on that aspect of my critique.

I'll give some more lame justifications: There's been some talk about Boost recently in the n.g. (here and in comp.lang.c++) about if what Boost does is really worth it, or if it's just a lot of show-how-clever-I-am falderol. The general idea among the Boost people is that if there's any way possible it could be done in a library, rather than the core, then that's the way it should be done. I don't agree with that idea. I think Boost stretches C++ past the breaking point, and rather than showing how powerful C++ is, shows instead that the C++ core lacks power. Some of the shortcoming workarounds in Boost are just incredible, in the dogged persistence of their inventors to somehow make them work. Even so, the Boost results still wind up with serious holes in them.

I fully agree.
 If some crucial features are added to the core language, then much of
 Boost either becomes irrelevant, or at least becomes far simpler and
 straightforward to implement.

Exactly. Making improvements to the language that generalizes common idioms, tremendously shrinks library code or gives additional expressive power is good. But foreach_reverse does not generalize anything or give any additional expressive power. With the boost analogy, it would just replace one single algorithm with a built in equivalent, not reduce the amount of scaffolding all the rest of boost needs. One example of a generalizing addition is Tomasz' suggestion for trailing delegates. It generalizes foreach, foreach_reverse and even the while-loop. Such an addition would not only make libraries simpler and more powerful. It could also simplify the core language. What is design if not the pursuit of simplicity? /Oskar

Ah, just what I tried to say somewhere else, just not so good at eloquently getting my points across when the ideas get too smart ;) -- Lars Ivar Igesund blog at http://larsivi.net DSource & #D: larsivi
Oct 18 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Oskar Linde wrote:
 One example of a generalizing addition is Tomasz' suggestion for 
 trailing delegates. It generalizes foreach, foreach_reverse and even the 
 while-loop. Such an addition would not only make libraries simpler and 
 more powerful.

foreach_reverse is about as simple as one can get, from a user standpoint. It also works efficiently with arrays, which is hugely important because most of the time it will be used for arrays.
 It could also simplify the core language.

foreach_reverse was pretty trivial to implement. All the machinery was already there.
 What is design if not the pursuit of simplicity?

Simplicity is sometimes an elusive goal. For example, D started out with a simple syntax for function literals. Nobody used it, nobody even noticed it, people kept asking for the feature even after I pointed it out to them that D had it. Then, I figured out a way to eliminate some of the extra syntax for it, and voila! suddenly it gets noticed. This is even though the newer style is harder to parse and implement. I also remember a thread here about D versus Ruby, and how everything was so simple in Ruby. It didn't matter that I showed how it could be done in D, it appeared to be simpler in Ruby, and that apparently made all the difference.
Oct 18 2006
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 Oskar Linde wrote:
 One example of a generalizing addition is Tomasz' suggestion for 
 trailing delegates. It generalizes foreach, foreach_reverse and even 
 the while-loop. Such an addition would not only make libraries simpler 
 and more powerful.

foreach_reverse is about as simple as one can get, from a user standpoint. It also works efficiently with arrays, which is hugely important because most of the time it will be used for arrays.

For what it's worth, I think iterative operation requirements all fall into one of three categories: forward, reverse, and unordered. Forward iteration is by far the most common, so if semantic differences are involved, it should obviously be the prettiest ;-) Reverse iteration is not terribly common, but it does find occasional use in search-oriented algorithms. Unordered (for lack of a better term) can be used to describe any operation which has no ordering requirement and simply must be applied to all elements in a sequence. I believe it is important that the compiler be able to recognize forward and reverse iteration at compile-time so optimizations may be applied. After all, that's the entire point of a built-in foreach in the first place. Also, the compiler should be allowed to degenerate both forward and reverse iteration to the third category, unordered, when it can determine that visitation order has no impact on the operations being performed. Some criteria for this may be if the statement block does not contain break, continue, or goto statements, and if all operations on sequence data are commutative. Optionally, in instances where a statement block may not qualify for auto-degeneration, the user should be able to specify that it should be used anyway. This would also allow user-defined types to implement unordered operations in non-trivial situations. So we have something like this: foreach() // the default: forward iteration, compiler may degenerate foreach!(fwd)() // forward iteration, compiler may degenerate foreach!(rev)() // reverse iteration, compiler may degenerate foreach!(any)() // unordered: SSE ops may be used, concurrency, etc foreach!(fwd,strict)() // forward iteration, compiler may not degenerate foreach!(rev,strict)() // reverse iteration, compiler may not degenerate foreach!(any,strict)() // unordered, same as without strict (the above code above isn't intended to suggest syntax so much as to describe the operations and restrictions I think may eventually be useful) Does this sound reasonable? And can anyone suggest a cleaner syntax? Sean
Oct 18 2006
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
The compiler is nowhere near ready to implement parallel stuff. But when 
it is, I'd like to try doing it automatically before inventing more 
syntax for it.
Oct 18 2006
parent Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 The compiler is nowhere near ready to implement parallel stuff. But when 
 it is, I'd like to try doing it automatically before inventing more 
 syntax for it.

I added the syntax mostly so the user had some way of specifying to container classes that an unordered operation should be used. But I do agree that adding syntax is never a good thing if other options are available. Sean
Oct 18 2006
prev sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Sean Kelly wrote:
 Walter Bright wrote:
 Oskar Linde wrote:
 One example of a generalizing addition is Tomasz' suggestion for 
 trailing delegates. It generalizes foreach, foreach_reverse and even 
 the while-loop. Such an addition would not only make libraries 
 simpler and more powerful.

foreach_reverse is about as simple as one can get, from a user standpoint. It also works efficiently with arrays, which is hugely important because most of the time it will be used for arrays.

For what it's worth, I think iterative operation requirements all fall into one of three categories: forward, reverse, and unordered. Forward iteration is by far the most common, so if semantic differences are involved, it should obviously be the prettiest ;-) Reverse iteration is not terribly common, but it does find occasional use in search-oriented algorithms. Unordered (for lack of a better term) can be used to describe any operation which has no ordering requirement and simply must be applied to all elements in a sequence. I believe it is important that the compiler be able to recognize forward and reverse iteration at compile-time so optimizations may be applied. After all, that's the entire point of a built-in foreach in the first place. Also, the compiler should be allowed to degenerate both forward and reverse iteration to the third category, unordered, when it can determine that visitation order has no impact on the operations being performed. Some criteria for this may be if the statement block does not contain break, continue, or goto statements, and if all operations on sequence data are commutative. Optionally, in instances where a statement block may not qualify for auto-degeneration, the user should be able to specify that it should be used anyway. This would also allow user-defined types to implement unordered operations in non-trivial situations. So we have something like this: foreach() // the default: forward iteration, compiler may degenerate foreach!(fwd)() // forward iteration, compiler may degenerate foreach!(rev)() // reverse iteration, compiler may degenerate foreach!(any)() // unordered: SSE ops may be used, concurrency, etc foreach!(fwd,strict)() // forward iteration, compiler may not degenerate foreach!(rev,strict)() // reverse iteration, compiler may not degenerate foreach!(any,strict)() // unordered, same as without strict (the above code above isn't intended to suggest syntax so much as to describe the operations and restrictions I think may eventually be useful) Does this sound reasonable? And can anyone suggest a cleaner syntax? Sean

Here's an idea: foreach(foo, aggregate) { // Unordered, so compiler may optmize foreach(foo, &aggregate.iterForward) { // Ordered and strict foreach(foo, &aggregate.iterReverse) { // Ordered and strict This way the strictness cannot be specified. Is it necessary? That is, is there a case where one wants an *ordered* iteration, but the compiler can optimize into an unordered (parallel) iteration? That does not seem to make sense. One issue here is that one cannot specify an unordered iterator (i.e., an iterator for the case where the order does not matter), so it defaults to one only. Could there be a structure where there would be more than one meaningful unordered iterator? -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Oct 19 2006
next sibling parent Sean Kelly <sean f4.ca> writes:
Bruno Medeiros wrote:
 
 Here's an idea:
 
   foreach(foo, aggregate) {  // Unordered, so compiler may optmize
   foreach(foo, &aggregate.iterForward) { // Ordered and strict
   foreach(foo, &aggregate.iterReverse) { // Ordered and strict
 
 This way the strictness cannot be specified. Is it necessary? That is, 
 is there a case where one wants an *ordered* iteration, but the compiler 
 can optimize into an unordered (parallel) iteration?

If the involved data is volatile and being monitored by another thread, then yes. But in that case some sort of memory barriers would probably be involved and the compiler could detect those and not optimize, so I'm not sure. Sean
Oct 19 2006
prev sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Bruno Medeiros wrote:
 Sean Kelly wrote:
 Walter Bright wrote:
 Oskar Linde wrote:
 One example of a generalizing addition is Tomasz' suggestion for 
 trailing delegates. It generalizes foreach, foreach_reverse and even 
 the while-loop. Such an addition would not only make libraries 
 simpler and more powerful.

foreach_reverse is about as simple as one can get, from a user standpoint. It also works efficiently with arrays, which is hugely important because most of the time it will be used for arrays.

For what it's worth, I think iterative operation requirements all fall into one of three categories: forward, reverse, and unordered. Forward iteration is by far the most common, so if semantic differences are involved, it should obviously be the prettiest ;-) Reverse iteration is not terribly common, but it does find occasional use in search-oriented algorithms. Unordered (for lack of a better term) can be used to describe any operation which has no ordering requirement and simply must be applied to all elements in a sequence. I believe it is important that the compiler be able to recognize forward and reverse iteration at compile-time so optimizations may be applied. After all, that's the entire point of a built-in foreach in the first place. Also, the compiler should be allowed to degenerate both forward and reverse iteration to the third category, unordered, when it can determine that visitation order has no impact on the operations being performed. Some criteria for this may be if the statement block does not contain break, continue, or goto statements, and if all operations on sequence data are commutative. Optionally, in instances where a statement block may not qualify for auto-degeneration, the user should be able to specify that it should be used anyway. This would also allow user-defined types to implement unordered operations in non-trivial situations. So we have something like this: foreach() // the default: forward iteration, compiler may degenerate foreach!(fwd)() // forward iteration, compiler may degenerate foreach!(rev)() // reverse iteration, compiler may degenerate foreach!(any)() // unordered: SSE ops may be used, concurrency, etc foreach!(fwd,strict)() // forward iteration, compiler may not degenerate foreach!(rev,strict)() // reverse iteration, compiler may not degenerate foreach!(any,strict)() // unordered, same as without strict (the above code above isn't intended to suggest syntax so much as to describe the operations and restrictions I think may eventually be useful) Does this sound reasonable? And can anyone suggest a cleaner syntax? Sean

Here's an idea: foreach(foo, aggregate) { // Unordered, so compiler may optmize foreach(foo, &aggregate.iterForward) { // Ordered and strict foreach(foo, &aggregate.iterReverse) { // Ordered and strict This way the strictness cannot be specified. Is it necessary? That is, is there a case where one wants an *ordered* iteration, but the compiler can optimize into an unordered (parallel) iteration? That does not seem to make sense. One issue here is that one cannot specify an unordered iterator (i.e., an iterator for the case where the order does not matter), so it defaults to one only. Could there be a structure where there would be more than one meaningful unordered iterator?

Scrap that, duh. Non-ordered 'iteration' is, kinda like you said, without breaks or gotos, and thus applied to all elements. So one can use regular functions with delegate parameters to do this 'iteration'. These non-ordered, complete 'iterations' are actually the list/collection 'comprehensions' (http://www.digitalmars.com/d/archives/digitalmars/D/39313.html , which we knew already, but didn't remember?) which are very easy to parallelize (think Google MapReduce). Doesn't this solve the issue, in quite cleaner syntax and semantics? I gotta start opinionating less and coding more... -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Oct 23 2006
parent reply Sean Kelly <sean f4.ca> writes:
Bruno Medeiros wrote:
 Bruno Medeiros wrote:
 Sean Kelly wrote:
 Walter Bright wrote:
 Oskar Linde wrote:
 One example of a generalizing addition is Tomasz' suggestion for 
 trailing delegates. It generalizes foreach, foreach_reverse and 
 even the while-loop. Such an addition would not only make libraries 
 simpler and more powerful.

foreach_reverse is about as simple as one can get, from a user standpoint. It also works efficiently with arrays, which is hugely important because most of the time it will be used for arrays.

For what it's worth, I think iterative operation requirements all fall into one of three categories: forward, reverse, and unordered. Forward iteration is by far the most common, so if semantic differences are involved, it should obviously be the prettiest ;-) Reverse iteration is not terribly common, but it does find occasional use in search-oriented algorithms. Unordered (for lack of a better term) can be used to describe any operation which has no ordering requirement and simply must be applied to all elements in a sequence. I believe it is important that the compiler be able to recognize forward and reverse iteration at compile-time so optimizations may be applied. After all, that's the entire point of a built-in foreach in the first place. Also, the compiler should be allowed to degenerate both forward and reverse iteration to the third category, unordered, when it can determine that visitation order has no impact on the operations being performed. Some criteria for this may be if the statement block does not contain break, continue, or goto statements, and if all operations on sequence data are commutative. Optionally, in instances where a statement block may not qualify for auto-degeneration, the user should be able to specify that it should be used anyway. This would also allow user-defined types to implement unordered operations in non-trivial situations. So we have something like this: foreach() // the default: forward iteration, compiler may degenerate foreach!(fwd)() // forward iteration, compiler may degenerate foreach!(rev)() // reverse iteration, compiler may degenerate foreach!(any)() // unordered: SSE ops may be used, concurrency, etc foreach!(fwd,strict)() // forward iteration, compiler may not degenerate foreach!(rev,strict)() // reverse iteration, compiler may not degenerate foreach!(any,strict)() // unordered, same as without strict (the above code above isn't intended to suggest syntax so much as to describe the operations and restrictions I think may eventually be useful) Does this sound reasonable? And can anyone suggest a cleaner syntax? Sean

Here's an idea: foreach(foo, aggregate) { // Unordered, so compiler may optmize foreach(foo, &aggregate.iterForward) { // Ordered and strict foreach(foo, &aggregate.iterReverse) { // Ordered and strict This way the strictness cannot be specified. Is it necessary? That is, is there a case where one wants an *ordered* iteration, but the compiler can optimize into an unordered (parallel) iteration? That does not seem to make sense. One issue here is that one cannot specify an unordered iterator (i.e., an iterator for the case where the order does not matter), so it defaults to one only. Could there be a structure where there would be more than one meaningful unordered iterator?

Scrap that, duh. Non-ordered 'iteration' is, kinda like you said, without breaks or gotos, and thus applied to all elements. So one can use regular functions with delegate parameters to do this 'iteration'. These non-ordered, complete 'iterations' are actually the list/collection 'comprehensions' (http://www.digitalmars.com/d/archives/digitalmars/D/39313.html , which we knew already, but didn't remember?) which are very easy to parallelize (think Google MapReduce). Doesn't this solve the issue, in quite cleaner syntax and semantics?

It's a cool idea: x = vector[ (int t){return t>5;} ]; // subset of vector vector[] = (inout int x) { x += 100; }; // update all members of vector However, the second example above seems like it wouldn't work for an array of delegates, since this is a legal 'copy' syntax. Sean
Oct 24 2006
next sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Sean Kelly wrote:
 Bruno Medeiros wrote:
 Scrap that, duh. Non-ordered 'iteration' is, kinda like you said, 
 without breaks or gotos, and thus applied to all elements. So one can 
 use regular functions with delegate parameters to do this 'iteration'. 
 These non-ordered, complete 'iterations' are actually the 
 list/collection 'comprehensions' 
 (http://www.digitalmars.com/d/archives/digitalmars/D/39313.html , 
 which we knew already, but didn't remember?) which are very easy to 
 parallelize (think Google MapReduce). Doesn't this solve the issue, in 
 quite cleaner syntax and semantics?

It's a cool idea: x = vector[ (int t){return t>5;} ]; // subset of vector vector[] = (inout int x) { x += 100; }; // update all members of vector However, the second example above seems like it wouldn't work for an array of delegates, since this is a legal 'copy' syntax. Sean

Do you have something against methods?... :p x = vector.filter( (int t){return t>5;} ); // subset of vector vector.apply( (inout int x) { x += 100;} ); // update all members -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Oct 26 2006
parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Bruno Medeiros wrote:
 Sean Kelly wrote:
 
 Bruno Medeiros wrote:

 Scrap that, duh. Non-ordered 'iteration' is, kinda like you said, 
 without breaks or gotos, and thus applied to all elements. So one can 
 use regular functions with delegate parameters to do this 
 'iteration'. These non-ordered, complete 'iterations' are actually 
 the list/collection 'comprehensions' 
 (http://www.digitalmars.com/d/archives/digitalmars/D/39313.html , 
 which we knew already, but didn't remember?) which are very easy to 
 parallelize (think Google MapReduce). Doesn't this solve the issue, 
 in quite cleaner syntax and semantics?

It's a cool idea: x = vector[ (int t){return t>5;} ]; // subset of vector vector[] = (inout int x) { x += 100; }; // update all members of vector However, the second example above seems like it wouldn't work for an array of delegates, since this is a legal 'copy' syntax. Sean

Do you have something against methods?... :p x = vector.filter( (int t){return t>5;} ); // subset of vector vector.apply( (inout int x) { x += 100;} ); // update all members

Looks good to me. I do have .filter implemented in CashewUtils, and might just add a .apply now that you mention it. -- Chris Nicholson-Sauls
Oct 26 2006
parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Chris Nicholson-Sauls wrote:
 Bruno Medeiros wrote:
 Sean Kelly wrote:

 Bruno Medeiros wrote:

 Scrap that, duh. Non-ordered 'iteration' is, kinda like you said, 
 without breaks or gotos, and thus applied to all elements. So one 
 can use regular functions with delegate parameters to do this 
 'iteration'. These non-ordered, complete 'iterations' are actually 
 the list/collection 'comprehensions' 
 (http://www.digitalmars.com/d/archives/digitalmars/D/39313.html , 
 which we knew already, but didn't remember?) which are very easy to 
 parallelize (think Google MapReduce). Doesn't this solve the issue, 
 in quite cleaner syntax and semantics?

It's a cool idea: x = vector[ (int t){return t>5;} ]; // subset of vector vector[] = (inout int x) { x += 100; }; // update all members of vector However, the second example above seems like it wouldn't work for an array of delegates, since this is a legal 'copy' syntax. Sean

Do you have something against methods?... :p x = vector.filter( (int t){return t>5;} ); // subset of vector vector.apply( (inout int x) { x += 100;} ); // update all members

Looks good to me. I do have .filter implemented in CashewUtils, and might just add a ..apply now that you mention it. -- Chris Nicholson-Sauls

If that's so, then you should check for Oskar Linde's array utility code. He's the one I first recall talking about array (list) comprehensions in D, and he posted quite some arrays lib code with that, but unfortunately I don't know exactly which post was it, so I can't find it. -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Oct 29 2006
prev sibling parent =?iso-8859-1?q?Knud_S=F8rensen?= <12tkvvb02 sneakemail.com> writes:
On Tue, 24 Oct 2006 08:42:13 -0700, Sean Kelly wrote:

 
 Scrap that, duh. Non-ordered 'iteration' is, kinda like you said, 
 without breaks or gotos, and thus applied to all elements. So one can 
 use regular functions with delegate parameters to do this 'iteration'. 
 These non-ordered, complete 'iterations' are actually the 
 list/collection 'comprehensions' 
 (http://www.digitalmars.com/d/archives/digitalmars/D/39313.html , which 
 we knew already, but didn't remember?) which are very easy to 
 parallelize (think Google MapReduce). Doesn't this solve the issue, in 
 quite cleaner syntax and semantics?

It's a cool idea: x = vector[ (int t){return t>5;} ]; // subset of vector vector[] = (inout int x) { x += 100; }; // update all members of vector

This is very close to the vectorization syntax http://www.all-technology.com/eigenpolls/dwishlist/index.php?it=10 x=[i in 0..length](if (vector[i]>5) return vector[i]); [i in 0..length](vector[i]+=100); maybe a slight change of notation. x=[i in 0..length]{if (vector[i]>5) return vector[i]}; [i in 0..length]{vector[i]+=100};
 However, the second example above seems like it wouldn't work for an 
 array of delegates, since this is a legal 'copy' syntax.
 
 
 Sean

Oct 28 2006
prev sibling parent reply Bill Baxter <wbaxter gmail.com> writes:
Walter Bright wrote:
 Oskar Linde wrote:

 It could also simplify the core language.

foreach_reverse was pretty trivial to implement. All the machinery was already there.
 What is design if not the pursuit of simplicity?

Simplicity is sometimes an elusive goal. For example, D started out with a simple syntax for function literals. Nobody used it, nobody even noticed it, people kept asking for the feature even after I pointed it out to them that D had it. Then, I figured out a way to eliminate some of the extra syntax for it, and voila! suddenly it gets noticed. This is even though the newer style is harder to parse and implement. I also remember a thread here about D versus Ruby, and how everything was so simple in Ruby. It didn't matter that I showed how it could be done in D, it appeared to be simpler in Ruby, and that apparently made all the difference.

Definitely. Simplicity of the language and simplicity of the implementation are NOT the same thing. What matters most to USERS is the the conceptual simplicity of the language itself. Not how many hoops the compiler writer had to jump thorugh to make it look simple. Sometimes a simple conceptual model goes hand-in-hand with simple implementation. Sometimes it doesn't. A good example of the former is Scheme. A good example of the latter is maybe Boost::Spirit, to pick an example from recent discussion, though it doesn't do that great a job of appearing simple (but much simpler than the underlying implementation). A better example is probably pure OO languages that make everything an object, including things like number literals. The thing to strive for is a simple conceptual model. Hmm, rereading this though, I think you'd argue that you didn't change or simplify any "concepts" you just changed syntax. Could be. But I think there is a connection between the two. Clumsy syntax can cloud the underlying clarity of the concepts. Just like the boost::spirit parser, real_p >> *(char_p(',') >> real_p) is the same thing as EBNF real (',' real)* but one makes the concept a lot easier to see than the other. Also -- and I think you've noted this before yourself -- end users often go for local optimizations. In the short term they want a fix to the immediate problem they see. But that's not a good way to design a language. You want the global optimum. --bb
Oct 18 2006
parent Walter Bright <newshound digitalmars.com> writes:
Bill Baxter wrote:
 Also -- and I think you've noted this before yourself -- end users often 
 go for local optimizations.  In the short term they want a fix to the 
 immediate problem they see.   But that's not a good way to design a 
 language.  You want the global optimum.

Sure. But in the year and a half since the long thread proposing foreach_reverse and various alternatives, nothing better has come up. foreach_reverse gets the job done in a simple, understandable, and efficient manner.
Oct 19 2006
prev sibling parent Charles D Hixson <charleshixsn earthlink.net> writes:
Walter Bright wrote:
 John Reimer wrote:
 I have to agree with Sean and Ary.  My own opinion: I don't really
 understand why "foreach_reverse" was, once again, just tossed into
 the language with (what seems to be) a minimum of discussion?

There was quite a bit of discussion. The thread was a bit old, but that doesn't make it less relevant: http://www.digitalmars.com/d/archives/digitalmars/D/17320.html
 Well, will you look at that.  Isn't that irony?  We got our rolls
 reversed, I think.  I used to be Walter that was hesitant to add
 keywords to the language.  Go figure! :D

I was reluctant to do it for a long time for that reason. It's just that no better solution emerged.

To me "for each" had the implication of an unordered traversal, with the undertone that *sometime* when multi-processor machines became more prominent each iteration might be done on a different processor. I'm aware that this was never the real intent...but that's the subtext that I got when I read the code. This is partially out of a desire to allow multi-processor systems to be used efficiently. (What did Intel say? 64 cores/chip in 10 years?) Perhaps another syntax to denote this will show up. (Each function or subroutine call, perhaps? But that doesn't imply parallelism.) Sorry, just a reaction.
Oct 17 2006
prev sibling next sibling parent reply Vladimir Kulev <me lightoze.net> writes:
Agree with you, foreach_reverse is unnecessary feature, so it should not
exist.
Oct 17 2006
parent reply J Duncan <jtd514 nospam.ameritech.net> writes:
Vladimir Kulev wrote:
 Agree with you, foreach_reverse is unnecessary feature, so it should not
 exist.

Disagree with you, its a nice thing to have.
Oct 17 2006
next sibling parent reply Vladimir Kulev <me lightoze.net> writes:
J Duncan wrote:
 Disagree with you, its a nice thing to have.

There are many things which are nice to have, but only really essential ones should be in language itself. Reverse foreach can be implemented in other way.
Oct 17 2006
next sibling parent J Duncan <jtd514 nospam.ameritech.net> writes:
Vladimir Kulev wrote:
 J Duncan wrote:
 Disagree with you, its a nice thing to have.

There are many things which are nice to have, but only really essential ones should be in language itself.

Well.... We are lucky to have Walter then.... :)
Oct 17 2006
prev sibling next sibling parent Lutger <lutger.blijdestijn gmail.com> writes:
Vladimir Kulev wrote:
 J Duncan wrote:
 Disagree with you, its a nice thing to have.

There are many things which are nice to have, but only really essential ones should be in language itself. Reverse foreach can be implemented in other way.

But there are some benefits to having foreach_reverse, this I could think of right now: - foreach and foreach_reverse are the basic kinds of iteration, supporting them both with a keyword and other kinds with a delegate makes sense as it looks more consistent imho. - having foreach_reverse means that reverse iteration will likely be done with the same syntax across code from different people. - it stands out more in code (syntax highlighting), I think this will be easier to read. Sure it is syntactic sugar, but the D language does have a lot of sugar (more than most languages probably) and it can be pretty sweet. I'm not saying it's better to have foreach_reverse perse, but it does have some benefits.
Oct 17 2006
prev sibling parent reply Stewart Gordon <smjg_1998 yahoo.com> writes:
Vladimir Kulev wrote:
 J Duncan wrote:
 Disagree with you, its a nice thing to have.

There are many things which are nice to have, but only really essential ones should be in language itself. Reverse foreach can be implemented in other way.

So can ordinary foreach. Stewart. -- -----BEGIN GEEK CODE BLOCK----- Version: 3.1 GCS/M d- s:- C++ a->--- UB P+ L E W++ N+++ o K- w++ O? M V? PS- PE- Y? PGP- t- 5? X? R b DI? D G e++++ h-- r-- !y ------END GEEK CODE BLOCK------ My e-mail is valid but not my primary mailbox. Please keep replies on the 'group where everyone may benefit.
Oct 17 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Stewart Gordon wrote:
 Vladimir Kulev wrote:
 J Duncan wrote:
 Disagree with you, its a nice thing to have.

There are many things which are nice to have, but only really essential ones should be in language itself. Reverse foreach can be implemented in other way.

So can ordinary foreach.

All you really need is if and goto!
Oct 17 2006
next sibling parent reply BCS <BCS pathlink.com> writes:
Walter Bright wrote:
 Stewart Gordon wrote:
 
 Vladimir Kulev wrote:

 J Duncan wrote:

 Disagree with you, its a nice thing to have.

There are many things which are nice to have, but only really essential ones should be in language itself. Reverse foreach can be implemented in other way.

So can ordinary foreach.

All you really need is if and goto!

no, all you really need is goto and label variables int i = 10; loop: i--; goto [loop, quit][cast(int)(i==0)]; quit:
Oct 18 2006
next sibling parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"BCS" <BCS pathlink.com> wrote in message 
news:eh5kki$11t$4 digitaldaemon.com...

 no, all you really need is goto and label variables

 int i = 10;
 loop:
 i--;
 goto [loop, quit][cast(int)(i==0)];
 quit:

Who needs flow control? If you need n iterations, copy and paste n times!
Oct 18 2006
prev sibling parent reply Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
BCS wrote:
 Walter Bright wrote:
 Stewart Gordon wrote:

 Vladimir Kulev wrote:

 J Duncan wrote:

 Disagree with you, its a nice thing to have.

There are many things which are nice to have, but only really essential ones should be in language itself. Reverse foreach can be implemented in other way.

So can ordinary foreach.

All you really need is if and goto!

no, all you really need is goto and label variables int i = 10; loop: i--; goto [loop, quit][cast(int)(i==0)]; quit:

But this doesn't work, you can't create an array of label names.
Oct 18 2006
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Ivan Senji wrote:
 BCS wrote:
 no, all you really need is goto and label variables

 int i = 10;
 loop:
     i--;
     goto [loop, quit][cast(int)(i==0)];
 quit:

But this doesn't work, you can't create an array of label names.

Read carefully. What he said was "all you really need is goto and label variables". The fact we can't /currently/ do it this (because we don't have the latter of the two) doesn't mean he's wrong ;).
Oct 18 2006
parent Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Frits van Bommel wrote:
 Ivan Senji wrote:
 BCS wrote:
 no, all you really need is goto and label variables

 int i = 10;
 loop:
     i--;
     goto [loop, quit][cast(int)(i==0)];
 quit:

But this doesn't work, you can't create an array of label names.

Read carefully. What he said was "all you really need is goto and label variables". The fact we can't /currently/ do it this (because we don't have the latter of the two) doesn't mean he's wrong ;).

Look, look, I really should have read more carefully, thanks :)
Oct 18 2006
prev sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
Walter Bright wrote:
<snip>
 So can ordinary foreach.

All you really need is if and goto!

Actually, all you really need is while. Stewart. -- -----BEGIN GEEK CODE BLOCK----- Version: 3.1 GCS/M d- s:- C++ a->--- UB P+ L E W++ N+++ o K- w++ O? M V? PS- PE- Y? PGP- t- 5? X? R b DI? D G e++++ h-- r-- !y ------END GEEK CODE BLOCK------ My e-mail is valid but not my primary mailbox. Please keep replies on the 'group where everyone may benefit.
Oct 23 2006
prev sibling parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
J Duncan wrote:
 Vladimir Kulev wrote:
 
 Agree with you, foreach_reverse is unnecessary feature, so it should not
 exist.

Disagree with you, its a nice thing to have.

Could we make the statement that the old construct foreach(int i; a) {...} is now considered to just be syntax sugar for: foreach(int i; a.opApply) {...} and similarly for foreach_reverse? If so, then really the question here is whether we think this syntax sugar is worth having. Russ
Oct 17 2006
prev sibling next sibling parent reply BCS <BCS pathlink.com> writes:
Ary Manzana wrote:



  class Tree {

      int inorder(int delegate(inout int)) {
              // inorder traversal
      }

      int preorder(int delegate(inout int)) {
              // preorder traversal
      }

     int postorder(int delegate(inout int)) {
              // postorder traversal
      }

  }

  void main() {
      Tree t = giveMeSomeTree();

      foreach(int i : &t.inorder) {
          // something
          }

      foreach(int i : &t.preorder) {
          // something
          }

      foreach(int i : &t.postorder) {
          // something
          }

  }

If I understand correctly, the above works with what is there now.

The things with the foreach_reverse is (I think) mostly for actuals 
arrays, and the opApplyReverse is really there more for orthogonality 
than need. that orthogonality has some cool side effects* so I'd say 
leave them in.

*: I have noticed recently that good orthogonality allows for some vary 
cool compile time options (think code generation). It almost lets 
c/c++/d act as dynamicly typed languages.
Oct 17 2006
parent Walter Bright <newshound digitalmars.com> writes:
BCS wrote:
 Ary Manzana wrote:
 
 
 
  class Tree {
 
      int inorder(int delegate(inout int)) {
              // inorder traversal
      }
 
      int preorder(int delegate(inout int)) {
              // preorder traversal
      }
 
     int postorder(int delegate(inout int)) {
              // postorder traversal
      }
 
  }
 
  void main() {
      Tree t = giveMeSomeTree();
 
      foreach(int i : &t.inorder) {
          // something
          }
 
      foreach(int i : &t.preorder) {
          // something
          }
 
      foreach(int i : &t.postorder) {
          // something
          }
 
  }
 
 If I understand correctly, the above works with what is there now.

You are correct, with delegates now allowed as the 'aggregate', you can have any order traversal needed for the particular collection type. (Nit: replace the ':' in your examples with ';'.)
 The things with the foreach_reverse is (I think) mostly for actuals 
 arrays, and the opApplyReverse is really there more for orthogonality 
 than need. that orthogonality has some cool side effects* so I'd say 
 leave them in.

Right. a.reverse reverses an array in place, and trying to support: int[] a; foreach (v; &a.reverse) is an awful hack.
Oct 17 2006
prev sibling parent Walter Bright <newshound digitalmars.com> writes:
Ary Manzana wrote:
 Could something like this be done? I think it has the clearest syntax: 
 no new keywords needed and very flexible. The compiler should check that 
 the right side of the foreach is an array, or a class or struct having 
 opApply, or a delegate of the singature I mentioned before.

Already done! See BCS's post.
Oct 17 2006
prev sibling next sibling parent reply Hasan Aljudy <hasan.aljudy gmail.com> writes:
Walter Bright wrote:
 Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

Lots of background for the foreach improvements in: http://www.digitalmars.com/d/archives/digitalmars/D/17320.html

I just go an idea. How about adding new statements: skip; reverse; They can be used inside the foreach body to skip over the next iteration or reverse the order of iteration (dynamically at runtime). Also, since foreach already takes two arguments (int i, T t) that is, index and element, you can add a third argument, of bool type, with the meaning "start in reverse mode" foreach( true, i, d; "Hello" ) { writefln( d ); } should print: o l l e H
Oct 17 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Hasan Aljudy wrote:
 I just go an idea.
 How about adding new statements:
 skip;
 reverse;
 
 They can be used inside the foreach body to skip over the next iteration

continue; can be used for that.
 or reverse the order of iteration (dynamically at runtime).

Aaaaggghhhh!!!!
 Also, since foreach already takes two arguments (int i, T t) that is, 
 index and element, you can add a third argument, of bool type, with the 
 meaning "start in reverse mode"
 foreach( true, i, d; "Hello" )
 {
     writefln( d );
 }
 
 should print:
 o
 l
 l
 e
 H

That would work, and something like it has been suggested before, but it is too obscure looking. When someone sees "foreach_reverse", I think it'll be very clear what's going on.
Oct 17 2006
parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Walter Bright wrote:
 Hasan Aljudy wrote:
 Also, since foreach already takes two arguments (int i, T t) that is, 
 index and element, you can add a third argument, of bool type, with 
 the meaning "start in reverse mode"
 foreach( true, i, d; "Hello" )
 {
     writefln( d );
 }

 should print:
 o
 l
 l
 e
 H

That would work, and something like it has been suggested before, but it is too obscure looking. When someone sees "foreach_reverse", I think it'll be very clear what's going on.

There's no need to use booleans (at least, not directly): enum Ordering : bool { forward, backwards, reversed = backwards } That should produce much more readable code, but work the same. Can be done right now, except you can't overload opApply for arrays :(. (Tell me if I'm wrong, but I tried and it didn't work)
Oct 17 2006
next sibling parent Sean Kelly <sean f4.ca> writes:
Frits van Bommel wrote:
 Walter Bright wrote:
 Hasan Aljudy wrote:
 Also, since foreach already takes two arguments (int i, T t) that is, 
 index and element, you can add a third argument, of bool type, with 
 the meaning "start in reverse mode"
 foreach( true, i, d; "Hello" )
 {
     writefln( d );
 }

 should print:
 o
 l
 l
 e
 H

That would work, and something like it has been suggested before, but it is too obscure looking. When someone sees "foreach_reverse", I think it'll be very clear what's going on.

There's no need to use booleans (at least, not directly): enum Ordering : bool { forward, backwards, reversed = backwards } That should produce much more readable code, but work the same. Can be done right now, except you can't overload opApply for arrays :(. (Tell me if I'm wrong, but I tried and it didn't work)

I like that the current implementation will produce a compile error if an object without opApplyReverse is used as an aggregate in foreach_reverse. If the syntax were to change, I wouldn't want to push this checking to run-time (which it seems a parameter-based method might do). Sean
Oct 17 2006
prev sibling parent BCS <BCS pathlink.com> writes:
Frits van Bommel wrote:
 Walter Bright wrote:
 
 Hasan Aljudy wrote:

 Also, since foreach already takes two arguments (int i, T t) that is, 
 index and element, you can add a third argument, of bool type, with 
 the meaning "start in reverse mode"
 foreach( true, i, d; "Hello" )
 {
     writefln( d );
 }

 should print:
 o
 l
 l
 e
 H

That would work, and something like it has been suggested before, but it is too obscure looking. When someone sees "foreach_reverse", I think it'll be very clear what's going on.

There's no need to use booleans (at least, not directly): enum Ordering : bool { forward, backwards, reversed = backwards } That should produce much more readable code, but work the same. Can be done right now, except you can't overload opApply for arrays :(. (Tell me if I'm wrong, but I tried and it didn't work)

IIRC something like this should work <code> int go(char[], int delegate(inout char [, ...]) dg) { } void main() { foreach(char c; &("hello world".go)){} } </code> if not, this should work: <code> template reverse(T) { int delegate(int delegate(inout T)) reverse(T[] stuff) { auto ret = new struct { T[] data; int go(int delegate(inout T) dg) { for (int i = data.length-1; i >= 0; i--) { if(int result = dg(data[i]); return result; } return 0; } } ret.data = stuff; return &ret.go; } } ... foreach(char c; reverse("hello world")); { ... } </code> // I havent tried either so I expect there to be a few errors in them.
Oct 18 2006
prev sibling next sibling parent "Chris Miller" <chris dprogramming.com> writes:
On Tue, 17 Oct 2006 05:58:47 -0400, Walter Bright  
<newshound digitalmars.com> wrote:

 Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.
  http://www.digitalmars.com/d/changelog.html

Lots of background for the foreach improvements in: http://www.digitalmars.com/d/archives/digitalmars/D/17320.html

Just to clarify, the OP in that thread was attempting to violate the restrictions placed on foreach ("The aggregate itself must not be resized..." - http://www.digitalmars.com/d/statement.html#foreach). To further clarify, there is a simple way to remove all selected items in a DFL ListBox: while(listBox.selectedIndices.count) { listBox.items.remove(listBox.selectedIndices[0]); }
Oct 17 2006
prev sibling parent James Dunne <james.jdunne gmail.com> writes:
Walter Bright wrote:
 Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

Lots of background for the foreach improvements in: http://www.digitalmars.com/d/archives/digitalmars/D/17320.html

*Jaw drops on floor* -- -----BEGIN GEEK CODE BLOCK----- Version: 3.1 GCS/MU/S d-pu s:+ a-->? C++++$ UL+++ P--- L+++ !E W-- N++ o? K? w--- O M-- V? PS PE Y+ PGP- t+ 5 X+ !R tv-->!tv b- DI++(+) D++ G e++>e h>--->++ r+++ y+++ ------END GEEK CODE BLOCK------ James Dunne
Oct 17 2006
prev sibling next sibling parent reply Lars Ivar Igesund <larsivar igesund.net> writes:
Walter Bright wrote:

 Added foreach_reverse, which addresses a serious shortcoming.
 
 http://www.digitalmars.com/d/changelog.html

But foreach_reverse is such an ugly name, then I like 'reveach' (courtesy of Mr Panek) much better :P -- Lars Ivar Igesund blog at http://larsivi.net DSource & #D: larsivi
Oct 17 2006
next sibling parent reply Kristian <kjkilpi gmail.com> writes:
On Tue, 17 Oct 2006 13:08:06 +0300, Lars Ivar Igesund  
<larsivar igesund.net> wrote:

 Walter Bright wrote:

 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

But foreach_reverse is such an ugly name, then I like 'reveach' (courtesy of Mr Panek) much better :P

'reveach' sounds good; I too think that 'foreach_reverse' is a bit awkward and lengthy.
Oct 17 2006
parent reply Lars Ivar Igesund <larsivar igesund.net> writes:
Kristian wrote:

 On Tue, 17 Oct 2006 13:08:06 +0300, Lars Ivar Igesund
 <larsivar igesund.net> wrote:
 
 Walter Bright wrote:

 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

But foreach_reverse is such an ugly name, then I like 'reveach' (courtesy of Mr Panek) much better :P

'reveach' sounds good; I too think that 'foreach_reverse' is a bit awkward and lengthy.

I'm not sure reveach is that good ;) I'd really like something else, though. 'rforeach' maybe? -- Lars Ivar Igesund blog at http://larsivi.net DSource & #D: larsivi
Oct 17 2006
parent Kristian <kjkilpi gmail.com> writes:
On Tue, 17 Oct 2006 14:03:46 +0300, Lars Ivar Igesund  =

<larsivar igesund.net> wrote:

 Kristian wrote:

 On Tue, 17 Oct 2006 13:08:06 +0300, Lars Ivar Igesund
 <larsivar igesund.net> wrote:

 Walter Bright wrote:

 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

But foreach_reverse is such an ugly name, then I like 'reveach' (courtesy of Mr Panek) much better :P

'reveach' sounds good; I too think that 'foreach_reverse' is a bit =


 awkward
 and lengthy.

I'm not sure reveach is that good ;) I'd really like something else, though. 'rforeach' maybe?

Too bad that special characters cannot be used... E.g. foreach<<() foreach>>() //=3D=3D foreach(); optional syntax for 'foreach' ...But then, what's stopping them to be used?
Oct 17 2006
prev sibling next sibling parent David Medlock <noone nowhere.com> writes:
Lars Ivar Igesund wrote:
 Walter Bright wrote:
 
 
Added foreach_reverse, which addresses a serious shortcoming.

http://www.digitalmars.com/d/changelog.html

But foreach_reverse is such an ugly name, then I like 'reveach' (courtesy of Mr Panek) much better :P

-DavidM
Oct 17 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Lars Ivar Igesund wrote:
 But foreach_reverse is such an ugly name, then I like 'reveach' (courtesy of
 Mr Panek) much better :P

The saving grace about foreach_reverse is: 1) Only a small (5% ?) of loops will be reverse, so you won't see it or need to type it that often. 2) It's very clear what it does. 3) It isn't likely to conflict with other names. 4) It is analogous with C++'s reverse_iterator names.
Oct 17 2006
next sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Walter Bright wrote:
 Lars Ivar Igesund wrote:
 But foreach_reverse is such an ugly name, then I like 'reveach' 
 (courtesy of
 Mr Panek) much better :P

The saving grace about foreach_reverse is:

[... three points I agree with ...]
 4) It is analogous with C++'s reverse_iterator names.

Actually, wouldn't reverse_foreach be analogous with C++'s reverse_iterator naming? :P
Oct 17 2006
parent Walter Bright <newshound digitalmars.com> writes:
Frits van Bommel wrote:
 Walter Bright wrote:
 4) It is analogous with C++'s reverse_iterator names.

Actually, wouldn't reverse_foreach be analogous with C++'s reverse_iterator naming? :P

The problem with naming things "iterator" and "reverse_iterator" is they wind up widely separated when doing an alpha sort.
Oct 17 2006
prev sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Walter Bright wrote:

 The saving grace about foreach_reverse is:
 
 1) Only a small (5% ?) of loops will be reverse, so you won't see it or 
 need to type it that often.

A good reason why it doesn't deserve its own keyword.
 2) It's very clear what it does.

And 'foreach(i; list.reversed)' is pretty clear as well.
 3) It isn't likely to conflict with other names.

Because it's a 15 letter keyword with an underscore! While we're at it, let's make a for_i_equals_one_to_ten keyword, too. I loop from 1 to 10 a lot in my code (well, not that much really <5%, but at least it's a name that's not likely to conflict with other names).
 4) It is analogous with C++'s reverse_iterator names.

But those aren't keywords. And even more analogous is STL's std::for_each in the standard header 'algorithm'. http://www.sgi.com/tech/stl/for_each.html Note that STL does not have a std::for_each_reverse. You get that behavior, as you might expect, by using a reverse iterator instead of a forward iterator as the argument. And in another message Walter Bright wrote:
 foreach_reverse was pretty trivial to implement. All the machinery 

That should be setting off warning bells in your head, too. "The machinery is already there" is just another way of saying "this feature is mostly redundant". The foreach machinery already does the job. foreach_reverse is more or less just a copy-paste of that code with all references to "opApply" replaced with "opApplyReverse". So of course it's trivial to implement. I'll repeat a line from the "zen of python" one more time, at the risk of being told that 'D isn't Python', because I think it's true regardless of the language: "Special cases aren't special enough to break the rules." As I understand it, the only real reason for foreach_reverse, when it comes down to it, is because of a strong desire to have a special case fast reverse iteration for arrays and strings. But it really should be possible to hide that special case from the user and just detect some particular property e.g. "some_array.reversed" in a foreach statement. It may be a little more work (and maybe you just punt on the optimization till 2.0), but in the long run, the language and all it's users will benefit from removing that special case. --bb
Oct 25 2006
next sibling parent reply "John Reimer" <terminal.node gmail.com> writes:
On Wed, 25 Oct 2006 18:45:25 -0700, Bill Baxter  
<dnewsgroup billbaxter.com> wrote:

 Walter Bright wrote:

 The saving grace about foreach_reverse is:
  1) Only a small (5% ?) of loops will be reverse, so you won't see it  
 or need to type it that often.

A good reason why it doesn't deserve its own keyword.

Agree.
 2) It's very clear what it does.

And 'foreach(i; list.reversed)' is pretty clear as well.

Agree again... That looks much bettter! For arrays, I'm sure such a property could be special-cased to remove any risk of creating a new reversed array in place.
 3) It isn't likely to conflict with other names.

Because it's a 15 letter keyword with an underscore! While we're at it, let's make a for_i_equals_one_to_ten keyword, too. I loop from 1 to 10 a lot in my code (well, not that much really <5%, but at least it's a name that's not likely to conflict with other names).

Agree.
 4) It is analogous with C++'s reverse_iterator names.

But those aren't keywords. And even more analogous is STL's std::for_each in the standard header 'algorithm'. http://www.sgi.com/tech/stl/for_each.html Note that STL does not have a std::for_each_reverse. You get that behavior, as you might expect, by using a reverse iterator instead of a forward iterator as the argument.

Agree... I'm afraid I'm already biased against any train of thought that basically reduces to "so D can do it /like/ C++". But, alas, Walter is biased oppositely (darn diodes).
 And in another message Walter Bright wrote:

  > foreach_reverse was pretty trivial to implement. All the machinery  
 was > already there.

 That should be setting off warning bells in your head, too.  "The  
 machinery is already there" is just another way of saying "this feature  
 is mostly redundant". The foreach machinery already does the job.  
 foreach_reverse is more or less just a copy-paste of that code with all  
 references to "opApply" replaced with "opApplyReverse".  So of course  
 it's trivial to implement.

 I'll repeat a line from the "zen of python" one more time, at the risk  
 of being told that 'D isn't Python', because I think it's true  
 regardless of the language:

    "Special cases aren't special enough to break the rules."

 As I understand it, the only real reason for foreach_reverse, when it  
 comes down to it, is because of a strong desire to have a special case  
 fast reverse iteration for arrays and strings.  But it really should be  
 possible to hide that special case from the user and just detect some  
 particular property e.g. "some_array.reversed" in a foreach statement.  
 It may be a little more work (and maybe you just punt on the  
 optimization till 2.0), but in the long run, the language and all it's  
 users will benefit from removing that special case.

I've heard Walter's arguments, and I acknowledge some of his reasons aren't completely arbitrary (are they ever?). Nonetheless, I still think foreach_reverse is a mistake and a cheap addition to D. I really hope it doesn't last in its current form. Other people may find it easy to accept foreach_reverse because (1) it fixes a problem they see in front of them here and now (in which case it's very hard to refuse the quick fix) or (2) they are getting tired of arguing with Walter every time a ugly feature gets added, and they figure it's not worth the effort to argue the matter out. :) Either way, I think most of us are giving up. Unfortunately, this is the way the D design continues to be done. At the same time, I do feel sorry for Walter when I see all the language feature suggestions that go on in this newsgroup. A whole lot of people seem to have there pet feature that they want in D. It's scary to think of what would happen if everyone got their wish. :P All I hope, in this situation, is that Walter starts agreeing with Bill's points. -JJR
Oct 25 2006
parent Marcin Kuszczak <aarti interia.pl> writes:
John Reimer wrote:

 (2)
 they are getting tired of arguing with Walter every time a ugly feature
 gets added, and they figure it's not worth the effort to argue the matter
 out. :)  Either way, I think most of us are giving up.  Unfortunately,
 this is the way the D design continues to be done.

It can be so true... I would never argue so long as a few 'hero fighters' - I just don't have so much time and motivation :-| So Walter, please remember that they just wants to find out good, general solution :-) -- Regards Marcin Kuszczak (Aarti_pl)
Oct 26 2006
prev sibling next sibling parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Bill Baxter wrote:
 Walter Bright wrote:
 
 The saving grace about foreach_reverse is:

 1) Only a small (5% ?) of loops will be reverse, so you won't see it 
 or need to type it that often.

A good reason why it doesn't deserve its own keyword.
 2) It's very clear what it does.

And 'foreach(i; list.reversed)' is pretty clear as well.

Sure, and primitive arrays already have the .reverse property; however, that means extra temporaries that hit performance and memory usage. Both these hits are canceled out by adding foreach_reverse. The presence of opApplyReverse is primarily for completeness, and for generalization within templates.
 3) It isn't likely to conflict with other names.

Because it's a 15 letter keyword with an underscore! While we're at it, let's make a for_i_equals_one_to_ten keyword, too. I loop from 1 to 10 a lot in my code (well, not that much really <5%, but at least it's a name that's not likely to conflict with other names).
 4) It is analogous with C++'s reverse_iterator names.

But those aren't keywords. And even more analogous is STL's std::for_each in the standard header 'algorithm'. http://www.sgi.com/tech/stl/for_each.html Note that STL does not have a std::for_each_reverse. You get that behavior, as you might expect, by using a reverse iterator instead of a forward iterator as the argument. And in another message Walter Bright wrote: > foreach_reverse was pretty trivial to implement. All the machinery was > already there. That should be setting off warning bells in your head, too. "The machinery is already there" is just another way of saying "this feature is mostly redundant". The foreach machinery already does the job. foreach_reverse is more or less just a copy-paste of that code with all references to "opApply" replaced with "opApplyReverse". So of course it's trivial to implement. I'll repeat a line from the "zen of python" one more time, at the risk of being told that 'D isn't Python', because I think it's true regardless of the language: "Special cases aren't special enough to break the rules." As I understand it, the only real reason for foreach_reverse, when it comes down to it, is because of a strong desire to have a special case fast reverse iteration for arrays and strings. But it really should be possible to hide that special case from the user and just detect some particular property e.g. "some_array.reversed" in a foreach statement. It may be a little more work (and maybe you just punt on the optimization till 2.0), but in the long run, the language and all it's users will benefit from removing that special case. --bb

Mostly agreeable. However, neither does the language nor its users suffer from having the foreach_reverse statement. -- Chris Nicholson-Sauls
Oct 25 2006
next sibling parent "John Reimer" <terminal.node gmail.com> writes:
On Wed, 25 Oct 2006 20:53:22 -0700, Chris Nicholson-Sauls  
<ibisbasenji gmail.com> wrote:


 Mostly agreeable.  However, neither does the language nor its users  
 suffer from having the foreach_reverse statement.

 -- Chris Nicholson-Sauls

I disagree. I believe that D's image suffers. But I guess that's yet to be seen. -JJR
Oct 25 2006
prev sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Chris Nicholson-Sauls wrote:
 Bill Baxter wrote:

 And  'foreach(i; list.reversed)' is pretty clear as well.

Sure, and primitive arrays already have the .reverse property; however, that means extra temporaries that hit performance and memory usage.

That's why I said 'reversed' with a -d, which could be a property of arrays that returns an opApply-style delegate (and could be implemented by classes and structs that care to as well).
 Both these hits are canceled out by adding foreach_reverse.  

Well, technically both of those hits are canceled out by a special case optimization in the compiler that checks if the argument of foreach_reverse is an array. Having a foreach_reverse keyword just makes that optimization opportunity easier to spot. The same optimization could be applied using 'foreach' by noticing that the argument of the foreach is a particular property of an array (.reversed .reverse_iter .opApplyReverse ... whatever).
 The presence of opApplyReverse is primarily for completeness,

If you want completeness then you'll need to add foreach_inorder, foreach_preorder, foreach_postorder, foreach_randomized, foreach_every_other_one ... etc.
 and for generalization within templates.

Yes that was something Walter said, but I still don't think I've seen a concrete example of how this makes generic templates easier. If I'm going to write a generic template that processes some items, I would think the best way to make it general (with the delegate-style iterator paradigm) would be to have the user pass in whatever delegate they want for iterating in whatever order they want. I guess if you want to iterate backwards over items in a template it's useful, but that's more of a specialization than a generalization. And that case could be handled just as well by unilaterally declaring opApplyReverse to be the "official name" of the reverse iterator method, and adding a corresponding opApplyReverse property to arrays. Similarly in C++, the names "iterator" and "reverse_iterator" are just conventions. You don't have to name your class's iterator that, but you should, because it will make your class more compatible with other people's code, and will be more readable to others.
   "Special cases aren't special enough to break the rules."

 As I understand it, the only real reason for foreach_reverse, when it 
 comes down to it, is because of a strong desire to have a special case 
 fast reverse iteration for arrays and strings.  But it really should 
 be possible to hide that special case from the user and just detect 
 some particular property e.g. "some_array.reversed" in a foreach 
 statement. It may be a little more work (and maybe you just punt on 
 the optimization till 2.0), but in the long run, the language and all 
 it's users will benefit from removing that special case.

 --bb

Mostly agreeable. However, neither does the language nor its users suffer from having the foreach_reverse statement.

The price of a poorly thought-out feature in a language can have repercussions beyond how it affects one's day to day writing of code. Already there have been a few people here who looked at foreach_reverse and said "if this is representative of D, then I'll find another alternative, thank you". If the community shrinks, or fails to grow as it could, then that certainly impacts all D users. It's all about the network effect. I can say for myself when I saw the foreach_reverse addition it seriously made me consider whether there was any hope for D long term. If this is the kind of design decision being made today, then what hope is there for the long term? There's no Bell Labs or Sun Microsystems backing it, so it can't just power its way through bad design. It's got to compete on quality. As another example of the importance of intangibles in the network effect, folks here have repeatedly mentioned Nemerle's syntax extension / lisp-like macro system. The fact that people spoke highly of it here got me curious enough to go take a look at it. I gave up on it after I saw it was a .NET thing, but still it was the network effect trying to take hold of me, and it probably would have kept me if I were in the target audience for Nemerle. And I can say that personally I haven't done much evangelizing of D precisely because of issues like this. One of the main attractions of D is the promise of a C++ designed properly. That's a compelling story. If I could genuinely tell people "check out D -- it's C++ designed properly" then I would. But right now, although D fixes many design problems and inconsistencies in C++, it introduces many others. foreach_reverse is definitely one such case of taking a step backwards from C++ in terms of design. A good yardstick for how foreach_reverse -- or any such design issue -- may impact the network effect could be to poll the top contributors to D. I think we can agree that these people are good for D, and it would be good for D to attract more people like them. What do these MVPs think of the feature? If it by-in-large turns them off, then probably it's a bad idea. If it's 50/50 or greater then, fine, maybe we should have more features like foreach_reverse. The bottom line is there aren't that many markets that really need the speed/efficiency of C++ any more. Games, 3D software, multimedia, numerical and scientific computing, operating systems, databases/datamining, embedded systems. That's about all I can think of. Python and Ruby are probably fast enough for 80% of all applications, and Java is fast enough for %50 of what's left. So D needs some powerful network effect going for it in order to avoid just withering away. It needs to soak up as much of that last 10% as possible. How? You need people to love the language. You need people to want to gush about it and love it so much that they're driven to write crazy stuff like this about it: http://poignantguide.net/ruby/chapter-2.html#section3 People don't gush about Visual Basic. It gets the job done, but it's ugly, inconsistent, and idiosyncratic. They gush about Ruby. Why? What I keep hearing is things like "it's beautiful" "it's elegant" "it's expressive". All that says to me a good, clean, concise, and consistent design. This iterator stuff has got to be done right if iterators are to become a truly core concept in D. If they are perceived as clunky or limited or inelegant, it will hurt D. --bb
Oct 25 2006
parent reply Mike Parker <aldacron71 yahoo.com> writes:
Bill Baxter wrote:

 The price of a poorly thought-out feature in a language can have 
 repercussions beyond how it affects one's day to day writing of code.

It's a keyword with an underscore. Big deal. No one has to use it. I really think this is being blown way out of proportion. I've read all of these arguments against foreach_reverse and they just don't make sense to me. How is it poorly thought out? It makes perfect sense to me.
 
 Already there have been a few people here who looked at foreach_reverse 
 and said "if this is representative of D, then I'll find another 
 alternative, thank you".  If the community shrinks, or fails to grow as 
 it could, then that certainly impacts all D users.  It's all about the 
 network effect.  I can say for myself when I saw the foreach_reverse 
 addition it seriously made me consider whether there was any hope for D 
 long term.  If this is the kind of design decision being made today, 
 then what hope is there for the long term?  There's no Bell Labs or Sun 
 Microsystems backing it, so it can't just power its way through bad 
 design.  It's got to compete on quality.

People who turn away from D because of one keyword they find unusual can stay away. I wouldn't want to work with such people. Programmers can be a fickle lot, but that's ridiculous in the extreme. It's like the C++ programmer who says, "If your code uses char*, you have a bug." There are other issues in D that are more likely to, and have, turned people away, as I see it. A keyword with an underscore that no one even need use is nothing.
Oct 26 2006
parent Endea <notknown none.com> writes:
Mike Parker kirjoitti:
 Bill Baxter wrote:
 
 The price of a poorly thought-out feature in a language can have 
 repercussions beyond how it affects one's day to day writing of code.

It's a keyword with an underscore. Big deal. No one has to use it. I really think this is being blown way out of proportion. I've read all of these arguments against foreach_reverse and they just don't make sense to me. How is it poorly thought out? It makes perfect sense to me.
 Already there have been a few people here who looked at 
 foreach_reverse and said "if this is representative of D, then I'll 
 find another alternative, thank you".  If the community shrinks, or 
 fails to grow as it could, then that certainly impacts all D users.  
 It's all about the network effect.  I can say for myself when I saw 
 the foreach_reverse addition it seriously made me consider whether 
 there was any hope for D long term.  If this is the kind of design 
 decision being made today, then what hope is there for the long term?  
 There's no Bell Labs or Sun Microsystems backing it, so it can't just 
 power its way through bad design.  It's got to compete on quality.

People who turn away from D because of one keyword they find unusual can stay away. I wouldn't want to work with such people. Programmers can be a fickle lot, but that's ridiculous in the extreme. It's like the C++ programmer who says, "If your code uses char*, you have a bug." There are other issues in D that are more likely to, and have, turned people away, as I see it. A keyword with an underscore that no one even need use is nothing.

I do not want to participate in verbal tennis, just to express my support and humble opinion as hobbyist programmer I totally agree with this one. I would use foreach_reverse to do foreach in reversed order.
Oct 26 2006
prev sibling parent reply Marcin Kuszczak <aarti interia.pl> writes:
Completely agree with below !

vote++ to remove foreach_reverse

Marcin Kuszczak
Aarti_pl

------------------------

Bill Baxter wrote:

 Walter Bright wrote:
 
 The saving grace about foreach_reverse is:
 
 1) Only a small (5% ?) of loops will be reverse, so you won't see it or
 need to type it that often.

A good reason why it doesn't deserve its own keyword.
 2) It's very clear what it does.

And 'foreach(i; list.reversed)' is pretty clear as well.
 3) It isn't likely to conflict with other names.

Because it's a 15 letter keyword with an underscore! While we're at it, let's make a for_i_equals_one_to_ten keyword, too. I loop from 1 to 10 a lot in my code (well, not that much really <5%, but at least it's a name that's not likely to conflict with other names).
 4) It is analogous with C++'s reverse_iterator names.

But those aren't keywords. And even more analogous is STL's std::for_each in the standard header 'algorithm'. http://www.sgi.com/tech/stl/for_each.html Note that STL does not have a std::for_each_reverse. You get that behavior, as you might expect, by using a reverse iterator instead of a forward iterator as the argument. And in another message Walter Bright wrote: > foreach_reverse was pretty trivial to implement. All the machinery was > already there. That should be setting off warning bells in your head, too. "The machinery is already there" is just another way of saying "this feature is mostly redundant". The foreach machinery already does the job. foreach_reverse is more or less just a copy-paste of that code with all references to "opApply" replaced with "opApplyReverse". So of course it's trivial to implement. I'll repeat a line from the "zen of python" one more time, at the risk of being told that 'D isn't Python', because I think it's true regardless of the language: "Special cases aren't special enough to break the rules." As I understand it, the only real reason for foreach_reverse, when it comes down to it, is because of a strong desire to have a special case fast reverse iteration for arrays and strings. But it really should be possible to hide that special case from the user and just detect some particular property e.g. "some_array.reversed" in a foreach statement. It may be a little more work (and maybe you just punt on the optimization till 2.0), but in the long run, the language and all it's users will benefit from removing that special case. --bb

-- Regards Marcin Kuszczak (Aarti_pl)
Oct 26 2006
parent reply Tomas Lindquist Olsen <tomas famolsen.dk> writes:
Marcin Kuszczak wrote:
 Completely agree with below !
 
 vote++ to remove foreach_reverse
 
 Marcin Kuszczak
 Aarti_pl
 
 ------------------------
 
 Bill Baxter wrote:
 
 Walter Bright wrote:

 The saving grace about foreach_reverse is:

 1) Only a small (5% ?) of loops will be reverse, so you won't see it or
 need to type it that often.

 2) It's very clear what it does.

 3) It isn't likely to conflict with other names.

let's make a for_i_equals_one_to_ten keyword, too. I loop from 1 to 10 a lot in my code (well, not that much really <5%, but at least it's a name that's not likely to conflict with other names).
 4) It is analogous with C++'s reverse_iterator names.

std::for_each in the standard header 'algorithm'. http://www.sgi.com/tech/stl/for_each.html Note that STL does not have a std::for_each_reverse. You get that behavior, as you might expect, by using a reverse iterator instead of a forward iterator as the argument. And in another message Walter Bright wrote: > foreach_reverse was pretty trivial to implement. All the machinery was > already there. That should be setting off warning bells in your head, too. "The machinery is already there" is just another way of saying "this feature is mostly redundant". The foreach machinery already does the job. foreach_reverse is more or less just a copy-paste of that code with all references to "opApply" replaced with "opApplyReverse". So of course it's trivial to implement. I'll repeat a line from the "zen of python" one more time, at the risk of being told that 'D isn't Python', because I think it's true regardless of the language: "Special cases aren't special enough to break the rules." As I understand it, the only real reason for foreach_reverse, when it comes down to it, is because of a strong desire to have a special case fast reverse iteration for arrays and strings. But it really should be possible to hide that special case from the user and just detect some particular property e.g. "some_array.reversed" in a foreach statement. It may be a little more work (and maybe you just punt on the optimization till 2.0), but in the long run, the language and all it's users will benefit from removing that special case. --bb


listen to this every day. I for one really like foreach_reverse and IMHO the proposed alternatives seem much more hackish. It also creates a standardized syntax for reverse iteration. D is not C++!
Oct 26 2006
parent Bill Baxter <wbaxter gmail.com> writes:
Tomas Lindquist Olsen wrote:

 Seems this discussion will never end. I feel sad that Walter has to 
 listen to this every day.

Yeh, sorry about that. This one probably could have rested as it was -- the points were already made. Anyway the ultimate goal is just to try to make D the best D it can be at the end of the day. I argue my point of view, and you argue yours, and we see what holds up under scrutiny.
 I for one really like foreach_reverse and IMHO the proposed alternatives 
 seem much more hackish. It also creates a standardized syntax for 
 reverse iteration.

And it seems like you're not alone in liking it.
 D is not C++!

Hooray for that. --bb
Oct 26 2006
prev sibling next sibling parent reply Serg Kovrov <kovrov no.spam> writes:
Hi Walter Bright, you wrote:
 Added foreach_reverse, which addresses a serious shortcoming.
 http://www.digitalmars.com/d/changelog.html

Thanks for great work, Walter! Although could someone explain what exactly "null is now an exact match for null pointers, delegates, arrays, class objects, etc." changed? thanks -- serg.
Oct 17 2006
next sibling parent "Frank Benoit (keinfarbton)" <benoit tionex.removethispart.de> writes:
 Although could someone explain what exactly "null is now an exact match
 for null pointers, delegates, arrays, class objects, etc." changed?

I also want to know this.
Oct 17 2006
prev sibling parent Walter Bright <newshound digitalmars.com> writes:
Serg Kovrov wrote:
 Hi Walter Bright, you wrote:
 Added foreach_reverse, which addresses a serious shortcoming.
 http://www.digitalmars.com/d/changelog.html

Thanks for great work, Walter! Although could someone explain what exactly "null is now an exact match for null pointers, delegates, arrays, class objects, etc." changed?

It makes overloading work more naturally. See bugzilla 412 for an example. It now works analogously to string literals, which will match any string type exactly.
Oct 17 2006
prev sibling next sibling parent "Frank Benoit (keinfarbton)" <benoit tionex.removethispart.de> writes:
Walter Bright schrieb:
 Added foreach_reverse, which addresses a serious shortcoming.
 
 http://www.digitalmars.com/d/changelog.html

Thanks for the release and the bug fixes. You can improve the change log with this: - Add the heading of the bug report also to the changelog. So the changelog is searchable for a specific change. And the reader does not need to click through all bugs. - Add a link to the doc of each language change.
Oct 17 2006
prev sibling next sibling parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.
 
 http://www.digitalmars.com/d/changelog.html

Thanks for the new release :) The foreach-on-delegate seems like a great feature, but in a somewhat harder to implement shape, it has been available for quite a while: ---- import std.stdio; template opHackedApply(alias theImplFunc, IterType) { Iter entry() { Iter it; it.impl = &theImplFunc; return it; } struct Iter { int delegate(IterType) impl; int opApply(IterType dg) { return impl(dg); } } } class Foo { int oldIterImpl(int delegate(inout int) dg) { int a; a = 3; dg(a); a = 9; dg(a); return 0; } mixin opHackedApply!(oldIterImpl, int delegate(inout int)) oldIterMix; alias oldIterMix.entry oldIter; } void main() { Foo f = new Foo; foreach (i; f.oldIter) { writefln(i); } } ---- Sure it doesn't look as nice, but at least it doesn't require the '&' token... But the point is that delegates don't have to be considered aggregates in order to implement this feature. Let's now assume that we have a few other features in D: 1. tuples 2. better metainfo for delegates and functions 3. hiding of private template members (so they dont interfere with automatic name promotion) 4. automatic name promotion of mixins: template foo() { void foo() {} } struct Bar { mixin foo myFunc; void otherFunc() { myFunc(); // currently requires `myFunc.foo();` } } Then the hacked opApply can be used like: ---- template opHackedApply(alias theImplFunc) { Iter opHackedApply() { Iter it; it.impl = &theImplFunc; return it; } private alias theImplFunc.paramTypesTuple; private struct Iter { int delegate(IterType) impl; int opApply(IterType dg) { return impl(dg); } } } class Foo { int oldIterImpl(int delegate(inout int) dg) { int a; a = 3; dg(a); a = 9; dg(a); return 0; } mixin opHackedApply!(oldIterImpl) oldIter; } ---- It's not as short as the treatment-of-delegates-as-aggregates but it only uses builtin features. Yeah, builtin features of my dreamed D version, but all the required features have been proposed before and would make the whole language better (IMHO, but I'm sure more people would agree with me here). On the other side, allowing iteration on delegates only because they match a required signature doesn't make the language simpler at all. -- Tomasz Stachowiak
Oct 17 2006
parent reply Lars Ivar Igesund <larsivar igesund.net> writes:
Walter, you always say that new features shouldn't be added if they fairly
easily can be done with existing language constructs. Now, the post below
is about possible new features in D (of general interest and with many
possible applications), and it is shown how they can be used to implement
an existing (and specific) feature in D. I'm not sure if this should be
used as an argument for removing the new delegate-as-aggregate feature, but
it certainly shows that the proposed features have merit.


Tom S wrote:

 Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.
 
 http://www.digitalmars.com/d/changelog.html

Thanks for the new release :) The foreach-on-delegate seems like a great feature, but in a somewhat harder to implement shape, it has been available for quite a while: ---- import std.stdio; template opHackedApply(alias theImplFunc, IterType) { Iter entry() { Iter it; it.impl = &theImplFunc; return it; } struct Iter { int delegate(IterType) impl; int opApply(IterType dg) { return impl(dg); } } } class Foo { int oldIterImpl(int delegate(inout int) dg) { int a; a = 3; dg(a); a = 9; dg(a); return 0; } mixin opHackedApply!(oldIterImpl, int delegate(inout int)) oldIterMix; alias oldIterMix.entry oldIter; } void main() { Foo f = new Foo; foreach (i; f.oldIter) { writefln(i); } } ---- Sure it doesn't look as nice, but at least it doesn't require the '&' token... But the point is that delegates don't have to be considered aggregates in order to implement this feature. Let's now assume that we have a few other features in D: 1. tuples 2. better metainfo for delegates and functions 3. hiding of private template members (so they dont interfere with automatic name promotion) 4. automatic name promotion of mixins: template foo() { void foo() {} } struct Bar { mixin foo myFunc; void otherFunc() { myFunc(); // currently requires `myFunc.foo();` } } Then the hacked opApply can be used like: ---- template opHackedApply(alias theImplFunc) { Iter opHackedApply() { Iter it; it.impl = &theImplFunc; return it; } private alias theImplFunc.paramTypesTuple; private struct Iter { int delegate(IterType) impl; int opApply(IterType dg) { return impl(dg); } } } class Foo { int oldIterImpl(int delegate(inout int) dg) { int a; a = 3; dg(a); a = 9; dg(a); return 0; } mixin opHackedApply!(oldIterImpl) oldIter; } ---- It's not as short as the treatment-of-delegates-as-aggregates but it only uses builtin features. Yeah, builtin features of my dreamed D version, but all the required features have been proposed before and would make the whole language better (IMHO, but I'm sure more people would agree with me here). On the other side, allowing iteration on delegates only because they match a required signature doesn't make the language simpler at all. -- Tomasz Stachowiak

-- Lars Ivar Igesund blog at http://larsivi.net DSource & #D: larsivi
Oct 17 2006
parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Lars Ivar Igesund" <larsivar igesund.net> wrote in message 
news:eh2fl7$2n9g$1 digitaldaemon.com...
 Walter, you always say that new features shouldn't be added if they fairly
 easily can be done with existing language constructs. Now, the post below
 is about possible new features in D (of general interest and with many
 possible applications), and it is shown how they can be used to implement
 an existing (and specific) feature in D. I'm not sure if this should be
 used as an argument for removing the new delegate-as-aggregate feature, 
 but
 it certainly shows that the proposed features have merit.

While I agree that foreach_reverse seems superfluous with the ability to pass in any delegate as the container, the delegate-as-container is just _too damn cool_ not to implement. I don't know about you, but I'd rather use a single ampersand than go through all that mixin-in and aliasing just to get it to work. That, and with the delegate-as-container, you're no longer limited to just class members - you could have just a nested function which you pass in. Without delegate-as-container, you'd have to create a dummy class with the appropriate mixed-in opApply to get it to work.
Oct 17 2006
next sibling parent reply Lars Ivar Igesund <larsivar igesund.net> writes:
Jarrett Billingsley wrote:

 "Lars Ivar Igesund" <larsivar igesund.net> wrote in message
 news:eh2fl7$2n9g$1 digitaldaemon.com...
 Walter, you always say that new features shouldn't be added if they
 fairly easily can be done with existing language constructs. Now, the
 post below is about possible new features in D (of general interest and
 with many possible applications), and it is shown how they can be used to
 implement an existing (and specific) feature in D. I'm not sure if this
 should be used as an argument for removing the new delegate-as-aggregate
 feature, but
 it certainly shows that the proposed features have merit.

While I agree that foreach_reverse seems superfluous with the ability to pass in any delegate as the container, the delegate-as-container is just _too damn cool_ not to implement. I don't know about you, but I'd rather use a single ampersand than go through all that mixin-in and aliasing just to get it to work. That, and with the delegate-as-container, you're no longer limited to just class members - you could have just a nested function which you pass in. Without delegate-as-container, you'd have to create a dummy class with the appropriate mixed-in opApply to get it to work.

I'm just trying to play the devil's (that's Tom) advocate here ;) What I think was shown by Tom, wasn't that the new feature isn't damn useful, but that there might be better, more flexible and more powerful ways to implement the feature, if it is possible with templates, then the sugar shouldn't be any worse, and the possibilities one could gain for D in general could be substantial. -- Lars Ivar Igesund blog at http://larsivi.net DSource & #D: larsivi
Oct 17 2006
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Lars Ivar Igesund wrote:
 I'm just trying to play the devil's (that's Tom) advocate here ;) What I
 think was shown by Tom, wasn't that the new feature isn't damn useful, but
 that there might be better, more flexible and more powerful ways to
 implement the feature, if it is possible with templates, then the sugar
 shouldn't be any worse, and the possibilities one could gain for D in
 general could be substantial.

Thanks, Lars :) Indeed, I'm not saying that the feature is superfluous, I'm just trying to find a better way. For instance, the older 'trailing delegate' proposal could make foreach obsolete by allowing totally custom foreach-alike loops to be created. Last time I mentioned it, Walter seemed to like the proposal, but there was one open problem - namely that if I had code like: void myLoop(void delegate() dg) { dg(); ... dg(); } myLoop { // special syntax sugar for trailing delegates return; } then the 'return' would actually only return from the delegate, not from the scope that encloses myLoop. This and break wouldn't work for custom loops. But after a while of brainstorming on #d, I return with another proposal. D could solve the problem by more or less translating the code: ---- void each(int[] a, void delegate(int) dg, inout void* ret) { for (int i = 0; i < a.length; ++i) { dg(a[i]); if (ret) return; } } char[] foo() { int[] arr; arr ~= 5; arr ~= 3; arr ~= 2; arr ~= 6; each (arr) (int a) { if (1 == a) return "blah"; if (2 == a) return "hmm"; if (3 == a) break; } return null; } void main() { char[] str = foo(); printf("foo returned: %.*s\n", str); } ---- into: ---- void* CONTINUE = cast(void*)0; void* BREAK = cast(void*)1; void each(int[] a, void delegate(int) dg, inout void* ret) { for (int i = 0; i < a.length; ++i) { dg(a[i]); if (ret) return; } } char[] foo() { int[] arr; arr ~= 5; arr ~= 2; arr ~= 3; arr ~= 6; { char[] retCode; void* ret; each(arr, (int a) { if (1 == a) { retCode = "blah"; ret = &retCode; return; } if (2 == a) { retCode = "hmm"; ret = &retCode; return; } if (3 == a) { ret = BREAK; return; } }, ret); if (ret !is BREAK && ret !is CONTINUE) return *cast(char[]*)ret; } return null; } void main() { char[] str = foo(); printf("foo returned: %.*s\n", str); } ---- Ok, what happened there ? The 'each' function takes two special parameters: 1. a delegate with no return 2. an inout void*: in this case, `void delegate(int) dg, inout void* ret`. They define the trailing delegate - 'dg' is the delegate's body and 'ret' is a special value used to communicate with the enclosing scope. The void* could be moved to the function and delegate's return type, but in that case, the custom loop function couldn't return anything to the enclosing scope. With this approach, e.g. the number of iterations can be returned. There's nothing special about the 'each' function itself, the only magic happens at its call site. In the custom loop's body, each 'break' is converted into '{ ret = BREAK; return; }', each 'continue' into '{ ret = CONTINUE; return; }' and each 'return X' into '{ retCode = X; ret = &retCode; return; } After the custom loop returns, its 'ret' is checked to see whether the return from the loop (in this case, the 'each' function) was a CONTINUE, BREAK or a return from the enclosing scope. In the latter case, that value is returned from the call site. I hope I've covered every spot, but the proposal may still have bugs... Anyway, thanks goto Oskar Linde for helping me come up with this on #d ! -- Tomasz Stachowiak
Oct 17 2006
next sibling parent Lars Ivar Igesund <larsivar igesund.net> writes:
Tom S wrote:

<snip>great proposal</snip>

Seems to me (after getting through the fog of cold) that Tom is on a rampage
today. This would allow almost everything of looping one could think of,
and that without templates and specialized constructs/opSomethings at all
(although I'm sure Tom would abuse templates to make sure that some even
more magnificent could come out of it).

-- 
Lars Ivar Igesund
blog at http://larsivi.net
DSource & #D: larsivi
Oct 17 2006
prev sibling next sibling parent reply Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Tom S wrote:

[snip proposal]

I'd definitely vote for this. It would be a new evolutionary step for D. 
The suggestion is an extremely powerful and generic construct that 
generalizes not only the foreach iterator constructs, but many others 
aswell. Just some quick thoughts:

You could reimplement the while-loop:

void _while(lazy bool condition, void delegate() dg, inout void* ret) {...}

The infinite loop could finally be expressed without cludges:

forever {...}

You could make your own threading construct:

asynchronously { s.connect(); s.send(something); s.close(); }

Or why not:

foreach_parallel (objects) (Object o) {
   o.doSomething();
}

A custom synchronization construct:

mySynchronized("namedLock") {
  ...
}

The possibilities seem endless. It is almost scary. And best of all: It 
doesn't contain a single template. :)

/Oskar
Oct 17 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Oskar Linde wrote:
 Tom S wrote:
 
 [snip proposal]
 

 The possibilities seem endless. It is almost scary. And best of all: It 
 doesn't contain a single template. :)

Er, but what if you want to support more than int[] as the type to be looped over?
 void each(int[] a, void delegate(int) dg, inout void* ret) {
     for (int i = 0; i < a.length; ++i) {
         dg(a[i]);
         if (ret) return;
     }
 }

Looks to me like you've got you an int[]-specific looper there. Gonna need some templates to make that generic, no? --bb
Oct 17 2006
parent Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
Bill Baxter wrote:
 Oskar Linde wrote:
 Tom S wrote:

 [snip proposal]

 The possibilities seem endless. It is almost scary. And best of all: 
 It doesn't contain a single template. :)

Er, but what if you want to support more than int[] as the type to be looped over? > void each(int[] a, void delegate(int) dg, inout void* ret) { > for (int i = 0; i < a.length; ++i) { > dg(a[i]); > if (ret) return; > } > } Looks to me like you've got you an int[]-specific looper there. Gonna need some templates to make that generic, no?

Yes. For the built in arrays, you would need either templates, or do as phobos does internally, work with void * and TypeInfo. The construct in itself is template less. But if you make your own generic container, you will of course need to make your iterator generic too. The "best of all"-part was a joke. :) /Oskar
Oct 17 2006
prev sibling next sibling parent Johan Granberg <lijat.meREM OVEgmail.com> writes:
Tom S wrote:
 

This is a great proposal and would make d stand out among similar languages. Walter please implement this.
Oct 17 2006
prev sibling next sibling parent =?ISO-8859-1?Q?Jari-Matti_M=E4kel=E4?= <jmjmak utu.fi.invalid> writes:
Tom S wrote:

<snip>great proposal</snip>

+1, yet another high level feature that reminds me of Ruby. :)
Oct 17 2006
prev sibling next sibling parent reply Reiner Pope <reiner.pope REMOVE.THIS.gmail.com> writes:
Tom S wrote:
 void each(int[] a, void delegate(int) dg, inout void* ret) {

predicates, like map, fold, and sort: int fold(int[] a, int start, void delegate(int, int) dg, inout void* ret) and fold(myList, 0) (a, b) { yield a + b; } // Yield returns a value from the delegate, as opposed to returning from the enclosing function Note that with some predicates shouldn't be able to control the flow of code, so I think that last parameter (inout void* ret) should be optional -- if the last parameter is a delegate, then break and return can't be used within the delegate.
     for (int i = 0; i < a.length; ++i) {
         dg(a[i]);
         if (ret) return;
     }
 }
 

     each (arr) (int a) {

each (arr) (a) { ... } or arr.each (a) { ... } Cheers, Reiner
Oct 17 2006
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Reiner Pope wrote:
 Tom S wrote:
 void each(int[] a, void delegate(int) dg, inout void* ret) {

predicates, like map, fold, and sort: int fold(int[] a, int start, void delegate(int, int) dg, inout void* ret) and fold(myList, 0) (a, b) { yield a + b; } // Yield returns a value from the delegate, as opposed to returning from the enclosing function

I think it's a great idea and it adds a whole new dimension to the proposal !
 Note that with some predicates shouldn't be able to control the flow of 
 code, so I think that last parameter (inout void* ret) should be 
 optional -- if the last parameter is a delegate, then break and return 
 can't be used within the delegate.

Another good idea :)
     each (arr) (int a) {

each (arr) (a) { ... } or arr.each (a) { ... }

Sure thing :) I'm not yet fully convinced if trailing delegates should be allowed implicitly, just because a function's signature matches some criteria. A special keyword like 'trailing' could be used for it. Of course, because of a lack of a better keyword at the moment, we could just call it 'static' <g> -- Tomasz Stachowiak
Oct 17 2006
parent Reiner Pope <reiner.pope REMOVE.THIS.gmail.com> writes:
Tom S wrote:
 
 I'm not yet fully convinced if trailing delegates should be allowed 
 implicitly, just because a function's signature matches some criteria. A 
 special keyword like 'trailing' could be used for it. Of course, because 
 of a lack of a better keyword at the moment, we could just call it 
 'static' <g>

Versus plain old delegates, trailing delegates can allow: 1. type inference of parameters 2. syntactic sugar to remove ';' at the end, making it look more native 3. continue/break/return behaviour. 1 and 2 are syntactic sugar for the call-site; therefore, they should be allowed implicitly. 3 is special behaviour and shouldn't be allowed implicitly. However, I don't think a new keyword is required. Just make an enum: enum IterationResult { CONTINUE, BREAK, RETURN }; and the break/continue behaviour is then only possible when the function has a delegate as a second-last parameter, and IterationResult as the last. Cheers, Reiner
Oct 17 2006
prev sibling next sibling parent Walter Bright <newshound digitalmars.com> writes:
Tom S wrote:
 ----
 
 void each(int[] a, void delegate(int) dg, inout void* ret) {
     for (int i = 0; i < a.length; ++i) {
         dg(a[i]);
         if (ret) return;
     }
 }
 
 
 char[] foo() {
     int[] arr;
     arr ~= 5;
     arr ~= 3;
     arr ~= 2;
     arr ~= 6;
 
     each (arr) (int a) {
         if (1 == a) return "blah";
         if (2 == a) return "hmm";
         if (3 == a) break;
     }
 
     return null;
 }
 
 
 void main() {
     char[] str = foo();
     printf("foo returned: %.*s\n", str);
 }
 
 ----
 
 
 into:
 
 
 ----
 
 void* CONTINUE    = cast(void*)0;
 void* BREAK        = cast(void*)1;
 
 
 void each(int[] a, void delegate(int) dg, inout void* ret) {
     for (int i = 0; i < a.length; ++i) {
         dg(a[i]);
         if (ret) return;
     }
 }
 
 
 char[] foo() {
     int[] arr;
     arr ~= 5;
     arr ~= 2;
     arr ~= 3;
     arr ~= 6;
 
     {
         char[]    retCode;
         void*    ret;
 
         each(arr, (int a) {
             if (1 == a) { retCode = "blah";    ret = &retCode; return; }
             if (2 == a) { retCode = "hmm";    ret = &retCode; return; }
             if (3 == a) { ret = BREAK; return; }
         }, ret);
 
         if (ret !is BREAK && ret !is CONTINUE) return *cast(char[]*)ret;
     }
 
     return null;
 }
 
 
 void main() {
     char[] str = foo();
     printf("foo returned: %.*s\n", str);
 }

That's a lot like how foreach is implemented now <g>.
Oct 17 2006
prev sibling parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Tom S wrote:
 Lars Ivar Igesund wrote:
 I'm just trying to play the devil's (that's Tom) advocate here ;) What I
 think was shown by Tom, wasn't that the new feature isn't damn useful, 
 but
 that there might be better, more flexible and more powerful ways to
 implement the feature, if it is possible with templates, then the sugar
 shouldn't be any worse, and the possibilities one could gain for D in
 general could be substantial.

Thanks, Lars :) Indeed, I'm not saying that the feature is superfluous, I'm just trying to find a better way. For instance, the older 'trailing delegate' proposal could make foreach obsolete by allowing totally custom foreach-alike loops to be created. Last time I mentioned it, Walter seemed to like the proposal, but there was one open problem - namely that if I had code like:

If there is another, even more general way than foreach-on-delegates, it may or may not, be better than foreach-on-delegates and make it superfluous. But as D currently stands, foreach-on-delegates is not superfluous, or less simple to the language. I find the otherwise: it is quite natural and better than using mixins hacks (even if the difference isn't that much). I've favored this feature ever since Oskar Linde(I think it was him) made some posts about using different kinds of iterators in foreach(using that wrapper hack), and the idea that the language itself could support it, like it does now. But as for foreach_reverse, I do agree that it is very superfluous and way, way specific. -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Oct 18 2006
prev sibling parent Walter Bright <newshound digitalmars.com> writes:
Jarrett Billingsley wrote:
 "Lars Ivar Igesund" <larsivar igesund.net> wrote in message 
 news:eh2fl7$2n9g$1 digitaldaemon.com...
 Walter, you always say that new features shouldn't be added if they fairly
 easily can be done with existing language constructs. Now, the post below
 is about possible new features in D (of general interest and with many
 possible applications), and it is shown how they can be used to implement
 an existing (and specific) feature in D. I'm not sure if this should be
 used as an argument for removing the new delegate-as-aggregate feature, 
 but
 it certainly shows that the proposed features have merit.


I think Tom S's proposed new features have merit, but I have to disagree that they are better for looping than the new delegate approach.
 While I agree that foreach_reverse seems superfluous with the ability to 
 pass in any delegate as the container, the delegate-as-container is just 
 _too damn cool_ not to implement.  I don't know about you, but I'd rather 
 use a single ampersand than go through all that mixin-in and aliasing just 
 to get it to work.  That, and with the delegate-as-container, you're no 
 longer limited to just class members - you could have just a nested function 
 which you pass in.  Without delegate-as-container, you'd have to create a 
 dummy class with the appropriate mixed-in opApply to get it to work. 

I agree with that. Note that: foreach (v; aggr) is shorthand for: foreach (v; &aggr.opApply) in other words, if you've figured out how to write opApply, you've figured out how to write any visitation order, by just changing the name of it. As an aside, I've always disliked designs that needed dummy classes <g>.
Oct 17 2006
prev sibling next sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.
 
 http://www.digitalmars.com/d/changelog.html

foreach_reverse addresses a serious shortcoming? What is that, if instead of: foreach_reverse(Foo f; aggregate) { ... I can do: foreach(Foo f; &aggregate.opApplyReverse) { ... The latter form is both more general (allows any kind of iterators) and more simple/orthogonal (no extra special statements are needed). -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Oct 17 2006
next sibling parent reply Lars Ivar Igesund <larsivar igesund.net> writes:
Bruno Medeiros wrote:

 Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.
 
 http://www.digitalmars.com/d/changelog.html

foreach_reverse addresses a serious shortcoming? What is that, if instead of: foreach_reverse(Foo f; aggregate) { ... I can do: foreach(Foo f; &aggregate.opApplyReverse) { ... The latter form is both more general (allows any kind of iterators) and more simple/orthogonal (no extra special statements are needed).

Good point and ties in with Tom's post; both of these features (foreach_reverse and delegate-as-aggregate) could be easily implemented using other constructs with some "fixes" to the core language. -- Lars Ivar Igesund blog at http://larsivi.net DSource & #D: larsivi
Oct 17 2006
parent Kawa <kawa kinside.com> writes:
Lars Ivar Igesund wrote:
 Bruno Medeiros wrote:
 
 Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

instead of: foreach_reverse(Foo f; aggregate) { ... I can do: foreach(Foo f; &aggregate.opApplyReverse) { ... The latter form is both more general (allows any kind of iterators) and more simple/orthogonal (no extra special statements are needed).

Good point and ties in with Tom's post; both of these features (foreach_reverse and delegate-as-aggregate) could be easily implemented using other constructs with some "fixes" to the core language.

+1 foreach(Foo f; &aggregate.opApplyReverse) seems a much more powerful form
Oct 17 2006
prev sibling next sibling parent reply Bill Baxter <wbaxter gmail.com> writes:
Bruno Medeiros wrote:
 Walter Bright wrote:
 
 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

foreach_reverse addresses a serious shortcoming? What is that, if instead of: foreach_reverse(Foo f; aggregate) { ... I can do: foreach(Foo f; &aggregate.opApplyReverse) { ... The latter form is both more general (allows any kind of iterators) and more simple/orthogonal (no extra special statements are needed).

I agree. Allowing any delegate to be used is a good move I think. But the incremental value added by 'foreach_reverse' and 'opApplyReverse' are minimal once you can already use any delegate as the aggregate. It would be nice to be able to write a function like "reversed" and then just do foreach(Foo f; reversed(aggregate)) { ... To me that seems like a more clean and natural way to support a variety of iteration strategies without adding special-cased reverse iterators to the language. Here's a somewhat limited version of that idea: It's limited by my lack of template-fu, so it just works for arrays, and you have to explicitly pass too many template parameters: class _rev_proxy(AggregateT, ElemT) { this(AggregateT theObj) { obj = theObj; } int opApply(int delegate(inout ElemT) dg) { int done = 0; for (int i = obj.length-1; i >=0; i--) { done = dg(obj[i]); if (done) break; } return done; } private: AggregateT obj; } _rev_proxy!(AggregateT,ElemT) reversed(AggregateT,ElemT)(AggregateT array) { return new _rev_proxy!(AggregateT,ElemT)(array); } unittest { void testrev() { int[] aint = [1,2,3,4,5,6,7]; real[] areal = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0]; foreach(int i; reversed!(int[],int)(aint)) { printf("%d\n",i); } foreach(real r; reversed!(real[],real)(areal)) //foreach(real r; areal) { printf("%f\n",cast(float)(r)); } } testrev(); } I would guess this could probably be expanded with more template-fu so that any class which supports a particular protocol (e.g. has a .length and [] operator, or a reversed() method) can automatically be reversed. And then as a last resort you could always write your own specialization of reversed!() particularly for your class. --bb
Oct 17 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
Is there any reason for not allowing a function to be used too?
Then you could also use a closure as the thing that does the iteration:

int function(int delegate(inout ElemT)) 
reversed(AggregateT,ElemT)(AggregateT array)
{
     int _innerFunc(int delegate(inout ElemT) loopBody)
     {
         int done = 0;
         for (int i = array.length-1; i >=0; i--)
         {
             done = loopBody(array[i]);
             if (done)
                 break;
         }
         return done;
     }
     return &_innerFunc;
}
...
foreach(real r; reversed!(real[],real)(areal))
{...}

--bb


Bill Baxter wrote:
 Bruno Medeiros wrote:
 
 Walter Bright wrote:

 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

foreach_reverse addresses a serious shortcoming? What is that, if instead of: foreach_reverse(Foo f; aggregate) { ... I can do: foreach(Foo f; &aggregate.opApplyReverse) { ... The latter form is both more general (allows any kind of iterators) and more simple/orthogonal (no extra special statements are needed).

I agree. Allowing any delegate to be used is a good move I think. But the incremental value added by 'foreach_reverse' and 'opApplyReverse' are minimal once you can already use any delegate as the aggregate. It would be nice to be able to write a function like "reversed" and then just do foreach(Foo f; reversed(aggregate)) { ... To me that seems like a more clean and natural way to support a variety of iteration strategies without adding special-cased reverse iterators to the language. Here's a somewhat limited version of that idea: It's limited by my lack of template-fu, so it just works for arrays, and you have to explicitly pass too many template parameters: class _rev_proxy(AggregateT, ElemT) { this(AggregateT theObj) { obj = theObj; } int opApply(int delegate(inout ElemT) dg) { int done = 0; for (int i = obj.length-1; i >=0; i--) { done = dg(obj[i]); if (done) break; } return done; } private: AggregateT obj; } _rev_proxy!(AggregateT,ElemT) reversed(AggregateT,ElemT)(AggregateT array) { return new _rev_proxy!(AggregateT,ElemT)(array); } unittest { void testrev() { int[] aint = [1,2,3,4,5,6,7]; real[] areal = [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0]; foreach(int i; reversed!(int[],int)(aint)) { printf("%d\n",i); } foreach(real r; reversed!(real[],real)(areal)) //foreach(real r; areal) { printf("%f\n",cast(float)(r)); } } testrev(); } I would guess this could probably be expanded with more template-fu so that any class which supports a particular protocol (e.g. has a .length and [] operator, or a reversed() method) can automatically be reversed. And then as a last resort you could always write your own specialization of reversed!() particularly for your class. --bb

Oct 17 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Bill Baxter wrote:
 Is there any reason for not allowing a function to be used too?
 Then you could also use a closure as the thing that does the iteration:

Ok, I just realized that "delegate" can also be pointer to a non-static nested function... Duh. So my question should have been -- why doesn't this work? int delegate(int delegate(inout ElemT)) reversed(AggregateT,ElemT)(AggregateT array) { int _innerFunc(int delegate(inout ElemT) loopBody) { int done = 0; for (int i = array.length-1; i >=0; i--) { done = loopBody(array[i]); if (done) break; } return done; } return &_innerFunc; } ... foreach(real r; reversed!(real[],real)(areal)) {...} Compiles but gives: "Error: Access Violation" I'm not totally clear on how pointers/objects are handled in D. It looks the call to reversed() is maybe creating a copy of the data? If I put in printfs the pointer value is different from that of the original int[]. --bb
Oct 17 2006
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Bill Baxter wrote:
 Bill Baxter wrote:
 Is there any reason for not allowing a function to be used too?
 Then you could also use a closure as the thing that does the iteration:

Ok, I just realized that "delegate" can also be pointer to a non-static nested function... Duh. So my question should have been -- why doesn't this work? int delegate(int delegate(inout ElemT)) reversed(AggregateT,ElemT)(AggregateT array) { int _innerFunc(int delegate(inout ElemT) loopBody) { int done = 0; for (int i = array.length-1; i >=0; i--) { done = loopBody(array[i]); if (done) break; } return done; } return &_innerFunc; } ... foreach(real r; reversed!(real[],real)(areal)) {...} Compiles but gives: "Error: Access Violation" I'm not totally clear on how pointers/objects are handled in D. It looks the call to reversed() is maybe creating a copy of the data? If I put in printfs the pointer value is different from that of the original int[].

Basically, when you leave 'reversed', any stack data defined within that function becomes invalid, as D doesn't support real closures. What you're aiming for can be achieved without the new feature anyway, e.g. through: ---- import std.stdio; struct reverse__(AggregType) { alias typeof(AggregType[0]) ElemType; AggregType arr; int opApply(int delegate(inout ElemType) dg) { int ret = 0; for (int i = arr.length -1; i >= 0; --i){ ret = dg(arr[i]); if (ret) break; } return ret; } } reverse__!(T) reverse(T)(T x) { reverse__!(T) res; res.arr = x; return res; } void main() { char[] foo = "foo bar"; foreach (c; foo.reverse) { writefln(c); } } ---- -- Tomasz Stachowiak
Oct 17 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Tom S wrote:
 Bill Baxter wrote:
 Bill Baxter wrote:
 Is there any reason for not allowing a function to be used too?
 Then you could also use a closure as the thing that does the iteration:

Ok, I just realized that "delegate" can also be pointer to a non-static nested function... Duh. So my question should have been -- why doesn't this work? int delegate(int delegate(inout ElemT)) reversed(AggregateT,ElemT)(AggregateT array) { int _innerFunc(int delegate(inout ElemT) loopBody) { int done = 0; for (int i = array.length-1; i >=0; i--) { done = loopBody(array[i]); if (done) break; } return done; } return &_innerFunc; } ... foreach(real r; reversed!(real[],real)(areal)) {...} Compiles but gives: "Error: Access Violation" I'm not totally clear on how pointers/objects are handled in D. It looks the call to reversed() is maybe creating a copy of the data? If I put in printfs the pointer value is different from that of the original int[].

Basically, when you leave 'reversed', any stack data defined within that function becomes invalid, as D doesn't support real closures. What you're aiming for can be achieved without the new feature anyway, e.g. through: ---- import std.stdio; struct reverse__(AggregType) { alias typeof(AggregType[0]) ElemType; AggregType arr; int opApply(int delegate(inout ElemType) dg) { int ret = 0; for (int i = arr.length -1; i >= 0; --i){ ret = dg(arr[i]); if (ret) break; } return ret; } } reverse__!(T) reverse(T)(T x) { reverse__!(T) res; res.arr = x; return res; } void main() { char[] foo = "foo bar"; foreach (c; foo.reverse) { writefln(c); } }

Did you mean foreach (c; reverse(foo)) ?? I guess so. it does seem to compile that way. I think this falls into Walter's "dummy classes and hackish stuff" category though. Is there no way to make something similar work with a nested function? If my reversed function above could just get the pointer to the actual array then it seems like it should work. Is there some way to declare the AggregateT array parameter so that that happens? --bb
Oct 17 2006
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Bill Baxter wrote:
 Tom S wrote:
 Bill Baxter wrote:
 Bill Baxter wrote:
 Is there any reason for not allowing a function to be used too?
 Then you could also use a closure as the thing that does the iteration:

Ok, I just realized that "delegate" can also be pointer to a non-static nested function... Duh. So my question should have been -- why doesn't this work? int delegate(int delegate(inout ElemT)) reversed(AggregateT,ElemT)(AggregateT array) { int _innerFunc(int delegate(inout ElemT) loopBody) { int done = 0; for (int i = array.length-1; i >=0; i--) { done = loopBody(array[i]); if (done) break; } return done; } return &_innerFunc; } ... foreach(real r; reversed!(real[],real)(areal)) {...} Compiles but gives: "Error: Access Violation" I'm not totally clear on how pointers/objects are handled in D. It looks the call to reversed() is maybe creating a copy of the data? If I put in printfs the pointer value is different from that of the original int[].

Basically, when you leave 'reversed', any stack data defined within that function becomes invalid, as D doesn't support real closures. What you're aiming for can be achieved without the new feature anyway, e.g. through: ---- import std.stdio; struct reverse__(AggregType) { alias typeof(AggregType[0]) ElemType; AggregType arr; int opApply(int delegate(inout ElemType) dg) { int ret = 0; for (int i = arr.length -1; i >= 0; --i){ ret = dg(arr[i]); if (ret) break; } return ret; } } reverse__!(T) reverse(T)(T x) { reverse__!(T) res; res.arr = x; return res; } void main() { char[] foo = "foo bar"; foreach (c; foo.reverse) { writefln(c); } }

Did you mean foreach (c; reverse(foo)) ?? I guess so. it does seem to compile that way.

Actually I meant foo.reverse. It compiles and runs fine on .169
 I think this falls into Walter's "dummy classes and hackish stuff" 
 category though.

It's not that bad. There's just one small dummy struct that resides on the stack. The rest is a function that returns it and a generic implementation of 'reverse' that will work on any array type.
 Is there no way to make something similar work with a nested function? 
 If my reversed function above could just get the pointer to the actual 
 array then it seems like it should work.  Is there some way to declare 
 the AggregateT array parameter so that that happens?

Not without dummy classes and hackish stuff <g> -- Tomasz Stachowiak
Oct 17 2006
next sibling parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Tom S wrote:
 Bill Baxter wrote:
 Did you mean
    foreach (c; reverse(foo)) ??
 I guess so.  it does seem to compile that way.

Actually I meant foo.reverse. It compiles and runs fine on .169

Uh, sorry about that... I forgot about the built-in .reverse for arrays and it seems that it was being used in this case. Indeed, it should be reverse(foo).
Oct 17 2006
prev sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Tom S wrote:
 Bill Baxter wrote:
 Tom S wrote:
 Bill Baxter wrote:
 Bill Baxter wrote:




 import std.stdio;


 struct reverse__(AggregType) {
     alias typeof(AggregType[0]) ElemType;
     AggregType arr;
     int opApply(int delegate(inout ElemType) dg) {
         int ret = 0;
         for (int i = arr.length -1; i >= 0; --i){
             ret = dg(arr[i]);
             if (ret) break;
         }
         return ret;
     }
 }

 reverse__!(T) reverse(T)(T x) {
     reverse__!(T) res;
     res.arr = x;
     return res;
 }


 void main() {
     char[] foo = "foo bar";
     foreach (c; foo.reverse) {
         writefln(c);
     }
 }

Did you mean foreach (c; reverse(foo)) ?? I guess so. it does seem to compile that way.

Actually I meant foo.reverse. It compiles and runs fine on .169

Ok, sure it compiles, but if you're just going to reverse the array in-place, then you don't need all that reverse__ stuff up there. I'm confused... :-? But anyway the reverse__ stuff *is* what I was looking to do and it does compile, too, and it does manage to iterate over the array without modifying it.
 I think this falls into Walter's "dummy classes and hackish stuff" 
 category though.

It's not that bad. There's just one small dummy struct that resides on the stack. The rest is a function that returns it and a generic implementation of 'reverse' that will work on any array type.

Any array type, or anything that has a .length property and overloads opIndex, right?
 Is there no way to make something similar work with a nested function? 
 If my reversed function above could just get the pointer to the actual 
 array then it seems like it should work.  Is there some way to declare 
 the AggregateT array parameter so that that happens?

Not without dummy classes and hackish stuff <g>

Seriously? Is there no way to write the function below so that the program prints out the same value twice? void print_addr( ??? arg ) { writefln(&arg); } void main() { int[] arr = [1,2,3,4,5]; writefln(&arr); print_addr(arr); } --bb
Oct 17 2006
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Bill Baxter wrote:
 Actually I meant foo.reverse. It compiles and runs fine on .169

Ok, sure it compiles, but if you're just going to reverse the array in-place, then you don't need all that reverse__ stuff up there. I'm confused... :-? But anyway the reverse__ stuff *is* what I was looking to do and it does compile, too, and it does manage to iterate over the array without modifying it.

Hey, I said I was sorry in a more recent post :P
 Any array type, or anything that has a .length property and overloads 
 opIndex, right?

Hmmm... yup, that should be enough
 Seriously?  Is there no way to write the function below so that the 
 program prints out the same value twice?
 
 void print_addr( ??? arg )
 {
    writefln(&arg);
 }
 
 void main()
 {
     int[] arr = [1,2,3,4,5];
     writefln(&arr);
     print_addr(arr);
 }

Sure it's possible, but in the earlier case, you were trying to access stack variables after returning from the function. In the same manner, 'arg' is no longer a valid variable after print_addr returns, you'd be referencing junk on the stack. You could store it in a static variable, but I consider it hackish, as it's not thread safe :)
Oct 17 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Tom S wrote:
 Bill Baxter wrote:
 Seriously?  Is there no way to write the function below so that the 
 program prints out the same value twice?

 void print_addr( ??? arg )
 {
    writefln(&arg);
 }

 void main()
 {
     int[] arr = [1,2,3,4,5];
     writefln(&arr);
     print_addr(arr);
 }

Sure it's possible, but in the earlier case, you were trying to access stack variables after returning from the function. In the same manner, 'arg' is no longer a valid variable after print_addr returns, you'd be referencing junk on the stack. You could store it in a static variable, but I consider it hackish, as it's not thread safe :)

Right, but really I don't want to access 'arg' I want to access the 'arr' in the outer scope. In C++ I would just make it a reference parameter, and take the address: void print_addr( IntArrayType& arg ) { writefln(&arg); } void main() { int[] arr = [1,2,3,4,5]; writefln(&arr); print_addr(arr); } Then aside from the fact that D is not C++, it would print the same value for both, and it wouldn't be accessing a static variable. And it would be perfectly thread safe. --bb
Oct 17 2006
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Bill Baxter wrote:
 In C++ I would just make it a reference parameter, and take the address:
 
 void print_addr( IntArrayType& arg )
 {
     writefln(&arg);
 }
 void main()
 {
     int[] arr = [1,2,3,4,5];
     writefln(&arr);
     print_addr(arr);
 }
 
 Then aside from the fact that D is not C++, it would print the same 
 value for both, and it wouldn't be accessing a static variable.  And it 
 would be perfectly thread safe.

Heh, that's not the same case. You can do that it D, except that you'd use inout for the reference. The problem arises when you try to return a delegate literal from a function, it then references stack data which is invalid after the function returns. Speaking of C++ analogies, it is just like returning pointers to stack data. Most compilers complain about it because it's simply wrong. There is one solution - actually embed that data in the returned value - just what I did with the struct. An alternative that I dont like very much would be to create a local class and an object thereof, then return a delegate pointing to a method of that object. It works, because objects live on the heap. It might be shorter implementation-wise than my previous solution, but it involves an object allocation and unnecessarily bothers the GC. If you want to use objects nevertheless, iirc an 'AdvancedDelegate' class once announced in this NG allowed a shortcut for this. My Bind library ( http://www-users.mat.uni.torun.pl/~h3r3tic/bind.rar ) could also be used to associate partial parameters with a function or a delegate. But it still requires an object.
Oct 17 2006
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Tom S wrote:
 Bill Baxter wrote:
 In C++ I would just make it a reference parameter, and take the address:

 void print_addr( IntArrayType& arg )
 {
     writefln(&arg);
 }
 void main()
 {
     int[] arr = [1,2,3,4,5];
     writefln(&arr);
     print_addr(arr);
 }

 Then aside from the fact that D is not C++, it would print the same 
 value for both, and it wouldn't be accessing a static variable.  And 
 it would be perfectly thread safe.

Heh, that's not the same case. You can do that it D, except that you'd use inout for the reference. The problem arises when you try to return a delegate literal from a function, it then references stack data which is invalid after the function returns. Speaking of C++ analogies, it is just like returning pointers to stack data.

I see. I was mislead into thinking that closures worked because this code compiled without complaint and worked fine in release mode: int delegate(int) AddN(int N) { int _addN(int x) { return x + N; } return &_addN; } writefln(AddN(3)(4)); But after recompiling with -g it gives me a garbage answer. I thought I could continue to access the _value_ of the N BUT! making a local copy of N in the function, it seems to work: | int delegate(int) AddN(int N) | { | int _addN(int x) { | int MyN = N; | return x + MyN; | } | return &_addN; | } | writefln(AddN(3)(4)); (prints 7 in debug mode too) And applying the same idea, this works too: int delegate(int delegate(inout typeof(AggregateT[0]))) reversed(AggregateT)(inout AggregateT array) { alias typeof(AggregateT[0]) ElemT; int _innerFunc(int delegate(inout ElemT) loopBody) { AggregateT myArr = array; // make a local ref! for (int i = myArr.length-1; i >=0; i--) { if (loopBody(myArr[i])) break; } return -99; } return &_innerFunc; } int[] aint = [1,2,3,4,5,6,7]; foreach(int i; reversed(aint)) { ... } So is that not guaranteed to work? If it is ok then we have a way to do reversed(foo) without dummy classes! (I'll put aside the issue of "hackish stuff" for the moment.) Syntactically and functionally it's not much different, but compared with the struct version it doesn't leak implementation issues to the outside world like having a reverse__ struct dangling out there does. So now, how to make it look less hackish... --bb
Oct 17 2006
prev sibling next sibling parent reply Ivan Senji <ivan.senji_REMOVE_ _THIS__gmail.com> writes:
Bruno Medeiros wrote:
 Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

foreach_reverse addresses a serious shortcoming? What is that, if instead of: foreach_reverse(Foo f; aggregate) { ... I can do: foreach(Foo f; &aggregate.opApplyReverse) { ... The latter form is both more general (allows any kind of iterators) and more simple/orthogonal (no extra special statements are needed).

Hmm, does foreach(Foo f; &aggregate.opApplyReverse) work/can be made to work if aggregate is Foo[]? If not, then I think foreach_reverse is useful.
Oct 17 2006
parent Walter Bright <newshound digitalmars.com> writes:
Ivan Senji wrote:
 Hmm, does foreach(Foo f; &aggregate.opApplyReverse) work/can be made to 
 work if aggregate is Foo[]?

It can be, but it comes off looking hackish.
 If not, then I think foreach_reverse is useful.

It's a spoonful of syntactic sugar.
Oct 17 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Bruno Medeiros wrote:
 Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

foreach_reverse addresses a serious shortcoming? What is that, if instead of: foreach_reverse(Foo f; aggregate) { ... I can do: foreach(Foo f; &aggregate.opApplyReverse) { ... The latter form is both more general (allows any kind of iterators) and more simple/orthogonal (no extra special statements are needed).

The latter form works now.
Oct 17 2006
parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Walter Bright wrote:
 Bruno Medeiros wrote:
 Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.

 http://www.digitalmars.com/d/changelog.html

foreach_reverse addresses a serious shortcoming? What is that, if instead of: foreach_reverse(Foo f; aggregate) { ... I can do: foreach(Foo f; &aggregate.opApplyReverse) { ... The latter form is both more general (allows any kind of iterators) and more simple/orthogonal (no extra special statements are needed).

The latter form works now.

I know it does (I said "can do" instead of "could do" :P ). So my question remains. PS: Note, for better readability, one can use a different (and better) delegate name: foreach(Foo f; &aggregate.iterReverse) { ... -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Oct 18 2006
prev sibling next sibling parent reply "Chris Miller" <chris dprogramming.com> writes:
interface IFoo
{
    void foo();
}

class Foo: IFoo
{
    final void foo() { }
}

DMD 0.170 output:
    test.d(6): class test.Foo interface function IFoo.foo isn't implemented

Is this really what should happen? I thought final could mean it's still  
virtual if it's an interface implementation function or overriding  
something from a base class, just that it cannot be overridden again.
Oct 17 2006
next sibling parent reply "Frank Benoit (keinfarbton)" <benoit tionex.removethispart.de> writes:
see bug report 440
Oct 17 2006
next sibling parent "Chris Miller" <chris dprogramming.com> writes:
On Tue, 17 Oct 2006 12:43:41 -0400, Frank Benoit (keinfarbton)  
<benoit tionex.removethispart.de> wrote:

 see bug report 440

oh, thanks; I wasn't sure if it was a bug. If so, I agree that it's high priority.
Oct 17 2006
prev sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Frank Benoit (keinfarbton) wrote:
 see bug report 440

Does that need a fix right away?
Oct 17 2006
parent reply "Chris Miller" <chris dprogramming.com> writes:
On Tue, 17 Oct 2006 18:17:33 -0400, Walter Bright  
<newshound digitalmars.com> wrote:

 Frank Benoit (keinfarbton) wrote:
 see bug report 440

Does that need a fix right away?

Broke a lot of my projects; went back to DMD 0.169 for now.
Oct 17 2006
parent reply Lutger <lutger.blijdestijn gmail.com> writes:
Chris Miller wrote:
 On Tue, 17 Oct 2006 18:17:33 -0400, Walter Bright 
 <newshound digitalmars.com> wrote:
 
 Frank Benoit (keinfarbton) wrote:
 see bug report 440

Does that need a fix right away?

Broke a lot of my projects; went back to DMD 0.169 for now.

Mango, or parts of it, are also broken by this unfortunatly.
Oct 17 2006
parent Walter Bright <newshound digitalmars.com> writes:
Ok, no prob, I'll get it fixed.
Oct 17 2006
prev sibling parent Walter Bright <newshound digitalmars.com> writes:
Chris Miller wrote:
 
 interface IFoo
 {
    void foo();
 }
 
 class Foo: IFoo
 {
    final void foo() { }
 }
 
 DMD 0.170 output:
    test.d(6): class test.Foo interface function IFoo.foo isn't implemented
 
 Is this really what should happen? I thought final could mean it's still 
 virtual if it's an interface implementation function or overriding 
 something from a base class, just that it cannot be overridden again.

It's a bug.
Oct 17 2006
prev sibling next sibling parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.
 
 http://www.digitalmars.com/d/changelog.html

I've been in the middle of a move, and therefore without internet for a while, so pardon me for responding late, but... Thank you, thank you, thank you, for adding delegate-as-aggregate! I can now send all my multi-iterator boilerplate code to /dev/null and do the happy joy dance. :) And all the other fixes, etc. -- Chris Nicholson-Sauls
Oct 19 2006
parent Walter Bright <newshound digitalmars.com> writes:
You're welcome!
Oct 19 2006
prev sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Walter Bright wrote:
 Added foreach_reverse, which addresses a serious shortcoming.
 
 http://www.digitalmars.com/d/changelog.html

Missing link on: http://www.digitalmars.com/d/phobos/std_outofmemory.html -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Oct 23 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Fixed. Thanks.
Oct 23 2006
parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Walter Bright wrote:
 Fixed. Thanks.

Also, (in case you haven't noticed) the dmd zips also don't have that html file, so the (current or future) releases will need updating too. -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Oct 24 2006