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.



http://excastle.com/blog/archive/2005/05/18/1019.aspx

    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."


(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'.


   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.



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(=




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? ;)


-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;
     }
 ?


 The iterator would have to contain a stack of pointers to previously 
 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;
     }
 ?


I'd say, the .next() takes an argument, which defines the policy by
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.

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.



 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.



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.


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.


 
 

 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:




I think that is about as expressive as could be needed?


 A single mechanism for all different kinds of iteration scenarios.
 

 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