This is the first article in a series dedicated to multiple dispatch - an advanced abstraction technique available to programmers out-of-the-box in some languages, and implementable in others. This first post in the series presents the technique and explains the problem it intends to solve. It uses C++ as the presentation language because C++ does not support multiple dispatch directly, but can be used to implement it in various ways. Showing how multiple dispatch is implemented in a language that doesn't support it natively is important, in my opinion, as it lets us understand the issue on a deeper level.
Follow-up articles will keep focusing on multiple dispatch using other programming languages : Part 2 will show how to implement multiple dispatch in Python; Part 3 will use Common Lisp, where multiple dispatch comes built-in as part of a large and powerful object-oriented system called CLOS; Part 4 will use Clojure, a more modern attempt at a Lisp, where multiple dispatch is also built-in, but works somewhat differently.
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 . 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
" ; } }; class Ellipse : public Shape { public : virtual void ComputeArea () const { std :: cout << "Ellipse: width times height times pi/4
" ; } }; 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 . 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 .
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 () << "]
" ; } void Intersect ( const Rectangle * r1 , const Rectangle * r2 ) { std :: cout << "Rectangle x Rectangle [names r1=" << r1 -> name () << ", r2=" << r2 -> name () << "]
" ; } // Fallback to shapes void Intersect ( const Shape * s1 , const Shape * s2 ) { std :: cout << "Shape x Shape [names s1=" << s1 -> name () << ", s2=" << s2 -> name () << "]
" ; } Now in main : Rectangle r1 , r2 ; Ellipse e ; Triangle t ; std :: cout << "Static type dispatch
" ; 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
... continue reading