A polyglot's guide to multiple dispatch

Polymorphism, single dispatch, multiple dispatch

There are many kinds of polymorphism in programming. The kind we're talking about here is runtime subtype-based polymorphism, where behavior is chosen dynamically based on the runtime types of objects. More specifically, multiple dispatch is all about the runtime types of more than one object.

The best way to understand multiple dispatch is to first think about single dispatch. Single dispatch is what we usually refer to as "runtime polymorphism" in languages like C++ and Java [1]. We have an object on which we call a method, and the actual method being called at runtime depends on the runtime type of the object. In C++ this is done with virtual functions:

class Shape {
public:
  virtual void ComputeArea() const = 0;
};

class Rectangle : public Shape {
public:
  virtual void ComputeArea() const {
    std::cout << "Rectangle: width times height\n";
  }
};

class Ellipse : public Shape {
public:
  virtual void ComputeArea() const {
    std::cout << "Ellipse: width times height times pi/4\n";
  }
};

int main(int argc, const char** argv) {
  std::unique_ptr<Shape> pr(new Rectangle);
  std::unique_ptr<Shape> pe(new Ellipse);

  pr->ComputeArea();    // invokes Rectangle::ComputeArea
  pe->ComputeArea();    // invokes Ellipse::ComputeArea

  return 0;
}

Even though both pr and pe are pointers to a Shape as far as the C++ compiler is concerned, the two calls to ComputeArea get dispatched to different methods at runtime due to C++'s implementation of runtime polymorphism via virtual functions.

Now, spend a few seconds thinking about the question: "What is the dispatch done upon in the code sample above?"

It's fairly obvious that the entity we dispatch upon is a pointer to Shape. We have pr and we call a method on it. The C++ compiler emits code for this call such that at runtime the right function is invoked. The decision which function to invoke is based upon examining a single object - what pr points to. Hence single dispatch.

A natural extension of this idea is multiple dispatch, wherein the decision which function to call is based on the runtime types of multiple objects. Why is this useful? It's not a tool programmers reach for very often, but when it is appropriate, alternatives tend to be cumbersome and repetitive. A telling sign that multiple dispatch may be in order is when you have some operation that involves more than one class and there is no single obvious class where this operation belongs. Think of simulating a sound when a drumstick hits a drum. There are many kinds of drumsticks, and many kinds of drums; their combinations produce different sounds. Say we want to write a function (or family of functions) that determines which sound is produced. Should this function be a method of the Drum class or the DrumStick class? Forcing this decision is one of the follies of classical OOP, and multiple dispatch helps us solve it naturally without adding a kludge into our design.

A simpler and more canonical example is computing intersections of shapes - maybe for computer graphics, or for simulation, or other use cases. A generic shape intersection computation can be complex to implement, but in many specific cases it's easy. For example, computing intersections of rectangles with rectangles is trivial; same for circles and ellipses; rectangles with triangles may be a tiny bit harder, but still much simpler than artibrary polygons, and so on [2].

How do we write code to handle all these cases? All in all, we just need an intersect function that takes two shapes and computes an intersection. This function may have a whole bunch of special cases inside for different combinations of shapes it knows how to do easily, before it resorts to some heavy-handed generic polygon intersection approach. Such code, however, would be gross to develop and maintain. Wouldn't it be nice if we could have:

void Intersect(const Rectangle* r, const Ellipse* e) {
  // implement intersection of rectangle with ellipse
}

void Intersect(const Rectangle* r1, const Rectangle* r2) {
  // implement intersection of rectangle with another rectangle
}

void Intersect(const Shape* s1, const Shape* s2) {
  // implement interesction of two generic shapes
}

And then the call Intersect(some_shape, other_shape) would just magically dispatch to the right function? This capability is what's most often referred to by multiple dispatch in programming language parlance [3].

A failed attempt in C++

You may be tempted to come up with the following "trivial" solution in C++:

class Shape {
public:
  virtual std::string name() const {
    return typeid(*this).name();
  }
};

class Rectangle : public Shape {};

class Ellipse : public Shape {};

class Triangle : public Shape {};

// Overloaded Intersect methods.
void Intersect(const Rectangle* r, const Ellipse* e) {
  std::cout << "Rectangle x Ellipse [names r=" << r->name()
            << ", e=" << e->name() << "]\n";
}

void Intersect(const Rectangle* r1, const Rectangle* r2) {
  std::cout << "Rectangle x Rectangle [names r1=" << r1->name()
            << ", r2=" << r2->name() << "]\n";
}

// Fallback to shapes
void Intersect(const Shape* s1, const Shape* s2) {
  std::cout << "Shape x Shape [names s1=" << s1->name()
            << ", s2=" << s2->name() << "]\n";
}

Now in main:

Rectangle r1, r2;
Ellipse e;
Triangle t;

std::cout << "Static type dispatch\n";
Intersect(&r1, &e);
Intersect(&r1, &r2);
Intersect(&r1, &t);

We'll see:

Static type dispatch
Rectangle x Ellipse [names r=9Rectangle, e=7Ellipse]
Rectangle x Rectangle [names r1=9Rectangle, r2=9Rectangle]
Shape x Shape [names s1=9Rectangle, s2=8Triangle]

Note how the intersections get dispatched to specialized functions when these exist and to a generic catch-all Shape x Shape handler when there is no specialized function.

So that's it, multiple dispatch works out of the box? Not so fast... What we see here is just C++ function overloading in action. The compiler knows the static, compile-time types of the pointers passed to the Intersect calls, so it just emits the right call. Function overloading is great and useful, but this is not the general problem we're trying to solve. In a realistic code-base, you won't be passing pointers to concrete subclasses of Shape around. You are almost certainly going to be dealing with pointers to the Shape base class. Let's try to see how the code in the previous sample works with dynamic types:

std::unique_ptr<Shape> pr1(new Rectangle);
std::unique_ptr<Shape> pr2(new Rectangle);
std::unique_ptr<Shape> pe(new Ellipse);
std::unique_ptr<Shape> pt(new Triangle);

std::cout << "Dynamic type dispatch\n";
Intersect(pr1.get(), pe.get());
Intersect(pr1.get(), pr2.get());
Intersect(pr1.get(), pt.get());

Prints:

Dynamic type dispatch
Shape x Shape [names s1=9Rectangle, s2=7Ellipse]
Shape x Shape [names s1=9Rectangle, s2=9Rectangle]
Shape x Shape [names s1=9Rectangle, s2=8Triangle]

Yeah... that's not good. All calls were dispatched to the generic Shape x Shape handler, even though the runtime types of the objects are different (see the names gathered from typeid). This is hardly surprising, because when the compiler sees Intersect(pr1.get(), pr2.get()), the static types for the two arguments are Shape* and Shape*. You could be forgiven for thinking that the compiler may invoke virtual dispatch here, but virtual dispatch in C++ doesn't work this way. It only works when a virtual method is called on a pointer to a base object, which is not what's happening here.

Multiple dispatch in C++ with the visitor pattern

I'll admit I'm calling this approach "the visitor pattern" only because this is how it's called elsewhere and because I don't have a better name for it. In fact, it's probably closer to an "inverted" visitor pattern, and in general the pattern name may obscure the code more than help. So forget about the name, and just study the code.

The last paragraph of the previous section ended with an important observation: virtual dispatch in C++ kicks in only when a virtual method is called on a pointer to a base object. Let's leverage this idea to simulate double dispatch on our hierarchy of shapes. The plan is to arrange Intersect to hop through virtual dispatches on both its arguments to get to the right method for their runtime types.

We'll start by defining Shape like this:

class Shape {
public:
  virtual std::string name() const {
    return typeid(*this).name();
  }

  // Dispatcher that should be called by clients to intersect different shapes.
  virtual void Intersect(const Shape*) const = 0;

  // Specific interesection methods implemented by subclasses. If subclass A
  // has a special way to intersect with subclass B, it should implement
  // InteresectWith(const B*).
  virtual void IntersectWith(const Shape*) const {}
  virtual void IntersectWith(const Rectangle*) const {}
  virtual void IntersectWith(const Ellipse*) const {}
};

The Intersect method is what the users of the code will invoke. To be able to make use of virtual dispatches, we are forced to turn a two-argument call Intersect(A*, B*) to a method call A->Intersect(B). The IntersectWith methods are concrete implementations of intersections the code will dispatch to and should be implemented by subclasses on a case-per-case basis.

class Rectangle : public Shape {
public:
  virtual void Intersect(const Shape* s) const {
    s->IntersectWith(this);
  }

  virtual void IntersectWith(const Shape* s) const {
    std::cout << "Rectangle x Shape [names this=" << this->name()
              << ", s=" << s->name() << "]\n";
  }

  virtual void IntersectWith(const Rectangle* r) const {
    std::cout << "Rectangle x Rectangle [names this=" << this->name()
              << ", r=" << r->name() << "]\n";
  }
};

class Ellipse : public Shape {
public:
  virtual void Intersect(const Shape* s) const {
    s->IntersectWith(this);
  }

  virtual void IntersectWith(const Rectangle* r) const {
    std::cout << "Ellipse x Rectangle [names this=" << this->name()
              << ", r=" << r->name() << "]\n";
  }
};

std::unique_ptr<Shape> pr1(new Rectangle);
std::unique_ptr<Shape> pr2(new Rectangle);
std::unique_ptr<Shape> pe(new Ellipse);

std::cout << "Dynamic type dispatch\n";
pr1->Intersect(pe.get());
pr1->Intersect(pr2.get());

Will now print:

Dynamic type dispatch
Ellipse x Rectangle [names this=7Ellipse, r=9Rectangle]
Rectangle x Rectangle [names this=9Rectangle, r=9Rectangle]

Success! Even though we're dealing solely in pointers to Shape, the right intersections are computed. Why does this work?

As I've mentioned before, the key here is use C++'s virtual function dispatch capability, twice. Let's trace through one execution to see what's going on. We have:

pr1->Intersect(pe.get());

pr1 is a pointer to Shape, and Intersect is a virtual method. Therefore, the runtime type's Intersect is called here, which is Rectangle::Intersect. The argument passed into the method is another pointer to Shape which at runtime points to an Ellipse (pe). Rectangle::Intersect calls s->IntersectWith(this). The compiler sees that s is a Shape*, and IntersectWith is a virtual method, so this is another virtual dispatch. What gets called is Ellipse::IntersectWith. But which overload of this method is called?

This is an extremely crucial point in the explanation, so please focus :-) Here is Rectangle::Intersect again:

virtual void Intersect(const Shape* s) const {
  s->IntersectWith(this);
}

s->IntersectWith is called with this, which the compiler knows is a pointer to Rectangle, statically. If you wondered why I define Intersect in each subclass rather than doing it once in Shape, even though its code is exactly the same for each subclass, this is the reason. Had I defined it in Shape, the compiler would think the type of this is Shape* and would always dispatch to the IntersectWith(const Shape*) overload. Defining this method in each subclass helps the compiler leverage overloading to call the right method.

What happens eventually is that the call pr1->Intersect(pe.get()) gets routed to Ellipse::IntersectWith(const Rectangle*), thanks to two virtual dispatches and one use of method overloading. The end result is double dispatch! [4]

But wait a second, how did we end up with Ellipse::IntersectWith(Rectangle)? Shouldn't pr1->Intersect(pe.get()) go to Rectangle::IntersectWith(Ellipse) instead? Well, yes and no. Yes because this is what you'd expect from how the call is syntactically structured. No because you almost certainly want double dispatches to be symmetric. I'll discuss this and other related issues in the next section.

Symmetry and base-class defaults

When we come up with ways to do multiple dispatch, whether in C++ or in other languages, there are two aspects of the solution we should always keep in mind:

1. Does it permit symmetry? In other words, does the order of objects dispatched upon matters? And if it doesn't, how much extra code is needed to express this fact.
2. Does base-class default dispatch work as expected? Suppose we create a new subclass of Rectangle, called Square and we don't explicitly create an IntersectWith method for Square and Ellipse. Will the right thing happen and the intersection between a Rectangle and Ellipse be invoked when we ask for Square x Ellipse? This is the right thing because this is what we've come to expect from class hierarchies in object-oriented languages.

In the visitor-based solution presented above, both aspects will work, though symmetry needs a bit of extra code. The full code sample is available here (and the accompanying .cpp file). It's conceptually similar to the code shown above, but with a bit more details. In particular, it implements symmetry between rectangle and ellipse intersections as follows:

namespace {

// All intersections between rectangles and ellipses dispatch here.
void SymmetricIntersectRectangleEllipse(const Rectangle* r, const Ellipse* e) {
  std::cout << "IntersectRectangleEllipse [names r=" << r->name()
            << ", e=" << e->name() << "]\n";
}
}

void Rectangle::IntersectWith(const Ellipse* e) const {
  SymmetricIntersectRectangleEllipse(this, e);
}

void Ellipse::IntersectWith(const Rectangle* r) const {
  SymmetricIntersectRectangleEllipse(r, this);
}

This ensures that both rectangle->Intersect(ellipse) and ellipse->Intersect(rectangle) end up in the same function. As far as I know there's not way to do this automatically in the visitor approach, so a bit of extra coding is due when symmetry between subclasses is desired.

Note also that this method doesn't force symmetry either. If some form of dispatch is order-dependent, it's easy to express.

The problem with the visitor-based approach

Although the visitor-based approach works, enables fairly clean client code and is efficient (constant time - two virtual calls), there's a glaring issue with it that's apparent with the most cursory look at the code: it's very intrusive, and hence hard to maintain.

Imagine we want to add a new kind of shape - a HyperFrob. Suppose also that there's an efficient algorithm for intersecting a HyperFrob with an Ellipse. Ideally, we'd only have to write code for the new functionality:

1. Define the new HyperFrob class deriving from Shape.
2. Implement the generic HyperFrob x Shape intersection algorithm.
3. Implement the specific HyperFrom x Ellipse algorithm.

But in reality, we're forced to modify the definition of the base class Shape to add an overload of IntersectWith for HyperFrob. Moreover, if we want intersections between HyperFrob and Ellipse to be symmetric (which we almost certainly do), we'll have to modify Ellipse as well to add the same overload.

If we don't control the Shape base class at all, we're in real trouble. This is an instance of the expression problem. I'll have more to say about the expression problem in a future post, but for now the Wikipedia link will have to do. It's not an easy problem to solve in C++, and the approaches to implement multiple dispatch should be judged by how flexible they are in this respect, along with the other considerations.

Multiple-dispatch in C++ by brute-force

The visitor-based approach is kind-of clever, leveraging single virtual dispatch multiple times to simulate multiple dispatch. But if we go back to first principles for a moment, it becomes clear that there's a much more obvious solution to the problem - brute-force if-else checks. I mentioned this possibility early in the article and called it "gross to develop and maintain", but it makes sense to at least get a feel for how it would look:

class Shape {
public:
  virtual std::string name() const {
    return typeid(*this).name();
  }
};

class Rectangle : public Shape {};

class Ellipse : public Shape {};

class Triangle : public Shape {};

void Intersect(const Shape* s1, const Shape* s2) {
  if (const Rectangle* r1 = dynamic_cast<const Rectangle*>(s1)) {
    if (const Rectangle* r2 = dynamic_cast<const Rectangle*>(s2)) {
      std::cout << "Rectangle x Rectangle [names r1=" << r1->name()
                << ", r2=" << r2->name() << "]\n";
    } else if (const Ellipse* e2 = dynamic_cast<const Ellipse*>(s2)) {
      std::cout << "Rectangle x Ellipse [names r1=" << r1->name()
                << ", e2=" << e2->name() << "]\n";

    } else {
      std::cout << "Rectangle x Shape [names r1=" << r1->name()
                << ", s2=" << s2->name() << "]\n";
    }
  } else if (const Ellipse* e1 = dynamic_cast<const Ellipse*>(s1)) {
    if (const Ellipse* e2 = dynamic_cast<const Ellipse*>(s2)) {
      std::cout << "Ellipse x Ellipse [names e1=" << e1->name()
                << ", e2=" << e2->name() << "]\n";
    } else {
      // Handle other Ellipse x ... dispatches.
    }
  } else {
    // Handle Triangle s1
  }
}

One thing is immediately noticeable: the intrusiveness issue of the visitor-based approach is completely solved. Obliterated! Intersect is now a stand-alone function that encapsulates the dispatch. If we add new kinds of shape, we only have to change Intersect, nothing else. Perfect... or is it?

The other immediately noticeable fact about this code is: holy cow, how long it is. I'm only showing a small snippet here, but the number of these if clauses grows as square of the number of subclasses. Imagine how this could look for 20 kinds of shapes. Moreover, Intersect is just one algorithm. We may have other "multi methods" - this travesty would have to be repeated for each algorithm.

Another, less obvious problem is that the code is somewhat brittle. Given a non-trivial inheritance hierarchy, we have to be very careful about the order of the if clauses, lest a parent class "shadows" all its subclasses by coming before them in the chain.

It's no wonder that one would be very reluctant to write all this code. In fact, smart folks came up with all kinds of ways to automate such if chains. If you're thinking - "hey I could just store pairs of typeids in a map and dispatch upon that" - congrats, you're in the right direction.

One of the most notable experts to tackle the beast is Andrei Alexandrescu, who dedicated chapter 11 of "Modern C++ Design" to this problem, implementing all kinds of automated solutions based on heavy template metaprogramming. It's a fairly impressive piece of work, presenting multiple approaches with different tradeoffs in terms of performance and intrusiveness. If you Google for Loki (his C++ template library) and look into the MultiMethods.h header you'll see it in all its glory - complete with type lists, traits, policies, and template templates. This is C++, and these are the abstractions the language provides for meta-programming - so take it or leave it :-) If you are seriously considering using multiple dispatch in your C++ code, Loki is well worth a look.

An attempt for standardization

By far the most interesting attempt to solve this problem came from Bjarne Stroustrup himself, who co-authored a paper with two of his students named "Open Multi-Methods for C++" [5]. In this paper, the authors thoroughly review the problem and propose a C++ language extension that will implement it efficiently in the compiler.

The main idea is to let function arguments be potentially virtual, meaning that they perform dynamic dispatch and not just static overloading. So we could implement our intersection problem as follows:

// This is not real C++: the syntax is based on the paper
// "Open Multi-Methods for C++" and was only implemented experimentally.

// Generic Shape x Shape intersection.
void Intersect(virtual const Shape*, virtual const Shape*);

// Interesection for Rectangle x Ellipse.
void Intersect(virtual const Rectangle*, virtual const Ellipse*);

Note how similar this is to the failed attempt to leverage overloading for multiple dispatch in the beginning of this article. All we add is the virtual keyword for arguments, and the dispatch turns from static to dynamic.

Unfortunately, the proposal never made it into the standard (it was proposed as document number N2216).

Conclusions and next steps

This part in the series presented the multiple dispatch problem and demonstrated possible solutions in C++. Each solution has its advantages and issues, and choosing one depends on the exact needs of your project. C++ presents unique challenges in designing such high-level abstractions, because it's comparatively rigid and statically typed. Abstractions in C++ also tend to strive to being as cheap as possible in terms of runtime performance and memory consumption, which adds another dimension of complexity to the problem.

In the following parts of the series we'll examine how the same problem is solved in other, more dynamic and structurally flexible programming languages.