View mode: basic / threaded / horizontal-split · Log in · Help
October 20, 2006
Re: foreach, an analogy
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?
October 20, 2006
Re: foreach, an analogy
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
October 20, 2006
Re: foreach, an analogy
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.
October 20, 2006
Re: foreach, an analogy
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
October 20, 2006
Re: foreach, an analogy
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.
October 20, 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;
>      }
> ?

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?
October 20, 2006
Re: foreach, an analogy
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
October 20, 2006
Re: foreach, an analogy
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
October 21, 2006
Re: foreach, an analogy
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
October 23, 2006
Re: foreach, an analogy
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
1 2 3 4 5 6
Top | Discussion index | About this forum | D home