Multiple dispatch


Multiple dispatch or multimethods is a feature of some programming languages in which a function or method can be dynamically dispatched based on the run time type or, in the more general case, some other attribute of more than one of its arguments. This is a generalization of single dispatch polymorphism where a function or method call is dynamically dispatched based on the derived type of the object on which the method has been called. Multiple dispatch routes the dynamic dispatch to the implementing function or method using the combined characteristics of one or more arguments.

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 more conventional, i.e., single-dispatch object-oriented programming languages, when invoking a method, one of its arguments is treated specially and used to determine which of the classes of 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, so that lion.sound would produce a roar, whereas sparrow.sound would produce a chirp.
In 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 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 then. 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, selection among alternative functions must occur then, 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.

Use in practice

To estimate how often multiple dispatch is used in practice, Muschevici et al. studied programs that use dynamic dispatch. They analyzed nine applications, mostly compilers, written in six different languages: Common Lisp Object System, Dylan, Cecil, MultiJava, Diesel, and Nice. Their results show that 13–32% of generic functions use the dynamic type of one argument, while 2.7–6.5% of them use the dynamic type of multiple arguments. The remaining 65–93% of generic functions have one concrete method, and thus are not considered to use the dynamic types of their arguments. Further, the study reports that 2–20% of generic functions had two and 3–6% had three concrete function implementations. The numbers decrease rapidly for functions with more concrete overriders.
Multiple dispatch is used much more heavily in Julia, where multiple dispatch was a central design concept from the origin of the language: collecting the same statistics as Muschevici on the average number of methods per generic function, it was found that the Julia standard library uses more than double the amount of overloading than in the other languages analyzed by Muschevici, and more than 10 times in the case of binary operators.
The data from these papers is summarized in the following table, where the dispatch ratio DR is the average number of methods per generic function; the choice ratio CR is the mean of the square of the number of methods ; and the degree of specialization "DoS" is the average number of type-specialized arguments per method :
LanguageAverage # methods Choice ratio Degree of specialization
Cecil2.3363.301.06
Common Lisp 2.036.341.17
Common Lisp 2.3215.431.17
Common Lisp 2.3726.571.11
Diesel2.0731.650.71
Dylan 1.7418.272.14
Dylan 2.5143.841.23
Julia5.8651.441.54
Julia 28.1378.062.01
MultiJava1.508.921.02
Nice1.363.460.33

Theory

The theory of multiple dispatching languages was first developed by Castagna et al., by defining a model for overloaded functions with late binding. It yielded the first formalization of the problem of covariance and contravariance of object-oriented languages and a solution to the problem of binary methods.

Examples

Distinguishing multiple and single dispatch may be made clearer by an example. Imagine a game that has, among its objects, spaceships and asteroids. When two objects collide, the program may need to do different things according to what has just hit what.

Languages with built-in multiple dispatch

C#

introduced support for dynamic multimethods in version 4 using the 'dynamic' keyword. The following example demonstrates multimethods in conjunction with switch expressions, introduced in version 8 . Like many other statically-typed languages, C# also supports static method overloading. Microsoft expects that developers will choose static typing over dynamic typing in most scenarios. The 'dynamic' keyword supports interoperability with COM objects and dynamically-typed.NET languages.

class Program

static class Collider

class SpaceObject

class Asteroid : SpaceObject

class Spaceship : SpaceObject


Output:

big-boom
a/s
s/s

Common Lisp

In a language with multiple dispatch, such as Common Lisp, it might look more like this :

)
;; deal with asteroid hitting asteroid
)
)
;; deal with asteroid hitting spaceship
)
)
;; deal with spaceship hitting asteroid
)
)
;; 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 above 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.

Julia

has built-in multiple dispatch, and it is central to the language design. The Julia version of the example above might look like:

collide_with =... # deal with asteroid hitting asteroid
collide_with =... # deal with asteroid hitting spaceship
collide_with =... # deal with spaceship hitting asteroid
collide_with =... # deal with spaceship hitting spaceship

Next Generation Shell

has built-in multiple dispatch and predicate dispatch, and they are central to the language design.
Methods with same name form a multiple dispatch method, hence no special declaration is required.
When a multiple dispatch method is called, the candidate method is searched from bottom to top. Whenever types of the arguments match the types specified for parameters, the method is invoked. That is in contrast to many other languages where the most type-wise specific match wins. Inside an invoked method, a failing guard causes the search of method to invoke to continue.

F init o.size = size
F collide "a/a"
F collide "a/s"
F collide "s/a"
F collide "s/s"
F collide
echo, Spaceship))
echo, Spaceship))

Output:

big-boom
a/s

Raku

, like Perl, uses proven ideas from other languages, and type systems have shown themselves to offer compelling advantages in compiler-side code analysis and powerful user-side semantics via multiple dispatch.
It has both multimethods, and multisubs. Since most operators are subroutines, it also has multiple dispatched operators.
Along with the usual type constraints, it also has where constraints that allow making very specialized subroutines.

subset Mass of Real where 0 ^..^ Inf;
role Stellar-Object
class Asteroid does Stellar-Object
class Spaceship does Stellar-Object
my Str @destroyed = < obliterated destroyed mangled >;
my Str @damaged = « damaged 'collided with' 'was damaged by' »;
  1. We add multi candidates to the numeric comparison operators because we are comparing them numerically,
  2. but makes no sense to have the objects coerce to a Numeric type.
  4. We could have also defined entirely new operators this same way.
multi sub infix:« <=> »
multi sub infix:« < »
multi sub infix:« > »
multi sub infix:« »
  1. Define a new multi dispatcher, and add some type constraints to the parameters.
  2. If we didn't define it we would have gotten a generic one that didn't have constraints.
proto sub collide
  1. No need to repeat the types here since they are the same as the prototype.
  2. The 'where' constraint technically only applies to $b not the whole signature.
  3. Note that the 'where' constraint uses the `<` operator candidate we added earlier.
multi sub collide
multi sub collide
  1. This has to be after the first two because the other ones
  2. have 'where' constraints, which get checked in the
  3. order the subs were written.
multi sub collide
  1. The following two candidates can be anywhere after the proto,
  2. because they have more specialized types than the preceding three.
  3. If the ships have unequal mass one of the first two candidates gets called instead.
multi sub collide
  1. You can unpack the attributes into variables within the signature.
  2. You could even have a constraint on them ``.
multi sub collide
my Spaceship $Enterprise.= new,:name);
collide Asteroid.new, $Enterprise;
collide $Enterprise, Spaceship.new;
collide $Enterprise, Asteroid.new;
collide $Enterprise, Spaceship.new;
collide Asteroid.new, Asteroid.new;

Extending languages with multiple dispatch libraries

JavaScript

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. JavaScript and TypeScript do not support multimethods at the syntax level, but it is possible to add multiple dispatch via a library. For example, the multimethod package provides an implementation of multiple-dispatch, generic functions.
Dynamically-typed version in JavaScript:

import from '@arrows/multimethod'
class Asteroid
class Spaceship
const collideWith = multi(
method,
method,
method,
method,

Statically-typed version in TypeScript:

import from '@arrows/multimethod'
class Asteroid
class Spaceship
type CollideWith = Multi &
const collideWith: CollideWith = multi(
method,
method,
method,
method,

Python

Multiple dispatch can be added to Python 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 as_func, ss_func, sa_func
collide = Dispatch
collide.add_rule
collide.add_rule
collide.add_rule
def aa_func:
"""Behavior when asteroid hits asteroid."""
#...define new behavior...
collide.add_rule


  1. ...later...
collide

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 with a simplified syntax:

@multimethod
def collide:
"""Behavior when asteroid hits a asteroid."""
#...define new behavior...
@multimethod
def collide:
"""Behavior when asteroid hits a spaceship."""
#...define new behavior...
  1. ... define other multimethod rules...

and then it goes on to define the multimethod decorator.
The PEAK-Rules package provides multiple dispatch with a syntax similar to the above example. It was later replaced by PyProtocols.
The Reg library also supports multiple and predicate dispatch.

Emulating multiple dispatch

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. Here is a simple example in C:

typedef void ;
void collision_AA ;
void collision_AS ;
void collision_SA ;
void collision_SS ;
typedef enum Thing;
CollisionCase collisionCases = ;
void collide
int main

With the C Object System library, C does support dynamic dispatch similar to CLOS. It is fully extensible and does not need any manual handling of the methods. Dynamic message are dispatched by the dispatcher of COS, which is faster than Objective-C. Here is an example in COS:

  1. include
  2. include
  3. include
// classes
defclass
// data members
endclass
defclass
// data members
endclass
// generics
defgeneric ;
// multimethods
defmethod
// deal with asteroid hitting asteroid
endmethod
defmethod
// deal with asteroid hitting spaceship
endmethod
defmethod
// deal with spaceship hitting asteroid
endmethod
defmethod
// deal with spaceship hitting spaceship
endmethod
// example of use
int main

C++

, C++ natively supports only single dispatch, though adding multi-dispatch is being considered. The methods of working around this limit are analogous: use either the visitor pattern, dynamic cast or a library:

// Example using run time type comparison via dynamic_cast
struct Thing ;
struct Asteroid : Thing ;
struct Spaceship : Thing ;

or pointer-to-method lookup table:

  1. include
  2. include
  3. include
class Thing ;
class Asteroid: public Thing ;
class Spaceship: public Thing ;
Thing::CollisionHandlerMap Thing::collisionCases;
const std::uint32_t Asteroid::cid = typeid.hash_code;
const std::uint32_t Spaceship::cid = typeid.hash_code;
void Asteroid::initCases
void Spaceship::initCases
int main

The yomm2 library provides a fast, orthogonal implementation of open multimethods.
The syntax for declaring open methods is inspired by a proposal for a native
C++ implementation. The library requires that the user registers all the
classes used as virtual arguments, but does not require
any modifications to existing code. Methods are implemented as ordinary
inline C++ functions; they can be overloaded and they can be passed by
pointer. There is no limit on the number of virtual arguments, and they can be
arbitrarily mixed with non-virtual arguments.
The library uses a combination of techniques to implement method calls in constant time, while
mitigating memory usage. Dispatching a call to an open method with a single
virtual argument takes only 15-30% more time than calling an ordinary virtual
member function, when a modern optimizing compiler is used.
The Asteroids example can be implemented as follows:

  1. include
using yorel::yomm2::virtual_;
class Thing ;
class Asteroid : public Thing ;
class Spaceship : public Thing ;
register_class;
register_class;
register_class;
declare_method;
define_method
define_method
define_method
define_method
define_method
int main

Stroustrup mentions in The Design and Evolution of C++ that he liked the concept of multimethods and considered implementing it in C++ but claims to have been unable to find an efficient sample implementation and resolve some possible type ambiguity problems. He then states that although the feature would still be nice to have, that it can be approximately implemented using double dispatch or a type based lookup table as outlined in the C/C++ example above so is a low priority feature for future language revisions.

D

, as do many other object-oriented programming languages, D natively supports only single dispatch. However, it is possible to emulate open multimethods as a library function in D. The openmethods library is an example.

// Declaration
Matrix plus;
// The override for two DenseMatrix objects
@method
Matrix _plus
// The override for two DiagonalMatrix objects
@method
Matrix _plus

Java

In a language with only single dispatch, such as Java, multiple dispatch can be emulated with multiple levels of single dispatch:

interface Collideable
class Asteroid implements Collideable
class Spaceship implements Collideable

Run time instanceof checks at one or both levels can also be used.

Support in programming languages

Primary paradigm

|url=http://nice.sourceforge.net/visitor.html
|title=Visitor Pattern Versus Multimethods
|access-date=2008-04-13

Via extensions