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
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:
- A data type is only ‘visitable’ if it has an
- 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.
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))
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.
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
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.