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 one of its arguments.^[1] This is a generalization of single-dispatch polymorphism where a function or method call is dynamically dispatched based on the actual 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 "conventional", i.e. single-dispatch object-oriented programming languages, when invoking a method ("sending a message" in Smalltalk, "calling 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), so that lion.sound() would produce a roar, whereas sparrow.sound() would produce a cheep.

By 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 (CLOS) 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 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 (i.e., late binding), the selection among alternative functions must 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, 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

In order to estimate how often multiple dispatch is used in practice, Muschevici et al.^[2] studied programs that utilize dynamic dispatch. They analyzed nine applications, mostly compilers, written in six different languages: CLOS, Dylan, Cecil, MultiJava, Diesel, and Nice. Their results show that 13%-32% of generic functions utilize the dynamic type of a single argument, while 2.7%-6.5% of them utilize the dynamic type of multiple arguments. The remaining 65%-93% of generic functions have a single concrete method (overrider), and therefore are not considered to use the dynamic types of their arguments. In addition, 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.

Theory

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

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.

Multiple dispatch examples

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.

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^[7] 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^[8] 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.

The PEAK-Rules package provides multiple dispatch with a syntax similar to the above example.^[9]

Examples of emulating multiple dispatch

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 */
 
 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 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 (*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*/ };
 
typedef enum {
    asteroid = 0,
    spaceship
} Thing;
 
enum {
    num_thing_types = 2
};
 
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++

While adding them to C++ is being considered,^[10] currently 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
 
 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 pointer-to-method lookup table:

#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^[11] automates this approach.

Stroustrup mentions in The Design and Evolution of C++ that he liked the concept of Multi-methods 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 goes on to state 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.^[12]

Support in programming languages

Programming languages that support general multimethods:

• Common Lisp (via the Common Lisp Object System)^[13]
• Haskell via multi-parameter type classes^[14]
• Scala, also via multi-parameter type classes
• 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]

Multimethods in other programming languages via extensions:

• Scheme (via e.g. TinyCLOS)
• Python (via PEAK-Rules, RuleDispatch, gnosis.magic.multimethods, PyMultimethods, or multipledispatch)
• 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)
• .NET (via the library MultiMethods.NET)
• C# (via the library multimethod-sharp)
• C++ (via the library yomm11)
• Factor (via the standard multi-methods vocabulary)

Also, multi-parameter type classes in Haskell and Scala can be used to emulate multiple dispatch.

See also

• Predicate dispatch

References

External links

• Bjarne Stroustrup; Yuriy Solodkyy; Peter Pirkelbauer (2007). Open Multi-Methods for C++. ACM 6th International Conference on Generative Programming and Component Engineering.