 Guiding Visitors: Separating Navigation from Computation
started 7/25/2002; 1:29:33 AM - last post 7/27/2002; 3:04:24 AM
|
|
jon fernquest - Guiding Visitors: Separating Navigation from Computation 
7/25/2002; 1:29:33 AM (reads: 1912, responses: 4)
|
|
| Guiding Visitors: Separating Navigation from Computation |
|
Operations on abstract syntax trees are an important
application of the Guide pattern which goes beyond the Visitor pattern and separates "navigation from computation and object structure":
"A guide is an object that captures a traversal scheme through an object structure....
the notion of top-down or bottom-up traversal can be captured
by a guide and used in visitors for pretty-printing, collecting components by
predicates, transforming a structure etc."
A simple example, counting the number
of leafs in a tree, is rewritten several times
gradually uncoupling navigation from the Visitor
computation and object structure and discussing the
implementation of similar libraries such as
JJForester,
JJTree
[1,
2],
Java Tree Builder, and
Walkabout.
A Generic extension to Java is used because
"parameterised types allow us to parameterise a class with another class.
This will prevent many type casts, especially when working with collections."
(an early-access implementation of the Java 2 SDK 1.5 compiler is used).
The paper also mentions an extension of the
JRefactory refactoring tool
to "collect the exceptions that are caught around a set of statements."
Posted to OOP by jon fernquest on 7/25/02; 1:36:34 AM
|
|
|
|
Ehud Lamm - Re: Guiding Visitors: Separating Navigation from Computation
7/25/2002; 1:59:55 AM (reads: 797, responses: 0)
|
|
|
direct link to the paper.
I wonder how this compares with functional approaches beased on h.o.f.
If I understand them correctly guides use data abstraction to implement what is essentially a procedural abstraction. This is, of course, the usually OOP way of doing things.
Chris would probably want to mention that guides vs. visitors is somewhat related to seperation of concerns as in MVC.
|
|
Martin Bravenboer - Re: Guiding Visitors: Separating Navigation from Computation
7/25/2002; 11:13:12 AM (reads: 756, responses: 0)
|
|
|
I've implemented this separation of navigation from computation before I actually become familiar with Stratego and JJTraveler. The separation I've described in this paper is related to the strategic programming of Stratego, where rewriting rules are applied according to a programmable rewriting strategy.
My implementation has a lot in common with the Visitor combinators (the paper on visitor combinators is very interesting!) of JJTraveler. The visitor combinators do however not enforce or reveal a clear distinction between navigation and computation. A combination of the visitor combinators of JJTraveler and the Guides - Visitors separation of my paper would be interesting, but unfortunately I haven't explored such an implementation yet.
I used this separation because a lot of Visitor applications (in this case in JRefactory) encode the traversal order/navigation in the visitor. In the most positive case, this is done by invoking some method in a superclass, which is an implemenation of a traversal scheme. In the most negative case, the traversal is implemented in the accept methods of the object-structure. Both approaches do not allow a different traversal order/navigation, which is a problem (this problem is also solved by JJTraveler and Stratego). I've used this seperation extensively and succesfully in an extension of the JRefactory tool (extract method, which is nowadays also supported by JRefactory itself). Nowadays I wouldn't even think about implementing such a meta-tool in Java ;-) .
|
|
Alex Sauer-Budge - Re: Guiding Visitors: Separating Navigation from Computation
7/25/2002; 1:51:41 PM (reads: 747, responses: 0)
|
|
|
I like the decompositions produced by concepts like the Guide-Visitor discussed by Martin, but I wonder if implementations of these decompositions in languages like Java and C++ (the latter being the one with which I am more familiar) are doomed to inefficiency because the language merely provides semantic mechanisms for the abstractions, but does not not support them at a fundamentally sufficient level for these decompositions to be productively employed (as a pragmatic solution). More concretely, I am concered that:
1) While the decomposition works, an inordinate amount of time must be spent developing the library (thus nullifying the advantage).
2) The decomposition is impossible to support efficiently (in the computational cost sense) enough to be viable.
3) A non-trivial portion of the code required to support the decomposition requires such language hijinks as to detrimentally obfuscate the code.
Can languages like Java and C++ be augmented to support these decompositions more naturally and efficiently, or do these decompositions suggest a new OOP paradigm which requires a "new" language to really swim?
|
|
jon fernquest - Re: Guiding Visitors: Separating Navigation from Computation
7/27/2002; 3:04:24 AM (reads: 699, responses: 0)
|
|
|
|
|
|