Multiple dispatch (a.k.a. multimethods) is the feature of some object-oriented languages in which a function can be dynamically dispatched based on the run-time type of more than one of its arguments.
Double dispatch is a special form of multiple dispatch, which dispatches a function call to different concrete functions depending on the run-time types of two objects involved in the call.
Understanding Dispatch
In single-dispatch languages, when you invoke a method, one of its arguments is treated specially and used to determine which of the (potentially many) methods of that name is to be applied. In many languages, the “special” argument is indicated syntactically, such as:
special.method(other,arguments,here)
In languages with multiple dispatch, all the arguments are treated symmetrically in the selection of which concrete method to call. The Common Lisp Object System (CLOS) is an early and well-known example of multiple dispatch. For example:
; declare the common argument structure prototype
(defgeneric f (x y))
; define an implementation for (f integer t), where t matches all types
(defmethod f ((x integer) y) 1)
(f 1 2.0) => 1
; define an implementation for (f integer real)
(defmethod f ((x integer) (y real)) 2)
(f 1 2.0) => 2 ; dispatch changed at runtime
You may think of multiple dispatch no more than function overloading if you are not familiar with dynamic run-times. There will be an example in C++ to show why the two mechanisms are different.
Multiple Dispatch is More than Function Overloading
At first glance, multiple dispatch appears to be a natural result of function overloading. Function overloading matches a function call to different concrete functions according to the type of the argument. However, there is a significant difference here if we consider how function overloading is done.
Function overloading is done at compile-time, rather than run-time, using a technique called “naming mangling” (a.k.a. name decoration), which uses internal names instead of user-defined names. It means that function f(int x) is named internally as __f_i rather than f, and function f() as __f_v (“v” for void). So the two concrete functions with the same name but different type of arguments will be internally identified as two totally different functions with different names. For example, f(123); will be internally interpreted as __f_i(123);.
Remember what we have discussed and take an example of the language C++, in which function overloading and dynamic binding (via virtual table) are supported, but no multiple dispatch. The following example is from [1].
class SpaceShip {};
class GiantSpaceShip : public SpaceShip {};
class Asteroid {
public:
virtual void CollideWith(SpaceShip&) {
cout << "Asteroid hit a SpaceShip" << endl;
}
virtual void CollideWith(GiantSpaceShip&) {
cout << "Asteroid hit a GiantSpaceShip" << endl;
}
};
class ExplodingAsteroid : public Asteroid {
public:
virtual void CollideWith(SpaceShip&) {
cout << "ExplodingAsteroid hit a SpaceShip" << endl;
}
virtual void CollideWith(GiantSpaceShip&) {
cout << "ExplodingAsteroid hit a GiantSpaceShip" << endl;
}
};
If you have...
Asteroid a;
SpaceShip s;
GiantSpaceShip g;
...then, because of function overloading...
a.CollideWith(s);
a.CollideWith(g);
...will print Asteroid hit a SpaceShip and Asteroid hit a GiantSpaceShip respectively, without using any dynamic dispatch. Furthermore...
ExplodingAsteroid e;
e.CollideWith(s);
e.CollideWith(g);
...will print ExplodingAsteroid hit a SpaceShip and ExplodingAsteroid hit a GiantSpaceShip respectively, again without dynamic dispatch.
With a reference to an Asteroid, dynamic dispatch is used and...
Asteroid& eRef = e;
eRef.CollideWith(s);
eRef.CollideWith(g);
...prints ExplodingAsteroid hit a SpaceShip and ExplodingAsteroid hit a GiantSpaceShip, again as expected. However,
SpaceShip& gRef = g;
a.CollideWith(gRef);
eRef.CollideWith(gRef);
prints Asteroid hit a SpaceShip and ExplodingAsteroid hit a SpaceShip, neither of which is correct. The problem is that, while virtual functions are dispatched dynamically in C++, function overloading is done statically.
Simulate Double Dispatch in C++ by Using a Visitor Pattern
The problem described above can be resolved by simulating double dispatch by using a visitor pattern. Suppose SpaceShip and GiantSpaceShip both have the function:
virtual void CollideWith(Asteroid& inAsteroid) {
inAsteroid.CollideWith(*this);
}
Then, while the previous example still does not work correctly, the following does:
SpaceShip& gRef = g;
Asteroid& eRef = e;
gRef.CollideWith(a);
gRef.CollideWith(eRef);
It prints out Asteroid hit a GiantSpaceShip and ExplodingAsteroid hit a GiantSpaceShip, as expected.
For more examples of emulating multiple dispatch, see [2]. There is also a research paper on how to cleanly add multiple dispatch to C++ by Bjarne Stroustrup, Yuriy Solodkyy and Peter Pirkelbauer.
Essential Difference Between Single and Multiple Dispatch [3]
A virtual method (single dispatch) is polymorphic in one dimension (the run-time type of the object the method is attached to). Multimethods (multiple dispatch) are polymorphic in multiple dimensions (the run-time types of the arguments, not just the attached object).
Multiple Dispatch in C# 4.0 with dynamic [3]
The dynamic keyword in C# 4.0 allows for method selection that depends on the runtime class of the arguments, not just the attached object. This allows true multimethods.
using System;
namespace MultiMethods
{
class Program
{
class Thing { }
class Asteroid : Thing { }
class Spaceship : Thing { }
static void CollideWithImpl(Asteroid x, Asteroid y)
{
Console.WriteLine("Asteroid hits an Asteroid");
}
static void CollideWithImpl(Asteroid x, Spaceship y)
{
Console.WriteLine("Asteroid hits a Spaceship");
}
static void CollideWithImpl(Spaceship x, Asteroid y)
{
Console.WriteLine("Spaceship hits an Asteroid");
}
static void CollideWithImpl(Spaceship x, Spaceship y)
{
Console.WriteLine("Spaceship hits a Spaceship");
}
static void CollideWith(Thing x, Thing y)
{
dynamic a = x;
dynamic b = y;
CollideWithImpl(a, b);
}
static void Main(string[] args)
{
var asteroid = new Asteroid();
var spaceship = new Spaceship();
CollideWith(asteroid, spaceship);
CollideWith(spaceship, spaceship);
}
}
}
