Click here to Skip to main content
Click here to Skip to main content

Tagged as

Go to top

Multiple dispatch and double dispatch

, 19 Aug 2011
Rate this:
Please Sign up or sign in to vote.
Multiple dispatch (a.k.a. multimethods) is the feature of some object-oriented languages in whicha 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

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);
        }
    }
}

License

This article, along with any associated source code and files, is licensed under The Creative Commons Attribution-Share Alike 3.0 Unported License

Share

About the Author

stfairy
Student Shanghai Jiao Tong University
China China
No Biography provided

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web03 | 2.8.140926.1 | Last Updated 19 Aug 2011
Article Copyright 2011 by stfairy
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid