Multiple dispatch
|
|
Multiple dispatch or multimethods is the feature of some object-oriented programming languages in which a function or method can be specialized on the type of more than one of its arguments.
| Contents |
Understanding dispatch
Developers of computer software typically organize source code into named blocks called, variously, 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 flow control to be transferred temporarily to the called function, and often subsequently return 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.meth(other,args,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 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.
C++
In a language with only single dispatch, such as C++, the code would probably look something like this:
void Asteroid::collide_with(Thing * other) {
Asteroid * other_asteroid = dynamic_cast<Asteroid>(other);
if (other_asteroid) {
// deal with asteroid hitting asteroid
return;
}
Spaceship * other_spaceship = dynamic_cast<Spaceship>(other);
if (other_spaceship) {
// deal with asteroid hitting spaceship
return;
}
}
void Spaceship::collide_with(Thing * other) {
Asteroid * other_asteroid = dynamic_cast<Asteroid>(other);
if (other_asteroid) {
// deal with spaceship hitting asteroid
return;
}
Spaceship * other_spaceship = dynamic_cast<Spaceship>(other);
if (other_spaceship) {
// deal with spaceship hitting spaceship
return;
}
}
with one collide_with member function for each kind of object that can collide with others, each containing one case per class.
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.
Multiple dispatch differs from overloading in C++ in that it takes place at run time, on the dynamic types of the arguments, rather at than compile time and on the static types of the arguments.
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, a):
"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.
Support in programming languages
Programming languages that support general multimethods:
- Common Lisp (via the Common Lisp Object System)
- Dylan
- Nice
- Python (via the module gnosis.magic.multimethods (http://gnosis.cx/download/gnosis/magic/multimethods.py))