Multiple dispatch

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (August 2006)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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.

1 Understanding dispatch
- 1.1 Data types
2 Examples
3 Support in programming languages
4 References
5 Other Links

[edit] 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.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.

[edit] 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.

[edit] 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.

[edit] 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
         }
     }
 }

[edit] 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.

[edit] C++

Multiple dispatch differs from overloading in C++ in that it takes place at run time, on the dynamic types of the arguments, rather than at compile time and on the static types of the arguments.

[edit] 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 ...

[edit] Python with PEAK-Rules

from peak.rules import *
 
@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...