Multiple dispatch

From Wikipedia, the free encyclopedia

This article needs additional citations for verification. Please help improve this article by adding reliable references (ideally, using inline citations). 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 similar to function overloading, which is statically dispatched based on static types.

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

[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/C++

A simple example using pointers to functions. C++ pointers to methods can also be used in a similar manner.

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*/ }
 
enum Object
{
    asteroid = 0,
    spaceship
};
 
CollisionCase colissionCases[ 4] = { &collision_AA, &collision_AS, &collision_SA, &collision_SS };
 
void collide( Object a, Object b)
{
    (*colissionCases[ a * 2 + b])();
}
 
int main()
{
    collide( spaceship, asteroid);
    return 0;
}

[edit] C++

As with Java, C++ only supports single dispatch natively. The methods of working around this limitation are analogous; either use the visitor pattern or dynamic cast:

 // Example using run time type comparison via dynamic_cast
 
 class Thing {
     public:
         virtual void collideWith(Thing& other) = 0;
 }
 
 class Asteroid : public Thing {
 public:
     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)
         Asteroid* asteroid = dynamic_cast<Asteroid*>(&other);
         if (asteroid) {
             // handle Asteroid-Asteroid collision
             //...
             return;
         }
         Spaceship* spaceship = dynamic_cast<Spaceship*>(&other);
         if (spaceship) {
             // handle Asteroid-Spaceship collision
             //...
             return;
         }
         // default collision handling here
         //...
     }
 }
 
 class Spaceship : public Thing {
 public:
     void collideWith(Thing& other) {
         Asteroid* asteroid = dynamic_cast<Asteroid*>(&other);
         if (asteroid) {
             // handle Spaceship-Asteroid collision
             //...
             return;
         }
         Spaceship* spaceship = dynamic_cast<Spaceship*>(&other);
         if (spaceship) {
             // handle Spaceship-Spaceship collision
             //...
             return;
         }
         // default collision handling here
         //...
     }
 }

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

and then it goes on to define the multimethod decorator.

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

[edit] Support in programming languages

Programming languages that support general multimethods:

• Common Lisp (via the Common Lisp Object System) ^[1]
• Dylan^[2]
• Nice^{[3][original research?]}
• Slate^[4]
• Cecil^[5]
• R^[6]
• Groovy^[7]
• Perl 6 ^[8]
• Clojure^[9]

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]
• .NET (via the library MultiMethods.NET)

[edit] References

[edit] Other Links

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