The Visitor pattern and multiple dispatch

Article
08/29/2005

Today I'll talk about multiple dispatch, a programming language feature that increases flexibility of method calls and eliminates the need for awkward pattern constructions, at the cost of some additional complexity in the dispatch algorithm.

The Visitor pattern

Those who have read the Gang of Four's seminal Design Patterns may recall the Visitor pattern. Its purpose is to provide new operations on a class or set of related classes without actually altering the classes involved. Design Patterns provides a real-world example in the document-view paradigm, but for simplicity I'll provide a simpler example here based on some notes by Corky Cartwright.

Say you wish to represent an arithmetic expression using integers and addition such as (1 + 5) + 2. In an object-oriented language, a natural way to do this is to create an abstract base class "Expression", and then create some related subclasses:

ConstantExpression: Represents a constant number, like 2.
SumExpression: Represents the result of adding two Expression objects.

The objects form a tree, where the leaves are ConstantExpression objects. To evaluate an expression represented in such a form, it suffices to create a virtual Evaluate() method which each subclass implements appropriately:

 abstract class Expression {
    public abstract int Evaluate();
}

class ConstantExpression : Expression {
    int constant;
    public override int Evaluate() {
        return constant;
    }
}

class SumExpression : Expression {
    Expression left, right;
    public override int Evaluate() {
        return left.Evaluate() + right.Evaluate();
    }
}

This may solve the problem if all you want to do is evaluate expressions, but there are all sorts of operations you can do on arithmetic expressions. Do we really want to add a virtual method for every one of them? We certainly don't want clients of the class to be forced to extend the classes just to add application-specific operations. The Visitor pattern solves this problem by replacing the Evaluate() method with an Accept() method that takes as a parameter a visitor object. The visitor object has a method for each type of expression, and Accept() invokes the appropriate one. Here's how we would evaluate expressions using the Visitor pattern:

 abstract class Expression {
    public abstract object Accept(Visitor v);
}

class ConstantExpression : Expression {
    public int constant;
    public override object Accept(Visitor v) {
        return v.VisitConstant(this);
    }
}

class SumExpression : Expression {
    public Expression left, right;
    public override object Accept(Visitor v) {
        return v.VisitSum(this);
    }
}

interface Visitor {
    object VisitConstant(ConstantExpression e);
    object VisitSum(SumExpression e);
}

class EvaluateVisitor : Visitor {
    public object VisitConstant(ConstantExpression e) {
        return e.constant;
    }
    public object VisitSum(SumExpression e) {
        return (int)e.left.Accept(this) + (int)e.right.Accept(this);
    }
}

We evaluate an expression e using (int)e.Accept(new EvaluateVisitor()), and adding new operations is easy; we just create new implementors of Visitor. Clients can create application-specific algorithms without touching the original classes. As an added benefit, the visitor class can keep state internal to the algorithm; for example, this visitor counts and stores the number of constants in an expression:

 class CountConstantsVisitor : Visitor {
    public int Count;
    public object VisitConstant(ConstantExpression e) {
        Count++;
        return null;
    }
    public object VisitSum(SumExpression e) {
        e.left.Accept(this);
        e.right.Accept(this);
        return null;
    }
}

But the wary designer will note that there is a maintainance problem here: if we add a new subclass of Expression, like ProductExpression, the Visitor interface and all classes implementing it have to be updated. If the Expression class rarely changes, this is fine, and may even be good: it forces the visitor classes to consider the new cases. If it's rapidly changing, however, we definitely have a problem.

Double dispatch

At this point we take a slight detour and consider another simple example. Polymorphism is the critical ability of an object-oriented method call to invoke different methods at runtime based on the type of the object, like Evaluate() in our first example. If you've ever dealt with operator overloading in C++ or C#, though, you may come up against the limits of polymorphism. If I write an operator+ for a class Complex for complex numbers, subclasses can override it in a polymorphic way - but only if the complex number is on the left. If the Complex object is on the right-hand side, there is no way to ensure the correct method is invoked polymorphically short of testing the type and invoking it yourself.

How cruel we are to the unprivileged right-hand sides! The built-in C operator + produces different types depending on both the type of its left and right argument; both a double plus a float and a float plus a double produce doubles. We want something similar for our own operators, the ability to polymorphically choose a method based on both the type of its left argument and its right argument. Then we could write code like this:

 Complex operator+(Complex c, int i) { ... }
Complex operator+(ComplexSubclass c, int i) { ... }
Complex operator+(int i, Complex c) { ... }
Complex operator+(int i, ComplexSubclass c) { ... }

The right method will be chosen at runtime based on the types of both sides; the most specific (most derived) type is always chosen. This is called double dispatch, because we select the method ("dispatch" the message) based on the type of two arguments.

Unfortunately, this new flexibility also introduces some new problems. Suppose we have these two methods:

 Complex operator+(ComplexSubclass s, Complex c) { ... }
Complex operator+(Complex c, ComplexSubclass s) { ... }

Now, suppose we try to add two objects of type ComplexSubclass. Neither of the above looks more appropriate than the other. There are various ways of dealing with this; for example, we can give the first argument precedence over the others, we can throw an error at runtime, or we can make the compiler require us to implement a method taking two ComplexSubclass objects. For this article, we'll sidestep the issue by saying we won't write any code that will invoke this dilemma.

Now, I'm sure you're wondering what any of this has to do with the Visitor pattern. The answer is that this feature allows us to drastically simplify our Visitor pattern example while retaining all of its benefits:

 abstract class Expression { }

class ConstantExpression : Expression {
    public int constant;
}

class SumExpression : Expression {
    public Expression left, right;
}

class EvaluateVisitor {
    public int Visit(ConstantExpression e) {
        return e.constant;
    }
    public int Visit(SumExpression e) {
        return Visit(e.left) + Visit(e.right);
    }
}

Now, this isn't valid C# of course, since C# doesn't support double dispatch, but you can see the effect it would have if it did: the Visitor interface is gone, the Accept() method is gone, and the calls in the last Visit() method are simplified. Best of all, it solves our dilemma of a rapidly changing Expression class hierarchy, because we can add a "default case" method that deals with any expression types we're not familiar with:

     public int Visit(Expression e) {
        throw new Exception("Unsupported type of expression"); // or whatever
    }

One handy trick you can do in Java and .NET languages is to have a method that examines the type of its argument and then uses reflection to pass it on to the correct overload, simulating polymorphism. This is much slower than native double dispatch support, but achieves much of the same effect.

If you've studied how polymorphic methods are dispatched, you're probably most familiar with the "vptr" and "vtable" model, where each object includes a reference to a type descriptor, which in turn contains a table of function pointers giving the right function to invoke for each method for an object of that type. With double dispatch this becomes trickier. One of the simplest strategies, and an effective one in practice, is to have the initial vtable dispatch the method to a "stub" method, whose job is to perform another vtable dispatch on the second argument. Because most methods don't require double dispatch, this avoids imposing a penalty on ordinary single dispatch methods.

Multiple dispatch

But why stop at two arguments? Why not choose the method based on all the arguments? Although increasingly less useful, there are legitimate applications of methods that dispatch on 3, 4, or more arguments. This form of dispatch, called multiple dispatch, is directly supported by languages such as Dylan, Cecil, and CLOS (the Common Lisp Object System). Not only does this feature ease design of an initial system, but it also greatly increase the ability to extend it in multiple directions in an object-oriented way. Try experimenting with some of them and going through their tutorials; even in languages that don't directly support multiple dispatch, it helps to be able to recognise a situation where it would apply and simulate it.

Thanks for reading, everyone.

The Visitor pattern and multiple dispatch