View mode: basic / threaded / horizontal-split · Log in · Help
October 19, 2006
Re: foreach, an analogy
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
October 19, 2006
Re: foreach, an analogy
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
October 19, 2006
Re: foreach, an analogy
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 {} ).
October 19, 2006
Re: foreach, an analogy
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
October 19, 2006
Re: foreach, an analogy
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
October 20, 2006
Re: foreach, an analogy
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.
October 20, 2006
Re: foreach, an analogy
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
October 20, 2006
Re: foreach, an analogy
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
October 20, 2006
Re: foreach, an analogy
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
October 20, 2006
Re: foreach, an analogy
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
1 2 3 4 5 6
Top | Discussion index | About this forum | D home