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 (dynamic) type or, in the more general case, some other attribute of more than…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 19 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 (dynamic) 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.

Expressiveness and modularity

In most popular programming languages, source code is delivered and deployed in granules of functionality which we will here call packages; actual terminology for this concept varies between language. Each package may contain multiple type, value, and function definitions, packages are often compiled separately in languages with a compilation step, and a non-cyclical dependency relationship may exist.

A complete program is a set of packages, with a main package which may depend on several other packages, and the whole program consisting of the transitive closure of the dependency relationship. The so-called expression problem relates to the ability for code in a depending package to extend behaviors (functions or datatypes) defined in a base package from within an including package, without modifying the source to the base package.

Traditional single-dispatch OO languages make it trivial to add new datatypes but not new functions; traditional functional languages tend to have the opposite effect, and multiple dispatch, if implemented correctly, allows both. It is desirable for an implementation of multiple dispatch to have the following properties: It is possible to define different "cases" of a multi-method from within different packages without modifying the source of a base package.

Inclusion of another package in the program should not change the behavior of a given multi-method call, when the call does not use any datatypes defined in the package. Conversely, if a datatype is defined in a given package, and a multi-method extension using that type is also defined in the same package, and a value of that type is passed (through a base type reference or into a generic function) into another package with no dependency on that package, and then the multi-method is invoked with that value as an argument, the multi-method case defined in the package which includes the type should be employed.

To put it another way—within a given program, the same multi-method invoked with the same set of arguments should resolve to the same implementation, regardless of the location of the call site, and whether or not a given definition is "in scope" or "visible" at the point of the method call.

Ambiguity

It is generally desirable that for any given invocation of a multi-method, there be at most one "best" candidate among implementation cases of the multi-method, and/or that if there is not, that this be resolved in a predictable and deterministic fashion, including failure. Non-deterministic behavior is undesirable.

Assuming a set of types with a non-circular subtyping relationship, one can define that one implementation of a multi-method is "better" (more specific) if all dynamically-dispatched arguments in the first are subtypes of all dynamically-dispatched arguments specified in the second, and at least one is a strict subtype. With single dispatch and in the absence of multiple inheritance, this condition is trivially satisfied, but with multiple dispatch, it is possible for two or more candidates to satisfy a given actual argument list, but neither is more specific than the other (one dynamic argument being the subtype in one case, another being the subtype in the other case).

This particularly can happen if two different packages, neither depending on the other, both extend some multi-method with implementations concerning each package's types, and then a third package that includes both (possibly indirectly) then invokes the multi-method using arguments from both packages. Possible resolutions include: Treating any ambiguous calls as an error.

This might be caught at compile time (or otherwise before deployment), but might not be detected until runtime and produce a runtime error. Ordering the arguments, so e.g. the case with the most specific first argument is selected, and subsequent arguments are not considered for ambiguity resolution unless the first argument is insufficient to resolve the issue.

Construction of other rules for resolving an ambiguity in one direction or another. Sometimes, such rules might be arbitrary and surprising. In the rules for static overload resolution in C++, for instance, a type which matches exactly is understandably considered a better match than a type which matches through a base type reference or a generic (template) parameter.

However, if the only possible matches are either through a base type or a generic parameter, the generic parameter is preferred over the base type, a rule that sometimes produces surprising behavior.

Efficiency

Efficient implementation of single-dispatch, including in programming languages that are separately compiled to object code and linked with a low-level (not-language-aware) linker, including dynamically at program load/start time or even under the direction of the application code, are well known. The "vtable" method developed in C++ and other early OO languages (where each class has an array of function pointers corresponding to that class's virtual functions) is nearly as fast as a static method call, requiring O(1) overhead and only one additional memory lookup even in the un-optimized case.

However, the vtable method uses the function name and not the argument type as its lookup key, and does not scale to the multiple dispatch case. (It also depends on the object-oriented paradigm of methods being features of classes, not standalone entities independent of any particular datatype).

Efficient implementation of multiple-dispatch remains an ongoing research problem. using static ColliderLibrary; Console.WriteLine(Collide(new Asteroid(101), new Spaceship(300))); Console.WriteLine(Collide(new Asteroid(10), new Spaceship(10))); Console.WriteLine(Collide(new Spaceship(101), new Spaceship(10))); string Collide(SpaceObject x, SpaceObject y) => x.Size > 100 && y.Size > 100 ? "Big boom!" : CollideWith(x as dynamic, y as dynamic); // Dynamic dispatch to CollideWith method class ColliderLibrary { public static string CollideWith(Asteroid x, Asteroid y) => "a/a"; public static string CollideWith(Asteroid x, Spaceship y) => "a/s"; public static string CollideWith(Spaceship x, Asteroid y) => "s/a"; public static string CollideWith(Spaceship x, Spaceship y) => "s/s"; } abstract record SpaceObject(int Size); record Asteroid(int Size) : SpaceObject(Size); record Spaceship(int Size) : SpaceObject(Size); Output: Big boom! a/s s/s /* Groovy implementation of C# example above Late binding works the same when using non-static methods or compiling class/methods statically (@CompileStatic annotation) / class Program { static void main(String[] args) { println Collider.collide(new Asteroid(101), new Spaceship(300)) println Collider.collide(new Asteroid(10), new Spaceship(10)) println Collider.collide(new Spaceship(101), new Spaceship(10)) } } class Collider { static String collide(SpaceObject x, SpaceObject y) { (x.size > 100 && y.size > 100) ?

"big-boom" : collideWith(x, y) // Dynamic dispatch to collideWith method } private static String collideWith(Asteroid x, Asteroid y) { "a/a" } private static String collideWith(Asteroid x, Spaceship y) { "a/s" } private static String collideWith(Spaceship x, Asteroid y) { "s/a" } private static String collideWith(Spaceship x, Spaceship y) { "s/s"} } class SpaceObject { int size SpaceObject(int size) { this.size = size } } @InheritConstructors class Asteroid extends SpaceObject {} @InheritConstructors class Spaceship extends SpaceObject {} (defclass asteroid () ((size :reader size :initarg :size))) (defclass spaceship () ((size :reader size :initarg :size))) (defun space-object (class size) (make-instance class :size size)) collide-with is a generic function with multiple dispatch (defmethod collide-with ((x asteroid) (y asteroid)) "a/a") (defmethod collide-with ((x asteroid) (y spaceship)) "a/s") (defmethod collide-with ((x spaceship) (y asteroid)) "s/a") (defmethod collide-with ((x spaceship) (y spaceship)) "s/s") (defun collide (x y) (if (and (> (size x) 100) (> (size y) 100)) "big-boom" (collide-with x y))) (print (collide (space-object 'asteroid 101) (space-object 'spaceship 300))) (print (collide (space-object 'asteroid 10) (space-object 'spaceship 10))) (print (collide (space-object 'spaceship 101) (space-object 'spaceship 10))) 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. abstract type SpaceObject end struct Asteroid 100 && y.size > 100) ?

"Big boom!" : collide_with(x, y) Output: julia> collide(Asteroid(101), Spaceship(300)) "Big boom!" julia> collide(Asteroid(10), Spaceship(10)) "a/s" julia> collide(Spaceship(101), Spaceship(10)) "s/s" subset Mass of Real where 0 ^..^ Inf; role Stellar-Object { has Mass $.mass is required; method name () returns Str {...}; } class Asteroid does Stellar-Object { method name () { 'an asteroid' } } class Spaceship does Stellar-Object { has Str $.name = 'some unnamed spaceship'; } my Str @destroyed = ; my Str @damaged = « damaged 'collided with' 'was damaged by' »; We add multi candidates to the numeric comparison operators because we are comparing them numerically, but makes no sense to have the objects coerce to a Numeric type. ( If they did coerce we wouldn't necessarily need to add these operators. ) We could have also defined entirely new operators this same way. multi sub infix:« » ( Stellar-Object:D $a, Stellar-Object:D $b ) { $a.mass $b.mass } multi sub infix:« » ( Stellar-Object:D $a, Stellar-Object:D $b ) { $a.mass > $b.mass } multi sub infix:«

» ( Stellar-Object:D $a, Stellar-Object:D $b ) { $a.mass

$b.mass } Define a new multi dispatcher, and add some type constraints to the parameters. If we didn't define it we would have gotten a generic one that didn't have constraints. proto sub collide ( Stellar-Object:D $, Stellar-Object:D $ ) {*} No need to repeat the types here since they are the same as the prototype.

The 'where' constraint technically only applies to $b not the whole signature. Note that the 'where' constraint uses the ` $b ) { # redispatch to the previous candidate with the arguments swapped samewith $b, $a; } This has to be after the first two because the other ones have 'where' constraints, which get checked in the order the subs were written.

( This one would always match. ) multi sub collide ( $a, $b ) { # randomize the order my ($n1, $n2) = ( $a.name, $b.name ).pick(*); say "$n1 @damaged.pick() $n2"; } The following two candidates can be anywhere after the proto, because they have more specialized types than the preceding three. If the ships have unequal mass one of the first two candidates gets called instead. multi sub collide ( Spaceship $a, Spaceship $b where $a == $b ){ my ($n1, $n2) = ( $a.name, $b.name ).pick(*); say "$n1 collided with $n2, and both ships were ", ( @destroyed.pick, 'left damaged' ).pick; } You can unpack the attributes into variables within the signature.

You could even have a constraint on them `(:mass($a) where 10)`. multi sub collide ( Asteroid $ (:mass($a)), Asteroid $ (:mass($b)) ){ say "two asteroids collided and combined into one larger asteroid of mass { $a + $b }"; } my Spaceship $Enterprise .= new(:mass(1),:name('The Enterprise')); collide Asteroid.new(:mass(.1)), $Enterprise; collide $Enterprise, Spaceship.new(:mass(.1)); collide $Enterprise, Asteroid.new(:mass(1)); collide $Enterprise, Spaceship.new(:mass(1)); collide Asteroid.new(:mass(10)), Asteroid.new(:mass(5)); import { multi, method } from '@arrows/multimethod' class Asteroid {} class Spaceship {} const collideWith = multi( method([Asteroid, Asteroid], (x, y) => { // deal with asteroid hitting asteroid }), method([Asteroid, Spaceship], (x, y) => { // deal with asteroid hitting spaceship }), method([Spaceship, Asteroid], (x, y) => { // deal with spaceship hitting asteroid }), method([Spaceship, Spaceship], (x, y) => { // deal with spaceship hitting spaceship }), ) Statically-typed version in TypeScript: import { multi, method, Multi } from '@arrows/multimethod' class Asteroid {} class Spaceship {} type CollideWith = Multi & { (x: Asteroid, y: Asteroid): void (x: Asteroid, y: Spaceship): void (x: Spaceship, y: Asteroid): void (x: Spaceship, y: Spaceship): void } const collideWith: CollideWith = multi( method([Asteroid, Asteroid], (x, y) => { // deal with asteroid hitting asteroid }), method([Asteroid, Spaceship], (x, y) => { // deal with asteroid hitting spaceship }), method([Spaceship, Asteroid], (x, y) => { // deal with spaceship hitting asteroid }), method([Spaceship, Spaceship], (x, y) => { // deal with spaceship hitting spaceship }), ) from typing import Any import game_behaviors from game_objects import Asteroid, Spaceship from multimethods import Dispatch collide: Dispatch = Dispatch() collide.add_rule((Asteroid, Spaceship), game_behaviors.as_func) collide.add_rule((Spaceship, Spaceship), game_behaviors.ss_func) collide.add_rule((Spaceship, Asteroid), game_behaviors.sa_func) def aa_func(a: Any, b: Any) -> None: """Behavior when asteroid hits asteroid.""" # ...define new behavior... collide.add_rule((Asteroid, Asteroid), aa_func) ...later... collide(thing1, thing2) Functionally, this is very similar to the CLOS example, but the syntax is conventional Python. Using decorators (introduced since Python 2.4), Guido van Rossum produced a sample implementation of multimethods with a simplified syntax: @multimethod(Asteroid, Asteroid) def collide(a: Asteroid, b: Asteroid) -> None: """Behavior when asteroid hits a asteroid.""" # ...define new behavior... @multimethod(Asteroid, Spaceship) def collide(a: Asteroid, b: Spaceship) -> None: """Behavior when asteroid hits a spaceship.""" # ...define new behavior... ... 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.

With the introduction of type hints, multiple dispatch is possible with even simpler syntax. For example, using plum-dispatch, from plum import dispatch @dispatch def collide(a: Asteroid, b: Asteroid) -> None: """Behavior when asteroid hits a asteroid.""" # ...define new behavior... @dispatch def collide(a: Asteroid, b: Spaceship) -> None: """Behavior when asteroid hits a spaceship.""" # ...define new behavior... ...define further rules... typedef void (*CollisionCase)(void); void collisionAsteroidAsteroid(void) { // handle Asteroid-Asteroid collision... } void collisionAsteroidSpaceship(void) { // handle Asteroid-Spaceship collision... } void collisionSpaceshipAsteroid(void) { // handle Spaceship-Asteroid collision... } void collisionSpaceshipSpaceship(void) { // handle Spaceship-Spaceship collision... } typedef enum { COLLIDEABLE_ASTEROID = 0, COLLIDEABLE_SPACESHIP, COLLIDEABLE_COUNT // not a type of Collideable itself, instead used to find number of space objects defined } Collideable; CollisionCase collisionCases[COLLIDEABLE_COUNT][COLLIDEABLE_COUNT] = { {&collisionAsteroidAsteroid, &collisionAsteroidSpaceship}, {&collisionSpaceshipAsteroid, &collisionSpaceshipSpaceship} }; void collide(Collideable a, Collideable b) { (*collisionCases[a][b])(); } int main(void) { collide(COLLIDEABLE_SPACESHIP, COLLIDEABLE_ASTEROID); } 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 (methods) are dispatched by the dispatcher of COS, which is faster than Objective-C.

Here is an example in COS: include include include // classes defclass (Asteroid) // data members endclass defclass (Spaceship) // data members endclass // generics defgeneric (bool, collide_with, _1, _2); // multimethods defmethod (bool, collide_with, Asteroid, Asteroid) // deal with asteroid hitting asteroid endmethod defmethod (bool, collide_with, Asteroid, Spaceship) // deal with asteroid hitting spaceship endmethod defmethod (bool, collide_with, Spaceship, Asteroid) // deal with spaceship hitting asteroid endmethod defmethod (bool, collide_with, Spaceship, Spaceship) // deal with spaceship hitting spaceship endmethod // example of use int main(void) { OBJ a = gnew(Asteroid); OBJ s = gnew(Spaceship); printf(" = %d\n", collide_with(a, a)); printf(" = %d\n", collide_with(a, s)); printf(" = %d\n", collide_with(s, a)); printf(" = %d\n", collide_with(s, s)); grelease(a); grelease(s); } // Example using run time type comparison via dynamic_cast class Collideable { public: virtual void collideWith(Collideable& other) = 0; }; class Asteroid: public Collideable { public: void collideWith(Collideable& other) { // dynamic_cast to a pointer type returns nullptr 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 } } }; class Spaceship: public Collideable { public: void collideWith(Collideable& other) { if (Asteroid* asteroid = dynamic_cast (&other)) { // handle Spaceship-Asteroid collision } else if (Spaceship* spaceship = dynamic_cast (&other)) { // handle Spaceship-Spaceship collision } else { // default collision handling here } } }; or pointer-to-method lookup table: import std; using std::unordered_map; class Collideable { protected: explicit Collideable(uint32_t cid): tid{cid} {} virtual ~Collideable() = default; const uint32_t tid; // type id using CollisionHandler = void (Collideable::*)(Collideable& other); using CollisionHandlers = unordered_map ; static void addHandler(uint32_t id1, uint32_t id2, CollisionHandler handler) { collisionCases.insert(CollisionHandlers::value_type(key(id1, id2), handler)); } static uint64_t key(uint32_t id1, uint32_t id2) { return uint64_t(id1) *handler->second)(other); // pointer-to-method call } else { // default collision handling } } }; class Asteroid: public Collideable { private: void asteroidCollision(Collideable& other) { // handle Asteroid-Asteroid collision } void spaceshipCollision(Collideable& other) { // handle Asteroid-Spaceship collision } public: Asteroid(): Collideable(cid) {} ~Asteroid() = default; static void initCases(); static inline const uint32_t cid = typeid(Asteroid).hash_code(); }; class Spaceship: public Collideable { private: void asteroidCollision(Collideable& other) { // handle Spaceship-Asteroid collision } void spaceshipCollision(Collideable& other) { // handle Spaceship-Spaceship collision } public: Spaceship(): Collideable(cid) {} ~Spaceship() = default; static void initCases(); static inline const uint32_t cid = typeid(Spaceship).hash_code(); // class id }; void Asteroid::initCases() { addHandler(cid, cid, CollisionHandler(&Asteroid::asteroidCollision)); addHandler(cid, Spaceship::cid, CollisionHandler(&Asteroid::spaceshipCollision)); } void Spaceship::initCases() { addHandler(cid, Asteroid::cid, CollisionHandler(&Spaceship::asteroidCollision)); addHandler(cid, cid, CollisionHandler(&Spaceship::spaceshipCollision)); } int main(int argc, char* argv[]) { Asteroid::initCases(); Spaceship::initCases(); Asteroid a1; Asteroid a2; Spaceship s1; Spaceship s2; a1.collideWith(a2); a1.collideWith(s1); s1.collideWith(s2); s1.collideWith(a1); } 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 (and their sub-classes), 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 (compressed dispatch tables, collision free integer hash table) 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: include import std; using std::unique_ptr; class Collideable { public: virtual ~Collideable() = default; }; class Asteroid : public Collideable { // ... }; class Spaceship : public Collideable { // ... }; register_classes(Collideable, Spaceship, Asteroid); declare_method(void, collideWith, (virtual_ , virtual_ )); define_method(void, collideWith, (Collideable& left, Collideable& right)) { // default collision handling } define_method(void, collideWith, (Asteroid& left, Asteroid& right)) { // handle Asteroid-Asteroid collision } define_method(void, collideWith, (Asteroid& left, Spaceship& right)) { // handle Asteroid-Spaceship collision } define_method(void, collideWith, (Spaceship& left, Asteroid& right)) { // handle Spaceship-Asteroid collision } define_method(void, collideWith, (Spaceship& left, Spaceship& right)) { // handle Spaceship-Spaceship collision } int main(int argc, char* argv[]) { yorel::yomm2::update_methods(); unique_ptr a1(std::make_unique ()); unique_ptr a2(std::make_unique ()); unique_ptr s1(std::make_unique ()); unique_ptr s2(std::make_unique ()); // note: types partially erased collideWith(*a1, *a2); // Asteroid-Asteroid collision collideWith(*a1, *s1); // Asteroid-Spaceship collision collideWith(*s1, *a1); // Spaceship-Asteroid collision collideWith(*s1, *s2); // Spaceship-Spaceship collision return 0; } 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 (comparable to virtual functions) 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. // Declaration Matrix plus(virtual!Matrix, virtual!Matrix); // The override for two DenseMatrix objects @method Matrix _plus(DenseMatrix a, DenseMatrix b) { const int nr = a.rows; const int nc = a.cols; assert(a.nr

b.nr); assert(a.nc

b.nc); auto result = new DenseMatrix; result.nr = nr; result.nc = nc; result.elems.length = a.elems.length; result.elems[] = a.elems[] + b.elems[]; return result; } // The override for two DiagonalMatrix objects @method Matrix _plus(DiagonalMatrix a, DiagonalMatrix b) { assert(a.rows == b.rows); double[] sum; sum.length = a.elems.length; sum[] = a.elems[] + b.elems[]; return new DiagonalMatrix(sum); } interface Collideable { void collideWith(Collideable other); // These methods would need different names in a language without method overloading. void collideWith(Asteroid asteroid); void collideWith(Spaceship spaceship); } class Asteroid implements Collideable { public void collideWith(Collideable other) { // Call collideWith on the other object. other.collideWith(this); } public void collideWith(Asteroid asteroid) { // Handle Asteroid-Asteroid collision. } public void collideWith(Spaceship spaceship) { // Handle Asteroid-Spaceship collision. } } class Spaceship implements Collideable { public void collideWith(Collideable other) { // Call collideWith on the other object. other.collideWith(this); } public void collideWith(Asteroid asteroid) { // Handle Spaceship-Asteroid collision. } public void collideWith(Spaceship spaceship) { // Handle Spaceship-Spaceship collision. } } Run time instanceof checks at one or both levels can also be used.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1350523768 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

37 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.