Multiple dispatch or multimethods or function overloading is the feature of some object-oriented programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
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 polymorphism
Polymorphism in object-oriented programming
Subtype polymorphism, almost universally called just polymorphism in the context of object-oriented programming, is the ability to create a variable, a function, or an object that has more than one form. The word derives from the Greek "πολυμορφισμός" meaning "having multiple forms"...
where a method call is dynamically dispatched based on the actual derived type of the object on which the method has been called. 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 variously called subroutines, procedures, subprograms, functions, or methods. The code in the function is executed by calling it - executing a piece of code that references its name. This transfers control temporarily to the called function; when the function's execution has completed, control is typically transferred back to the instruction in the caller that follows the reference.
Function names are usually selected so as to be descriptive of the function's purpose. It is sometimes desirable to give several functions the same name, often because they perform conceptually similar tasks, 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
Smalltalk
Smalltalk 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...
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
) 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), so that lion.call would produce a roar, whereas sparrow.call would produce a cheep.
By contrast, in languages with multiple dispatch, the selected method is simply the one whose arguments match the number and type of the function call. There is no "special" argument that "owns" the function/method carried out in a particular call.
The Common Lisp Object System is the facility for object-oriented programming which is part of ANSI Common Lisp. CLOS is a powerful 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...
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 must 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.
Common Lisp
In a language with multiple dispatch, such as Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
, 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 function
Generic function
In 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. Typically a generic function itself is an instance of a class that inherits both from function and standard-object...
s.
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
Python (programming language)
Python is a general-purpose, high-level programming language whose 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.
Guido 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...
@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"
In a language with only single dispatch, such as Java, the code would probably look something like this (although the visitor pattern
Visitor pattern
In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure on 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 */
interface Collideable {
/* making this a class would not change the demonstration */
void collideWith(Collideable other);
}
class Asteroid implements Collideable {
public void collideWith(Collideable other) {
if (other instanceof Asteroid) {
// handle Asteroid-Asteroid collision
}
else if (other instanceof Spaceship) {
// handle Asteroid-Spaceship collision
}
}
}
class Spaceship implements Collideable {
public void collideWith(Collideable other) {
if (other instanceof Asteroid) {
// handle Spaceship-Asteroid collision
}
else if (other instanceof Spaceship) {
// handle Spaceship-Spaceship collision
}
}
}
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 branch table
Branch table
In computer programming, a branch table is a term used to describe an efficient method of transferring program control to another part of a program using a table of branch instructions. It is a form of multiway branch...
void collide(Thing a, Thing b) {
(*collisionCases[a][b]);
}
int main {
collide(spaceship, asteroid);
}
C++
While adding them to C++ is being considered, currently C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
only supports single dispatch natively. The methods of working around this limitation are analogous; either use the visitor pattern
Visitor pattern
In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure on which it operates. A practical result of this separation is the ability to add new operations to existing object structures without modifying those...
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...
, dynamic cast:
// Example using run time type comparison via dynamic_cast
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
}
}
}
int main {
Asteroid::initCases;
Spaceship::initCases;
Asteroid a1, a2;
Spaceship s1, s2;
a1.collideWith(a2);
a1.collideWith(s1);
s1.collideWith(s2);
s1.collideWith(a1);
}
Stroustrup mentions in The Design and Evolution of C++ that he liked the concept of Multi-methods 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
Double dispatch
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...
or a type based lookup table as outlined in the C/C++ example above so is a low priority feature for future language revisions.
Support in programming languages
Programming languages that support general multimethods:
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...
R is a programming language and software environment for statistical computing and graphics. The R language is widely used among statisticians for developing statistical software, and R is widely used for statistical software development and data analysis....
Perl 6 is a major revision to the Perl programming language. It is still in development, as a specification from which several interpreter and compiler implementations are being written. It is introducing elements of many modern and historical languages. Perl 6 is intended to have many...
Clojure |closure]]") is a recent dialect of the Lisp programming language created by Rich Hickey. It is a general-purpose language supporting interactive development that encourages a functional programming style, and simplifies multithreaded programming....
C# 4.0 is the latest version of the C# programming language, which was released on April 11, 2010. Microsoft has released the 4.0 runtime and development environment Visual Studio 2010...
Fortress
Multimethods in other programming languages via extensions:
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
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...
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 first developed and designed by Yukihiro "Matz" Matsumoto...
The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...
Factor is a stack-oriented programming language created by Slava Pestov. Factor is dynamically typed and has automatic memory management, as well as powerful metaprogramming features. The language has a single implementation featuring a self-hosted optimizing compiler and an interactive development...
