In
programming language theory
Programming language theory (PLT) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of formal languages known as programming languages. Programming language theory is clos ...
and
type theory, polymorphism is the provision of a single
interface
Interface or interfacing may refer to:
Academic journals
* ''Interface'' (journal), by the Electrochemical Society
* '' Interface, Journal of Applied Linguistics'', now merged with ''ITL International Journal of Applied Linguistics''
* '' Int ...
to entities of different
types or the use of a single symbol to represent multiple different types.
[: "Polymorphic types are types whose operations are applicable to values of more than one type."] The concept is borrowed from a principle in biology where an organism or species can have many different forms or stages.
The most commonly recognized major classes of polymorphism are:
* ''
Ad hoc polymorphism'': defines a common interface for an arbitrary set of individually specified types.
* ''
Parametric polymorphism'': not specifying concrete types and instead use abstract symbols that can substitute for any type.
* ''
Subtyping'' (also called ''subtype polymorphism'' or ''inclusion polymorphism''): when a name denotes instances of many different classes related by some common superclass.
History
Interest in polymorphic
type systems developed significantly in the 1960s, with practical implementations beginning to appear by the end of the decade. ''Ad hoc polymorphism'' and ''parametric polymorphism'' were originally described in
Christopher Strachey
Christopher S. Strachey (; 16 November 1916 – 18 May 1975) was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design and computer time-sharing.F. J. Corbató, et al., T ...
's ''
Fundamental Concepts in Programming Languages
''Fundamental Concepts in Programming Languages'' were an influential set of lecture notes written by Christopher Strachey for the International Summer School in Computer Programming at Copenhagen in August, 1967. It introduced much programming l ...
'',
where they are listed as "the two main classes" of polymorphism. Ad hoc polymorphism was a feature of
Algol 68
ALGOL 68 (short for ''Algorithmic Language 1968'') is an imperative programming language that was conceived as a successor to the ALGOL 60 programming language, designed with the goal of a much wider scope of application and more rigorously de ...
, while parametric polymorphism was the core feature of
ML's type system.
In a 1985 paper,
Peter Wegner and
Luca Cardelli
Luca Andrea Cardelli, Fellow of the Royal Society (FRS), is an Italian computer scientist who is a research professor at the University of Oxford in Oxford, UK. Cardelli is well known for his research in type theory and operational semantics. A ...
introduced the term ''inclusion polymorphism'' to model subtypes and
inheritance
Inheritance is the practice of receiving private property, titles, debts, entitlements, privileges, rights, and obligations upon the death of an individual. The rules of inheritance differ among societies and have changed over time. Officiall ...
,
citing
Simula as the first programming language to implement it.
Types
Ad hoc polymorphism
Christopher Strachey
Christopher S. Strachey (; 16 November 1916 – 18 May 1975) was a British computer scientist. He was one of the founders of denotational semantics, and a pioneer in programming language design and computer time-sharing.F. J. Corbató, et al., T ...
chose the term ''ad hoc polymorphism'' to refer to polymorphic functions that can be applied to arguments of different types, but that behave differently depending on the type of the argument to which they are applied (also known as
function overloading or
operator overloading
In computer programming, operator overloading, sometimes termed ''operator ad hoc polymorphism'', is a specific case of polymorphism, where different operators have different implementations depending on their arguments. Operator overloading i ...
).
[ The term "]ad hoc
Ad hoc is a Latin phrase meaning literally 'to this'. In English, it typically signifies a solution for a specific purpose, problem, or task rather than a generalized solution adaptable to collateral instances. (Compare with ''a priori''.)
Com ...
" in this context is not intended to be pejorative; it refers simply to the fact that this type of polymorphism is not a fundamental feature of the type system. In the Pascal
Pascal, Pascal's or PASCAL may refer to:
People and fictional characters
* Pascal (given name), including a list of people with the name
* Pascal (surname), including a list of people and fictional characters with the name
** Blaise Pascal, Frenc ...
/ Delphi example below, the Add
functions seem to work generically over various types when looking at the invocations, but are considered to be two entirely distinct functions by the compiler for all intents and purposes:
program Adhoc;
function Add(x, y : Integer) : Integer;
begin
Add := x + y
end;
function Add(s, t : String) : String;
begin
Add := Concat(s, t)
end;
begin
Writeln(Add(1, 2)); (* Prints "3" *)
Writeln(Add('Hello, ', 'Mammals!')); (* Prints "Hello, Mammals!" *)
end.
In dynamically typed languages the situation can be more complex as the correct function that needs to be invoked might only be determinable at run time.
Implicit type conversion has also been defined as a form of polymorphism, referred to as "coercion polymorphism".
Parametric polymorphism
''Parametric polymorphism'' allows a function or a data type to be written generically, so that it can handle values ''uniformly'' without depending on their type. Parametric polymorphism is a way to make a language more expressive while still maintaining full static type-safety.
The concept of parametric polymorphism applies to both data types and function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
s. A function that can evaluate to or be applied to values of different types is known as a ''polymorphic function.'' A data type that can appear to be of a generalized type (e.g. a list
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby union ...
with elements of arbitrary type) is designated ''polymorphic data type'' like the generalized type from which such specializations are made.
Parametric polymorphism is ubiquitous in functional programming, where it is often simply referred to as "polymorphism". The following example in Haskell shows a parameterized list data type and two parametrically polymorphic functions on them:
data List a = Nil , Cons a (List a)
length :: List a -> Integer
length Nil = 0
length (Cons x xs) = 1 + length xs
map :: (a -> b) -> List a -> List b
map f Nil = Nil
map f (Cons x xs) = Cons (f x) (map f xs)
Parametric polymorphism is also available in several object-oriented languages. For instance, templates in C++ and D, or under the name generics
Generic or generics may refer to:
In business
* Generic term, a common name used for a range or class of similar things not protected by trademark
* Generic brand, a brand for a product that does not have an associated brand or trademark, other ...
in C#, Delphi, Java and Go:
class List
List map(Func f, List xs)
John C. Reynolds
John Charles Reynolds (June 1, 1935 – April 28, 2013) was an American computer scientist.
Education and affiliations
John Reynolds studied at Purdue University and then earned a Doctor of Philosophy (Ph.D.) in theoretical physics from Harvard U ...
(and later Jean-Yves Girard) formally developed this notion of polymorphism as an extension to lambda calculus (called the polymorphic lambda calculus or System F). Any parametrically polymorphic function is necessarily restricted in what it can do, working on the shape of the data instead of its value, leading to the concept of parametricity.
Subtyping
Some languages employ the idea of ''subtyping'' (also called ''subtype polymorphism'' or ''inclusion polymorphism'') to restrict the range of types that can be used in a particular case of polymorphism. In these languages, subtyping allows a function to be written to take an object of a certain type ''T'', but also work correctly, if passed an object that belongs to a type ''S'' that is a subtype of ''T'' (according to the Liskov substitution principle
The Liskov substitution principle (LSP) is a particular definition of a subtyping relation, called strong behavioral subtyping, that was initially introduced by Barbara Liskov in a 1988 conference keynote address titled ''Data abstraction and h ...
). This type relation is sometimes written ''S'' <: ''T''. Conversely, ''T'' is said to be a ''supertype'' of ''S''—written ''T'' :> ''S''. Subtype polymorphism is usually resolved dynamically (see below).
In the following Java example we make cats and dogs subtypes of animals. The procedure letsHear()
accepts an animal, but will also work correctly if a subtype is passed to it:
abstract class Animal
class Cat extends Animal
class Dog extends Animal
static void letsHear(final Animal a)
static void main(String[] args)
In another example, if ''Number'', ''Rational'', and ''Integer'' are types such that ''Number'' :> ''Rational'' and ''Number'' :> ''Integer'', a function written to take a ''Number'' will work equally well when passed an ''Integer'' or ''Rational'' as when passed a ''Number''. The actual type of the object can be hidden from clients into a black box
In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings. Its implementation is "opaque" (black). The te ...
, and accessed via object identity
Identity may refer to:
* Identity document
* Identity (philosophy)
* Identity (social science)
* Identity (mathematics)
Arts and entertainment Film and television
* ''Identity'' (1987 film), an Iranian film
* ''Identity'' (2003 film), an ...
.
In fact, if the ''Number'' type is ''abstract'', it may not even be possible to get your hands on an object whose ''most-derived'' type is ''Number'' (see abstract data type
In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behavior (semantics) from the point of view of a '' user'', of the data, specifically in terms of possible values, po ...
, abstract class
In programming languages, an abstract type is a type in a nominative type system that cannot be instantiated directly; a type that is not abstract – which ''can'' be instantiated – is called a ''concrete type''. Every instance of an abstra ...
). This particular kind of type hierarchy is known—especially in the context of the Scheme programming language
Scheme is a dialect of the Lisp family of programming languages. Scheme was created during the 1970s at the MIT AI Lab and released by its developers, Guy L. Steele and Gerald Jay Sussman, via a series of memos now known as the Lambda Papers. ...
—as a '' numerical tower'', and usually contains many more types.
Object-oriented programming language
Object-oriented programming (OOP) is a programming paradigm based on the concept of " objects", which can contain data and code. The data is in the form of fields (often known as attributes or ''properties''), and the code is in the form of ...
s offer subtype polymorphism using '' subclassing'' (also known as ''inheritance
Inheritance is the practice of receiving private property, titles, debts, entitlements, privileges, rights, and obligations upon the death of an individual. The rules of inheritance differ among societies and have changed over time. Officiall ...
''). In typical implementations, each class contains what is called a '' virtual table''—a table of functions that implement the polymorphic part of the class interface—and each object contains a pointer to the "vtable" of its class, which is then consulted whenever a polymorphic method is called. This mechanism is an example of:
* '' late binding'', because virtual function calls are not bound until the time of invocation;
* ''single dispatch
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-orient ...
'' (i.e. single-argument polymorphism), because virtual function calls are bound simply by looking through the vtable provided by the first argument (the this
object), so the runtime types of the other arguments are completely irrelevant.
The same goes for most other popular object systems. Some, however, such as Common Lisp Object System
The Common Lisp Object System (CLOS) is the facility for object-oriented programming which is part of ANSI Common Lisp. CLOS is a powerful dynamic object system which differs radically from the OOP facilities found in more static languages suc ...
, provide ''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 o ...
'', under which method calls are polymorphic in ''all'' arguments.
The interaction between parametric polymorphism and subtyping leads to the concepts of variance and bounded quantification
In type theory, bounded quantification (also bounded polymorphism or constrained genericity) refers to universal or existential quantifiers which are restricted ("bounded") to range only over the subtypes of a particular type. Bounded quantificat ...
.
Row polymorphism
Row polymorphism is a similar, but distinct concept from subtyping. It deals with structural types. It allows the usage of all values whose types have certain properties, without losing the remaining type information.
Polytypism
A related concept is ''polytypism'' (or ''data type genericity''). A polytypic function is more general than polymorphic, and in such a function, "though one can provide fixed ad hoc cases for specific data types, an ad hoc combinator is absent".
Implementation aspects
Static and dynamic polymorphism
Polymorphism can be distinguished by when the implementation is selected: statically (at compile time) or dynamically (at run time, typically via a virtual function
In object-oriented programming, in languages such as C++, and Object Pascal, a virtual function or virtual method is an inheritable and overridable function or method for which dynamic dispatch is facilitated. This concept is an important par ...
). This is known respectively as ''static dispatch
In computing, static dispatch is a form of polymorphism fully resolved during compile time. It is a form of ''method dispatch,'' which describes how a language or environment will select which implementation of a method or function to use.
E ...
'' and '' dynamic dispatch,'' and the corresponding forms of polymorphism are accordingly called ''static polymorphism'' and ''dynamic polymorphism''.
Static polymorphism executes faster, because there is no dynamic dispatch overhead, but requires additional compiler support. Further, static polymorphism allows greater static analysis by compilers (notably for optimization), source code analysis tools, and human readers (programmers). Dynamic polymorphism is more flexible but slower—for example, dynamic polymorphism allows duck typing, and a dynamically linked library may operate on objects without knowing their full type.
Static polymorphism typically occurs in ad hoc polymorphism and parametric polymorphism, whereas dynamic polymorphism is usual for subtype polymorphism. However, it is possible to achieve static polymorphism with subtyping through more sophisticated use of template metaprogramming
Template metaprogramming (TMP) is a metaprogramming technique in which templates are used by a compiler to generate temporary source code, which is merged by the compiler with the rest of the source code and then compiled. The output of these t ...
, namely the curiously recurring template pattern.
When polymorphism is exposed via a library, static polymorphism becomes impossible for dynamic libraries as there is no way of knowing what types the parameters are when the shared object
In computer science, a library is a collection of non-volatile resources used by computer programs, often for software development. These may include configuration data, documentation, help data, message templates, pre-written code and subro ...
is built. While languages like C++ and Rust use monomorphized templates, the Swift programming language
Swift is a general-purpose, multi-paradigm, compiled programming language developed by Apple Inc. and the open-source community. First released in 2014, Swift was developed as a replacement for Apple's earlier programming language Objectiv ...
makes extensive use of dynamic dispatch to build the application binary interface
In computer software, an application binary interface (ABI) is an interface between two binary program modules. Often, one of these modules is a library or operating system facility, and the other is a program that is being run by a user.
An ' ...
for these libraries by default. As a result, more code can be shared for a reduced system size at the cost of runtime overhead.
See also
* Duck typing for polymorphism without (static) types
* Polymorphic code (computer virus terminology)
* System F for a lambda calculus with parametric polymorphism.
* Type class
* Type theory
* Virtual inheritance
Virtual inheritance is a C++ technique that ensures only one copy of a base classs member variables are inherited by grandchild derived classes. Without virtual inheritance, if two classes B and C inherit from a class A, and a class D inherits ...
References
External links
C++ examples of polymorphism
Objects and Polymorphism (Visual Prolog)
Polymorphism on MSDN
{{DEFAULTSORT:Polymorphism
Articles with example C Sharp code
Articles with example Haskell code
Articles with example Java code
Articles with example Pascal code
Data types
Functional programming
Object-oriented programming
Programming language concepts
Type theory
Generic programming