View mode: basic / threaded / horizontal-split · Log in · Help
October 19, 2006
Re: foreach, an analogy
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
October 19, 2006
Re: foreach, an analogy
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
October 19, 2006
Re: foreach, an analogy
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;
	}
?
October 19, 2006
Re: foreach, an analogy
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
October 19, 2006
Re: foreach, an analogy
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
October 19, 2006
Re: foreach, an analogy
Vladimir Kulev wrote:
> Did you mean writing own class with iterator, or using standard classes with
> one?

Writing your own.
October 19, 2006
Re: foreach, an analogy
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.
October 19, 2006
Re: foreach, an analogy
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
October 19, 2006
Re: foreach, an analogy
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.
October 19, 2006
Re: foreach, an analogy
Sean Kelly wrote:

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

But that holds for "foreach" also.
1 2 3 4 5 6
Top | Discussion index | About this forum | D home