This is an OOPSLA '99 paper.

Bibtex entry:

AUTHOR       = "Johan Ovlinger and Mitchell Wand",
TITLE        = "{A Language for Specifying Traversals of Object Structures}",
INSTITUTION  = "College of Computer Science, Northeastern University",
YEAR         = 1998,
MONTH        = "November",
NUMBER       = "{NU-CCS-98-??}",
ADDRESS      = "Boston, MA"

This paper proposes to separate traversal code from action code so that traversals talk about how to navigate while visitors talk about what to do during the navigation. The motivation is proper separation of concerns.

The separation into traversals and visitors shields visitors from changes in the class structure. If there is a change in the class structure, it might only be necessary to update the traversal code and the visitor might remain unchanged.

The paper addresses the small methods problem of OO programming in that many of those small methods are specified in a traversal specification rather than having them scattered through several classes. Traversal automata solve an important tangling problem that hinders maintenance of large OO systems.

The paper introduces a new traversal specification language that is translated into Java. Software developers who don't like new languages, can use this paper as a design pattern called "Traversal Separation" in Java or other OO languages. This is practical because the translation shown in the paper only multiplies the length with a small constant factor.

This paper builds on the Demeter theme: separate traversals and actions and write the traversals and actions in a structure-shy way. The paper only focusses on: "separate traversals and actions" but it makes the traversals more expressive. Can some of that additional expressiveness also be added to structure-shy traversals?

I have prepared a response to Mitch Wand's question whether AP (structure-shy traversals) are a sound methodology: Comparing AP and OO.

Because the traversal specifications in this paper are explicit, there is no need for using sophisticated adaptations of automata algorithms to compile them (as in the case of strategies). However, the authors use another basic algorithm: constraint solving, to compile their traversals specifications and to do type inference and compatability checking.

The paper is available in Postscript.

Errata: There are several to be corrected.