Hi Mitch:

before Node 			//before
before -> Node,right,Node	//middle
after  Node			//right
=============================
Hi Mitch:

your traversal automata fill a gap in the current traversal
specification languages: how to talk about visits back to the root
in a "symmetric" way.

Your solution:

>d(q1,leaf) = e					  //don't do anything at a leaf
>d(q1,node) = "before" left q1 "middle" right q1 "after"

is more symmetric than:

BinTree : Leaf | Node.
Leaf = .
Node = <left> BinTree <right> BinTree.

gauche =
{-> Node BinTree only-through -> *,left,*
 -> BinTree *}

droite =
{-> Node BinTree only-through -> *,right,*
 -> BinTree *}

your =
seq(gauche, droite)

The code for the 3 phases goes into the methods (expressed in visitors):
your.gauche.Root.before: "before"
your.droite.Root.before: "middle"
your.droite.Root.after : "right"

Since the purpose of strategies is also to describe detailed traversals
if needed, maybe there is an elegant way to marry traversal
automata and strategies.

It would be nice if in the syntactic representation of the traversal
automata there is a nice way to avoid mentioning all those state names.

I will put this topic on for the next seminar as you suggested.

-- Karl
PS.
Here is probably a little typo:
>d(q1,leaf) = e
>d(q1,node) = "before" left q1 right q1
			    ^^       ^^

>From wand@ccs.neu.edu Wed Jan  7 16:49:18 1998
>From: Mitchell Wand <wand@ccs.neu.edu>
>To: lieber@ccs.neu.edu, will@ccs.neu.edu
>Cc: dem@ccs.neu.edu, jcurry@ccs.neu.edu, lblando@ccs.neu.edu,
>        palsberg@cs.purdue.edu, wand@ccs.neu.edu
>Subject: Traversal automata:  another specification language for traversals
>
>One of the foundations of the demeter method is the separation of processing
>into traversals and visitors.
>
>As we've seen, succinct traversal specifications are perhaps *too* succinct:
>they turn out to be brittle instead of robust in the presence of changes in
>dense class graphs.
>
>So I propose a somewhat lower-level mechanism for specifying traversals on
>concrete object graphs. It is not so succinct as the [A,B] notation, but its
>semantics is clearer in complex class graphs.  It is still declarative in
>flavor, and far more structured than plain old Java code, so that the
>traversal specifications will be easy to change as class graphs change.
>
>Note that this proposal does not yet address parameterization. I'll say a few
>words about this at the end. 
>
>I call this proposal "Traversal Automata".  Here's the setup:
>
>We assume we have:
>
>A class graph with a set C of classes
>An object graph with a set O of objects. 
>An alphabet M of labels (of edges in the object graph)
>An alphabet P of visit parameters (to be explained later).  
>
>Let oP denote P | e  (ie an optional P)
>
>Let A denote the regular expression oP(M Q oP)* , ie (MxQ)* with optional P's
>before, between, or after each MxQ pair.
>
>We assume we have a map class: O -> C mapping each object to its class.
>
>A traversal automaton consists of:
>
>a state set Q 
>a transition function d: Q x C -> A
>
>We describe the action of the automaton as a function 
>
>d* : Q x O -> (O x P)*
>
>d*, given a starting state q and an object o, gives the sequence of method
>calls generated by the automaton traversing the object graph.
>
>The idea is that a sequence in A describes the visits to the current object
>and the visits to the successors of that object in the object graph.
>
>Let V(o,p) = if p = e then e else (o,p)    ; p in oP
>  {turn a p into a visit, else empty string} 
>
>d*(q, o) = 
>  let w = d(q, class(o)) in   ;; w is the local traversal spec
>  in let (p1 m1 q1 p2 m2 q2 ....pk mk qk p_(k+1)) = w  
>			;; pattern matching on w 
>                    
>  in  V(o,p1) ^ d*(q1, o.m1) ^ V(o,p2)  ^ 
>      ... ^ V(o,pk) ^ d*(qk, o.mk) ^ V(o,p_(k+1))
>
>The point of the story is that the automaton, traversing object o in state q,
>traverses o.m1,..., o.mk in states q1,..,qk, in the meantime doing an official
>Visit to o as many as k+1 times, with parameters given by the p1,..,pk+1; if
>any of these are empty, the corresponding potential visit is not performed.
>
>So I'd write Will's traversal as something like
>
>d(q1,leaf) = e					  //don't do anything at a leaf
>d(q1,node) = "before" left q1 "middle" right q1 "after"
>
>This visits each node 3 times, with parameters "before", "middle", and
>"after," respectively. 
>
>A pre-order traversal would be
>
>d(q1,leaf) = e
>d(q1,node) = "before" left right
>
>Notes:
>
>1.  This extends my earlier proposal about proving the correctness of
>traversals by adding multiple states, by allowing the specification of
>visit/no-visit, and by being flexible about how the visitor gets to know which
>visit it is (this last was always pretty confusing in my previous proposal).
>
>2.  The formal spec needs to be patched to correctly account for infinite
>loops.  This shouldn't be hard.
>
>3.  The basic idea is that we would need a tool that takes a traversal
>automaton and generates a set of methods to do the traversal, which we would
>then call with a visitor.  Checking consistency with types would probably be
>nice, while we're at it.
>
>4.  Like the basic traversal/visitor factorization, this proposal allows you
>to re-use a traversal with different visitors.  It does not allow a traversal
>automaton to be reused with different class graphs.  However, one could
>imagine a code-generation process that would take a traversal automaton and a
>name map to produce traversal methods.  This would allow a traveral automaton
>to be re-used with different class graphs.
>
>5.  This is not intended as a replacement for the [A,B] notation, but rather
>as an *addition* to Demeter, to give its users another choice of language for
>specifying traversals.
>
>Let's talk about this over the next few days, and then maybe we can talk about
>it some more at the next seminar.
>
>--Mitch
>