Re: recursive iterators

> To be (lightly) more specific, I have a program where I walk tree
> structures recursively, generating elements of a sequence. The program
> does several of these walks at once, doing different things with the
> elements.
>
> I'd like to express this as loops over tree nodes, but the recursion in
> the iterator doesn't easily fit into C++-style iterators. It works as
> recursive functions, but then the loop bodies become closure-like
> parameters.
>
> I can force this in C and C++, but it's clumsy.
>
> What I'd like is something more like Smalltalk, where the loop iterator
> calls the loop body (or better, one of several alternative bodies).


The C++ Standard Template Library contains a number of classes (e.g.
map, multimap, set, multiset) that are normally constructed as trees
internally, but which provide iterators that work the way you mention.
There is no reason in principle why an AST node class (say) couldn't
offer iterators that make walking subtrees trivially easy, using the
same kind of idea, e.g.:


void walk_my_tree(ast_node *n)
{
      ast_node::preorder_iterator pi = n->begin_preorder();
      ast_node::preorder_iterator piEnd = n->end_preorder();


      while(pi != piEnd)
      {
            ast_node &this_node = *pi;


            // do something with the node...


            ++pi;
      }
}


It is possible to see how (as I've hinted) you could define preorder,
in order and postorder iterators. Note that STL iterators are kind-of
scrunged to 'look like' pointers syntactically, but except in special
cases they are often not implemented as anything remotely like a
pointer.


Sarah

Return to the comp.compilers page.
Search the comp.compilers archives again.