Multimethod ( English multimethod ) or multiple dispatching ( English multiple dispatch ) - a mechanism that allows you to select one of several functions depending on the dynamic types or values of the arguments. It is an extension of single dispatching ( virtual functions ), where the method is selected dynamically based on the actual type of the object for which this method was called. Multiple scheduling generalizes dynamic scheduling for cases with two or more objects.
Explicitly, multimethods are supported by the Common Lisp Object System ( CLOS ).
Dispatching Basics
Software developers typically group source code into named blocks called calls, procedures, routines , functions, or methods. The function code is executed by calling it, which consists in executing a piece of code indicated by its name. In this case, control is temporarily transferred to the called function; when this function completes, control is usually passed back to the command following the function call.
Function names are usually chosen to describe their purpose. Sometimes it is necessary to name several functions by the same name - usually because they perform conceptually similar tasks, but work with different types of input data. In such cases, a single function name at the place of its call is not enough to determine the called block of code. In addition to the name, in this case, the number and type of arguments of the called function are also used to select a specific implementation of the function.
In more traditional object-oriented programming languages with single dispatch, when calling a method (sending a message in Smalltalk , calling a member function in C ++ ), one of its arguments is considered in a special way and is used to determine which of (potentially many) methods with this name must be called. In many languages, this special argument is syntactically indicated, for example, in a number of programming languages, a special argument is placed before the dot when the method is called:
special.method (other, arguments, here)
so lion.sound () will give a roar, and sparrow.sound () will give a tweet.
In contrast to them, in languages with multiple dispatching, the selected method is just that method whose arguments coincide with the number and type of arguments in the function call. There is no particular argument that “owns” the function / method referenced by a particular call.
The Common Lisp Object System (CLOS) is one of the first and well-known implementations of multiple dispatch.
Data Types
When working with languages in which data types differ at compile time, the choice among the available options for functions may occur at compile time. Creating such alternatives for alternative functions to choose at compile time is usually called function overloading .
In programming languages that define data types at runtime (late binding), the choice among options for functions must occur at runtime based on dynamically defined types of function arguments. Functions whose alternative implementations are chosen in this way are usually called multimethods.
There are some costs during program execution associated with dynamic dispatch of function calls. In some languages, the distinction between function overloading and multimethods can be blurred, while the compiler determines whether the called function can be selected at compile time, or slower scheduling will be required during program execution.
Practical use
In order to assess how often multiple dispatch is used in practice, Muschevici et al. [1] investigated applications using dynamic dispatch. They analyzed nine applications, mostly compilers, written in six different programming languages: Common Lisp Object System , Dylan , Cecil, MultiJava, Diesel, and Nice. The results show that from 13% to 32% of generalized functions use dynamic typing of one argument, while from 2.7% to 6.5% of functions use dynamic typing of several arguments. The remaining 65% -93% of generalized functions have one specific method (overloaded), and thus were not considered as using dynamic typing of their arguments. In addition, the study reports that from 2% to 20% of the generalized functions had two, and 3% -6% had three of their specific implementations. The proportion of functions with a large number of specific implementations rapidly decreased.
Theory
The theory of languages with multi-calls was first developed by Castagna et al. By defining a model for overloaded functions with late binding [2] [3] . This gave the first formalization of the problem of covariance and contravariance of object-oriented programming languages [4] and the solution of the problem of binary methods [5] .
Example
To better understand the difference between multimethods and single dispatch, you can demonstrate the following example. Imagine a game in which, along with various other objects, asteroids and spaceships are present. When two of any objects collide, the program must choose any specific algorithm of actions, depending on what is faced with what.
Common Lisp
In a language with multimethod support, such as Common Lisp , the code would look like this:
( defgeneric collide ( x y ))
( defmethod collide (( x asteroid ) ( y asteroid ))
; asteroid collides with an asteroid
)
( defmethod collide (( x asteroid ) ( y spaceship ))
;; an asteroid collides with a spaceship
)
( defmethod collide (( x spaceship ) ( y asteroid ))
;; a spaceship collides with an asteroid
)
( defmethod collide (( x spaceship ) ( y spaceship ))
;; the spacecraft collides with the spacecraft
)
and similarly for other methods. Explicit checking and "dynamic type casting" are not used here.
With multiple dispatching, the traditional approach to defining methods in classes and storing them in objects becomes less attractive, since each collide-with method belongs to two different classes, rather than one. Thus, the special syntax for calling a method generally disappears, so a method call looks exactly like a normal function call, and methods are grouped not by classes, but by generalized functions .
Perl 6
Perl 6, like its previous versions, uses proven ideas from other languages and type systems that offer convincing advantages in compiler code analysis and powerful semantics through multiple dispatch.
It has both multimethods and multi-subroutines. Since most operators are actually subroutines, there are also multi-dispatch operators.
Along with the usual type restrictions, it also has "where" type restrictions, which allows you to create very specialized routines.
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 = < obliterated destroyed mangled >;
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 doesn't make 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 }
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 `<` operator candidate we added earlier.
multi sub collide ( $ a , $ b where $ a < $ b ) {
say "$ a.name () was @ destroyed.pick () by $ b.name ()" ;
}
multi sub collide ( $ a , $ b where $ a > $ 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 ));
Python
In languages that do not support multiple dispatch at the syntax level, such as Python , it is usually possible to use multiple dispatch using extension libraries. For example, the multimethods.py module [6] implements CLOS-style multimethods in Python without changing the 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 follows the standard Python syntax.
Using Python 2.4 decorators, Guido van Rossum wrote an example implementation of multimethods [7] 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 a decorator multimethod is defined.
The PEAK-Rules package implements multiple scheduling with syntax similar to the example above. [eight]
Multiple Dispatch Emulation
Java
In languages that have only a single dispatch, such as Java , this code will look like this (however, a visitor pattern can help solve this problem):
/ * Example using run time type comparison via Java's "instanceof" operator * /
interface Collideable {
/ * Making this a class would not change the demonstration. * /
void collideWith ( Collideable other );
}
class Asteroid implements Collideable {
public void collideWith ( Collideable other ) {
if ( other instanceof Asteroid ) {
// Handle Asteroid-Asteroid collision.
}
else if ( other instanceof Spaceship ) {
// Handle Asteroid-Spaceship collision.
}
}
}
class Spaceship implements Collideable {
public void collideWith ( Collideable other ) {
if ( other instanceof Asteroid ) {
// Handle Spaceship-Asteroid collision.
}
else if ( other instanceof Spaceship ) {
// Handle Spaceship-Spaceship collision.
}
}
}
C
C does not have dynamic dispatching, so it must be implemented manually in one form or another. An enumeration is often used to identify an object subtype. Dynamic scheduling can be implemented by searching for this value in the branch table of function pointers. Here is a simple example in C:
typedef void ( * CollisionCase ) ();
void collision_AA () { / * collision handling Asteroid-Asteroid * / };
void collision_AS () { / * Asteroid-Ship collision processing * / };
void collision_SA () { / * Ship-Asteroid collision processing * / };
void collision_SS () { / * ship-to-ship collision processing * / };
typedef enum {
asteroid = 0 ,
spaceship
num_thing_types / * is not an object type, it is used to find the number of objects * /
} Thing ;
CollisionCase collisionCases [ num_thing_types ] [ num_thing_types ] = {
{ & collision_AA , & collision_AS },
{ & collision_SA , & collision_SS }
};
void collide ( Thing a , Thing b ) {
( * collisionCases [ a ] [ b ]) ();
}
int main () {
collide ( spaceship , asteroid );
}
C ++
For 2015, C ++ only supports single dispatch, although support for multiple dispatch is contemplated. [9] Workarounds for this restriction are similar: either using a visitor template or dynamic type casting:
// Example using run time type comparison via dynamic_cast
struct thing {
virtual void collideWith ( Thing & other ) = 0 ;
};
struct Asteroid : Thing {
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)
if ( Asteroid * asteroid = dynamic_cast < Asteroid *> ( & other )) {
// handle Asteroid-Asteroid collision
} else if ( Spaceship * spaceship = dynamic_cast < Spaceship *> ( & other )) {
// handle Asteroid-Spaceship collision
} else {
// default collision handling here
}
}
};
struct Spaceship : Thing {
void collideWith ( Thing & other ) {
if ( Asteroid * asteroid = dynamic_cast < Asteroid *> ( & other )) {
// handle Spaceship-Asteroid collision
} else if ( Spaceship * spaceship = dynamic_cast < Spaceship *> ( & other )) {
// handle Spaceship-Spaceship collision
} else {
// default collision handling here
}
}
};
or tables for finding pointers to methods:
#include <typeinfo>
#include <unordered_map>
typedef unsigned uint4 ;
typedef unsigned long long uint8 ;
class thing {
protected :
Thing ( const uint4 cid ) : tid ( cid ) {}
const uint4 tid ; // type id
typedef void ( Thing :: * CollisionHandler ) ( Thing & other );
typedef std :: unordered_map < uint8 , CollisionHandler > CollisionHandlerMap ;
static void addHandler ( const uint4 id1 , const uint4 id2 , const CollisionHandler handler ) {
collisionCases . insert ( CollisionHandlerMap :: value_type ( key ( id1 , id2 ), handler ));
}
static uint8 key ( const uint4 id1 , const uint4 id2 ) {
return uint8 ( id1 ) << 32 | id2 ;
}
static CollisionHandlerMap collisionCases ;
public :
void collideWith ( Thing & other ) {
CollisionHandlerMap :: const_iterator handler = collisionCases . find ( key ( tid , other . tid ));
if ( handler ! = collisionCases . end ()) {
( this -> * handler -> second ) ( other ); // pointer-to-method call
} else {
// default collision handling
}
}
};
class Asteroid : public Thing {
void asteroid_collision ( Thing & other ) { / * handle Asteroid-Asteroid collision * / }
void spaceship_collision ( Thing & other ) { / * handle Asteroid-Spaceship collision * / }
public :
Asteroid () : Thing ( cid ) {}
static void initCases ();
static const uint4 cid ;
};
class Spaceship : public Thing {
void asteroid_collision ( Thing & other ) { / * handle Spaceship-Asteroid collision * / }
void spaceship_collision ( Thing & other ) { / * handle Spaceship-Spaceship collision * / }
public :
Spaceship () : Thing ( cid ) {}
static void initCases ();
static const uint4 cid ; // class id
};
Thing :: CollisionHandlerMap Thing :: collisionCases ;
const uint4 Asteroid :: cid = typeid ( Asteroid ). hash_code ();
const uint4 Spaceship :: cid = typeid ( Spaceship ). hash_code ();
void Asteroid :: initCases () {
addHandler ( cid , cid , ( CollisionHandler ) & Asteroid :: asteroid_collision );
addHandler ( cid , Spaceship :: cid , ( CollisionHandler ) & Asteroid :: spaceship_collision );
}
void Spaceship :: initCases () {
addHandler ( cid , Asteroid :: cid , ( CollisionHandler ) & Spaceship :: asteroid_collision );
addHandler ( cid , cid , ( CollisionHandler ) & Spaceship :: spaceship_collision );
}
int main () {
Asteroid :: initCases ();
Spaceship :: initCases ();
Asteroid a1 , a2 ;
Spaceship s1 , s2 ;
a1 . collideWith ( a2 );
a1 . collideWith ( s1 );
s1 . collideWith ( s2 );
s1 . collideWith ( a1 );
}
The yomm11 library [10] allows you to automate this approach.
In his book "The Design and Evolution of C ++", Stroustrup mentions that he likes the concept of multimethods and that he considered the possibility of their implementation in C ++, but claims that he could not find an effective example (in comparison with virtual functions) their implementation and solve some possible types of ambiguity problems. He further claims that although it would be good to implement support for this concept, it can be approximately implemented by double dispatch or a type-based lookup table, as described in the C / C ++ example above, so this task has low priority in developing future versions of the language . [eleven]
Implementation in programming languages
- Common Lisp (via the Common Lisp Object System ) [12]
- Haskell , through multiparameter type classes [13]
- Scala , also through multiparameter type classes
- Elixir [14]
- Dylan [15]
- Nice [16]
- Cecil [17]
- R [18]
- Julia [19]
- Groovy [20]
- Lasso [21]
- Perl 6 [22]
- Seed7 [23]
- Clojure [24]
- C # 4.0 [25]
- Fortress [26]
- TADS [27]
- Xtend [28]
- Nim [29]
Support for multimethods in other languages through extensions:
- Scheme (via TinyCLOS )
- Python (via PEAK-Rules , RuleDispatch , gnosis.magic.multimethods , PyMultimethods , or multipledispatch )
- Perl (via Class :: Multimethods module )
- Java (via the MultiJava extension)
- Ruby (via The Multiple Dispatch Library , Multimethod and Vlx-Multimethods packages )
- .NET (through the MultiMethods.NET library)
- C # (via multimethod-sharp library)
- C ++ (via yomm11 library)
- Factor ( multi-methods vocabulary standard)
Multiparameter type classes in Haskell and Scala can also be used to emulate multimethods.
Notes
- ↑ Muschevici, Radu; Potanin, Alex; Tempero, Ewan; Noble, James (2008). "Multiple dispatch in practice" . Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications . OOPSLA '08 (Nashville, TN, USA: ACM): 563-582
- ↑ Giuseppe Castagna; Giorgio Ghelli & Giuseppe Longo (1995). "A calculus for overloaded functions with subtyping." . Information and Computation (Academic press) 117 (1): 115–135
- ↑ Castagna, Giuseppe (1996). Object-Oriented Programming: A Unified Foundation . Birkhäuser. p. 384.
- ↑ Giuseppe Castagna (1995). "Covariance and contravariance: conflict without a cause . " Transactions on Programming Languages and Systems (TOPLAS) (ACM) 17 (3). doi : 10.1145 / 203095.203096
- ↑ Kim Bruce; Luca Cardelli; Giuseppe Castagna; Gary T. Leavens; Benjamin Pierce (1995). "On binary methods" . Theory and Practice of Object Systems 1 (3)
- ↑ multimethods.py , Multiple dispatch in Python with configurable dispatch resolution by David Mertz, et al.
- ↑ Five-minute Multimethods in Python
- ↑ "PEAK-Rules 0.5a1.dev" . Python Package Index . Retrieved March 21, 2014.
- ↑ http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2216.pdf
- ↑ yomm11 , Open Multi-Methods for C ++ 11 by Jean-Louis Leroy.
- ↑ Stroustrup, Bjarne (1994). "Section 13.8". The Design and Evolution of C ++ . Indianapolis, IN, USA: Addison Wesley. ISBN 0-201-54330-3 .
- ↑ Steele, Guy L. (1990). "chapter 28". Common LISP: The Language . Bedford, MA, USA: Digital Press. ISBN 1-55558-041-6 .
- ↑ "Type classes: exploring the design space" . 1997-05-02.
- ↑ "Elixir Lang | Getting Started | Modules" . Retrieved2016-02-21.
- ↑ "Background and Goals" . Retrieved 2008-04-13.
- ↑ "Visitor Pattern Versus Multimethods" . Retrieved2008-04-13.
- ↑ "Cecil Language" . Retrieved 2008-04-13.
- ↑ "How S4 Methods Work" (PDF). Retrieved 2008-04-13.
- ↑ "Methods" . The Julia Manual . Julialang. Retrieved May 11, 2014.
- ↑ "Multimethods in Groovy" . Retrieved 2008-04-13.
- ↑ "Methods - LassoGuide 9.2" . Retrieved 2014-11-11.
- ↑ "Perl 6 FAQ" . Retrieved 2008-04-13.
- ↑ "Multiple Dispatch in Seed7" . Retrieved 2011-04-23
- ↑ "Multimethods in Clojure" . Retrieved 2008-09-04.
- ↑ "Multimethods in C # 4.0 With 'Dynamic'" . Retrieved2009-08-20.
- ↑ "The Fortress Language Specification, Version 1.0" Archived January 20, 2013 by Wayback Machine (PDF). Retrieved 2010-04-23.
- ↑ "TADS 3 System Manual" . Retrieved 2012-03-19
- ↑ "Multiple dispatch" .
- ↑ "Nim Manual" . Retrieved 2015-05-08.