Hi:

Mitchell Wand told me about your interesting Zephyr project.
I thought I would share the idea of traversal strategies with you since we 
find it to be very useful to traverse abstract syntax trees.

The benefits of traversal strategies are that 
compilers get simpler and easier to understand
and more robust to changes in the grammar. (important for quickly changing
domain specific languages.) Visitors, which complement the
traversals, lead to a natural incremental programming style facilitating
changes in the functionality. Therefore, both structural and
behavioral changes become easier.
See: http://www.ccs.neu.edu/research/demeter
for more information.

Regarding the compilation of traversal strategies,
the starting point is the TOPLAS (March 1995) paper by Palsberg et al.
http://www.ccs.neu.edu/research/demeter/biblio/compile-ap.html      
on compiling traversal strategies. It presents a fast but limited algorithm.

Palsberg et al. generalized the compilation algorithm but at the cost
of run-time efficiency which may be exponential in the worst case:
http://www.ccs.neu.edu/research/demeter/biblio/compile2-ap.html
(ESOP '96)

Recently, Boaz Patt-Shamir and I improved the algorithm exponentially
and generalized the concept of traversal strategies.
The new algorithm is fast and practucal.
http://www.ccs.neu.edu/research/demeter/biblio/strategies.html
(submitted to Journal of the ACM)

I think that the concept of traversal strategies and 
this new algorithm which we have implemented in Java
and use regularly, would be very useful for the National Compiler
Infrastructure project and especially the Zephyr project.
The source code for our compiler from Demeter/Java to Java is at:
http://www.ccs.neu.edu/research/demeter/DemeterJava/use/latest-demjava
It shows extensive use of traversals.

Since both your and our project is supported by DARPA and NSF, it would
be interesting to have some sharing of know-how.

We in turn would like to use your compiler infrastructure project
to compile Demeter/Java directly into machine code,
provided it supports a traversal/visitor style of programming
based on traversal strategies.

-- Karl

http://www.cs.virginia.edu/zephyr/mail/zephyr.html
zephyr-investigators@virginia.edu