Alex headshot

AlBlue’s Blog

Macs, Modularity and More

Why I don't like the visitor pattern

2009, java

I've got a vague general dislike of the visitor pattern, and I've never really gotten around to writing about it.

The visitor pattern is a way of encoding a visitor which can abstractly walk over an abstract data structure in order to do some kind of processing. This pattern is common in a number of object-oriented languages (less so in functional ones, because it just becomes a function) and the canonical examples are found in Java and C++. However, the pattern is usually described (and adapted from) the GoF book, which used a C++ example in order to get its point across.

So, why do I dislike the pattern? Well, it can be summarised as:

  • Double-dispatch not necessary in Java
  • Double-dispatch means that your ADT has to pre-support visitors (i.e. can't be added onto an existing structure)
  • Typing methods on the visitor interface itself mean it's not easy to extend to new abstract types
  • Control over visitation order gets re-implemented by every visitor
  • Data accumulated by walking the tree has to be stored on the visitor

Let's take a look through these in turn.

Double-dispatch, part 1. In the original C++ implementation, a form of double dispatch was used to get around for the fact that C++ is a statically compiled language with no reflection. What this says, in a nutshell, is that the visitor calls a generic accept(visitor) method, which then internally delegates back to acceptSpecificDataStructure(this). Huge swathes of visitor patterns are basically getting around for the fact that the visitor doesn't have any a-priori knowledge of the data structure's type, and so to do so, it needs to ask it how to handle it. It's called double-dispatch, because you're doing 2 dispatches; one to the data structure, and then back from the data structure to the visitor.

Why is this needed? Well, C++ didn't have any concept of performing any kind of dynamic lookup, and so in order to build in knowledge of what the specific data structure was, you had to have some kind of branching logic to do the callback. Since objects naturally form different method calls when invoked with a (virtual) method, using this OO trick to do the first part of the dispatch alleviated that problem. The second dispatch is of course the re-invocation of the visitor's appropriate acceptSpecificDataStructure() call, which given that the visitor itself is usually a subtype, forms a second part of the dispatch.

Whilst that might make sense in the days of C++, things have moved on in the programming world. Java has dynamic methods like java.lang.reflect.Method, and thanks to excessive use by the J2EE servers of the heyday of that platform, was optimised to the extent where it is often more performant than doing a double-dispatch in the first place. Java's only slight weakness comes from the fact that overloaded methods are not done on a signature basis but at runtime, which means that although lexically your code can contain accept(Foo foo) and accept(Bar bar), then an appropriate call to accept(x) will do the right thing, provided that the type of X is known at compile time.

Using reflection can avoid the need to do double dispatch at all. In fact, services like Restlet use reflection to delegate HTTP methods back to their method implementations; GET is mapped to doGet() and so on. But reflection is used as a fallback, so that an HTTP FOO method is mapped to doFoo(), which allows Restlets to support new HTTP methods before the framework does. (This is somewhat reminiscent of Ruby's form-follows-function approach, in which conventions rather than configuration files allow the system to be extended much later in the cycle than with other platforms.)

In summary, whilst most visitor patterns are simply copied over from C++, Java has reflective capabilities which obliviate the need for double-dispatch. Yet these are rarely used, if only because the pattern books all tend to be based from the early GoF beginnings.

Double-dispatch, part 2. So Java doesn't need DD. So? Should you care? Well, in a nutshell, yes. One of the key things that the visitor pattern's DD enforces is not only that the visitor knows about the data structures, but that the data structures must know about the visitor. In other words, you've got a leaky abstraction; your data structure 'knows' more than it should about the way that the data structure should be used.

This isn't an academic observation, though. Using the DD visitor pattern means that a priori your data structure must know that it will be visited at some point. Now, if you control the source code to both the data structure and the visitor (as in most compilers or Objective-C IDEs), this isn't too much of a deal. You just whack in an interface (or abstract class) and let others extend that.

This of course breaks down when you don't have access to the source. For example, want to add a DD visitor to the Swing hierarchy of a view? You can't. Ditto for any other data structure in the base Java libraries.

Typed methods. This is a follow-on from the fact that C++ didn't really support the dynamic method binding/invocation that Java has. In Java, it's perfectly possible to not know the name of a method at compile time and yet be able to run it at run-time. The trick can be used to extend the types that weren't known at runtime, for example, a Visitor can dynamically call visitFoo(Foo) when it finds a Foo object, even if that method isn't know when the parental visitor doesn't know about it. This makes it easier for someone else to extend your hierarchy without knowledge of your specific data structures. Coming back to the Swing example earlier, if I create a BouncyContainer, any visitor isn't going to know about that (since I just created it) but I can put a specific visitation method in and have it called (c.f. the Restlet example above).

Visitation order. One of the problems with the visitor is that the 'visitation order' – that is, which nodes get visited and in which order – is distributed across your visitor tree. Sometimes, it makes sense for a traversal of a data structure to be depth-first; sometimes it makes sense for it to be breadth-first. But having the visitation logic of 'which node to follow next' embedded in each of the visit calls can actually be counter-productive.

What is the case, however, is that for every node that gets visited in the ADT, there are two kinds of nodes:

  • Leaf nodes
  • Container/tree nodes

In fact, these can be generalised into a mechanism which allows you to determine whether a node has children and in which order those children should be visited. In our Swing example, things fall naturally into Container and Component groups. Even in a generic ADT, there's often a getChildren() call or equivalent that determines whether a node has children or not.

Data accumulation. Since the purpose of a data structure walk is to introspect some data from it, there is usually some kind of data that needs to be accumulated, either at the time of the walk or afterwards. In fact, most of the XSLT transformations are just that - transformations of an existing tree-based data structure into another form.

This transformation may require some kind of data to be accumulated as the introspection/walking happens; in most normal visitor implementations, the visitor instance itself is used as the data store. Unfortunately, that doesn't lend itself well to traversals where the walk may be multi-threaded (as in walking a very large parse tree) or where the specific order of evaluation is non-commutatitve. In fact, there may be a number of situations where walking a tree structure needs some kind of state (like evaluating a simple expression language in the context of some binding). For these instances, a visitor is non-optimal way of solving that problem.

Conclusion. The standard Visitor pattern is normally implemented based on constraints of a static language which is missing certain key dynamic features, and as a result, enforces a way of working that is non-optimal in a more dynamic language. Enforcing your data structure to know about the concept of visitors is an unnecessary coupling, both at the data structure layer and at the visitor layer. And finally, having encoded all of the traversal logic in your individual visitor, it makes it difficult to extend or reuse visitor code to traverse data structures in a different order.