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?

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

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.

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

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.

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?

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

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

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

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