Multiple dispatch

This article needs additional citations for verification. Please help improve this article by adding reliable references. Unsourced material may be challenged and removed. (February 2009)

Multiple dispatch or multimethods is the feature of some object-oriented programming languages in which a function or method can be dynamically dispatched based on the run time (dynamic) type of more than one of its arguments. This is an extension of single dispatch polymorphism where a method call is dynamically dispatched based on the actual derived type of the object. Multiple dispatch generalizes the dynamic dispatching to work with a combination of two or more objects.

Understanding dispatch

Developers of computer software typically organize source code into named blocks called subroutines, procedures, subprograms, functions, or methods. The choice of term depends on the language being used and, sometimes, on subtle differences between their characteristics. The name of a function is used to refer to it from other source code that calls the function. When code is executed, a call to a function causes control to be transferred temporarily to the called function, and often subsequently returns control to the instructions following the function call in the caller.

Function names are usually selected so as to be descriptive of the function's purpose. Sometimes, it is desirable to give several functions the same name, often because they perform a conceptually similar task, but operate on different types of input data. In such cases, the name reference at the function call site is not sufficient for identifying the block of code to be executed. Instead, the number and type of the arguments to the function call are also used to select among several function implementations.

In "conventional", i.e. single dispatch, object-oriented programming languages, when you invoke a method ("send a message" in Smalltalk, "call a member function" in C++) 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; for example, a number of programming languages put the special argument before a dot in making a method call: special.method(other,arguments,here).

In languages with multiple dispatch, all the arguments are treated symmetrically in the selection of which method to call. Matching recognizes first, second, third, etc. position within the call syntax, but no one argument "owns" the function/method carried out in a particular call.

The Common Lisp Object System (CLOS) is an early and well-known example of multiple dispatch.

Data types

When working with languages that can discriminate data types at compile-time, selecting among the alternatives can occur at compile-time. The act of creating such alternative functions for compile-time selection is usually referred to as overloading a function.

In programming languages that defer data type identification until run-time, the selection among alternative functions can occur at run-time, based on the dynamically-determined types of function arguments. Functions whose alternative implementations are selected in this manner are referred to most generally as multimethods.

There is some run-time cost associated with dynamically dispatching function calls. In some languages^{[citation needed]}, the distinction between overloading and multimethods can be blurred, with the compiler determining whether compile-time selection can be applied to a given function call, or whether slower run-time dispatch is needed.

Examples

Distinguishing multiple and single dispatch may be made clearer by an example. Imagine a game which has, among its (user-visible) objects, spaceships and asteroids. When two objects collide, the program may need to do different things according to what has just hit what.

Java

In a language with only single dispatch, such as Java, the code would probably look something like this (although the visitor pattern can help to solve this problem):

 /* Example using run time type comparison via Java's "instanceof" operator */
 
 abstract class Thing {
     /** making this method non-abstract would not change this demonstration */
     public abstract void collideWith(Thing other);
 }
 
 class Asteroid extends Thing {
     public void collideWith(Thing other) {
         if (other instanceof Asteroid) {
             // handle Asteroid-Asteroid collision
         }
         else if (other instanceof Spaceship) {
             // handle Asteroid-Spaceship collision
         }
     }
 }
 
 class Spaceship extends Thing {
     public void collideWith(Thing other) {
         if (other instanceof Asteroid) {
             // handle Spaceship-Asteroid collision
         }
         else if (other instanceof Spaceship) {
             // handle Spaceship-Spaceship collision
         }
     }
 }

Common Lisp

In a language with multiple dispatch, such as Common Lisp, it might look more like this:

 (defmethod collide-with ((x asteroid) (y asteroid))
   ;; deal with asteroid hitting asteroid
   )
 (defmethod collide-with ((x asteroid) (y spaceship))
   ;; deal with asteroid hitting spaceship
   )
 (defmethod collide-with ((x spaceship) (y asteroid))
   ;; deal with spaceship hitting asteroid
   )
 (defmethod collide-with ((x spaceship) (y spaceship))
   ;; deal with spaceship hitting spaceship
   )

and similarly for the other methods. Explicit testing and "dynamic casting" are not used.

In the presence of multiple dispatch, the traditional idea of methods as being defined in classes and contained in objects becomes less appealing—each collide-with method there is attached to two different classes, not one. Hence, the special syntax for method invocation generally disappears, so that method invocation looks exactly like ordinary function invocation, and methods are grouped not in classes but in generic functions.

C

C does not have dynamic dispatch, so it must be implemented manually in some form. Often an enum is used to identify the subtype of an object. Dynamic dispatch can be done by looking up this value in a function pointer table. Here is a simple example in C.

typedef void (*CollisionCase)();
 
void collision_AA() { /* handle Asteroid-Asteroid collision*/   };
void collision_AS() { /* handle Asteroid-Spaceship collision*/  };
void collision_SA() { /* handle Spaceship-Asteroid collision*/  };
void collision_SS() { /* handle Spaceship-Spaceship collision*/ };
 
typedef enum
{
    asteroid = 0,
    spaceship
} Object;
 
enum {
    no_objects = 2
};
 
CollisionCase colissionCases[no_objects][no_objects] = {
    {&collision_AA, &collision_AS},
    {&collision_SA, &collision_SS} };
 
void collide(Object a, Object b)
{
    (*colissionCases[a][b])();
}
 
int main()
{
    collide( spaceship, asteroid);
    return 0;
}

C++

While adding them to C++ is being considered,^[1] currently C++ only supports single dispatch natively. The methods of working around this limitation are analogous; either use the visitor pattern, double dispatch or dynamic cast:

 // Example using run time type comparison via dynamic_cast
 
 struct Thing {
     virtual void collideWith(Thing& other) = 0;
 }
 
 struct Asteroid : Thing {
     void collideWith(Thing& other) {
         // dynamic_cast to a pointer type returns NULL if the cast fails
         // (dynamic_cast to a reference type would throw an exception on failure)
         if (Asteroid* asteroid = dynamic_cast<Asteroid*>(&other)) {
             // handle Asteroid-Asteroid collision
         }
         else if (Spaceship* spaceship = dynamic_cast<Spaceship*>(&other)) {
             // handle Asteroid-Spaceship collision
         }
         else {
             // default collision handling here
         }
     }
 }
 
 struct Spaceship : Thing {
     void collideWith(Thing& other) {
         if (Asteroid* asteroid = dynamic_cast<Asteroid*>(&other)) {
             // handle Spaceship-Asteroid collision
         }
         else if (Spaceship* spaceship = dynamic_cast<Spaceship*>(&other)) {
             // handle Spaceship-Spaceship collision
         }
         else {
             // default collision handling here
         }
     }
 }

Stroustrup mentions that he liked the concept of Multi-methods in The Design and Evolution of C++ and considered implementing it in C++ but claims to have been unable to find an efficient sample implementation (comparable to virtual functions) and resolve some possible type ambiguity problems. He goes on to state that although the feature would still be nice to have, that it can be approximately implemented using double dispatch or a type based lookup table as outlined in the C/C++ example above so is a low priority feature for future language revisions.^[2]

Python

In languages that do not support multiple dispatch at the language definition or syntactic level, it is often possible to add multiple dispatch using a library extension. For example, the module multimethods.py provides CLOS-style multimethods for Python without changing the underlying syntax or keywords of the language.

from multimethods import Dispatch
from game_objects import Asteroid, Spaceship
from game_behaviors import ASFunc, SSFunc, SAFunc
collide = Dispatch()
collide.add_rule((Asteroid,  Spaceship), ASFunc)
collide.add_rule((Spaceship, Spaceship), SSFunc)
collide.add_rule((Spaceship,  Asteroid), SAFunc)
def AAFunc(a, b):
    """Behavior when asteroid hits asteroid"""
    # ...define new behavior...
collide.add_rule((Asteroid, Asteroid), AAFunc)

# ...later...
collide(thing1, thing2)

Functionally, this is very similar to the CLOS example, but the syntax is conventional Python.

Using Python 2.4 decorators, Guido van Rossum produced a sample implementation of multimethods [1] with a simplified syntax:

@multimethod(Asteroid, Asteroid)
def collide(a, b):
    """Behavior when asteroid hits asteroid"""
    # ...define new behavior...
@multimethod(Asteroid, Spaceship)
def collide(a, b):
    """Behavior when asteroid hits spaceship"""
    # ...define new behavior...
# ... define other multimethod rules ...

and then it goes on to define the multimethod decorator.

Python with PEAK-Rules

from peak.rules import abstract, when
 
@abstract 
def collide(a, b):
    "Process collision of two objects"
 
@when(collide, (Asteroid, Asteroid))
def collide_asteroids(asteroid1, asteroid2):
    pass
 
@when(collide, (Spaceship, Asteroid))
def collide_spaceship_with_asteroid(spaceship, asteroid):
    pass
 
@when(collide, (Asteroid, Spaceship))
def collide_asteroid_with_spaceship(asteroid, spaceship):
    return collide_spaceship_with_asteroid(spaceship, asteroid)
 
# etc...

Support in programming languages

Programming languages that support general multimethods:

• Common Lisp (via the Common Lisp Object System) ^[3]
• Dylan^[4]
• Nice^{[5][original research?]}
• Slate^[6]
• Cecil^[7]
• R^[8]
• Groovy^[9]
• Perl 6 ^[10]
• Clojure^[11]
• C# 4.0^[12]
• Nimrod^[13]

Multimethods in other programming languages via extensions:

• Scheme (via e.g. TinyCLOS)
• Python (via PEAK-Rules, RuleDispatch, gnosis.magic.multimethods, or PyMultimethods)
• Perl (via the module Class::Multimethods)
• Java (using the extension MultiJava)
• Ruby (via the library The Multiple Dispatch Library and Multimethod Package and Vlx-Multimethods Package)
• [MSc Thesis on Multiple Dispatch] [2]^{[original research?]}
• .NET (via the library MultiMethods.NET)
• C# (via the library multimethod-sharp)

References

External links

• Research paper on how to cleanly add multiple dispatch to C++ by Bjarne Stroustrup, Yuriy Solodkyy and Peter Pirkelbauer