Double dispatch

From Wikipedia, the free encyclopedia

In software engineering, double dispatch is a mechanism that dispatches a function call to different concrete functions depending on the runtime types of multiple objects involved in the call. A related concept is multimethods. 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.

[edit] Examples

Double dispatch is useful in situations where the result of some computation depends on the runtime types of its arguments. For example, one could use double dispatch in the following situations:

• Adaptive collision algorithms usually require that collisions between different objects are handled in different ways. A typical example is in a game environment where the collision between a spaceship and an asteroid will be computed differently than the collision between a spaceship and a spacestation.
• Painting algorithms that shade different types of 2-D sprites that may overlap require that we render the intersection points of these sprites in a different manner.
• Personnel management systems may dispatch different types of job to different personnel. A schedule algorithm passed a person object typed as an accountant and a job typed as engineering will reject the scheduling of that person for that job.
• Event handling, where the appropriate handling routine to call depends on both the event type and the type of the receptor object.

[edit] A common idiom

The common idiom in the examples presented above is that we have made the selection of the appropriate algorithm based on the call's argument types at runtime. Therefore the call is subject to all the usual performance trade-offs that are associated with dynamic resolving of calls, usually more so than in a language supporting 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 therefore can statically calculate the offset. In a language supporting double dispatch, this is more costly, because the compiler must generate code to calculate the method's offset in the method table at runtime.

[edit] Double dispatch is more than function overloading

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 as well as the class on which it is called, but calling an overloaded function goes through at most one virtual table, so dynamic dispatch is only based on the type of the calling object. Consider the following example, written in C++, of collisions in a game:

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 theAsteroid;
SpaceShip theSpaceShip;
GiantSpaceShip theGiantSpaceShip;

then, because of function overloading,

theAsteroid.CollideWith(theSpaceShip); 
theAsteroid.CollideWith(theGiantSpaceShip);

will print Asteroid hit a SpaceShip and Asteroid hit a GiantSpaceShip respectively, without using any dynamic dispatch. Furthermore

ExplodingAsteroid theExplodingAsteroid;
theExplodingAsteroid.CollideWith(theSpaceShip); 
theExplodingAsteroid.CollideWith(theGiantSpaceShip);

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& theAsteroidReference = theExplodingAsteroid;
theAsteroidReference.CollideWith(theSpaceShip); 
theAsteroidReference.CollideWith(theGiantSpaceShip);

prints ExplodingAsteroid hit a SpaceShip and ExplodingAsteroid hit a GiantSpaceShip, again as expected. However,

SpaceShip& theSpaceShipReference = theGiantSpaceShip;
theAsteroid.CollideWith(theSpaceShipReference); 
theAsteroidReference.CollideWith(theSpaceShipReference);

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.

[edit] Double dispatch in C++

The problem described above can be resolved with a technique similar to that used by the 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& theSpaceShipReference = theGiantSpaceShip;
Asteroid& theAsteroidReference = theExplodingAsteroid;
theSpaceShipReference.CollideWith(theAsteroid);
theSpaceShipReference.CollideWith(theAsteroidReference);

It prints out Asteroid hit a GiantSpaceShip and ExplodingAsteroid hit a GiantSpaceShip, as expected. The key is that theSpaceShipReference.CollideWith(theAsteroidReference); does the following at run time:

1. theSpaceShipReference is a reference, so C++ looks up the correct method in the vtable. In this case, it will call GiantSpaceShip::CollideWith(Asteroid&).
2. Within GiantSpaceShip::CollideWith(Asteroid&), inAsteroid is a reference, so inAsteroid.CollideWith(*this) will result in another vtable lookup. In this case, inAsteroid is a reference to an ExplodingAsteroid so ExplodingAsteroid::CollideWith(GiantSpaceShip&) will be called.

[edit] See also

• Visitor pattern
• Multiple dispatch
• Virtual table

[edit] References

This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed. (August 2008)