Visitor Pattern

The Visitor Pattern is an OO Design Pattern that makes it easy to add new operations to a set of related classes without having to modify each class to add the new method. It is somewhat related to pattern matching and algebraic types. General discussions at [L1 ] and [L2 ].

Here is a simple example in Tcl to demonstrate the idea. The example here will be a simple OO tree representing integer arithmetic expressions (similar to expr, but much simpler). First, we define the nodes that represent each class, and give each a visit method:

package require XOTcl 1.5
namespace import xotcl::*
# A dummy Term class as superclass
Class Term
# Integers
Class Int -superclass Term
Int method init val { my set val $val }
Int method visit v { $v visitInt [my set val] }
# Addition
Class Add -superclass Term
Add method init {a b} { my set a $a; my set b $b }
Add method visit v {
    my instvar a b
    $v visitAdd [$a visit $v] [$b visit $v]
}
# Multiplication
Class Mul -superclass Term
Mul method init {a b} { my set a $a; my set b $b }
Mul method visit v {
    my instvar a b
    $v visitMul [$a visit $v] [$b visit $v]
}
# Create an example: t1 = (12 + (3 * 4))
Add t1 [Int new 12] [Mul new [Int new 3] [Int new 4]]

We can now use these visit methods to define as many operations as we want over our complex data-type:

# Pretty printer
Object pprint
pprint proc visitInt val   { return $val }
pprint proc visitAdd {a b} { return "($a + $b)" }
pprint proc visitMul {a b} { return "($a * $b)" }
# Simple interpreter/calculator
Object calc
calc proc visitInt val     { return $val }
calc proc visitAdd {a b}   { expr {$a + $b} }
calc proc visitMul {a b}   { expr {$a * $b} }
# Example:
puts "[t1 visit pprint] = [t1 visit calc]"
#=> (12 + (3 * 4)) = 24

See also A lambda calculus interpreter with arithmetic for an alternative to the visitor pattern.

Lars H: I still can't help but feeling this is just data is code, but with extra indirection (sort of turning itself inside out at every step) to make it fit into an OO framework. Which is natural, I suppose, if OO is your primary mechanism for structuring stuff… However, Tcl generally favours functional idioms over OO-idioms.

NEM: Not really. It's just a way of defining a generic traversal (fold) over an inductively defined datatype. As programming languages are also inductively defined, then it is not surprising that it looks similar (code is data, after all). The advantage that would be claimed for the OO representation, as with all things OO, is that it nicely abstracts away the specifics of the concrete representation. A generic fold operation also does this. Treating data as code doesn't do this, as if you change the representation then everything breaks (e.g., if you decide to add source line/column annotations to each term). Of course, you could define a fold procedure (much like the one in the lambda-calc interpreter) that treated data as code within that procedure (and hid this aspect from clients), which would make pattern matching quite simple and fast, but I think I still prefer an explicit pattern matcher (especially if it can match complex sub-terms).

Lars H: One might argue that if you change the representation, then you have also changed the data, but that's getting into a debate on transparent vs. opaque. Besides, one trivial operation in data is code is precisely to convert data to a different format. One thing I'm getting at is that this is effectively what you do with visit above; after (provided I get the syntax right)

Add method listvisit v {
    my instvar a b
    list $v visitAdd [$a listvisit $v] [$b listvisit $v]
}
Mul method listvisit v {
    my instvar a b
    list $v visitMul [$a listvisit $v] [$b listvisit $v]
}
Int method listvisit v {list $v visitInt [my set val] }

the result from

  t1 listvisit $v

is a data structure

  v visitAdd {v visitInt 12} {v visitMul {v visitInt 3} {v visitInt 4}}

that when suitably evaluated produces the same result as t1 visit $v. Moreover, the vs here could just as well be encoded into the evaluation procedure, so after that piece of factorisation we're left with

  visitAdd {visitInt 12} {visitMul {visitInt 3} {visitInt 4}}

to be generated by a dic (for data is code) method defined as

Add method dic {} {
    my instvar a b
    list visitAdd [$a dic] [$b dic]
}
Mul method dic {} {
    my instvar a b
    list visitMul [$a dic] [$b dic]
}
Int method dic {} {list visitInt [my set val] }

What is the difference? In the visitor pattern, the dic data structure is never realised in full, because it is being consumed about as quickly as it is being generated. Again, this is natural if you don't have a more elementary structuring mechanism for data than that provided by the OO, but in Tcl object are heavy and lists are light.

Another thing I'm slightly concerned about is that visit isn't a generic tree traversal operation, in the sense that it only offers post-order traversal.

NEM I really don't see the point of this discussion. Yes you could build up and return a temporary data-structure during the traversal, and then eval it at the end (much like how Haskell handles monads), but I don't really see what you are gaining here. Again, data is code is just one means of implementing the visitor pattern (or a fold), but it doesn't address the core issue that both a fold and the visitor pattern address: namely encapsulation, and insulating your code from changes in representation. Being able to preprocess your structure back to its original form (i.e., stripping the extra information you've added) is not a substitute for proper encapsulation. If you want a list-based representation, still with properly encapsulated traversal logic, then see the lambda-calc interpreter and its generic fold (catamorphism), which achieves the same thing in a non-OO manner.

The visit is generic in two senses: firstly, it abstracts the traversal from the specific operations to be performed during that traversal (thus allowing generic operations to be lifted over the datastructure), and secondly, as a pattern it can be applied to any inductively-defined datastructure. Post-order traversal is all that is generally used, as it tends to be the most useful. You could write a pre-order or in-order traversal, if you so wished.

RFox - 2012-09-17 12:25:20

I think most of the folks commenting on this, and maybe even the original poster are missing the point of the visitor pattern. Normally, this is a collaboration of two objects and a graph of related objects.

Since I don't feel like reproducing the diagram in http://en.wikipedia.org/wiki/Visitor_pattern let's name these two objects the

"Visitor" and the Iteration objects. Let's call the graph of objects the "Visited objects"

Each visited object implements a visit method which expects to receive as a parameter a Visitor object. Each visitor object in turn is expected to implement a method (let's call it Visit) which accepts a Visited object as a parameter. The visited object passes itself to the Visitor. The Iteration object determines which if any Visited objects in the graph are visited and in which order if order is important.

Here's a trivial example of a visitor pattern in use. Since people want to talk about trees. Counting the leaf nodes of a tree. In addition to the methods described above, each visited object implements a leaf method which returns 'true' if it has no children.

In this case the iterator object iterates the nodes of the tree in any order at all passing a visitor to each visited node. The visited node passes itself back to the visitor's Visit method. The Visitor then invokes the leaf method and, if that's true, increments its counter of leaf nodes.

When the iteration object finishes visiting each node, it asks the visitor how many leaf nodes it visited and that completes the operation.

Less trivial, but only slightly contrived: Suppose you want to implement a higher level set of graphics objects on top of a set of primitives like draw point or draw line segment. Suppose you want that system to be able to output a scene of those objects to a different set of output devices. You could use require each graphic object to supply a method that returned a vector of the points it requires drawn and another to return the set of line segments it requires.

To draw the scene of objects, the iterator would use an instance of the abstract factory pattern to instantiate a line and point drawing visitor for the correct output device (see http://en.wikipedia.org/wiki/Abstract_Factory_pattern for information on the abstract factory pattern). It would then visit each object of the scene once passing the point drawer as the objects visitor. The point drawer would then ask each object for the set of points it needs drawn and draw them. Similarly for the line drawer.

In this case, the visitor pattern and abstract factory pattern team up to provide a device independent graphics layer separating the concerns of device specific rendering from device independent rendering and object representation.

Category Example
Updated 2012-09-17 12:25:20