Guiding visitors: separating navigation from computation

Abstract

Traversals over the object structure are widely used in object-oriented programming, in particular in language processing applications. The visitor pattern separates computation from traversal by specifying the computations that should be performed at each object in a separate visitor class. This makes the implementation of different computations reusing the same traversal scheme possible. However, navigation through the object structure is fixed in the accept methods implemented by the objects that are traversed. This makes it difficult to use other navigation orders. In this paper, we introduce the Guide pattern that describes the separation of navigation from computation and object structure using a double-dispatching iterator. The pattern makes it possible to implement a whole range of navigation schemes for an object-structure. Using a selfdispatching approach based on re flctive method lookup such navigation schemes can be made reusable for whole classes of object-structures (implementing a common interface). The efficiency of this approach is provided by caching method lookups. We extend the approach to generic navigation through arbitrary object-structures using reflelctive field lookup. This results in a generalization of the Walkabout class of Palsberg and Jay with a huge performance improvement in Java, making the Walkabout usable in practice.