Visitor and Walkabout (in Python)

A couple of weeks ago I found a link to a stackoverflow question I’d saved away a long time ago. I’d saved it due to having asked myself the exact same question and being curious about the papers when I found that answer. Over the last few weeks I’ve made my way through those papers and as so often I found a couple of references to other papers that sound interesting. One such paper was The Essence of the Visitor Pattern by Jens Palsberg and C. Barry Jay. There was however one little thing that bugged me with the Walkabout pattern and I thought I’d try to work that out for myself. Of course I’m using Python rather than Java ;)

The full code can be found at https://gist.github.com/magthe/ad6e23fb560a8a494fd2

Visitor

The Visitor pattern separates the traversal and the operation. It does this by using an accept method in the classes making up the data structure, this method takes a Visitor instance which implements the operation to be carried out. This enables adding new operations without modifying the data structure.

First we need a simple structure to play with: a tree where each node can have zero or more sub-trees.

class Tree:
    def __init__(self, value, children=[]):
        self.value = value
        self.children = children

The implementation of accept for this type is rather obvious:

    def accept(self, visitor):
        visitor.visit(self)
        for c in self.children:
            c.accept(visitor)

Next we need an implemention of a Visitor that all visitors can derive from. Since Python’s dispatch doesn’t depend at all on the type of the argument we’ll have to implement the necessary behaviour ourselves, i.e. inspect the type and then pick the correct method to call.

class Visitor:
    def visit(self, obj):
        func_name = 'visit_' + obj.__class__.__name__
        visit_func = getattr(self, func_name)
        visit_func(obj)

In order to visit a Tree type it also needs the appropriately named method:

    def visit_Tree(self, obj):
        pass

Now it’s easy to create a visitor. Here’s a very simple one:

class TreePrintVisitor(Visitor):
    def visit_Tree(self, obj):
        print('Tree (%s): %i' % (hex(id(obj)), obj.value))

Finally here’s a function that exercises what we’ve just put together:

def test_visitor():
    leaves = [Tree(42), Tree(17)]
    tree = Tree(1, leaves)
    printer = TreePrintVisitor()
    tree.accept(printer)

Looking at this it’s easy to see the objections Palsberg and Jay present in their paper:

  1. A data type is only ‘visitable’ if it has an accept method, and
  2. we must know the types of all objects we want to visit, so changes to the class structure requires changes to the visitors.

The authors then introduce Walkabout in order to remove these limitations.

Walkabout

To remove these limitations the authors use reflection to find if the visitor has a method to carry out the operation on the type of the current object. If such a method doesn’t exist they use reflection to find all members of the object and then visits them. The Walkbout class and its visit method then looks something like this:

class Walkabout:
    def visit(self, obj):
        func_name = 'visit_%s' % obj.__class__.__name__
        if hasattr(self, func_name):
            visit_func = getattr(self, func_name)
            visit_func(obj)
        elif hasattr(obj, '__dict__'):
            for m in obj.__dict__.keys():
                self.visit(getattr(obj, m))

The accept method can be removed from Tree and the visitor is changed to include code to continue the traversal:

class TreePrintWalkabout(Walkabout):
    def visit_Tree(self, tree):
        print('Tree (%s): %i' % (hex(id(tree)), tree.value))
        for c in tree.children:
            self.visit(c)

The function for exercising this only changes slightly:

def test_walkabout():
    leaves = [Tree(42), Tree(17)]
    tree = Tree(1, leaves)
    printer = TreePrintWalkabout()
    printer.visit(tree)

This is where Palsberg and Jay stop, but I think there is one little detail in Walkabout that’s worth looking a little closer at.

Walkabout Two

I personally find it a little strange that the authors first note that the visitor pattern suffers from the limitation that one has to know up front the full set of types to visit, then they don’t recognise that their own solution to this instead require one to know the shape of (parts of) the structure to operate on. In other words, the classes deriving from Walkabout are in charge of carrying on the traversal (the last two lines of visit_Tree above).

This little detail is of course easy to work around, we just modify visit to always visit all members irrespective of whether there is a method to handle the current object. There may be cases where we want to stop the walking about for efficiency reasons, we can address that at the same time and WalkaboutTwo will then look like this:

class WalkaboutTwo:
    def visit(self, obj):
        func_name = 'visit_%s' % obj.__class__.__name__
        descend = True
        if hasattr(self, func_name):
            visit_func = getattr(self, func_name)
            descend = visit_func(obj)
        if descend and hasattr(obj, '__dict__'):
            for m in obj.__dict__.keys():
                self.visit(getattr(obj, m))
        if descend and hasattr(obj, '__iter__'):
            for o in obj:
                self.visit(o)

One little detail above is that if we use only reflection to traverse the Tree we won’t actually find the sub-trees as immediate members since they are contained in a list. We address this by checking whether the object has an iterator as well, and if it does we visit all items.

2014-06-12 Fixed minor typo, thanks to Joe for pointing it out.

Share

One Comment

  1. Great article, thanks! Just noticed that the usage example for the first Walkabout has the following:

    printer =

    I think it should be:

    printer = Walkabout()

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>