More Visitor (in Python)

Right after writing the previous post on the Visitor pattern in Python I picked up another paper on the same topic, Visitor Combination and Traversal Control. Of course this one also used Java for its examples, so once again I decided to use Python to explore the ideas presented.

The first part of the paper is all about writing small visitors that then are combined into more complicated ones. This part is nice but not that exciting. The interesting bit is when it gets to controlling traversal, which means it’s possible to remove the traversal code that usually appear in the accept method each visited type has to implement. Let’s see how that can look in Python.

The full code in this post is available at

First we need a structure to traverse, a simple tree will do.

class Tree(Visitable):
    def __init__(self, left, right):
        self.left = left
        self.right = right

class Leaf(Visitable):
    def __init__(self, value):
        self.value = value

def build_tree():
    l0 = Leaf(0)
    l1 = Leaf(1)
    t0 = Tree(l0, l1)
    l2 = Leaf(2)
    t1 = Tree(t0, l2)
    l3 = Leaf(3)
    l4 = Leaf(4)
    t2 = Tree(l3, l4)
    return Tree(t1, t2)

But before this we really should define Visitor, the base class for visitors, and Visitable, the base class of everything that can be visited.

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

    def visit_Tree(self, t):

    def visit_Leaf(self, l):

class Visitable:
    def accept(self, visitor):

We’ll throw in a visitor for printing the whole tree too:

class Print(Visitor):
    def visit_Tree(self, t):
        print('Tree (%s)' % hex(id(t)))

    def visit_Leaf(self, l):
        print('Leaf (%s): %i' % (hex(id(l)), l.value))

Due to the lack of traversal in the accept methods it’s easy to be underwhelmed by the Print visitor:

In [32]: build_tree().accept(Print())
Tree (0x7f1680681a90)

To address this we first need a visitor combinator that runs two visitors in sequence. Unsurprisingly we’ll call it Sequence. Its constructor takes two visitors, and for each node in the tree it passed each one to the node.accept method.

class Sequence(Visitor):
    def __init__(self, first, then):
        self.first = first
        self.then = then

    def visit_Tree(self, t):

    def visit_Leaf(self, l):

The next building block is a visitor that descends one level down from a Tree node.

class All(Visitor):
    def __init__(self, v):
        self.v = v

    def visit_Tree(self, t):

At this point it’s worth noting that the name All probably isn’t very well chosen, since we don’t really get all nodes:

In [33]: build_tree().accept(All(Print()))
Tree (0x7f1680681278)
Tree (0x7f1680681be0)

We only descend one level, but we still keep the name since that’s the name they use in the paper.

With this in place it does become possible to create combinations that do traverse the full tree though. It even becomes rather simple. Traversing top-down is a simple matter of using a sequence that ends with All, and bottom-up is a matter of using a sequence starting with All.

class TopDown(Sequence):
    def __init__(self, v):
        Sequence.__init__(self, v, All(self))

class BottomUp(Sequence):
    def __init__(self, v):
        Sequence.__init__(self, All(self), v)

First top-down:

In [34]: build_tree().accept(TopDown(Print()))
Tree (0x7f1680681ef0)
Tree (0x7f16806814a8)
Tree (0x7f16806813c8)
Leaf (0x7f1680681278): 0
Leaf (0x7f1680681550): 1
Leaf (0x7f1680681a90): 2
Tree (0x7f1680681f28)
Leaf (0x7f1680681ba8): 3
Leaf (0x7f1680681a20): 4

Then bottom-up:

In [35]: build_tree().accept(BottomUp(Print()))
Leaf (0x7f1680681ba8): 0
Leaf (0x7f16806814a8): 1
Tree (0x7f1680681a90)
Leaf (0x7f16806813c8): 2
Tree (0x7f1680681550)
Leaf (0x7f1680681278): 3
Leaf (0x7f16806a1048): 4
Tree (0x7f16806a1198)
Tree (0x7f16806a1390)

That’s all rather cute I think.

Leave a comment