Visitor pattern w/ separate iterator (like fold) need ideas

I am pursuing an idea I have had for a while, which I call the VIT
triple, for visitor, iterator, and tree. The name, besides being
descriptive, is designed to invoke memories of the MVC (model, view,
and controller) design pattern from Smalltalk. This is a design
pattern for applying the visitor pattern to AST's (and similar trees,
such as parse trees). The key "innovation" in the pattern is the
separation of the iterator from the visitor. By separating the
iterator from the visitor it is easier to make each reusable.


The model matches roughly a design methodology used in modern FP
(functional programming) languages like ML or Haskell, and I want to
spell out the correspondence here to make things clear.


The tree is the set of data types in the collection. In my model,
they are the AST, the abstract syntax tree. Note, because it is a
tree, it is also the collection itself and the shape (types of
branchings) of the tree is relevant as well as the types of the
leaves. In another model, one might want to separate the container
from the leaves and have a VICL (visitor, iterator, container, and
leaves) pattern. However, in my world, the container and leaves
inextricably connected into a tree, so I don't make the distinction.


The visitor is the function to be applied at the leaves (and in my
case at all the branches also). The visitor does a "pattern match" to
determine what action (what value to compute) it is to take at each
leaf (or branch).


The iterator function is the "fold" or "map" operator, i.e. it is a
higher-order-function. It walks the collection in a specific order to
apply the visitor to the desired leaves. The obvious common orders
are preorder and postorder. However, one can apply "pattern matching"
at the branches to compute special custom orders. For example to
prune the tree at a certain level, one can define an order that does
not walk children below certain branches. One can also define orders
the skip the brnaches and walk only the children. Again, by using
pattern matching one can mix-and-match to define an iterator that
walks the tree in any order one wants (i.e. doing postorder for most
branches, except for a few specific branches where it does preorder).


Ok, now I have used this design pattern to implement an interpreter,
where the visitor function is the execute operation for each part of
the language. The iterator for this interpreter stops at the
"statement" level and does not walk the tree below it. From that
level we can do separate walks of the expression trees belowe with a
different interpreter to do evaluations of expressions. That
implements the intended semantics for my little (domain specific)
language pretty well.


However, and this is the spark for my question, I come to an
interesting situation with statements that contain other statements
nested within them, e.g. if-then-elses and loops. The trivial
solution is to start a new iterator on the tree, that executes those
statements within the context of executing that statement they are
nested within. Below is some pseudo-code that illustrates how I can do
that.


class if-then-else-stmt is-a stmt
      { // there are 3 parts to this object
      var if-expr: *expr;
      var then-stmt: *stmt;
      var else-stmt: *stmt;


      // here is the iterator
      func xqt-iterator() = no-childern-iterator();


      // here is the visitor
      func xqt-visitor()
            {
            var iter: iterator;
            var rslt: value;
            forall iter = new expr-iterator(root = if-expr)
                {
                rslt = iter->expr-visitor(); // compute the if-expr value
                }
            if rslt then
                {
                forall iter = new xqt-iterator(root = then-stmt)
                    {
                    iter->xqt-visitor(); // execute the then clause
                    }
                }
            else
                {
                forall iter = new xqt-iterator(root = else-stmt)
                    {
                    iter->xqt-visitor(); // execute the else clause
                    }
                }
            }
      }


This is fairly simple, straight-forward and does what I want.
However, it has the disadvantage of creating new iterators to walk the
then or the else clauses. It would be much better, if I could
somehow, change the xqt-iterator for the if-then-else-stmt to execute
the desired then or else clause. As I write this out, I have an idea
how to do that. However, I would like recommendations.


So, I am soliciting suggestions on how to improve this model.
Including ones like read the XYZZY book or article.


Thanks,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

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