| Theories and practice of polymorphism |
|---|
|
In computer science, dynamic dispatch (also known as dynamic binding) is the process of mapping a message to a specific sequence of code (method) at runtime. This is done to support the cases where the appropriate method can't be determined at compile-time (i.e. statically). Dynamic dispatch is only used for code invocation and not for other binding processes (such as for global variables) and the name is normally only used to describe a language feature where a runtime decision is required to determine which code to invoke.
This Object-Oriented feature allows substituting a particular implementation using the same interface, and therefore it enables polymorphism.
Contents |
Dynamic dispatch is needed when multiple classes contain different implementations of the same method (for example foo()). If the class of an object x is not known at compile-time, then when x.foo() is called, the program must decide at runtime which implementation of foo() to invoke, based on the runtime type of object x. This case is known as single dispatch because an implementation is chosen based on a single type—that of the type of the instance. Single dispatch is supported by many object-oriented languages, including statically typed languages such as C++ and Java, and dynamically typed languages such as Smalltalk and Objective-C.
In a small number of languages such as Common Lisp and Dylan, methods or functions can also be dynamically dispatched based on the type of arguments. Expressed in pseudocode, the code manager.handle(y) could call different implementations depending on the type of object y. This is known as multiple dispatch.
A language may be implemented with different dynamic dispatch mechanisms. The choices of the dynamic dispatch mechanism offered by a language to a large extent alter the programming paradigms that are available or are most natural to use within a given language.
Normally, in a typed language, the dispatch mechanism will be performed based on the type of the arguments (most commonly based on the type of the receiver of a message). This might be dubbed 'per type dynamic dispatch'. Languages with weak or no typing systems often carry a dispatch table as part of the object data for each object. This allows instance behaviour as each instance may map a given message to a separate method.
Some languages offer a hybrid approach.
Dynamic dispatch will always incur an overhead so some languages offer the option to turn dynamic dispatch off for particular methods.
C++ uses a virtual table that defines the message to method mapping for a given class. Instances of that type will then store a pointer to this table as part of their instance data. This is complicated when multiple inheritance is used. The virtual table in a C++ object cannot be modified at run-time, which limits the potential set of dispatch targets to a finite set chosen at compile-time.
Although the overhead involved in this dispatch mechanism is low, it may still be significant for some application areas that the language was designed to target. For this reason, Bjarne Stroustrup, the designer of C++, elected to make dynamic dispatch optional and non-default. Only functions declared with the virtual keyword will be dispatched based on the runtime type of the object; other functions will be dispatched based on the object's static type.
As it is possible to store function pointers as part of an object's data, instance behaviour can be used within a C++ program.
Type overloading does not produce dynamic dispatch in C++ as the language considers the types of the message parameters part of the formal message name. This means that the message name the programmer sees is not the formal name used for binding.
JavaScript stores the methods as part of the normal instance data. When an object is defined, methods are loaded into it at any point and may be changed at any time. This allows for great flexibility in the object models used to implement systems with the object definitions being determined at runtime. JavaScript is in the family of prototype-based languages, and as such method lookup must search the method dictionaries of parent prototype objects. Caching strategies allow this to perform well.
There is a separate mechanism that allows a class template to be created with a single constructor and to have default methods attached to it. These default methods will then be available to every instance of that type.
Smalltalk uses a type based message dispatcher. Each instance has a single type whose definition contains the methods. When an instance receives a message, the dispatcher looks up the corresponding method in the message-to-method map for the type and then invokes the method.
A naive implementation of Smalltalk's mechanism would seem to have a significantly higher overhead than that of C++ and this overhead would be incurred for each and every message that an object receives.
In real Smalltalk implementations, a technique known as inline caching is often used that makes method dispatch very fast. Inline caching basically stores the previous destination method address and object class of this call site (or multiple pairs for multi-way caching). The cache method is initialized with the most common target method (or just the cache miss handler), based on the method selector. When the method call site is reached during execution, it just calls the address in the cache (in a dynamic code generator, this call is a direct call as the direct address is back patched by cache miss logic). Prologue code in the called method then compares the cached class with the actual object class, and if they don't match, execution branches to a cache miss handler to find the correct method in the class. A fast implementation may have multiple cache entries and it often only takes a couple instructions to get execution to the correct method on an initial cache miss. The common case will be a cached class match, and execution will just continue in the method.
Out-of-line caching can also be used in the method invocation logic, using the object class and method selector. In one design, the class and method selector are hashed, and used as an index into a method dispatch cache table.
As Smalltalk is a reflective language, many implementations allow mutating individual objects into objects with dynamically generated method lookup tables. This allows altering object behavior on a per object basis. A whole category of languages known as prototype based languages has grown from this, the most famous of which are Self and JavaScript. Careful design of the method dispatch caching allows even prototype based languages to have high performance method dispatch.
Many other dynamically typed languages, including Python, Ruby, Objective-C and Groovy use similar approaches.