Version 5 of 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.