In software engineering, double dispatch is a special form of multiple dispatch, and a mechanism that dispatches a function call to different concrete functions depending on the runtime types of two objects involved in the call. In most object-oriented systems, the concrete function that is called from a function call in the code depends on the dynamic type of a single object and therefore they are known as single dispatch calls, or simply virtual function calls.
Dan Ingalls first described how to use double dispatching in Smalltalk, calling it multiple polymorphism.A Simple Technique for Handling Multiple Polymorphism. In Proceedings of OOPSLA '86, Object–Oriented Programming Systems, Languages and Applications, pages 347–349, November 1986. Printed as SIGPLAN Notices, 21(11).
Overview The general problem addressed is how to dispatch a message to different methods depending not only on the receiver but also on the arguments.
To that end, systems like CLOS implement multiple dispatch. Double dispatch is another solution that gradually reduces the polymorphism on systems that do not support multiple dispatch.
Use cases Double dispatch is useful in situations where the choice of computation depends on the runtime types of its arguments. For example, a programmer could use double dispatch in the following situations: Sorting a mixed set of objects: algorithms require that a list of objects be sorted into some canonical order. Deciding if one element comes before another element requires knowledge of both types and possibly some subset of the fields. Adaptive collision algorithms usually require that collisions between different objects be handled in different ways. A typical example is in a game environment where the collision between a spaceship and an asteroid is computed differently from the collision between a spaceship and a spacestation.More Effective C++ by Scott Meyers(Addison-Wesley, 1996) Painting algorithms that require the intersection points of overlapping sprites to be rendered in a different manner. Personnel management systems may dispatch different types of jobs to different personnel. A schedule algorithm that is given a person object typed as an accountant and a job object typed as engineering rejects the scheduling of that person for that job. Event handling systems that use both the event type and the type of the receptor object in order to call the correct event handling routine. Lock and key systems where there are many types of locks and many types of keys and every type of key opens multiple types of locks. Not only do you need to know the types of the objects involved, but the subset of "information about a particular key that are relevant to seeing if a particular key opens a particular lock" is different between different lock types.
A common idiom The common idiom, as in the examples presented above, is that the selection of the appropriate algorithm is based on the call's argument types at runtime. The call is therefore subject to all the usual additional performance costs that are associated with dynamic resolution of calls, usually more than in a language supporting only single method dispatch. In C++, for example, a dynamic function call is usually resolved by a single offset calculation - which is possible because the compiler knows the location of the function in the object's method table and so can statically calculate the offset. In a language supporting double dispatch, this is slightly more costly, because the compiler must generate code to calculate the method's offset in the method table at runtime, thereby increasing the overall instruction path length (by an amount that is likely to be no more than the total number of calls to the function, which may not be very significant).
Examples Ruby A common use case is displaying an object on a display port which can be a screen or a printer, or something else entirely that doesn't exist yet. This is a naive implementation of how to deal with those different media.
class Rectangle def display_on(port) # selects the right code based on the object class case port when DisplayPort # code for displaying on DisplayPort when PrinterPort # code for displaying on PrinterPort when RemotePort # code for displaying on RemotePort end end end
The same would need to be written for Oval, Triangle and any other object that wants to display itself on a medium, and all would need to be rewritten if a new type of port were to be created. The problem is that more than one degree of polymorphism exist: one for dispatching the display_on method to an object and another for selecting the right code (or method) for displaying.
A much cleaner and more maintainable solution is then to do a second dispatch, this time for selecting the right method for displaying the object on the medium:
class Rectangle def display_on(port) # second dispatch port.display_rectangle(self) end end
class Oval def display_on(port) # second dispatch port.display_oval(self) end end
class DisplayPort def display_rectangle(object) # code for displaying a rectangle on a DisplayPort end def display_oval(object) # code for displaying an oval on a DisplayPort end # ... end
class PrinterPort def display_rectangle(object) # code for displaying a rectangle on a PrinterPort end def display_oval(object) # code for displaying an oval on a PrinterPort end # ... end
C++ At first glance, double dispatch appears to be a natural result of function overloading. Function overloading allows the function called to depend on the type of the argument. Function overloading, however, is done at compile time using "name mangling" where the internal name of the function encodes the argument's type. For example, a function foo(int) may internally be called and the function foo(double) may be called . Thus, there is no name collision, and no virtual table lookup. By contrast, dynamic dispatch is based on the type of the calling object, meaning it uses virtual functions (overriding) instead of function overloading, and does result in a vtable lookup. Consider the following example, written in C++, of collisions in a game: class Spaceship {}; class ApolloSpacecraft : public Spaceship {};
class Asteroid { public: virtual void collideWith(Spaceship&) { std::println("Asteroid hit a Spaceship");
virtual void collideWith(ApolloSpacecraft&) { std::println("Asteroid hit an ApolloSpacecraft");
class ExplodingAsteroid : public Asteroid { public: void collideWith(Spaceship&) override { std::println("ExplodingAsteroid hit a Spaceship");
void collideWith(ApolloSpacecraft&) override { std::println("ExplodingAsteroid hit an ApolloSpacecraft");
If you have: Asteroid asteroid; Spaceship spaceship; ApolloSpacecraft apolloSpacecraft; then, because of function overloading, asteroid.collideWith(spaceship); asteroid.collideWith(apolloSpacecraft); will print, respectively, Asteroid hit a Spaceship and Asteroid hit an ApolloSpacecraft, without using any dynamic dispatch. Furthermore: ExplodingAsteroid explodingAsteroid; explodingAsteroid.collideWith(spaceship); explodingAsteroid.collideWith(apolloSpacecraft); will print ExplodingAsteroid hit a Spaceship and ExplodingAsteroid hit an ApolloSpacecraft respectively, again without dynamic dispatch.
With a reference to an Asteroid, dynamic dispatch is used, and this code: Asteroid& asteroidRef = explodingAsteroid; asteroidRef.collideWith(spaceship); asteroidRef.collideWith(apolloSpacecraft); prints ExplodingAsteroid hit a Spaceship and ExplodingAsteroid hit an ApolloSpacecraft, again as expected. However, the following code does not work as desired: Spaceship& spaceshipRef = apolloSpacecraft; asteroid.collideWith(spaceshipRef); asteroidRef.collideWith(spaceshipRef); The desired behaviour is to bind these calls to the function that takes apolloSpacecraft as its argument, as that is the instantiated type of the variable, meaning the expected output would be Asteroid hit an ApolloSpacecraft and ExplodingAsteroid hit an ApolloSpacecraft. However, the output is actually Asteroid hit a Spaceship and ExplodingAsteroid hit a Spaceship. The problem is that, while virtual functions are dispatched dynamically in C++, function overloading is done statically.
The problem described above can be resolved by simulating double dispatch, for example by using a visitor pattern. Suppose the existing code is extended so that both Spaceship and ApolloSpacecraft are given the function virtual void collideWith(Asteroid& asteroid) { asteroid.collideWith(*this); } Then, while the previous example still does not work correctly, reframing the calls so that the spaceship is the agent gives us the desired behaviour: Spaceship& spaceshipRef = apolloSpacecraft; Asteroid& asteroidRef = explodingAsteroid; spaceshipRef.collideWith(asteroid); spaceshipRef.collideWith(asteroidRef); It prints out Asteroid hit an ApolloSpacecraft and ExplodingAsteroid hit an ApolloSpacecraft, as expected. The key is that spaceshipRef.collideWith(asteroidRef); does the following at run time: spaceshipRef is a reference, so C++ looks up the correct method in the vtable. In this case, it will call ApolloSpacecraft::collideWith(Asteroid&). Within ApolloSpacecraft::collideWith(Asteroid&), asteroid is a reference, so asteroid.collideWith(*this) will result in another vtable lookup. In this case, asteroid is a reference to an ExplodingAsteroid so ExplodingAsteroid::collideWith(ApolloSpacecraft&) will be called.
C# In C#, when calling an instance method accepting an argument, multiple dispatch can be achieved without employing the visitor pattern. This is done by using traditional polymorphism while also casting the argument to dynamic. The run-time binder will choose the appropriate method overload at run-time. This decision will take into consideration the run-time type of the object instance (polymorphism) as well as the run-time type of the argument.
Eiffel The Eiffel programming language can bring the concept of agents to bear on the double-dispatch problem. The example below applies the agent language construct to the double-dispatch problem.
Consider a problem domain with various forms of SHAPE and of drawing SURFACE upon which to draw a SHAPE. Both SHAPE and SURFACE know about a function called `draw' in themselves, but not in each other. We want objects of the two types to co-variantly interact with each other in a double-dispatch using a visitor pattern.
The challenge is to get a polymorphic SURFACE to draw a polymorphic SHAPE on itself.
Output The output example below shows the results of two SURFACE visitor objects being polymorphically passed over a list of polymorphic SHAPE objects. The visitor code pattern is only aware of SHAPE and SURFACE generically and not of the specific type of either. Instead, the code relies on run-time polymorphism and the mechanics of agents to achieve a highly flexible co-variant relationship between these two deferred classes and their descendants.
draw a POLYGON on ETCHASKETCH draw a POLYGON on GRAFFITI_WALL draw a RECTANGLE on ETCHASKETCH draw a RECTANGLE on GRAFFITI_WALL draw a QUADRILATERAL on ETCHASKETCH draw a QUADRILATERAL on GRAFFITI_WALL draw a PARALLELOGRAM on ETCHASKETCH draw a PARALLELOGRAM on GRAFFITI_WALL draw a POLYGON on ETCHASKETCH draw a POLYGON on GRAFFITI_WALL draw a RECTANGLE on ETCHASKETCH draw a RECTANGLE on GRAFFITI_WALL
Setup Before looking at SHAPE or SURFACE, we need to examine the high level decoupled use of our double-dispatch.
Visitor pattern The visitor pattern works by way of a visitor object visiting the elements of a data structure (e.g. list, tree and so on) polymorphically, applying some action (call or agent) against the polymorphic element objects in the visited target structure.