The VISITOR Pattern as a Reusable, Generic, Type-Safe Component

The VISITOR design pattern shows how to separate the

structure of an object hierarchy from the behaviour of traversals

over that hierarchy. The pattern is very flexible; this very

flexibility makes it difficult to capture the pattern formally.

We show how to capture the essence of the VISITOR

pattern as a reusable software library, by using advanced

type system features appearing in modern object-oriented

languages such as Scala. We preserve type-safety statically:

no reflection or similar mechanisms are used. The library is

generic, in two senses: by types (the traversal return type and

the object hierarchy shape) and by strategy (internal versus

external control, imperative versus functional behaviour, orthogonal

aspects such as tracing and memoisation). Finally,

we propose a generalised datatype-like notation, providing a

convenient functional decomposition style in object-oriented

languages.