Multiple dispatch or
multimethods is the feature of some object-oriented
programming languageA programming language is an artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human...
s 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
polymorphismSubtype polymorphism, almost universally called just polymorphism in the context of object-oriented programming, is the ability of one type, A, to appear as and be used like another type, B...
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.
Developers of computer software typically organize source code into named blocks called subroutines, procedures, subprograms, functions, or methods.
Multiple dispatch or
multimethods is the feature of some object-oriented
programming languageA programming language is an artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human...
s 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
polymorphismSubtype polymorphism, almost universally called just polymorphism in the context of object-oriented programming, is the ability of one type, A, to appear as and be used like another type, B...
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
SmalltalkSmalltalk is an object-oriented, dynamically typed, reflective programming language. Smalltalk was created as the language to underpin the "new world" of computing exemplified by "human–computer symbiosis." It was designed and created in part for educational use, more so for constructionist...
, "call a member function" in
C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
) 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)The Common Lisp Object System is the facility for object-oriented programming which is part of ANSI Common Lisp. CLOS is a dynamic object system which differs radically from the OOP facilities found in more static languages such as C++ or Java. CLOS was inspired by earlier Lisp object systems such...
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, 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 patternIn object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure upon which it operates. A practical result of this separation is the ability to add new operations to existing object structures without modifying those...
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 LispCommon Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . Developed to standardize the divergent variants of Lisp which predated it, it is not an implementation but rather a language specification...
, 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 functionIn certain systems for object-oriented programming such as the Common Lisp Object System and Dylan, a generic function is an entity made up of all methods having the same name....
s.
C
A simple example using function pointers 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, currently
C++C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as a middle-level language, as it comprises a combination of both high-level and low-level language features...
only supports single dispatch natively. The methods of working around this limitation are analogous; either use the
visitor patternIn object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure upon which it operates. A practical result of this separation is the ability to add new operations to existing object structures without modifying those...
,
double dispatchIn 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...
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(&other)) {
// handle Asteroid-Asteroid collision
}
else if (Spaceship* spaceship = dynamic_cast(&other)) {
// handle Asteroid-Spaceship collision
}
else {
// default collision handling here
}
}
}
struct Spaceship : Thing {
void collideWith(Thing& other) {
if (Asteroid* asteroid = dynamic_cast(&other)) {
// handle Spaceship-Asteroid collision
}
else if (Spaceship* spaceship = dynamic_cast(&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 dispatchIn 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...
or a type based lookup table as outlined in the C/C++ example above so is a low priority feature for future language revisions.
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
PythonPython is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
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 RossumGuido van Rossum is a Dutch computer programmer who is best known as the author of the Python programming language. In the Python community, Van Rossum is known as a “Benevolent Dictator for Life” , meaning that he continues to oversee the Python development process, making decisions where necessary...
produced a sample implementation of multimethods
http://www.artima.com/weblogs/viewpost.jsp?thread=101605 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
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . Developed to standardize the divergent variants of Lisp which predated it, it is not an implementation but rather a language specification...
(via the Common Lisp Object System)
- Dylan
- Nice
- Slate
- Cecil
- R
In computing, R is a programming language and software environment for statistical computing and graphics. It is an implementation of the S programming language with lexical scoping semantics inspired by Scheme. R was created by Ross Ihaka and Robert Gentleman at the University of Auckland, New...
- Groovy
- Perl 6
Perl 6 is a programming language specification. It serves as a major revision to Perl, introducing elements of many modern and historical languages. Perl 6 is intended to have many implementations. Backward compatibility with earlier versions of Perl is not a direct goal, though a compatibility...
- Clojure
Clojure is a modern dialect of the Lisp programming language. It is a general-purpose language supporting interactive development that encourages a functional programming style which enables simplified multithreaded programming. Clojure runs on the Java Virtual Machine...
- C# 4.0
C# 4.0 is the latest version of the C# programming language, which has been finalized and is in beta testing as of May 2009. Microsoft has released the 4.0 runtime and development environment in a public beta of Visual Studio 2010. The major focus of C# 4.0 is interoperability with partially or...
Multimethods in other programming languages via extensions:
- Scheme (via e.g. TinyCLOS)
- Python
Python is a general-purpose high-level programming language. Its design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
(via PEAK-Rules, RuleDispatch, gnosis.magic.multimethods, or PyMultimethods)
- Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall, a linguist working as a systems administrator for NASA, in 1987, as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone...
(via the module Class:Multimethods)
- Java
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
(using the extension MultiJava)
- Ruby
Ruby is a dynamic, reflective, general purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was initially developed and designed by Yukihiro "Matz" Matsumoto...
(via the library The Multiple Dispatch Library and Multimethod Package and Vlx-Multimethods Package)
- [MSc Thesis on Multiple Dispatch] http://wwwhomes.doc.ic.ac.uk/~aas04/project/MSc/thesis.pdf
- .NET
The Microsoft .NET Framework is a software framework that can be installed on computers running Microsoft Windows operating systems. It includes a large library of coded solutions to common programming problems and a virtual machine that manages the execution of programs written specifically for...
(via the library MultiMethods.NET)
- C# (via the library multimethod-sharp)
External links
- Research paper on how to cleanly add multiple dispatch to C++ by Bjarne Stroustrup, Yuriy Solodkyy and Peter Pirkelbauer