Community hub
Recent from talks
Contribute something
Nothing was collected or created yet.
Dynamic dispatch
View on Wikipedia
| Polymorphism |
|---|
| Ad hoc polymorphism |
| Parametric polymorphism |
| Subtyping |
In computer science, dynamic dispatch is the process of selecting which implementation of a polymorphic operation (method or function) to call at run time. It is commonly employed in, and considered a prime characteristic of, object-oriented programming (OOP) languages and systems.[1]
Object-oriented systems model a problem as a set of interacting objects that enact operations referred to by name. Polymorphism is the phenomenon wherein somewhat interchangeable objects each expose an operation of the same name but possibly differing in behavior. As an example, a File object and a Database object both have a StoreRecord method that can be used to write a personnel record to storage. Their implementations differ. A program holds a reference to an object which may be either a File object or a Database object. Which one it is may have been determined by a run-time setting, and at this stage, the program may not know or care which. When the program calls StoreRecord on the object, something needs to choose which behavior gets enacted. If one thinks of OOP as sending messages to objects, then in this example the program sends a StoreRecord message to an object of unknown type, leaving it to the run-time support system to dispatch the message to the right object. The object enacts whichever behavior it implements.[2]
Dynamic dispatch contrasts with static dispatch, in which the implementation of a polymorphic operation is selected at compile time. The purpose of dynamic dispatch is to defer the selection of an appropriate implementation until the run time type of a parameter (or multiple parameters) is known.
Dynamic dispatch is different from late binding (also known as dynamic binding). Name binding associates a name with an operation. A polymorphic operation has several implementations, all associated with the same name. Bindings can be made at compile time or (with late binding) at run time. With dynamic dispatch, one particular implementation of an operation is chosen at run time. While dynamic dispatch does not imply late binding, late binding does imply dynamic dispatch, since the implementation of a late-bound operation is not known until run time.[citation needed]
Mechanisms
[edit]Single and multiple dispatch
[edit]The choice of which version of a method to call may be based either on a single object, or on a combination of objects. The former is called single dispatch and is directly supported by common object-oriented languages such as Smalltalk, C++, Java, C#, Objective-C, Swift, JavaScript, and Python. In these and similar languages, one may call a method for division with syntax that resembles
dividend.divide(divisor) # dividend / divisor
where the parameters are optional. This is thought of as sending a message named divide with parameter divisor to dividend. An implementation will be chosen based only on dividend's type (perhaps rational, floating point, matrix), disregarding the type or value of divisor.
By contrast, some languages dispatch methods or functions based on the combination of operands; in the division case, the types of the dividend and divisor together determine which divide operation will be performed. This is known as multiple dispatch. Examples of languages that support multiple dispatch are Common Lisp, Dylan, and Julia.
Dynamic dispatch mechanisms
[edit]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). 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 static dispatch for particular methods.
C++ implementation
[edit]C++ uses early binding and offers both dynamic and static dispatch. The default form of dispatch is static. To get dynamic dispatch the programmer must declare a method as virtual.
C++ compilers typically implement dynamic dispatch with a data structure called a virtual function table (vtable) that defines the name-to-implementation mapping for a given class as a set of member function pointers. This is purely an implementation detail, as the C++ specification does not mention vtables. Instances of that type will then store a pointer to this table as part of their instance data, complicating scenarios when multiple inheritance is used. Since C++ does not support late binding, the virtual table in a C++ object cannot be modified at runtime, which limits the potential set of dispatch targets to a finite set chosen at compile time.
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.
Go, Rust and Nim implementation
[edit]In Go, Rust and Nim, a more versatile variation of early binding is used. Vtable pointers are carried with object references as 'fat pointers' ('interfaces' in Go, or 'trait objects' in Rust[3][4]).
This decouples the supported interfaces from the underlying data structures. Each compiled library needn't know the full range of interfaces supported in order to correctly use a type, just the specific vtable layout that they require. Code can pass around different interfaces to the same piece of data to different functions. This versatility comes at the expense of extra data with each object reference, which is problematic if many such references are stored persistently.
The term fat pointer simply refers to a pointer with additional associated information. The additional information may be a vtable pointer for dynamic dispatch described above, but is more commonly the associated object's size to describe e.g. a slice.[citation needed]
Smalltalk implementation
[edit]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.
Because a type can have a chain of base types, this look-up can be expensive. 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 every message that an object receives.
Real Smalltalk implementations often use a technique known as inline caching[5] that makes method dispatch very fast. Inline caching basically stores the previous destination method address and object class of the call site (or multiple pairs for multi-way caching). The cached 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 of 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.
Examples
[edit]
C
[edit]Dynamic dispatch is not built in to C like other languages, but it is still possible by manually managing function pointers.
#include <stdio.h>
#include <stdlib.h>
typedef struct Pet {
const char* name;
void (*speak)(struct Pet*); // holds function pointer
} Pet;
Pet* createPet(const char* name, void (*speakFunc)(Pet*)) {
Pet* pet = (Pet*)malloc(sizeof(Pet));
pet->name = name;
pet->speak = speakFunc;
return pet;
}
void destroyPet(Pet* pet) {
free(pet);
}
void dogSpeak(Pet* pet) {
printf("%s says 'Woof!'\n", pet->name);
}
void catSpeak(Pet* pet) {
printf("%s says 'Meow!'\n", pet->name);
}
void speak(Pet* pet) {
pet->speak(pet);
}
int main() {
Pet* fido = createPet("Fido", dogSpeak);
Pet* simba = createPet("Simba", catSpeak);
speak(fido); // calls dogSpeak()
speak(simba); // speaks catSpeak();
// cleanup; free resources
destroyPet(fido);
destroyPet(simba);
return 0;
}
C++
[edit]import std;
using std::string;
// make Pet an abstract virtual base class
class Pet {
protected:
string name;
public:
explicit Pet(const string& name):
name{name} {}
virtual void speak() = 0;
};
class Dog : public Pet {
public:
explicit Dog(const string& name):
Pet(name) {}
void speak() override {
std::println("{} says 'Woof!'", name);
}
};
class Cat : public Pet {
public:
explicit Cat(const string& name):
Pet(name) {}
void speak() override {
std::println("{} says 'Meow!'", name);
}
};
// speak() will be able to accept anything deriving from Pet
void speak(Pet& pet) {
pet.speak();
}
int main() {
Dog fido("Fido");
Cat simba("Simba");
speak(fido);
speak(simba);
return 0;
}
C#
[edit]namespace Wikipedia.Examples;
using System;
abstract class Pet
{
protected string name;
public Pet(string name)
{
this.name = name;
}
public abstract void Speak();
}
class Dog : Pet
{
public Dog(string name) : base(name) { }
public override void Speak()
{
Console.WriteLine($"{name} says 'Woof!'");
}
}
class Cat : Pet
{
public Cat(string name) : base(name) { }
public override void Speak()
{
Console.WriteLine($"{name} says 'Meow!'");
}
}
public class Main
{
public static void Speak(Pet pet)
{
pet.Speak();
}
public static void Main()
{
Dog fido = new("Fido");
Cat simba = new("Simba");
Speak(fido);
Speak(simba);
}
}
Java
[edit]package org.wikipedia.examples;
abstract class Pet {
protected String name;
public Pet(String name) {
this.name = name;
}
public abstract void speak();
}
class Dog extends Pet {
public Dog(String name) {
super(name);
}
@Override
public void speak() {
System.out.printf("%s says 'Woof!'%n", name);
}
}
class Cat extends Pet {
public Cat(String name) {
super(name);
}
@Override
public void speak() {
System.out.printf("%s says 'Meow!'%n", name);
}
};
public class Main {
public static void speak(Pet pet) {
pet.speak();
}
public static void main(String[] args) {
Dog fido = new Dog("Fido");
Cat simba = new Cat("Simba");
speak(fido);
speak(simba);
}
}
Python
[edit]from abc import ABC, abstractmethod
from typing import Never
# ABC is a class used to denote that classes directly extending it are abstract
class Pet(ABC):
def __init__(self, name: str) -> None:
self.name = name
@abstractmethod
def speak(self) -> Never:
raise NotImplementedError("Abstract method must be implemented by derived classes")
class Dog(Pet):
def __init__(self, name: str) -> None:
super.__init__(name)
def speak(self) -> None:
print(f"{self.name} says 'Woof!'")
class Cat(Pet):
def __init__(self, name: str) -> None:
super.__init__(name)
def speak(self) -> None:
print(f"{self.name} says 'Meow!'")
def speak(pet: Pet) -> None:
# Dynamically dispatches the speak method
# pet can either be an instance of Dog or Cat
pet.speak()
if __name__ == "__main__":
fido: Dog = Dog("Fido")
speak(dog)
simba: Cat = Cat("Simba")
speak(cat)
Rust
[edit]trait Pet {
fn speak(&self);
}
struct Dog<'a> {
name: &'a str
}
struct Cat<'a> {
name: &'a str
}
impl<'a> Dog<'a> {
fn new(name: &'a str) -> Self {
Dog { name }
}
}
impl<'a> Cat<'a> {
fn new(name: &'a str) -> Self {
Cat { name }
}
}
impl Pet<'a> for Dog<'a> {
fn speak(&self) {
println!("{} says 'Woof!'", self.name);
}
}
impl Pet<'a> for Cat<'a> {
fn speak(&self) {
println!("{} says 'Meow!'", self.name);
}
}
// speak() uses dynamic dispatch and resolves the type at runtime,
// for any type that implements the trait Pet
fn speak(pet: &dyn Pet) {
pet.speak();
}
fn main() {
let fido: Dog = Dog::new("Fido");
let simba: Cat = Cat::new("Simba");
speak(&fido);
speak(&simba);
}
See also
[edit]
References
[edit]- ^ Milton, Scott; Schmidt, Heinz W. (1994). Dynamic Dispatch in Object-Oriented Languages (Technical report). Vol. TR-CS-94-02. Australian National University. CiteSeerX 10.1.1.33.4292.
- ^ Driesen, Karel; Hölzle, Urs; Vitek, Jan (1995). "Message Dispatch on Pipelined Processors". ECOOP’95 — Object-Oriented Programming, 9th European Conference, Åarhus, Denmark, August 7–11, 1995. Lecture Notes in Computer Science. Vol. 952. Springer. CiteSeerX 10.1.1.122.281. doi:10.1007/3-540-49538-X_13. ISBN 3-540-49538-X.
- ^ Klabnik, Steve; Nichols, Carol (2023) [2018]. "17. Object-oriented programming features". The Rust Programming Language (2 ed.). San Francisco, California, USA: No Starch Press, Inc. pp. 375–396 [379–384]. ISBN 978-1-7185-0310-6. p. 384:
Trait objects perform dynamic dispatch […] When we use trait objects, Rust must use dynamic dispatch. The compiler doesn't know all the types that might be used with the code that's using trait objects, so it doesn't know which method implemented on which type to call. Instead, at runtime, Rust uses the pointers inside the trait object to know which method to call. This lookup incurs a runtime cost that doesn't occur with static dispatch. Dynamic dispatch also prevents the compiler from choosing to inline a method's code, which in turn prevents some optimizations.
(xxix+1+527+3 pages) - ^ "Trait objects". The Rust Reference. Retrieved 2023-04-27.
- ^ Müller, Martin (1995). Message Dispatch in Dynamically-Typed Object-Oriented Languages (Master thesis). University of New Mexico. pp. 16–17. CiteSeerX 10.1.1.55.1782.
Further reading
[edit]- Lippman, Stanley B. (1996). Inside the C++ Object Model. Addison-Wesley. ISBN 0-201-83454-5.
- Groeber, Marcus; Di Geronimo, Jr., Edward "Ed"; Paul, Matthias R. (2002-03-02) [2002-02-24]. "GEOS/NDO info for RBIL62?". Newsgroup: comp.os.geos.programmer. Archived from the original on 2019-04-20. Retrieved 2019-04-20.
[…] The reason Geos needs 16 interrupts is because the scheme is used to convert inter-segment ("far") function calls into interrupts, without changing the size of the code. The reason this is done so that "something" (the kernel) can hook itself into every inter-segment call made by a Geos application and make sure that the proper code segments are loaded from virtual memory and locked down. In DOS terms, this would be comparable to an overlay loader, but one that can be added without requiring explicit support from the compiler or the application. What happens is something like this: […] 1. The real mode compiler generates an instruction like this: CALL <segment>:<offset> -> 9A <offlow><offhigh><seglow><seghigh> with <seglow><seghigh> normally being defined as an address that must be fixed up at load time depending on the address where the code has been placed. […] 2. The Geos linker turns this into something else: INT 8xh -> CD 8x […] DB <seghigh>,<offlow>,<offhigh> […] Note that this is again five bytes, so it can be fixed up "in place". Now the problem is that an interrupt requires two bytes, while a CALL FAR instruction only needs one. As a result, the 32-bit vector (<seg><ofs>) must be compressed into 24 bits. […] This is achieved by two things: First, the <seg> address is encoded as a "handle" to the segment, whose lowest nibble is always zero. This saves four bits. In addition […] the remaining four bits go into the low nibble of the interrupt vector, thus creating anything from INT 80h to 8Fh. […] The interrupt handler for all those vectors is the same. It will "unpack" the address from the three-and-a-half byte notation, look up the absolute address of the segment, and forward the call, after having done its virtual memory loading thing... Return from the call will also pass through the corresponding unlocking code. […] The low nibble of the interrupt vector (80h–8Fh) holds bit 4 through 7 of the segment handle. Bit 0 to 3 of a segment handle are (by definition of a Geos handle) always 0. […] all Geos API run through the "overlay" scheme […]: when a Geos application is loaded into memory, the loader will automatically replace calls to functions in the system libraries by the corresponding INT-based calls. Anyway, these are not constant, but depend on the handle assigned to the library's code segment. […] Geos was originally intended to be converted to protected mode very early on […], with real mode only being a "legacy option" […] almost every single line of assembly code is ready for it […]
- Paul, Matthias R. (2002-04-11). "Re: [fd-dev] ANNOUNCE: CuteMouse 2.0 alpha 1". freedos-dev. Archived from the original on 2020-02-21. Retrieved 2020-02-21.
[…] in case of such mangled pointers […] many years ago Axel and I were thinking about a way how to use *one* entry point into a driver for multiple interrupt vectors (as this would save us a lot of space for the multiple entry points and the more or less identical startup/exit framing code in all of them), and then switch to the different interrupt handlers internally. For example: 1234h:0000h […] 1233h:0010h […] 1232h:0020h […] 1231h:0030h […] 1230h:0040h […] all point to exactly the same entry point. If you hook INT 21h onto 1234h:0000h and INT 2Fh onto 1233h:0010h, and so on, they would all go through the same "loophole", but you would still be able to distinguish between them and branch into the different handlers internally. Think of a "compressed" entry point into a A20 stub for HMA loading. This works as long as no program starts doing segment:offset magics. […] Contrast this with the opposite approach to have multiple entry points (maybe even supporting IBM's Interrupt Sharing Protocol), which consumes much more memory if you hook many interrupts. […] We came to the result that this would most probably not be save in practise because you never know if other drivers normalize or denormalize pointers, for what reasons ever. […]
(NB. Something similar to "fat pointers" specifically for Intel's real-mode segment:offset addressing on x86 processors, containing both a deliberately denormalized pointer to a shared code entry point and some info to still distinguish the different callers in the shared code. While, in an open system, pointer-normalizing 3rd-party instances (in other drivers or applications) cannot be ruled out completely on public interfaces, the scheme can be used safely on internal interfaces to avoid redundant entry code sequences.) - Bright, Walter (2009-12-22). "C's Biggest Mistake". Digital Mars. Archived from the original on 2022-06-08. Retrieved 2022-07-11. [1]
- Holden, Daniel (2015). "A Fat Pointer Library". Cello: High Level C. Archived from the original on 2022-07-11. Retrieved 2022-07-11.
Dynamic dispatch
View on Grokipediavirtual keyword for methods and uses pointers or references for invocation; in Java, it applies by default to non-static, non-final instance methods on reference types.[3] Even in database systems like Oracle SQL object types, dynamic dispatch navigates the type hierarchy upward from the instance's type to find the nearest overriding implementation.[4]
Dynamic dispatch is commonly realized through virtual function tables (vtables), data structures where each class maintains a table of function pointers to its methods, and each object includes a hidden pointer (vptr) to its class's vtable for quick runtime lookup.[3] This approach ensures efficient O(1) dispatch time while handling inheritance hierarchies, though it introduces slight runtime overhead compared to static calls due to indirection.[5] Languages like C++ and Java rely on this for core polymorphic behavior, making dynamic dispatch a cornerstone of modern OOP paradigms.[3]
Introduction
Definition and purpose
Dynamic dispatch is the process of selecting which method implementation to invoke based on the runtime type of the object on which the method is called.[2] This mechanism, also known as late binding or virtual method invocation, enables runtime polymorphism by resolving method calls dynamically rather than at compile time.[6] In object-oriented programming, it allows a single method name to exhibit different behaviors depending on the actual type of the object, even when invoked through a reference or pointer to a superclass or interface. The primary purpose of dynamic dispatch is to support inheritance hierarchies and interface implementations, allowing subclasses to override superclass methods while maintaining a uniform interface.[2] This facilitates flexible code reuse by decoupling the caller from specific implementations, promoting modular and extensible designs without requiring tight coupling between classes.[6] By enabling such polymorphism, dynamic dispatch ensures that code written against a base type can seamlessly accommodate derived types added later, enhancing maintainability in large software systems. Key benefits include achieving late binding, which contrasts with compile-time decisions by permitting runtime adaptability and supporting implicit extensibility in class hierarchies.[6] This approach avoids code duplication and allows for more generic programming patterns, where the same invocation logic applies across diverse object types. Most object-oriented languages implement dynamic dispatch as single dispatch, resolving the method based solely on the receiver object's type.[7] A basic illustration of dispatch resolution can be seen in the following pseudocode for a method calle.m():
1. Evaluate e to value v.
2. Let C be the class of v.
3. Search C for method m(); if not found, repeat with C's superclass.
4. Execute m() with this bound to v.
1. Evaluate e to value v.
2. Let C be the class of v.
3. Search C for method m(); if not found, repeat with C's superclass.
4. Execute m() with this bound to v.
Historical development
The roots of dynamic dispatch trace back to early programming languages that emphasized flexible function application and runtime behavior, such as Lisp (developed by John McCarthy in 1958), where features like symbols, property lists, and the eval function enabled runtime resolution of expressions, laying foundational ideas for later polymorphic mechanisms.[8] However, dynamic dispatch as a core mechanism in object-oriented programming was pioneered in Simula 67, introduced in 1967 by Ole-Johan Dahl and Kristen Nygaard, where virtual procedures were introduced for simulation purposes, allowing method calls to be resolved at runtime based on object types to support inheritance and polymorphism in the first object-oriented language.[9] The 1970s saw dynamic dispatch gain prominence in object-oriented paradigms through Smalltalk, conceived by Alan Kay and his team at Xerox PARC starting in 1972. Smalltalk popularized message passing as a core mechanism, where objects respond to messages via dynamic lookup at runtime, influencing the view of computation as communication between autonomous entities and embedding dispatch deeply into the language's design.[10] Building on these ideas, Bjarne Stroustrup introduced virtual functions in C++ in 1983, extending C with runtime polymorphism to support large-scale software development at Bell Labs, which became a staple for efficient, low-level object-oriented programming.[11] In the 1990s, Java, led by James Gosling at Sun Microsystems and first released in 1995, inherited dynamic dispatch from C++ but made all non-static instance methods virtual by default, emphasizing platform independence through the Java Virtual Machine while simplifying polymorphism for widespread adoption.[12] Concurrently, multiple dispatch—a generalization allowing resolution on multiple arguments—emerged in the Common Lisp Object System (CLOS), developed in the late 1980s and standardized in 1994, integrating generic functions with runtime method selection for flexible, extensible systems.[13] This approach influenced later languages like Julia, released in 2012 by Jeff Bezanson, Stefan Karpinski, Viral Shah, and Alan Edelman, where multiple dispatch is central to scientific computing, enabling type-specialized functions for performance-critical applications.[14] Key milestones include the formalization of C++'s virtual functions in the ISO/IEC 14882 standard of 1998, ensuring portable runtime polymorphism across implementations, and Rust's introduction of trait objects for dynamic dispatch upon its 1.0 stable release in 2015, providing safe, memory-managed alternatives to traditional virtual tables in systems programming.[15]Core Concepts
Static versus dynamic dispatch
Static dispatch resolves method calls at compile time based on the declared static types of the arguments, employing techniques such as function overloading or generics to select the appropriate implementation.[6] This approach enables early binding, where the compiler determines the exact function to invoke without runtime overhead, resulting in efficient execution but limited flexibility for handling polymorphism that emerges at runtime.[16] In contrast, dynamic dispatch defers resolution until runtime, selecting the method based on the actual dynamic types of the objects involved, which supports method overriding in inheritance hierarchies and accommodates duck typing in dynamically typed languages.[6] This mechanism allows for runtime polymorphism, where the behavior of a call can vary depending on the concrete object type, even if the reference is of a supertype.[16] The following pseudocode illustrates the difference: in static dispatch, a direct function call is resolved immediately by the compiler based on the parameter types.function processShape(shape: [Shape](/page/Shape)) {
return shape.area(); // Static: resolved to Shape.area() if no overloads
}
function processShape(shape: [Shape](/page/Shape)) {
return shape.area(); // Static: resolved to Shape.area() if no overloads
}
function processShape(shape: [Shape](/page/Shape)) {
return shape.area(); // Dynamic: resolved to actual type's area() at runtime
}
function processShape(shape: [Shape](/page/Shape)) {
return shape.area(); // Dynamic: resolved to actual type's area() at runtime
}
Single versus multiple dispatch
Single dispatch refers to a form of dynamic dispatch in which the selection of the appropriate method is determined solely by the runtime type of the receiver, or first argument, of the method call. This mechanism is prevalent in class-based object-oriented programming languages, where each class maintains its own set of methods, and the dispatch resolves to the method defined in the subclass hierarchy based on the actual object type. For instance, in a call likecar.collide(bike), the method chosen depends only on the type of car, regardless of bike's type.[17]
In contrast, multiple dispatch extends this by selecting the method based on the runtime types of two or more arguments, enabling more nuanced polymorphism that considers interactions between multiple objects. This approach is particularly useful for operations where the behavior depends symmetrically on all involved types, such as arithmetic operations between different numeric types (e.g., adding an integer to a float versus float to float) or collision detection between diverse entities (e.g., collide(car, bike) dispatching differently from collide(bike, car) based on both types). Multiple dispatch provides greater expressiveness than single dispatch, as it generalizes the latter—any single-dispatch scenario can be simulated by ignoring additional arguments—while allowing for more flexible method resolution without relying on workarounds like explicit type checks.[17][18]
Conceptually, single dispatch aligns well with hierarchical inheritance structures in object-oriented languages, where methods are overridden along a class inheritance chain to specialize behavior for subclasses, promoting encapsulation around the receiver object. Multiple dispatch, however, better accommodates symmetric or multi-party relationships that do not privilege one argument, such as binary operators or generic functions that operate on peer arguments, reducing the need for visitor patterns or conditional logic in single-dispatch systems.[17]
To illustrate single dispatch in pseudocode, consider a method call on an object:
let obj = new Subclass(); // runtime type is Subclass
obj.method(arg); // dispatches to Subclass.method based on obj's type
let obj = new Subclass(); // runtime type is Subclass
obj.method(arg); // dispatches to Subclass.method based on obj's type
obj alone.[17]
For multiple dispatch, the pseudocode involves a generic function call with multiple arguments:
collide(car: [Car](/page/Car), bike: Bike); // dispatches to method matching both Car and Bike types
collide(car: [Car](/page/Car), bike: Bike); // dispatches to method matching both Car and Bike types
General Mechanisms
Virtual method tables
Virtual method tables, often abbreviated as vtables, serve as a fundamental mechanism for implementing single dynamic dispatch in object-oriented languages with compiled code generation. A vtable is a per-class data structure consisting of an array of function pointers that map virtual method names or signatures to their concrete implementations. Each instance of a class contains a hidden pointer, known as the virtual pointer or vptr, typically located at the beginning of the object's memory layout, which references the appropriate vtable for that class. This setup enables runtime resolution of method calls based on the actual type of the object, rather than its compile-time declared type.[20] The dispatch process occurs at runtime as follows: when a virtual method is invoked on an object through a base class pointer or reference, the runtime first loads the vptr from the object's memory layout. This vptr points to the vtable, from which the system indexes into the specific slot corresponding to the method's offset—determined at compile time based on the method's declaration order in the class hierarchy—and retrieves the function pointer for execution. This indirection adds a small runtime overhead but ensures polymorphic behavior. In implementations like the Itanium C++ ABI, the vtable may include additional entries such as offset-to-top for virtual base class adjustments and pointers to runtime type information (RTTI), enhancing support for more complex inheritance scenarios.[21][22] Inheritance is handled by extending and modifying vtables in derived classes. A derived class inherits the vtable layout from its base class, copying entries for non-overridden methods while replacing slots for overridden virtual methods with pointers to the new implementations. For single inheritance, the vtable remains straightforward, with the derived class's vtable building directly upon the base's. In cases of multiple inheritance, complications arise due to multiple base classes potentially contributing virtual methods; the Itanium C++ ABI addresses this by generating secondary vtables for non-primary bases and employing thunk functions—small assembly stubs that adjust the implicitthis pointer to align with the correct subobject offset before delegating to the actual method implementation. These thunks are stored in the vtable entries, ensuring correct dispatch across the inheritance graph without requiring pointer adjustments at every call site.[23][24]
To illustrate, consider the memory layout of an object in a single inheritance hierarchy. The object begins with the vptr (e.g., an 8-byte pointer on 64-bit systems) pointing to the class's vtable, followed by non-static data members. The vtable itself is an array starting with metadata like the offset-to-top (0 for the most derived class) and RTTI pointer, then slots for virtual methods: the base class's methods first, followed by any new or overridden ones in the derived class. For example:
Object Layout:
+-------------+
| vptr ----> | (points to VTable)
+-------------+
| data1 |
+-------------+
| data2 |
+-------------+
VTable:
+-------------+
| offset-to-top (0) |
+-------------+
| RTTI ptr |
+-------------+
| base_method1| (ptr to impl)
+-------------+
| base_method2| (ptr to overridden impl in derived)
+-------------+
| derived_method | (ptr to new impl)
+-------------+
Object Layout:
+-------------+
| vptr ----> | (points to VTable)
+-------------+
| data1 |
+-------------+
| data2 |
+-------------+
VTable:
+-------------+
| offset-to-top (0) |
+-------------+
| RTTI ptr |
+-------------+
| base_method1| (ptr to impl)
+-------------+
| base_method2| (ptr to overridden impl in derived)
+-------------+
| derived_method | (ptr to new impl)
+-------------+
base_method2() loads the vptr, indexes to the second function slot, and jumps to the derived implementation if overridden.[25][21]
Vtables are central to languages like C++, where the Itanium ABI standardizes their construction for compatibility across compilers, and Java, where the HotSpot JVM implementation uses vtables (or method tables) per class to support invokevirtual bytecode for dynamic dispatch—though the JVM specification itself does not mandate this exact mechanism, leaving room for alternatives in other implementations. In contrast, interpreted languages tend to rely less on precomputed vtables, favoring dictionary-based lookups at runtime for greater flexibility.[26][27][28]
Message passing and dynamic lookup
In the message passing paradigm, objects communicate by sending messages, which are essentially method invocations, to other objects. The receiver object determines the appropriate response at runtime by searching for a matching implementation in its method dictionary, a data structure typically implemented as a hash table keyed by message selectors (unique identifiers for methods). This approach, foundational to pure object-oriented languages, enables flexible interactions without requiring compile-time knowledge of the receiver's type.[29] The dynamic lookup process occurs entirely at runtime: upon receiving a message, the system hashes the selector to probe the receiver's class method dictionary. If no match is found, it traverses the class hierarchy (superclasses) or prototype chain until a suitable method is located or an error is raised. This search-based resolution supports metaclasses, where classes themselves are objects that can define meta-methods, facilitating meta-programming such as runtime class modifications. Unlike precomputed pointer tables, this mechanism avoids fixed structures, allowing methods to be added or overridden dynamically during execution.[29][30] Polymorphism is handled through late binding, where the same message can elicit different behaviors based on the receiver's current state or class, even if methods are introduced post-deployment. For instance, a message likedisplay might render a rectangle differently from a circle, resolved solely at invocation time. This runtime flexibility contrasts with static approaches by permitting on-the-fly extensions without recompilation.[30]
The lookup can be illustrated in pseudocode, adapted from early Smalltalk implementations:
send message to receiver:
currentClass = receiver's class
while currentClass is not nil:
method = currentClass's methodDictionary lookup: message selector
if method found:
create new context with method, receiver, and arguments
execute method in context
return result
currentClass = currentClass's superclass
raise doesNotUnderstand error
send message to receiver:
currentClass = receiver's class
while currentClass is not nil:
method = currentClass's methodDictionary lookup: message selector
if method found:
create new context with method, receiver, and arguments
execute method in context
return result
currentClass = currentClass's superclass
raise doesNotUnderstand error
Language Implementations
C++
In C++, dynamic dispatch is primarily achieved through virtual functions, which allow runtime polymorphism by enabling derived classes to override base class methods. Thevirtual keyword is used in the declaration of a non-static member function within a base class to mark it as virtual, supporting dynamic dispatch via pointers or references to the base class. When a derived class defines a function with the same name, parameter types, cv-qualifiers, and ref-qualifiers as a virtual function in the base class, it overrides the base version, either implicitly or explicitly using the override specifier (introduced in C++11 for safety). This mechanism ensures that the correct derived class implementation is invoked at runtime, regardless of the static type of the pointer or reference.[32]
The compiler implements virtual functions using virtual method tables (vtables), one per class containing virtual functions, and a virtual pointer (vptr) embedded in each object instance. For each class with virtual functions, the compiler generates a vtable—a static array of function pointers corresponding to the virtual functions in declaration order. During object construction, the vptr (typically the first member of the object layout) is initialized to point to the appropriate vtable for that class's type. At runtime, when a virtual function is called through a base pointer or reference, the system dereferences the vptr to access the vtable and jumps to the function pointer at the correct offset, resolving the call based on the dynamic type of the object. This process adds a small runtime overhead but enables flexible polymorphism.[33]
Pure virtual functions, declared using the = 0 syntax (e.g., virtual void func() = 0;), further extend this by defining abstract base classes that cannot be instantiated directly. A class is abstract if it declares or inherits at least one pure virtual function without providing an implementation, serving as an interface for derived classes to implement. Derived classes must override all pure virtual functions from the base to become concrete and instantiable, promoting a clear hierarchy for polymorphism. The following code example illustrates a simple base-derived hierarchy with an abstract base class Shape, demonstrating upcasting and dynamic dispatch resolution:
class Shape { // Abstract base class
public:
virtual ~Shape() = default; // Virtual destructor for proper cleanup
virtual double area() const = 0; // Pure virtual function
};
class Circle : [public](/page/Public) Shape {
private:
double radius;
public:
Circle(double r) : radius(r) {}
double area() const override {
return 3.14159 * radius * radius;
}
};
class Rectangle : [public](/page/Public) Shape {
private:
double width, height;
public:
Rectangle(double w, double h) : width(w), height(h) {}
double area() const override {
return width * height;
}
};
void printArea(const Shape& s) { // Accepts base reference (upcasting)
std::cout << "Area: " << s.area() << std::endl; // Dynamic dispatch
}
int main() {
Circle c(5.0);
Rectangle r(4.0, 6.0);
printArea(c); // Calls Circle::area()
printArea(r); // Calls Rectangle::area()
return 0;
}
class Shape { // Abstract base class
public:
virtual ~Shape() = default; // Virtual destructor for proper cleanup
virtual double area() const = 0; // Pure virtual function
};
class Circle : [public](/page/Public) Shape {
private:
double radius;
public:
Circle(double r) : radius(r) {}
double area() const override {
return 3.14159 * radius * radius;
}
};
class Rectangle : [public](/page/Public) Shape {
private:
double width, height;
public:
Rectangle(double w, double h) : width(w), height(h) {}
double area() const override {
return width * height;
}
};
void printArea(const Shape& s) { // Accepts base reference (upcasting)
std::cout << "Area: " << s.area() << std::endl; // Dynamic dispatch
}
int main() {
Circle c(5.0);
Rectangle r(4.0, 6.0);
printArea(c); // Calls Circle::area()
printArea(r); // Calls Rectangle::area()
return 0;
}
area() through the Shape reference resolve to the derived class implementations at runtime, showcasing polymorphism without knowing the exact type.[32]
C++ supports multiple inheritance, allowing a derived class to inherit from multiple base classes, but this introduces challenges like the diamond problem, where ambiguity arises from a shared base class. Consider a hierarchy where classes B and C both inherit from A, and D inherits from both B and C; without mitigation, D would contain two separate subobjects of A, leading to duplicate data members and ambiguous member access (e.g., which A::data to use). Virtual inheritance resolves this by using the virtual keyword in the inheritance list of intermediate classes (e.g., class B : public virtual A), ensuring a single shared subobject of the virtual base class A in D, thus eliminating duplication and ambiguity. However, virtual inheritance incurs costs, such as increased object sizes due to additional vtable pointers or offsets (typically 4-8 bytes per virtual base on common architectures) and slightly more complex construction semantics, where the virtual base is constructed only once by the most derived class.[34]
As an alternative to virtual functions for achieving polymorphism without runtime dispatch, C++ provides the Curiously Recurring Template Pattern (CRTP), a compile-time technique for static polymorphism. In CRTP, a base class template is instantiated with the derived class as a template parameter (e.g., template <typename Derived> class Base; class Derived : public Base<Derived> {}), allowing the base to access and call derived-specific methods via static_cast<Derived*>(this) at compile time. This resolves function calls statically, avoiding vtable overhead and enabling optimizations like inlining, while still providing a polymorphic interface. CRTP is particularly useful in performance-critical scenarios where dynamic dispatch is undesirable.
Java
In Java, dynamic dispatch is realized through virtual methods executed on the Java Virtual Machine (JVM), ensuring platform-neutral runtime polymorphism across diverse hardware and operating systems. All non-static, non-final, and non-private instance methods are virtual by default, permitting subclasses to override superclass implementations for behavior variation based on the actual object type at runtime. Interfaces reinforce this by declaring abstract methods that implementing classes must provide, thereby enforcing dispatch to concrete realizations and facilitating modular, extensible designs.[35][36] The JVM orchestrates dynamic dispatch via theinvokevirtual bytecode instruction, which resolves method calls during execution by consulting method tables embedded in class metadata within the runtime constant pool. This process links symbolic references to direct method implementations at load time or lazily upon first invocation, while the JVM's support for dynamic class loading enables seamless integration of new classes—loaded via ClassLoader—into the dispatch hierarchy without halting the application.[37][38]
A representative example demonstrates polymorphism through interface implementation and method overriding. Consider the Shape interface with an abstract area() method, implemented by Circle and Rectangle classes:
interface Shape {
double area();
}
class Circle implements Shape {
private double radius;
public Circle(double radius) { this.radius = radius; }
@Override
public double area() { return Math.PI * radius * radius; }
}
class Rectangle implements Shape {
private double width, height;
public Rectangle(double width, double height) { this.width = width; this.height = height; }
@Override
public double area() { return width * height; }
}
// Polymorphic usage
Shape shape1 = new Circle(5.0);
Shape shape2 = new Rectangle(4.0, 6.0);
System.out.println(shape1.area()); // Outputs ≈78.54 (Circle's implementation)
System.out.println(shape2.area()); // Outputs 24.0 (Rectangle's implementation)
interface Shape {
double area();
}
class Circle implements Shape {
private double radius;
public Circle(double radius) { this.radius = radius; }
@Override
public double area() { return Math.PI * radius * radius; }
}
class Rectangle implements Shape {
private double width, height;
public Rectangle(double width, double height) { this.width = width; this.height = height; }
@Override
public double area() { return width * height; }
}
// Polymorphic usage
Shape shape1 = new Circle(5.0);
Shape shape2 = new Rectangle(4.0, 6.0);
System.out.println(shape1.area()); // Outputs ≈78.54 (Circle's implementation)
System.out.println(shape2.area()); // Outputs 24.0 (Rectangle's implementation)
Shape invoke area() polymorphically, with the JVM dispatching to the overriding method of the underlying object instance via invokevirtual.[39]
Introduced in Java 8, default methods in interfaces provide concrete implementations, enabling API evolution by adding functionality to existing interfaces without requiring recompilation or breaking binary compatibility for prior implementers. Resolution of default methods during dispatch favors the most specific implementation in inheritance hierarchies; for instance, if a class implements multiple interfaces with override-equivalent default methods, a compile-time error occurs unless the class explicitly overrides the conflicting method to resolve the ambiguity.[36][40]
Java's reflection API supports meta-level dynamic dispatch by enabling runtime inspection and invocation of methods through the java.lang.reflect package. The Method.invoke(Object obj, Object... args) call executes a method on a specified object instance (or null for static methods), performing dynamic resolution akin to normal dispatch but with additional overhead for introspection; any underlying exceptions are encapsulated in an InvocationTargetException for extraction via getCause(). This facility is essential for tools like serialization frameworks and dependency injectors that manipulate code generically at runtime.[41]
Python
In Python, dynamic dispatch is achieved through a flexible mechanism involving descriptors and the__getattribute__ method, making all instance methods implicitly virtual. When an attribute is accessed on an instance, such as obj.method, the object.__getattribute__ method performs the lookup by first checking the class's __dict__ for descriptors. Functions defined in a class act as non-data descriptors, and their __get__ method binds the instance as the first argument (self), transforming the function into a bound method at runtime. This process ensures that method resolution occurs dynamically, allowing polymorphism based on the actual object type without explicit virtual declarations.[31]
For classes with multiple inheritance, Python employs the Method Resolution Order (MRO) to determine the sequence in which base classes are searched for attributes and methods, preventing ambiguities in diamond inheritance scenarios. The MRO is computed using the C3 linearization algorithm, introduced in Python 2.3 for new-style classes, which produces a monotonic linearization that respects local precedence (superclasses appear before subclasses) and the order of base classes in the inheritance list. For example, in a diamond hierarchy where class A inherits from B and C, both of which inherit from D, the MRO for A would be [A, B, C, D], ensuring D's methods are only called after B and C if not overridden. This runtime computation of the MRO, accessible via the __mro__ attribute, enables consistent method dispatch across complex hierarchies.[42]
The super() function facilitates cooperative multiple inheritance by allowing classes to invoke methods from the next class in the MRO dynamically, promoting code reuse without hardcoding parent class names. In a class hierarchy, super().method() resolves the appropriate class at runtime based on the MRO, enabling each class to extend or modify behavior from subsequent ones. Consider the following example demonstrating runtime resolution in a multiple inheritance setup:
class Base:
def __init__(self):
print("Base init")
class Left(Base):
def __init__(self):
super().__init__()
print("Left init")
class Right(Base):
def __init__(self):
super().__init__()
print("Right init")
class Derived(Left, Right):
def __init__(self):
super().__init__()
print("Derived init")
Derived() # Outputs: Base init\nLeft init\nRight init\nDerived init
class Base:
def __init__(self):
print("Base init")
class Left(Base):
def __init__(self):
super().__init__()
print("Left init")
class Right(Base):
def __init__(self):
super().__init__()
print("Right init")
class Derived(Left, Right):
def __init__(self):
super().__init__()
print("Derived init")
Derived() # Outputs: Base init\nLeft init\nRight init\nDerived init
super() in Derived calls Left.__init__, which chains to Right.__init__ and then Base.__init__, illustrating cooperative dispatch along the MRO [Derived, Left, Right, Base].[43]
Special methods, often called dunder methods (e.g., __add__, __eq__), enable operator overloading and follow single dispatch semantics, where the method is selected based on the type of the left operand. For instance, implementing __add__(self, other) in a class allows custom behavior for the + operator, such as adding two custom objects; if unsupported, Python attempts the reflected method __radd__ on the right operand. This provides duck-typed polymorphism for operators without multi-argument dispatch. An example is a simple vector class:
class Vector:
def __init__(self, x, y):
[self](/page/Self).x, [self](/page/Self).y = x, y
def __add__(self, other):
if isinstance(other, Vector):
return Vector([self](/page/Self).x + other.x, [self](/page/Self).y + other.y)
return NotImplemented
def __str__(self):
return f"Vector({[self](/page/Self).x}, {[self](/page/Self).y})"
v1 = Vector(1, 2)
v2 = Vector(3, 4)
print(v1 + v2) # Outputs: Vector(4, 6)
class Vector:
def __init__(self, x, y):
[self](/page/Self).x, [self](/page/Self).y = x, y
def __add__(self, other):
if isinstance(other, Vector):
return Vector([self](/page/Self).x + other.x, [self](/page/Self).y + other.y)
return NotImplemented
def __str__(self):
return f"Vector({[self](/page/Self).x}, {[self](/page/Self).y})"
v1 = Vector(1, 2)
v2 = Vector(3, 4)
print(v1 + v2) # Outputs: Vector(4, 6)
type as the default, allow customization of class creation, including alterations to dispatch mechanisms before instances are made. By subclassing type and overriding methods like __new__ or __prepare__, a metaclass can modify the class's namespace or attribute resolution at creation time. For example, a custom metaclass can inject dynamic dispatch logic into method lookups:
class DispatchMeta(type):
def __new__(cls, name, bases, namespace):
# Customize dispatch by adding a descriptor
class DynamicMethod:
def __get__(self, instance, owner):
if instance is None:
return self
return lambda *args, **kwargs: print(f"Dynamic dispatch for {name}")
namespace['dynamic_method'] = DynamicMethod()
return super().__new__(cls, name, bases, namespace)
class MyClass(metaclass=DispatchMeta):
pass
obj = MyClass()
obj.dynamic_method() # Outputs: Dynamic dispatch for MyClass
class DispatchMeta(type):
def __new__(cls, name, bases, namespace):
# Customize dispatch by adding a descriptor
class DynamicMethod:
def __get__(self, instance, owner):
if instance is None:
return self
return lambda *args, **kwargs: print(f"Dynamic dispatch for {name}")
namespace['dynamic_method'] = DynamicMethod()
return super().__new__(cls, name, bases, namespace)
class MyClass(metaclass=DispatchMeta):
pass
obj = MyClass()
obj.dynamic_method() # Outputs: Dynamic dispatch for MyClass
Rust
In Rust, dynamic dispatch is achieved primarily through trait objects, which enable runtime polymorphism while maintaining the language's emphasis on memory safety and zero-cost abstractions. A trait object is formed using thedyn keyword, such as Box<dyn Trait> for heap-allocated ownership or &dyn Trait for borrowing, allowing values of different types that implement the same trait to be treated uniformly at runtime.[46] These trait objects are implemented as fat pointers, consisting of a pointer to the data and a pointer to a virtual method table (vtable) that stores function pointers for the trait's methods.[46] This structure facilitates dynamic dispatch, where the specific method implementation is resolved at runtime by consulting the vtable, contrasting with compile-time monomorphization in static dispatch.[47]
The Rust compiler automatically generates vtables for traits used in dynamic dispatch, embedding them in the binary as static data structures containing pointers to the appropriate method implementations for each type.[47] Unlike class-based languages, Rust does not support multiple inheritance; instead, it promotes composition through traits, allowing types to implement multiple traits and enabling flexible, modular code without diamond inheritance problems.[48] For example, a trait Drawable might define a draw method, implemented by structs like Circle and Rectangle. A heterogeneous collection, such as Vec<Box<dyn Drawable>>, can then store instances of both, invoking draw via dynamic dispatch at runtime.[46]
trait Drawable {
fn draw(&self);
}
struct Circle;
impl Drawable for Circle {
fn draw(&self) {
println!("Drawing a circle");
}
}
struct Rectangle;
impl Drawable for Rectangle {
fn draw(&self) {
println!("Drawing a rectangle");
}
}
fn main() {
let mut shapes: Vec<Box<dyn Drawable>> = Vec::new();
shapes.push(Box::new(Circle));
shapes.push(Box::new(Rectangle));
for shape in shapes {
shape.draw(); // Dynamic dispatch via vtable
}
}
trait Drawable {
fn draw(&self);
}
struct Circle;
impl Drawable for Circle {
fn draw(&self) {
println!("Drawing a circle");
}
}
struct Rectangle;
impl Drawable for Rectangle {
fn draw(&self) {
println!("Drawing a rectangle");
}
}
fn main() {
let mut shapes: Vec<Box<dyn Drawable>> = Vec::new();
shapes.push(Box::new(Circle));
shapes.push(Box::new(Rectangle));
for shape in shapes {
shape.draw(); // Dynamic dispatch via vtable
}
}
dyn, it must be object-safe (also termed dyn-compatible), meaning it satisfies specific criteria to ensure method calls on trait objects are well-defined without knowledge of the concrete type at compile time. A trait is object-safe if it does not require Self: Sized and all its methods are object-safe: each method must lack generic type parameters, use a fixed receiver type (like &self or &mut self), and avoid returning Self or using Self in argument positions except as the receiver.[49] Violations, such as a method returning Self, prevent coercion to dyn and trigger compile-time errors; in such cases, alternatives like enums provide static dispatch with exhaustive pattern matching for type safety without runtime overhead.[49][46]
Advanced usage involves unsafe coercion to form trait objects from raw pointers, which is necessary for foreign function interfaces (FFI) or low-level memory management but carries significant risks. Using std::ptr::from_raw_parts or from_raw_parts_mut, a raw data pointer can be combined with a raw vtable pointer to construct a raw pointer to dyn Trait; this must then be safely converted to a reference or smart pointer.[50] Such operations are inherently unsafe, as they bypass Rust's borrow checker, requiring the programmer to ensure the pointers are valid, properly aligned, and respect lifetimes—the vtable's lifetime must outlive the data to prevent use-after-free errors.[50] Incorrect usage can lead to undefined behavior, emphasizing Rust's design philosophy of explicit unsafety for performance-critical code.
Smalltalk
In Smalltalk, dynamic dispatch is realized through a pure message-passing paradigm within a unified object model where everything is an object, including primitives, classes, and metaclasses. Methods are not invoked directly but are instead messages sent to a receiver object, which performs runtime lookup in the method dictionaries of its class and superclass chain to resolve the appropriate implementation. This late binding ensures that the specific method executed depends on the receiver's class at runtime, enabling polymorphism without explicit keywords like "virtual."[51][52] The dispatch process begins when a message selector (e.g.,#drawOn:) and arguments are sent to the receiver; if no matching method is found after traversing the inheritance hierarchy, Smalltalk raises a DoesNotUnderstand error by sending the doesNotUnderstand: message to the receiver, carrying a Message object with the selector and arguments. This mechanism supports meta-level extensions, such as dynamic method addition or proxying, allowing reflective interventions at runtime. Additionally, blocks—first-class objects representing closures with lexical scoping—facilitate deferred execution and are integral to control structures, capturing context via messages like value: or valueWithArguments:.[51][52]
A representative example illustrates polymorphism in a simple class hierarchy. Consider a base class Shape with subclasses Circle and Rectangle, where the #area message yields different computations:
Shape subclass: #Circle
instanceVariableNames: 'radius'
classVariableNames: ''
package: 'Shapes'.
Circle >> area
^ Float pi * radius squared.
Shape subclass: #Rectangle
instanceVariableNames: 'width height'
classVariableNames: ''
package: 'Shapes'.
Rectangle >> area
^ width * height.
Shape subclass: #Circle
instanceVariableNames: 'radius'
classVariableNames: ''
package: 'Shapes'.
Circle >> area
^ Float pi * radius squared.
Shape subclass: #Rectangle
instanceVariableNames: 'width height'
classVariableNames: ''
package: 'Shapes'.
Rectangle >> area
^ width * height.
#area to a Circle instance computes πr², while the same message to a Rectangle returns width × height, demonstrating runtime resolution without static type checks.[52]
Smalltalk employs single inheritance, with all classes descending from Object via the abstract root Behavior, which defines the protocol for class creation and method management. Mixin-like behavior is achieved through traits (in modern implementations like Pharo) or by composing subclasses and dynamically adding methods to classes at runtime using metaclasses—objects whose instances are classes themselves, enabling modifications such as class-side methods or instance variable additions without recompilation. The Metaclass hierarchy parallels the regular class hierarchy, supporting reflective operations like inspecting or altering method dictionaries.[51][52]
Smalltalk's emphasis on late binding and reflection has profoundly influenced modern languages, including Ruby and Python, by promoting dynamic, introspective designs that prioritize runtime flexibility and live programming environments over static declarations.[53]
Common Lisp
In Common Lisp, dynamic dispatch is implemented through the Common Lisp Object System (CLOS), which provides support for multiple dispatch on the classes or identities of all arguments to a generic function. A generic function serves as an extensible entry point for operations, where the specific behavior is determined at runtime by selecting and combining applicable methods based on argument types.[54] This approach decouples the definition of operations from specific classes, enabling flexible, multi-argument polymorphism.[55] Generic functions are defined using thedefgeneric macro, which specifies the function name, lambda list, and optional declarations or method combinations, without providing a body. Methods for a generic function are then added via the defmethod macro, where each method specializes one or more arguments on a class (using a class name as the specializer) or on the identity of an object (using (eql object)). This specialization enables multiple dispatch, as the system considers the combination of all argument specializers to determine applicability. For instance, methods can be defined to handle different pairs of argument classes, such as numeric types or user-defined classes, allowing the generic function to resolve to the most appropriate implementation dynamically.
The dispatch algorithm in CLOS proceeds in several steps to compute and execute an effective method. First, the generic function uses compute-applicable-methods to identify all methods whose specializers match the classes of the supplied arguments, producing a list of applicable methods. These methods are then sorted from most to least specific based on the class precedence lists of the argument classes. Finally, the sorted list is combined into an effective method using the generic function's method combination type, which by default is the standard method combination. This combination incorporates primary methods (the core implementations) along with optional :before, :after, and :around methods, enabling aspect-oriented programming-like behavior: :before methods run first (most specific to least) without returning values, followed by the primary method, then :after methods (least to most specific), with :around methods wrapping the entire sequence and allowing control over proceeding to the next method via call-next-method. If no applicable methods exist, an error is signaled.
To illustrate multiple dispatch resolution, consider a generic function add that extends arithmetic addition to include user-defined types, such as a simple vector class representing one-dimensional vectors:
(defclass vector ()
((components :initarg :components :reader components)))
(defgeneric add (x y))
(defmethod add ((x number) (y number))
(+ x y))
(defmethod add ((x vector) (y vector))
(make-instance 'vector
:components (mapcar #'+ (components x) (components y))))
(defmethod add ((x number) (y vector))
(make-instance 'vector
:components (mapcar (lambda (c) (+ x c)) (components y))))
(defmethod add ((x vector) (y number))
(add y x)) ; Leverage symmetry
(defclass vector ()
((components :initarg :components :reader components)))
(defgeneric add (x y))
(defmethod add ((x number) (y number))
(+ x y))
(defmethod add ((x vector) (y vector))
(make-instance 'vector
:components (mapcar #'+ (components x) (components y))))
(defmethod add ((x number) (y vector))
(make-instance 'vector
:components (mapcar (lambda (c) (+ x c)) (components y))))
(defmethod add ((x vector) (y number))
(add y x)) ; Leverage symmetry
(add 5 (make-instance 'vector :components '(1 2 3))) dispatches to the number-vector method, producing a vector (6 7 8), while (add (make-instance 'vector :components '(1 2)) (make-instance 'vector :components '(3 4))) uses the vector-vector method to yield (4 6). This demonstrates how dispatch resolves based on the combined argument classes.[19][56]
CLOS supports metaprogramming through its metaobject protocol (MOP), where classes, generic functions, and methods are themselves instances of metaclasses, allowing programmatic inspection and modification.[55] The generic function compute-applicable-methods can be specialized or extended to implement custom dispatch logic, such as dispatching on predicates beyond classes or integrating domain-specific applicability rules. For example, users can define a subclass of standard-generic-function and override MOP methods to alter how applicable methods are computed, enabling tailored dispatch without altering the core system.[54]
Integration with Common Lisp's macro system allows developers to choose between compile-time and runtime dispatch for performance-critical code. While CLOS dispatch is inherently dynamic and occurs at runtime, macros can analyze argument types at compile time (using tools like cl-environments for environment access) to generate specialized inline code or select methods early, bypassing full generic function invocation. Conversely, the compile-all-dispatch-code macro in some implementations precompiles dispatch tables for known generic functions, optimizing runtime resolution while preserving CLOS's extensibility for cases where types are unknown until execution.[57] This hybrid approach leverages Lisp's homoiconicity to blend static optimizations with dynamic flexibility.[58]