www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - foreach, an analogy

reply Bill Baxter <dnewsgroup billbaxter.com> writes:
I like analogies, so here goes one.  If you don't just skip it.  :-)

Say you've built a house and you're almost done, but you find one 
doorway with a door that's about an inch too narrow for the frame. 
You'd really like to cover that gap somehow.  You could just leave it 
as-is.  Sure.  You've got *most* of the doorway covered after all.  It's 
not like a criminal could sneak in through a one-inch gap.  Still, it 
could get pretty cold in the winter, so you'd really like to fix it.

Clearly the best solution long term is to get a bigger door.

But you don't have a bigger door.  You do, however, have a clever 
solution: take another door, identical to the first, and hang it on the 
*other side* of the frame to cover the gap.  Perfect!  The gap is covered!

But hmm.  Now there are two doors.  Either of them alone *almost* enough 
to cover the doorway.  You don't really _need_ two doors doing almost 
exactly the same thing.

It's not so bad, though.  At least in the summer, when you don't need 
it, you can just leave that second door open and out of the way. Even 
take it off its hinges and put it in the basement.

That second door, as I'm sure you've figured out, is foreach_reverse.

And really I do believe it's not so bad.  It's an ugly hack, like 
hanging a second door to fill a small gap, but if you don't want to 
iterate backwards over arrays as fast as possible, then you're free to 
ignore it, put that door in the basement, and use whatever technique you 
prefer.

However, I still hope the plan is to one day get a bigger door.

--bb
Oct 18 2006
next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Bill Baxter wrote:

 And really I do believe it's not so bad.  It's an ugly hack, like 
 hanging a second door to fill a small gap, 

Sorry, my apologies to Walter. Let me take that bit back. "Ugly hack" is way too strong. I should have said "it's a band-aid". foreach_reverse does solve a legitimate problem. But just like a band-aid, you hope to be able to take it off eventually. --bb
Oct 18 2006
prev sibling next sibling parent reply John Demme <me teqdruid.com> writes:
Bill Baxter wrote:

 I like analogies, so here goes one.  If you don't just skip it.  :-)
 
 Say you've built a house and you're almost done, but you find one
 doorway with a door that's about an inch too narrow for the frame.
 You'd really like to cover that gap somehow.  You could just leave it
 as-is.  Sure.  You've got *most* of the doorway covered after all.  It's
 not like a criminal could sneak in through a one-inch gap.  Still, it
 could get pretty cold in the winter, so you'd really like to fix it.
 
 Clearly the best solution long term is to get a bigger door.
 
 But you don't have a bigger door.  You do, however, have a clever
 solution: take another door, identical to the first, and hang it on the
 *other side* of the frame to cover the gap.  Perfect!  The gap is covered!
 
 But hmm.  Now there are two doors.  Either of them alone *almost* enough
 to cover the doorway.  You don't really _need_ two doors doing almost
 exactly the same thing.
 
 It's not so bad, though.  At least in the summer, when you don't need
 it, you can just leave that second door open and out of the way. Even
 take it off its hinges and put it in the basement.
 
 That second door, as I'm sure you've figured out, is foreach_reverse.
 
 And really I do believe it's not so bad.  It's an ugly hack, like
 hanging a second door to fill a small gap, but if you don't want to
 iterate backwards over arrays as fast as possible, then you're free to
 ignore it, put that door in the basement, and use whatever technique you
 prefer.
 
 However, I still hope the plan is to one day get a bigger door.
 
 --bb

What is your "bigger door"? -- ~John Demme me teqdruid.com http://www.teqdruid.com/
Oct 18 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
John Demme wrote:
 Bill Baxter wrote:
 ...
 However, I still hope the plan is to one day get a bigger door.

 --bb

What is your "bigger door"?

I think it may be Ruby blocks. But the point is "one day". It can be a D 2.0 thing. --bb
Oct 18 2006
parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
news:eh6rva$1anj$2 digitaldaemon.com...

 I think it may be Ruby blocks.

They're just anonymous functions which happen to come after the function call's closing paren.. I wouldn't really say that they're incredibly earth-shattering or the answer to everything. And D can almost do them already. Instead of: something.each do |item| puts item end You can have: something.each((int item) { writefln(item); }); In fact the "allowing a trailing function literal" has been proposed (by myself included), which would allow: something.each()(int item) { writefln(item); } // maybe there'd need to be a semicolon here? Which is damn close if you ask me.
Oct 18 2006
next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Jarrett Billingsley wrote:
 "Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
 news:eh6rva$1anj$2 digitaldaemon.com...
 
 I think it may be Ruby blocks.

They're just anonymous functions which happen to come after the function call's closing paren.. I wouldn't really say that they're incredibly earth-shattering or the answer to everything.

We don't need the answer to everything, just the answer to how to generalize and make foreach more consistent.
 And D can almost do them
 already.  Instead of:
 
 something.each do |item|
     puts item
 end
 
 You can have:
 
 something.each((int item) {
     writefln(item);
 });
 
 In fact the "allowing a trailing function literal" has been proposed (by 
 myself included), which would allow:
 
 something.each()(int item)
 {
     writefln(item);
 }
 // maybe there'd need to be a semicolon here?
 
 Which is damn close if you ask me. 

That does look pretty good. How do you write an inorder traverser? With Ruby: def traverse left.traverse {|node| yield node } yield self right.traverse {|node| yield node } end Then you do: atree.traverse()(Node node) { writefln(item); } --bb
Oct 18 2006
prev sibling next sibling parent reply Pragma <ericanderton yahoo.removeme.com> writes:
Jarrett Billingsley wrote:
 You can have:
 
 something.each((int item) {
     writefln(item);
 });

I like the look of that. I've been doing a lot of Javascript coding with Prototype lately, and I really gotten used to using closures in this way. But it's almost a parallel solution to for/foreach anyway. If IFTI were a little smarter, you wouldn't need compiler support to pull it off. As a bonus, that would mean that all the other kinds of iteration imaginable (unordered, reverse, sorted, etc) would just be additional iterator templates. // fn returns false to break the loop, true to continue void each(T)(T[] arr, int delegate(inout T) fn){ for(uint i=0; i<arr.length; i++) if(!fn(arr[i])) break; } void reverse(T)(T[] arr, int delegate(inout T) fn){ for(uint i=length-1; i>=0; i--) if!(fn(arr[i])) break; } AFAIK, I'm mostly sure this will work now. Haven't tried it though. Aside from not being able to use break and continue to control the loop behavior, I'd happily use a library that does this. Prototype uses "throw BREAK;" (where 'BREAK' is a constant defined elsewhere) which might be a better looking solution, if a bit kludgey. - EricAnderton at yahoo
Oct 19 2006
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Pragma wrote:
 Jarrett Billingsley wrote:
 You can have:

 something.each((int item) {
     writefln(item);
 });

I like the look of that. I've been doing a lot of Javascript coding with Prototype lately, and I really gotten used to using closures in this way.

Apparently C# allows something similar. From this page: http://excastle.com/blog/archive/2005/05/18/1019.aspx "C# 2.0 will have some compiler magic for closures, but the syntax isn't as elegant as Ruby's you need extra keywords, and the code block has to be inside the parentheses, which seems really clumsy after you get used to Ruby's syntax." C# also has "foreach" which seems to do something very similar to D's: (http://msdn.microsoft.com/msdnmag/issues/04/05/C20/#S3) BinaryTree<int> tree = new BinaryTree<int>(); tree.Add(4,6,2,7,5,3,1); foreach(int num in tree.InOrder) { Trace.WriteLine(num); } In D that would be foreach(int num; &tree.InOrder) { writefln(num); } The only thing that really makes D's look more of a hack is that in D you need that '&'. And maybe the mysterious ';' instead of a more readable 'in'. Actually C# is eerily similar. It also allows iteration over collections: string[] cities = {"New York","Paris","London"}; foreach(string city in cities) { Console.WriteLine(city); } using the magic "GetEnumerator()" method on string. Aka opApply(). Note however, that there is no foreach_reverse.
 Aside from not being able to use break and continue to control the loop 
 behavior, I'd happily use a library that does this.  Prototype uses 
 "throw BREAK;" (where 'BREAK' is a constant defined elsewhere) which 
 might be a better looking solution, if a bit kludgey.

Seems like a 'yield' keyword is needed a la C#, Ruby, Python, and maybe others. --bb
Oct 19 2006
prev sibling parent reply renox <renosky free.fr> writes:
Jarrett Billingsley wrote:

 "Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
 news:eh6rva$1anj$2 digitaldaemon.com...
 
 
I think it may be Ruby blocks.

They're just anonymous functions which happen to come after the function call's closing paren.. I wouldn't really say that they're incredibly earth-shattering or the answer to everything. And D can almost do them already. Instead of: something.each do |item| puts item end You can have: something.each((int item) { writefln(item); }); In fact the "allowing a trailing function literal" has been proposed (by myself included), which would allow: something.each()(int item) { writefln(item); }

You know, personally I prefer the first way to do it than the second, it's "more orthogonal/clean". I wonder why it's not used more? It seems quite readable, maybe there is a performance impact (shouldn't happen if the compiler inline the each function call). Of course both ways are a little more verbose than Ruby due to the static typing, but they are still very good. I wonder if with templates there couldn't be a way to have the "item" element declared implicitely with the correct type? Regards, renoX
 // maybe there'd need to be a semicolon here?
 
 Which is damn close if you ask me. 
 
 

Oct 24 2006
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
renox wrote:
 Jarrett Billingsley wrote:
 
 "Bill Baxter" <dnewsgroup billbaxter.com> wrote in message 
 news:eh6rva$1anj$2 digitaldaemon.com...


 I think it may be Ruby blocks.

They're just anonymous functions which happen to come after the function call's closing paren.. I wouldn't really say that they're incredibly earth-shattering or the answer to everything. And D can almost do them already. Instead of: something.each do |item| puts item end You can have: something.each((int item) { writefln(item); }); In fact the "allowing a trailing function literal" has been proposed (by myself included), which would allow: something.each()(int item) { writefln(item); }

You know, personally I prefer the first way to do it than the second, it's "more orthogonal/clean".

To each his own. I don't think version 1 would be made illegal or anything if the trailing delegate proposal were implemented. But the main difference between them is that version 1 doesn't handle labeled break or goto from within the delegate. Version 2 would presumably rewrite the delegate literal in the same way 'foreach' does now. On the other hand, version 1 works perfectly well with non-literal delegates too, and I don't see version 2 ever being made to work that way. something.each() foo; where foo can be any arbitrary expression that evaluates to a delegate, is probably never going to be allowed.
 I wonder why it's not used more? It seems quite readable, maybe there is 
 a performance impact (shouldn't happen if the compiler inline the each 
 function call).
 
 Of course both ways are a little more verbose than Ruby due to the 
 static typing, but they are still very good.

Ok by me if its a little more verbose, as long as the verbosity is really the minimal required to make static typing work.
 I wonder if with templates there couldn't be a way to have the "item" 
 element declared implicitely with the correct type?

I think we covered most of the bases in the "Prettier iterator implementations in D?" thread in digtalmars.D. Reiner suggested that some types could potentially be deduced and substituted with 'auto'. --bb
Oct 24 2006
prev sibling next sibling parent reply Gregor Richards <Richards codu.org> writes:
Bill Baxter wrote:
 I like analogies, so here goes one.  If you don't just skip it.  :-)
 
 Say you've built a house and you're almost done, but you find one 
 doorway with a door that's about an inch too narrow for the frame. You'd 
 really like to cover that gap somehow.  You could just leave it as-is.  
 Sure.  You've got *most* of the doorway covered after all.  It's not 
 like a criminal could sneak in through a one-inch gap.  Still, it could 
 get pretty cold in the winter, so you'd really like to fix it.
 
 Clearly the best solution long term is to get a bigger door.
 
 But you don't have a bigger door.  You do, however, have a clever 
 solution: take another door, identical to the first, and hang it on the 
 *other side* of the frame to cover the gap.  Perfect!  The gap is covered!
 
 But hmm.  Now there are two doors.  Either of them alone *almost* enough 
 to cover the doorway.  You don't really _need_ two doors doing almost 
 exactly the same thing.
 
 It's not so bad, though.  At least in the summer, when you don't need 
 it, you can just leave that second door open and out of the way. Even 
 take it off its hinges and put it in the basement.
 
 That second door, as I'm sure you've figured out, is foreach_reverse.
 
 And really I do believe it's not so bad.  It's an ugly hack, like 
 hanging a second door to fill a small gap, but if you don't want to 
 iterate backwards over arrays as fast as possible, then you're free to 
 ignore it, put that door in the basement, and use whatever technique you 
 prefer.
 
 However, I still hope the plan is to one day get a bigger door.
 
 --bb

The bigger door is 'for'. 'foreach' is nothing but a convenient wrapper around 'for'. And don't you OOphiles go telling me that your fancy class foo that has iteration /needs/ 'foreach': for (auto bar = foo.begin(); !(bar is null); bar = foo.iterate(bar)) Is it less pretty than foreach? Yeah. That's why foreach exists. But don't go saying that the reverse foreach is a band-aid patch, because both forms are just convenience wrappers around the far more powerful and useful 'for'. Your small door is actually the screen door. - Gregor Richards
Oct 18 2006
next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Gregor Richards wrote:
 Bill Baxter wrote:

 The bigger door is 'for'.  'foreach' is nothing but a convenient wrapper 
 around 'for'.  And don't you OOphiles go telling me that your fancy 
 class foo that has iteration /needs/ 'foreach':
   for (auto bar = foo.begin(); !(bar is null); bar = foo.iterate(bar))
 Is it less pretty than foreach?  Yeah.  That's why foreach exists. 

:-) Heh heh.
 But 
 don't go saying that the reverse foreach is a band-aid patch, because
 both forms are just convenience wrappers around the far more powerful 
 and useful 'for'.  

Yeh, for is like a piece of wood. You can do anything with it. Including make a door. But sometimes its better just to have the door pre-made.
 Your small door is actually the screen door.

Lots of little holes? Maybe. But screen doors have their uses too. Much better for the summertime to help make the livin' easy. ;-) --bb
Oct 18 2006
parent reply "John Reimer" <terminal.node gmail.com> writes:
On Wed, 18 Oct 2006 20:43:13 -0700, Bill Baxter  =

<dnewsgroup billbaxter.com> wrote:

 Gregor Richards wrote:
 Bill Baxter wrote:

 The bigger door is 'for'.  'foreach' is nothing but a convenient  =


 wrapper around 'for'.  And don't you OOphiles go telling me that your=


 fancy class foo that has iteration /needs/ 'foreach':
   for (auto bar =3D foo.begin(); !(bar is null); bar =3D foo.iterate(=


 Is it less pretty than foreach?  Yeah.  That's why foreach exists.

:-) Heh heh.
 But don't go saying that the reverse foreach is a band-aid patch,  =


 because
 both forms are just convenience wrappers around the far more powerful=


 and useful 'for'.

Yeh, for is like a piece of wood. You can do anything with it. =

 Including make a door.  But sometimes its better just to have the door=

 pre-made.

 Your small door is actually the screen door.

Lots of little holes? Maybe. But screen doors have their uses too. Much better for the summertime to help make the livin' easy. ;-) --bb

Don't screen doors keep the bugs out? ;) -JJR
Oct 19 2006
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
John Reimer wrote:
 On Wed, 18 Oct 2006 20:43:13 -0700, Bill Baxter 
 <dnewsgroup billbaxter.com> wrote:
 
 Gregor Richards wrote:
 Bill Baxter wrote:

 The bigger door is 'for'.  'foreach' is nothing but a convenient 
 wrapper around 'for'.  And don't you OOphiles go telling me that your 
 fancy class foo that has iteration /needs/ 'foreach':
   for (auto bar = foo.begin(); !(bar is null); bar = foo.iterate(bar))
 Is it less pretty than foreach?  Yeah.  That's why foreach exists.

:-) Heh heh.
 But don't go saying that the reverse foreach is a band-aid patch, 
 because
 both forms are just convenience wrappers around the far more powerful 
 and useful 'for'.

Yeh, for is like a piece of wood. You can do anything with it. Including make a door. But sometimes its better just to have the door pre-made.
 Your small door is actually the screen door.

Lots of little holes? Maybe. But screen doors have their uses too. Much better for the summertime to help make the livin' easy. ;-) --bb

Don't screen doors keep the bugs out? ;)

LOL! Yes, they do! ;-) --bb
Oct 19 2006
prev sibling next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Gregor Richards wrote:

 The bigger door is 'for'.  'foreach' is nothing but a convenient wrapper 
 around 'for'.  And don't you OOphiles go telling me that your fancy 
 class foo that has iteration /needs/ 'foreach':
   for (auto bar = foo.begin(); !(bar is null); bar = foo.iterate(bar))
 Is it less pretty than foreach?  Yeah.  That's why foreach exists.  

Actually, you've got a point there, sort of. Iterating over *arrays* with for is really really not that bad. for (int i=0; i<x.length; i++) { something(x[i]); } That kind of thing never made me want to run screaming to find a new career while doing C++ programming. But this: for (auto bar = foo.begin(); !(bar is null); bar = foo.iterate(bar)) { something(bar) } would. Yeh, the auto makes it a big improvement over current C++. But still, it's annoyingly long for something that happens so frequently. I really can't stand ugly STL for's anymore after working with Python for a while. But Python doesn't do everything I need. It's not fast. That's why I'm here. --bb
Oct 18 2006
prev sibling next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Gregor Richards wrote:
 The bigger door is 'for'.  'foreach' is nothing but a convenient wrapper 
 around 'for'.  And don't you OOphiles go telling me that your fancy 
 class foo that has iteration /needs/ 'foreach':
   for (auto bar = foo.begin(); !(bar is null); bar = foo.iterate(bar))
 Is it less pretty than foreach?  Yeah.  That's why foreach exists.  But 
 don't go saying that the reverse foreach is a band-aid patch, because 
 both forms are just convenience wrappers around the far more powerful 
 and useful 'for'.

The C++ iterator approach has a serious problem: collections need to be linearized. This is not reasonable for some types of collections, such as a binary tree, which really wants to be traversed in a recursive descent fashion, rather than linearly.
Oct 19 2006
parent reply Gregor Richards <Richards codu.org> writes:
Walter Bright wrote:
 Gregor Richards wrote:
 
 The bigger door is 'for'.  'foreach' is nothing but a convenient 
 wrapper around 'for'.  And don't you OOphiles go telling me that your 
 fancy class foo that has iteration /needs/ 'foreach':
   for (auto bar = foo.begin(); !(bar is null); bar = foo.iterate(bar))
 Is it less pretty than foreach?  Yeah.  That's why foreach exists.  
 But don't go saying that the reverse foreach is a band-aid patch, 
 because both forms are just convenience wrappers around the far more 
 powerful and useful 'for'.

The C++ iterator approach has a serious problem: collections need to be linearized. This is not reasonable for some types of collections, such as a binary tree, which really wants to be traversed in a recursive descent fashion, rather than linearly.

A slight modification can fix that: for (auto bar = foo.begin(); !(bar is null); bar = bar.next()) Anyway, my point was merely that 'foreach' is not analogous to the too-small-door, since it's merely an alternative to 'for' :) - Gregor Richards
Oct 19 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Gregor Richards wrote:
 Walter Bright wrote:
 The C++ iterator approach has a serious problem: collections need to 
 be linearized. This is not reasonable for some types of collections, 
 such as a binary tree, which really wants to be traversed in a 
 recursive descent fashion, rather than linearly.

A slight modification can fix that: for (auto bar = foo.begin(); !(bar is null); bar = bar.next()) Anyway, my point was merely that 'foreach' is not analogous to the too-small-door, since it's merely an alternative to 'for' :)

How do you make for work with the following data structure: struct Tree { Tree* left; Tree* right; int data; } ?
Oct 19 2006
next sibling parent reply Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 
 How do you make for work with the following data structure:
 
     struct Tree
     {    Tree* left;
         Tree* right;
         int data;
     }
 ?

The iterator would have to contain a stack of pointers to previously visited nodes. C++ tree containers don't have this problem because the performance requirements require a balanced tree, and nodes for such a structure contain a pointer to the parent node as well. Sean
Oct 19 2006
next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Sean Kelly wrote:
 Walter Bright wrote:
 How do you make for work with the following data structure:

     struct Tree
     {    Tree* left;
         Tree* right;
         int data;
     }
 ?

visited nodes.

Yes, it's messy and complicated. A stack of pointers also means storage allocation issues.
 C++ tree containers don't have this problem because the 
 performance requirements require a balanced tree,

The iterator requirement is what's really driving the design of C++ containers. D's AAs deliver better performance than STL's trees.
 and nodes for such a 
 structure contain a pointer to the parent node as well.

I know. They're also *far* more complex. Take a look at the STL source for them. I wanted containers for D to be much easier to program.
Oct 19 2006
parent Sean Kelly <sean f4.ca> writes:
Walter Bright wrote:
 Sean Kelly wrote:
 
 C++ tree containers don't have this problem because the performance 
 requirements require a balanced tree,

The iterator requirement is what's really driving the design of C++ containers. D's AAs deliver better performance than STL's trees.

Agreed. Thankfully, C++ 0x will add unordered_map, etc, which are hash containers.
 and nodes for such a structure contain a pointer to the parent node as 
 well.

I know. They're also *far* more complex. Take a look at the STL source for them. I wanted containers for D to be much easier to program.

foreach definately makes iteration through complex containers simpler, and offers more flexibility in container implementation without the need for messy tradeoffs. Sean
Oct 19 2006
prev sibling parent reply Karen Lanrap <karen digitaldaemon.com> writes:
Sean Kelly wrote:

 The iterator would have to contain a stack of pointers to
 previously visited nodes.

But that holds for "foreach" also.
Oct 19 2006
parent reply Andy Knowles <andy.knowles gmail.com> writes:
Karen Lanrap wrote:
 Sean Kelly wrote:
 
 The iterator would have to contain a stack of pointers to
 previously visited nodes.

But that holds for "foreach" also.

No, it doesn't: class Tree { Tree left; Tree right; int data; int opApply(int delegate(inout Tree n) dg) { int ret = dg(this); if(!ret && left != null) ret = left.opApply(dg); if(!ret && right != null) ret = right.opApply(dg); return ret; } } The call stack stores our stack implicitly. This is the difference between for loops and foreach - it doesn't much change the way one writes a loop but it can drastically change the way one writes an iterator.
Oct 19 2006
parent reply Karen Lanrap <karen digitaldaemon.com> writes:
Andy Knowles wrote:

[some code]
There are at least two bugs in your code. Stays the opApply as easy 
if the visits must be inorder?


 The call stack stores our stack implicitly.

Would this be true in any case of enumeration of the tree, asuming that the stored structure has indeed the property of a tree?
Oct 19 2006
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Karen Lanrap wrote:
 Andy Knowles wrote:
 
 [some code]
 There are at least two bugs in your code. Stays the opApply as easy 
 if the visits must be inorder?

Yep. (Assuming the original code worked...) in-order should just require swapping a few lines: class Tree { Tree left; Tree right; int data; int opApply(int delegate(inout Tree n) dg) { int ret=0; if (left != null) ret = left.opApply(dg); if (!ret) ret = dg(this); if(!ret && right != null) ret = right.opApply(dg); return ret; } } I think this example more than anything else shows why ret must die by whatever means possible. The basic algorithm is very simple but it's hard to see that amidst all the setting and checking and returning of 'ret's. And it's very easy to mess up the ret-handling logic, with the result being a bug you won't see until someone tries to do a goto long, long down the road.
 The call stack stores our stack implicitly.

Would this be true in any case of enumeration of the tree, asuming that the stored structure has indeed the property of a tree?

I don't understand your question. --bb
Oct 19 2006
parent reply Karen Lanrap <karen digitaldaemon.com> writes:
Bill Baxter wrote:

 The call stack stores our stack implicitly.

Would this be true in any case of enumeration of the tree, asuming that the stored structure has indeed the property of a tree?

I don't understand your question.

I know of at least one algorithm where it was necessary to peek down into the stack. This is not possible, if the stack is stored implicitely. Therefore the assumed benefit may turn out as a waste of space.
Oct 20 2006
parent reply Bill Baxter <wbaxter gmail.com> writes:
Karen Lanrap wrote:
 Bill Baxter wrote:
 
 
The call stack stores our stack implicitly.

Would this be true in any case of enumeration of the tree, asuming that the stored structure has indeed the property of a tree?

I don't understand your question.

I know of at least one algorithm where it was necessary to peek down into the stack. This is not possible, if the stack is stored implicitely. Therefore the assumed benefit may turn out as a waste of space.

Ah, I see. Yeh, I suppose a traversal algorithm with that sort of property would be trickier. Also I seem to recall reading advice somewhere to the effect of, "if you need the best speed, turn your recursive tree algorithm into a non-recursive one." -- basically by managing the stack of nodes yourself in a list or something. Then you save function call overhead. You're not storing the extra frame pointers, extra copies of local variables etc, that go with pushing and popping stack frames. You just push and pop the node values in your data structure. And then there's the issue with stack depths often being limited (don't know if this is an issue with D or not, but if so...). If foreach/delegate/opApply is D's primary iterator strategy, then to write a serious tree library for big data on 64-bit architectures, does that mean I'll need to avoid opApply as a means of traversing? I guess it's still possible to write the opApply tree traverser non-recursively if you need to. --bb
Oct 20 2006
parent Karen Lanrap <karen digitaldaemon.com> writes:
Bill Baxter wrote:

 I guess it's still possible to write the opApply tree traverser 
 non-recursively if you need to.

Yes---only guesses. In this tree example the traversal is somehow canonical a stream of data without a special leading element. For such streams the 'foreach' is well suited. But if the traversal does have a special leading element, that must be treated differently, then plain old 'for' is well suited.
Oct 20 2006
prev sibling next sibling parent rm <roel.mathys gmail.com> writes:
Walter Bright wrote:
 Gregor Richards wrote:
 Walter Bright wrote:
 The C++ iterator approach has a serious problem: collections need to
 be linearized. This is not reasonable for some types of collections,
 such as a binary tree, which really wants to be traversed in a
 recursive descent fashion, rather than linearly.

A slight modification can fix that: for (auto bar = foo.begin(); !(bar is null); bar = bar.next()) Anyway, my point was merely that 'foreach' is not analogous to the too-small-door, since it's merely an alternative to 'for' :)

How do you make for work with the following data structure: struct Tree { Tree* left; Tree* right; int data; } ?

which the tree is traversed. No argument in the call would mean a default policy, like depth-first or something. Other policy could be provided, and custom policies could be defined and given as a parameter. my 5 cents though, roel
Oct 19 2006
prev sibling parent reply Karen Lanrap <karen digitaldaemon.com> writes:
Walter Bright wrote:

 How do you make for work with the following data structure:
 
      struct Tree
      {     Tree* left;
           Tree* right;
           int data;
      }
 ?

How do you make an iterator for foreach, if you do not own this (or any other) struct or class (because it comes from a library)? What is the general pattern that has to be implemented into every struct or class to allow every user of that struct or class to provide an efficient enumeration for her/his purposes, which are unknown at present? ---und how does the compiler support this?
Oct 20 2006
parent reply Sean Kelly <sean f4.ca> writes:
Karen Lanrap wrote:
 Walter Bright wrote:
 
 How do you make for work with the following data structure:

      struct Tree
      {     Tree* left;
           Tree* right;
           int data;
      }
 ?

How do you make an iterator for foreach, if you do not own this (or any other) struct or class (because it comes from a library)?

I'm not sure I understand. foreach for a class merely calls opApply in that class, so the designer of the class is responsible for writing the iteration code. It's simply a bit easier to write such code as a fixed loop or recursive function than by attempting to retain state for a C++ style iterator. Sean
Oct 20 2006
parent Karen Lanrap <karen digitaldaemon.com> writes:
Sean Kelly wrote:

 I'm not sure I understand.  foreach for a class merely calls
 opApply in that class, so the designer of the class is
 responsible for writing the iteration code.

Yes, that is the current state. But is it suitable for any project? | Iterators have caused problems in the research on ownership | systems. Typically, the dilemma comes up of whether the | collection should own/contain the iterator or vice versa. Some | systems provide solutions that allow iterators to be programmed, | but they do not address the problem of verifying their | functional behavior. "Iterators revisited: proof rules and implementation", http://research.microsoft.com/projects/specsharp/papers/Iterators.pdf
Oct 20 2006
prev sibling next sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Gregor Richards wrote:
 Bill Baxter wrote:
 I like analogies, so here goes one.  If you don't just skip it.  :-)

 Say you've built a house and you're almost done, but you find one 
 doorway with a door that's about an inch too narrow for the frame. 
 You'd really like to cover that gap somehow.  You could just leave it 
 as-is.  Sure.  You've got *most* of the doorway covered after all.  
 It's not like a criminal could sneak in through a one-inch gap.  
 Still, it could get pretty cold in the winter, so you'd really like to 
 fix it.

 Clearly the best solution long term is to get a bigger door.

 But you don't have a bigger door.  You do, however, have a clever 
 solution: take another door, identical to the first, and hang it on 
 the *other side* of the frame to cover the gap.  Perfect!  The gap is 
 covered!

 But hmm.  Now there are two doors.  Either of them alone *almost* 
 enough to cover the doorway.  You don't really _need_ two doors doing 
 almost exactly the same thing.

 It's not so bad, though.  At least in the summer, when you don't need 
 it, you can just leave that second door open and out of the way. Even 
 take it off its hinges and put it in the basement.

 That second door, as I'm sure you've figured out, is foreach_reverse.

 And really I do believe it's not so bad.  It's an ugly hack, like 
 hanging a second door to fill a small gap, but if you don't want to 
 iterate backwards over arrays as fast as possible, then you're free to 
 ignore it, put that door in the basement, and use whatever technique 
 you prefer.

 However, I still hope the plan is to one day get a bigger door.

 --bb

The bigger door is 'for'. 'foreach' is nothing but a convenient wrapper around 'for'. And don't you OOphiles go telling me that your fancy class foo that has iteration /needs/ 'foreach': for (auto bar = foo.begin(); !(bar is null); bar = foo.iterate(bar)) Is it less pretty than foreach? Yeah. That's why foreach exists. But don't go saying that the reverse foreach is a band-aid patch, because both forms are just convenience wrappers around the far more powerful and useful 'for'. Your small door is actually the screen door. - Gregor Richards

Not so. "'foreach' is nothing but a convenient wrapper around 'for'", yes, true, but 'foreach_reverse' is just a wrapper around this: foreach(Foo f; &aggregate.opApplyReverse) { ... which is not more complicated that the 'foreach_reverse' form. As such 'foreach_reverse' is a wrapper, but not a particularly convenient one, unlike 'foreach' which is. As of DMD now, the only advantage in 'foreach_reverse' is ephemerous: it allows efficient reverse iteration of arrays. But couldn't the compiler easily detect this: foreach(Foo f; &fooarray.opApplyReverse) { ... and and compile it as if it were a: foreach_reverse(Foo f; fooarray) { ... -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Oct 19 2006
parent reply Walter Bright <newshound digitalmars.com> writes:
Bruno Medeiros wrote:
 As of DMD now, the only advantage in 'foreach_reverse' is ephemerous: it 
 allows efficient reverse iteration of arrays.

That's the most important use case.
 But couldn't the compiler 
 easily detect this:
   foreach(Foo f; &fooarray.opApplyReverse) { ...
 and and compile it as if it were a:
   foreach_reverse(Foo f; fooarray) { ...

Yes, it could. But it looks like a hack. A little syntactic sugar makes a big difference.
Oct 19 2006
next sibling parent Marcio <mqmnews123 sglebs.com> writes:
Walter Bright wrote:
 But couldn't the compiler easily detect this:
   foreach(Foo f; &fooarray.opApplyReverse) { ...
 and and compile it as if it were a:
   foreach_reverse(Foo f; fooarray) { ...

Yes, it could. But it looks like a hack. A little syntactic sugar makes a big difference.

Don't these things belong to a macro layer? I mean a LISP-like macros, not C macros. In my other message I mentioned Nemerle http://nemerle.org/What_is_Nemerle . They talk about their macro support here http://nemerle.org/Macros I think Paul Graham has a series of essays on the advantages of macros in LISP etc http://www.paulgraham.com/avg.html Is there any text explaining what D templates can do versus macros as in LISP? That might be an interesting article to read... Thanks, marcio
Oct 19 2006
prev sibling next sibling parent reply Reiner Pope <reiner.pope REMOVE.THIS.gmail.com> writes:
Walter Bright wrote:
 Bruno Medeiros wrote:
 As of DMD now, the only advantage in 'foreach_reverse' is ephemerous: 
 it allows efficient reverse iteration of arrays.

That's the most important use case.
 But couldn't the compiler easily detect this:
   foreach(Foo f; &fooarray.opApplyReverse) { ...
 and and compile it as if it were a:
   foreach_reverse(Foo f; fooarray) { ...

Yes, it could. But it looks like a hack. A little syntactic sugar makes a big difference.

Here's a better solution: allow trailing delegates, and define iteration according to them, making user iteration first-class. Then, mandate that arrays support forwards and backwards iteration using, eg, 'each' and 'each_r' and the compiler can optimize such calls away: [0,1,2].each (i) writefln(i); // Prints 0 1 2 [0,1,2].each_r (i) writefln(i); // Prints 2 1 0 void random(int[] array, void print(int i, out IterationStatus v), inout IterationStatus s) { /* define my own random iterator */ } [0,1,2].random (i) writefln(i); // Prints 0 2 1 You get the efficiency and an even nicer syntax. Cheers, Reiner
Oct 19 2006
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Reiner Pope wrote:
 Walter Bright wrote:
 Bruno Medeiros wrote:
 As of DMD now, the only advantage in 'foreach_reverse' is ephemerous: 
 it allows efficient reverse iteration of arrays.

That's the most important use case.
 But couldn't the compiler easily detect this:
   foreach(Foo f; &fooarray.opApplyReverse) { ...
 and and compile it as if it were a:
   foreach_reverse(Foo f; fooarray) { ...

Yes, it could. But it looks like a hack. A little syntactic sugar makes a big difference.

Here's a better solution: allow trailing delegates, and define iteration according to them, making user iteration first-class. Then, mandate that arrays support forwards and backwards iteration using, eg, 'each' and 'each_r' and the compiler can optimize such calls away: [0,1,2].each (i) writefln(i); // Prints 0 1 2 [0,1,2].each_r (i) writefln(i); // Prints 2 1 0 void random(int[] array, void print(int i, out IterationStatus v), inout IterationStatus s) { /* define my own random iterator */ } [0,1,2].random (i) writefln(i); // Prints 0 2 1 You get the efficiency and an even nicer syntax.

Exactly.
   foreach(Foo f; &fooarray.opApplyReverse) { ...



looks like a hack because "foreach" doesn't really *do* anything there, it's the opApplyReverse that does all the work. 'foreach' is just standing there as a signal to the compiler that it should pass the following block as a delagate. But Reiner is right. The compiler doesn't really need that hint, because just using a trailing delegate is already unambiguous, and is much cleaner, and is a more general concept, and at the same time it requires no magic methods (opApply/opApplyReverse) and no keywords (foreach/foreach_reverse). If Reiner's suggestion were in there, I'd could probably accept foreach(i; collection) { body } foreach_reverse(i; collection) {body) as aliases for collection.opApply(i) { body } collection.opApplyReverse(i) { body } But I probably wouldn't use it. I'd probably go with a convention more like Reiner's and do collection.foreach(i) { body } Look, I'm not a Ruby programmer. What I know about Ruby blocks I learned in the past two days. But the instant I read the explanation of how they work, it was like "yes! that's it! it makes perfect sense. THAT's the way to do it." Riener's proposal basically is Ruby blocks for D. Before, when only arrays and objects were allowed in foreach, it kind of made sense. I can totally see why foreach works the way it does. But with the ability to pass an arbitrary delegate-accepting function in there, the 'foreach' becomes like a vestigial tail. It's just not needed anymore. But the current approach is like letting that vestigial tail wag the entire dog. --bb
Oct 19 2006
prev sibling parent reply janderson <askme me.com> writes:
Walter Bright wrote:
 Bruno Medeiros wrote:
 As of DMD now, the only advantage in 'foreach_reverse' is ephemerous: 
 it allows efficient reverse iteration of arrays.

That's the most important use case.
 But couldn't the compiler easily detect this:
   foreach(Foo f; &fooarray.opApplyReverse) { ...
 and and compile it as if it were a:
   foreach_reverse(Foo f; fooarray) { ...

Yes, it could. But it looks like a hack. A little syntactic sugar makes a big difference.

What about: foreach (Foo f; array.reverse) {} The compiler would optimize. -Joel
Jan 25 2007
next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
janderson wrote:
 Walter Bright wrote:
 Bruno Medeiros wrote:
 As of DMD now, the only advantage in 'foreach_reverse' is ephemerous: 
 it allows efficient reverse iteration of arrays.

That's the most important use case.
 But couldn't the compiler easily detect this:
   foreach(Foo f; &fooarray.opApplyReverse) { ...
 and and compile it as if it were a:
   foreach_reverse(Foo f; fooarray) { ...

Yes, it could. But it looks like a hack. A little syntactic sugar makes a big difference.

What about: foreach (Foo f; array.reverse) {} The compiler would optimize. -Joel

Blast from the past! In D, array.reverse calls the method 'reverse'. Anyway, elsewhere in that thread I think Walter basically said, yes the compiler could probably be made to optimize such a thing, but it would be difficult. And he doesn't seem to see anything wrong with foreach_reverse, so I guess he's not inclined to try to make it work that way. --bb
Jan 25 2007
prev sibling parent reply Lionello Lunesu <lio lunesu.remove.com> writes:
janderson wrote:
 Walter Bright wrote:
 Bruno Medeiros wrote:
 As of DMD now, the only advantage in 'foreach_reverse' is ephemerous: 
 it allows efficient reverse iteration of arrays.

That's the most important use case.
 But couldn't the compiler easily detect this:
   foreach(Foo f; &fooarray.opApplyReverse) { ...
 and and compile it as if it were a:
   foreach_reverse(Foo f; fooarray) { ...

Yes, it could. But it looks like a hack. A little syntactic sugar makes a big difference.

What about: foreach (Foo f; array.reverse) {} The compiler would optimize.

But the array would still be reversed after the foreach. L.
Jan 25 2007
parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Lionello Lunesu wrote:
 janderson wrote:
 Walter Bright wrote:
 Bruno Medeiros wrote:
 As of DMD now, the only advantage in 'foreach_reverse' is 
 ephemerous: it allows efficient reverse iteration of arrays.

That's the most important use case.
 But couldn't the compiler easily detect this:
   foreach(Foo f; &fooarray.opApplyReverse) { ...
 and and compile it as if it were a:
   foreach_reverse(Foo f; fooarray) { ...

Yes, it could. But it looks like a hack. A little syntactic sugar makes a big difference.

What about: foreach (Foo f; array.reverse) {} The compiler would optimize.

But the array would still be reversed after the foreach. L.

Is that what he was talking about? I forgot that 'reverse' was an actual existing method that mutates the array. If that's what you meant, then, yeh, what Lionello said. --bb
Jan 25 2007
prev sibling parent Marcio <mqmnews123 sglebs.com> writes:
Gregor Richards wrote:
 The bigger door is 'for'.  'foreach' is nothing but a convenient wrapper 
 around 'for'.  And don't you OOphiles go telling me that your fancy 
 class foo that has iteration /needs/ 'foreach':
   for (auto bar = foo.begin(); !(bar is null); bar = foo.iterate(bar))
 Is it less pretty than foreach?  Yeah.  That's why foreach exists.  But 
 don't go saying that the reverse foreach is a band-aid patch, because 
 both forms are just convenience wrappers around the far more powerful 
 and useful 'for'.  Your small door is actually the screen door.
 
  - Gregor Richards

Wrapper... pre-defined... ok... Then maybe the general mechanism is a way to let the end-user define these wrappers, and therefore make your language extensible and be able to define even DSLs? Isn't that what Nemerle does, inspired by LISP? http://nemerle.org/What_is_Nemerle Mix that with yield-like iterators, and then you have very expressive power. Code that reads well, in a language close to the problem domain. marcio
Oct 19 2006
prev sibling next sibling parent reply Vladimir Kulev <me lightoze.net> writes:
I just want to put my heartfelt cry here. Foreach_reverse is evil! I like D,
but such a things just increase probability that it never will be not a
toy. Implement an iterators integration into foreach, or do something else,
but do in intensive way, not extensive!
Walter, read some books about language architectures and design, please!
There are lots of info in the Internet.
Oct 19 2006
next sibling parent Mike Parker <aldacron71 yahoo.com> writes:
Vladimir Kulev wrote:
 I just want to put my heartfelt cry here. Foreach_reverse is evil! I like D,
 but such a things just increase probability that it never will be not a
 toy. Implement an iterators integration into foreach, or do something else,
 but do in intensive way, not extensive!

I disagree. foreach_reverse is much more clear and concise than any solution using iterators. I don't get why so many people are griping about it. It's just sugar, much like foreach itself. If you don't like it, don't use it. You can implement iterators yourself, or use delegates with a plain foreach to get any sort of order traversal you like. Don't take away foreach_reverse from those of use who actually like it.
 Walter, read some books about language architectures and design, please!
 There are lots of info in the Internet.

Oh, that's a gem.
Oct 19 2006
prev sibling next sibling parent reply Walter Bright <newshound digitalmars.com> writes:
Vladimir Kulev wrote:
 I just want to put my heartfelt cry here. Foreach_reverse is evil! I like D,
 but such a things just increase probability that it never will be not a
 toy. Implement an iterators integration into foreach, or do something else,
 but do in intensive way, not extensive!
 Walter, read some books about language architectures and design, please!
 There are lots of info in the Internet.

Not many programmers can implement an iterator correctly. For the moment let's assume that's not an issue. But still foreach is much more likely to be done correctly, and it is much easier to look at it and see that it is correct.
Oct 19 2006
parent reply Vladimir Kulev <me lightoze.net> writes:
Did you mean writing own class with iterator, or using standard classes with
one?
Oct 19 2006
parent Walter Bright <newshound digitalmars.com> writes:
Vladimir Kulev wrote:
 Did you mean writing own class with iterator, or using standard classes with
 one?

Writing your own.
Oct 19 2006
prev sibling next sibling parent J Duncan <jtd514 nospam.ameritech.net> writes:
Vladimir Kulev wrote:
 Walter, read some books about language architectures and design, please!
 There are lots of info in the Internet.

Thanks, this just made my morning :D
Oct 19 2006
prev sibling next sibling parent reply "Andrey Khropov" <andkhropov_nosp m_mtu-net.ru> writes:
Vladimir Kulev wrote:

 I just want to put my heartfelt cry here. Foreach_reverse is evil! I like D,
 but such a things just increase probability that it never will be not a
 toy. Implement an iterators integration into foreach, or do something else,
 but do in intensive way, not extensive!
 Walter, read some books about language architectures and design, please!
 There are lots of info in the Internet.

I absolutely agree! -- 'non-optimal' is a politically correct term for shit
Oct 19 2006
parent reply Brad Anderson <brad dsource.org> writes:
Andrey Khropov wrote:
 Vladimir Kulev wrote:
 
 I just want to put my heartfelt cry here. Foreach_reverse is evil! I like D,
 but such a things just increase probability that it never will be not a
 toy. Implement an iterators integration into foreach, or do something else,
 but do in intensive way, not extensive!
 Walter, read some books about language architectures and design, please!
 There are lots of info in the Internet.

I absolutely agree!

I would guess that Walter has forgotten more about language architectures and compiler design than you two ever knew combined. foreach_reverse is not a large enough issue to question Walter's abilities. If you've listened closely, and I don't think you have, he has said repeatedly that he sees enough utility (its use w/ arrays) that it's staying. Give it a few releases and hopefully this woeful abomination of sugar won't affect you too much. BA
Oct 19 2006
parent reply "Andrey Khropov" <andkhropov_nosp m_mtu-net.ru> writes:
Brad Anderson wrote:

 I would guess that Walter has forgotten more about language architectures and
 compiler design than you two ever knew combined.  foreach_reverse is not a
 large enough issue to question Walter's abilities.

My intention was not to offend him personally, but some design decisions seem to be really strange. There're foreach analogs in Java 1.5, C#, Python, Ruby etc. but none of these languages have foreach_reverse. Why do you think? I think because reverse it's not so common operation and should better be accomplished in such a way (more generic): --------------- foreach(i;array.reverseIter) -------------- IMHO, it's more flexible.
 
 If you've listened closely, and I don't think you have, he has said repeatedly
 that he sees enough utility (its use w/ arrays) that it's staying.  Give it a
 few releases and hopefully this woeful abomination of sugar won't affect you
 too much.

I think language should be consistent. Shouldn't contain unnecessary built-in hacks. Why not foreach_inorder, foreach_preorder, foreach_postorder, foreach_depthfirst, foreach_breadthfirst? Want syntactic sugar for common operations? Allow syntax extensions such as in Nemerle: http://nemerle.org/Syntax_extensions
Oct 21 2006
parent Brad Anderson <brad dsource.org> writes:
Andrey Khropov wrote:
 Brad Anderson wrote:
 
 I would guess that Walter has forgotten more about language architectures and
 compiler design than you two ever knew combined.  foreach_reverse is not a
 large enough issue to question Walter's abilities.

My intention was not to offend him personally, but some design decisions seem to be really strange.

ok. I just wanted to make sure you understood some of the decisions are based on Walter's vast experience.
 There're foreach analogs in Java 1.5, C#, Python, Ruby etc.
 but none of these languages have foreach_reverse. 
 Why do you think?
 
 I think because reverse it's not so common operation and should better be
 accomplished in such a way (more generic):
 
 ---------------
   foreach(i;array.reverseIter)
 --------------
 
 IMHO, it's more flexible.

And it's been stated in this thread that foreach could be replaced with a more generic 'for', and shouldn't exist at all. It depends on how far back you want to go to be "pure." Some sugar exists, and this is one that Walter seems to want to keep around based on his comments.
 
 If you've listened closely, and I don't think you have, he has said repeatedly
 that he sees enough utility (its use w/ arrays) that it's staying.  Give it a
 few releases and hopefully this woeful abomination of sugar won't affect you
 too much.

I think language should be consistent. Shouldn't contain unnecessary built-in hacks. Why not foreach_inorder, foreach_preorder, foreach_postorder, foreach_depthfirst, foreach_breadthfirst? Want syntactic sugar for common operations? Allow syntax extensions such as in Nemerle: http://nemerle.org/Syntax_extensions

I see your point here, and thanks for the link. I think these Nemerle extensions might be as far as D can go. While I would love to see Lisp-like macros, D isn't the language for it, based on its non-sexp syntax. BA
Oct 23 2006
prev sibling next sibling parent "John Reimer" <terminal.node gmail.com> writes:
On Thu, 19 Oct 2006 02:32:23 -0700, Vladimir Kulev <me lightoze.net> wrote:

 Walter, read some books about language architectures and design, please!
 There are lots of info in the Internet.

Um... at this point in the game, I think Walter could write one. When you're spearheading an effort in design, you are the one that decides what is proper design or not. Books just reveal other peoples ideas on what's right or wrong: they had make things up to at one point. Disagreement with Walter's design decisions here should not be construed as equivalent to a demand that he go back to school. While I don't necesarily agree with some of these decisions (and I most certainly am a novice in this area), I'm content to drop the matter, if no argument convinces him otherwise. It's been the nature of D developement for ages, and it's not likely to change. I just wish for the very best to go into D. I'm sure Walter does too, but it's natural that he sees things differently since his perspective and experience is not the same as everyone elses. -JJR
Oct 19 2006
prev sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Vladimir Kulev wrote:
 I just want to put my heartfelt cry here. Foreach_reverse is evil!

:-) It may not be the most elegant work Walter has done, but it's not going to steal your socks or eat babies, so y'know keep a little perspective here. :-)
I like D,
 but such a things just increase probability that it never will be not a
 toy. Implement an iterators integration into foreach, or do something else,
 but do in intensive way, not extensive!

Agreed it should be done as an integral feature of the language, not as a patch on top of a concept that is not sufficiently powerful to achieve the desired behavior.
 Walter, read some books about language architectures and design, please!
 There are lots of info in the Internet.

I see you got a lot of flack for this statement, but I don't think it's too out of line. Walter's credentials as a language *implementer* and *compiler* designer are totally unassailable. But when it comes to language *architecture* and language *design*, I haven't seen anything to indicate he has much more creds than many of the other folks here. In terms of design of all things computer-related, this book is said to be spectacular by everyone I know who has taken the time to read and understand it: http://www.amazon.com/Computer-Architecture-Concepts-Evolution-Set/dp/0201105578/sr=8-1/qid=1161303518 I wish I had taken that class in grad school now, myself. --bb
Oct 19 2006
parent "John Reimer" <terminal.node gmail.com> writes:
On Thu, 19 Oct 2006 17:24:51 -0700, Bill Baxter  
<dnewsgroup billbaxter.com> wrote:

 I see you got a lot of flack for this statement, but I don't think it's  
 too out of line.  Walter's credentials as a language *implementer* and  
 *compiler* designer are totally unassailable.  But when it comes to  
 language *architecture* and language *design*, I haven't seen anything  
 to indicate he has much more creds than many of the other folks here.

Good point. Now that I think of it, I have to agree with you here. -JJR
Oct 19 2006
prev sibling parent reply clayasaurus <clayasaurus gmail.com> writes:
Bill Baxter wrote:
 ... long analogy

Here is my view on foreach_reverse 1) I really like the idea of foreach being the defacto-iterator for D 2) foreach_reverse allows me to implement an opApply function to my doubly linked list template for not only forward iteration, but backwards iteration as well! Otherwise, I'd have to pass it a &list.reverse delegate which is hackish. Although I wonder if one could just pass in an extra parameter in the opApply function to specify forward, reverse, unordered, ordered. like... foreach(int b; array; "reverse") foreach(int b; array); // assume forward, or whatever the default is foreach(int b; array; "ordered") foreach(int b; array; "unordered") I like the functionality of foreach_reverse, I just think there might be a more flexible way to implement, and in a way so that it makes sense to anyone who understands the D language. (I'm not saying that foreach_reverse is not understandable, I'm just not very excited about allowing the programmer to program their own flow control loop statements like forever {} ).
Oct 19 2006
parent reply Benji Smith <dlanguage benjismith.net> writes:
clayasaurus wrote:
 Here is my view on foreach_reverse
 
 1) I really like the idea of foreach being the defacto-iterator for D

Me too.
 2) foreach_reverse allows me to implement an opApply function to my 
 doubly linked list template for not only forward iteration, but 
 backwards iteration as well! Otherwise, I'd have to pass it a 
 &list.reverse delegate which is hackish.

In C#, the foreach construct operates over arrays or objects that implement the IEnumerable<T> interface (which includes the ICollection<T> subinterface). In Java, the "enhanced for loop" operates over arrays or objects that implement the Iterable<T> interface (which includes the Collection<T> sub-interface). As far as I'm concerned, each class should be responsible for determining which iterators it offers. A doubly-linked list could provide: DoublyLinkedList.getForwardIterator(); DoublyLinkedList.getReverseIterator(); Whereas a binary tree might provide even more: BinaryTree.getInOrderIterator(); BinaryTree.getReverseOrderIterator(); BinaryTree.getDepthFirstIterator(); BinaryTree.getBreadthFirstIterator(); Then, the foreach just iterates through any object that's iterable. Like this: IEnumerable<T> iterator = myBinaryTree.getDepthFirstIterator(); foreach(T item in iterator) { // do stuff with item } A single mechanism for all different kinds of iteration scenarios. The ECMA C# specification (starting on page 236) gives a thorough description of how compilers should implement foreach: http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-334.pdf I think it's a very elegant solution. In D, even overlooking the presence of a fifteen-letter keyword ("foreach_reverse"), the ugliest part is the presence of the opApplyReverse() method, which suggests that the collection object should be responsible for its own iteration, whereas I think iteration should be delegated to a separate object. --Benji Smith
Oct 25 2006
parent Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Benji Smith wrote:
 clayasaurus wrote:
 
 Here is my view on foreach_reverse

 1) I really like the idea of foreach being the defacto-iterator for D

Me too.
 2) foreach_reverse allows me to implement an opApply function to my 
 doubly linked list template for not only forward iteration, but 
 backwards iteration as well! Otherwise, I'd have to pass it a 
 &list.reverse delegate which is hackish.

In C#, the foreach construct operates over arrays or objects that implement the IEnumerable<T> interface (which includes the ICollection<T> subinterface). In Java, the "enhanced for loop" operates over arrays or objects that implement the Iterable<T> interface (which includes the Collection<T> sub-interface). As far as I'm concerned, each class should be responsible for determining which iterators it offers. A doubly-linked list could provide: DoublyLinkedList.getForwardIterator(); DoublyLinkedList.getReverseIterator(); Whereas a binary tree might provide even more: BinaryTree.getInOrderIterator(); BinaryTree.getReverseOrderIterator(); BinaryTree.getDepthFirstIterator(); BinaryTree.getBreadthFirstIterator(); Then, the foreach just iterates through any object that's iterable. Like this: IEnumerable<T> iterator = myBinaryTree.getDepthFirstIterator(); foreach(T item in iterator) { // do stuff with item }

Or, using the current situation: # foreach (item; &myBinaryTree.depthFirstIterator) { # // do stuff with item # } I think that is about as expressive as could be needed?
 A single mechanism for all different kinds of iteration scenarios.
 
 The ECMA C# specification (starting on page 236) gives a thorough 
 description of how compilers should implement foreach:
 
 http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-334.pdf
 
 I think it's a very elegant solution.
 
 In D, even overlooking the presence of a fifteen-letter keyword 
 ("foreach_reverse"), the ugliest part is the presence of the 
 opApplyReverse() method, which suggests that the collection object 
 should be responsible for its own iteration, whereas I think iteration 
 should be delegated to a separate object.
 
 --Benji Smith

-- Chris Nicholson-Sauls
Oct 25 2006