Implementing the Visitor Pattern

The visitor pattern is a very interesting way to go if you have a lot of operations
which need to be applied to one data structure. Especially if this is a recursive data structure such as a tree.

Python provides a very interesting way to implement the visitor patter and get
around some of its inherent problems. Granted when done this way you are really getting something closer to double dispatch then the visitor pattern.

Allow me to take a short deter into CLOS (the common lisp object system). Objects
in CLOS bear more of a resemblance to Structures in C then to Objects in a language Like Java or Python in that a CLOS object has no methods. The methods are defined separately as generic functions. One feature of generic
fumigates is that they can select an implementation based on multiple arguments, where's in most OO languages only the first (the calling object) is considered. This idea is really quite powerful.

back on the python front. Here is an interesting way to implement the visitor
pattern using the available introspection tools.

class Node(object):

    def __init__(self):
        self.MethodNames = [ cls.__name__ for cls in self.__class__.__mro__]

   def accepts(self, visitor, prefix='visit_'):
       for name in self.MethodNames:
           vName = prefix+name
           if hasattr(visitor, vName):
               # we could have allowed getattr to raise an exception but this is generally slower
               # then an explicit check. In this case we assume that the exception would be 
               # thrown regularly under normal operation and would hurt performance.
               getattr(visitor, vName)(self)
               #do any cleanup activity
               return
       raise AttributeException("Visitor %s does not contain a suitable method." %  visitor)


class Visitor(object):

    def visit_Node(self, node):
        #do something
        pass

The important thing about these code is the use of __class__.__mro__
__mro__ stands for Method Resolution Order and is a list of class objects in the
order they are tried when a definition is needed for a method. In Older versions of python this is a simple (and fundamentally broken) depth first search. The problem with simple depth first search is that it doesn't handle
multiple inheritance corectly. Since Python 2.4 a more sophisticated algorithm is used (incidentally the same Algorithm as used in CLOS).

We have in effect created a Dispatch method which is polymorphic on the type of the current class. And moreover has the same method resolution order as the python language its self. The main advantage of this approach over a more
traditional one is that we are free to extend the Node class hiarchy at any time
without breaking existing visitors. Granted the dynamic dispatch will be slightly
slower than accept methods which explicitly call a particular method.