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
method each visited type has to implement. Let’s see how that can look in
The full code in this post is available at https://gist.github.com/magthe/beddad5c627946f28748.
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,
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): pass def visit_Leaf(self, l): pass class Visitable: def accept(self, visitor): visitor.visit(self)
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
In : 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
class Sequence(Visitor): def __init__(self, first, then): self.first = first self.then = then def visit_Tree(self, t): t.accept(self.first) t.accept(self.then) def visit_Leaf(self, l): l.accept(self.first) l.accept(self.then)
The next building block is a visitor that descends one level down from a
class All(Visitor): def __init__(self, v): self.v = v def visit_Tree(self, t): t.left.accept(self.v) t.right.accept(self.v)
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 : 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
bottom-up is a matter of using a sequence starting with
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)
In : 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
In : 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.