Visitor pattern revisited: it's not (exactly) about double dispatch after all!

[Kaz Kylheku]

I was just doing some thinking about the Visitor pattern, and came to
the conclusion that it does not in fact emulate dispatch on multiple
method arguments, like the feature of CLOS.

In fact, the visitor object encapsulates a generic function, behind
which there are methods specialized to various kinds of objects being
visited. In fact it is a polymorphic functor.

In the visitor pattern, the generic function is indirected upon. This
is done by deriving different kinds of visitor-functors, which
represent different algorithms.

But ultimately, there is only single dispatch that takes place:
dispatching the generic function over one argument, the visited
object, to find a method.

It's function indirection with single dispatch.

In Lisp, a visitor can be represented not as a class object, but as a
generic function:

(defgeneric pretty-print (node)) ;; visitor for pretty printing

(defgeneric evaluate (node)) ;; visitor for evaluation

(defmethod pretty-print ((node foo-node))
;; method specialized over foo-node class
...)

Given a simple list of objects, we can apply a visitor to each of them
using the good old MAPC applicator:

(mapc #'pretty-print list-of-nodes)

See? Double indirection: first through ordinary function application,
then through the object system's method selection. The #'pretty-print
expression *is* an object, a function-object representing a generic
function. That generic function is a container of similar methods for
operating on different kinds of nodes, exactly like a visitor.

It would be stupid to model the visitor as an object, since it is
really an *algorithm* decoupled from objects. Algorithm, consequently,
function.

You can easily use an ordinary non-generic function:

(mapc #'(lambda (node) ...) list-of-nodes)

all the node types go down the node argument; if you need to
distinguish them, then the function body can call generic functions,
or you can use TYPECASE or whatever.

If you really wanted to do the equivalent using double dispatch, the
algorithm selector would probably just be a symbol, or a dummy class:

(defclass pretty-print-dummy () ())

(defmethod visit ((algorithm pretty-print-dummy) (foo-node node))
(declare (ignore algorithm)) ;; it's just a dummy for dispatch

;; do the job of pretty-printing the node
)

So only in this sense is the Visitor Pattern like a two step dispatch:
a dispatch in which one of the classes is a dummy placeholder to do
one level of the dispatching.

Doing it this way in CLOS would be silly. You can no longer use a
lambda expression for the algorithm, because an object is required.
You are forced to define a class, put your code in a method, and then
make sure you have an instance of the class which is quite
inconvenient.

You might as well use symbols to select the algorithm then, taking
advantage of the capability in CLOS to dispatch on symbol identity or
integer value rather than just type:

(defmethod visit ((algorithm (eql :pretty-print))
(foo-node node)) ...)

Then:

(dolist (node list-of-nodes)
(visit :pretty-print node))

(dolist (node list-of-nodes)
(visit :evaluate node))

A symbol makes a more convenient selection dummy than a class.