Dynamic dispatch

From Wikipedia, the free encyclopedia

In computer science, dynamic dispatch 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 cannot 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.

Contents

[edit] Single and multiple dispatch

Main article: multiple dispatch

Dynamic dispatch is needed when multiple classes contain different implementations of the same method foo(). If the type 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 this or self object. Single dispatch is supported by many object-oriented languages, including static 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, 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.

[edit] Dynamic dispatch mechanisms

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.

[edit] C++ Implementation

C++ uses a virtual table which 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.

[edit] Smalltalk Implementation

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.

Smalltalk's mechanism has a significantly higher overhead than that of C++ or Java and this overhead is incurred for each and every message that an object receives. It is possible to alter the Smalltalk message dispatcher to allow instance behaviour, but this is not normally done as it would make the message dispatch even less efficient.

Many other dynamically typed languages, including Python, Ruby and Objective-C use similar approaches.

[edit] JavaScript Implementation

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.

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.

In this context, the Python programming language is fairly unique in that it also allows object-level binding of methods, next to class-level method lookup. This is a feature not found in Smalltalk, unless reflection techniques are used.

[edit] References

  • Lippman, Stanley B. (1996). Inside the C++ Object Model. Addison-Wesley. ISBN 0-201-83454-5.
In other languages