In
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s and
type theory
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a fou ...
, parametric polymorphism allows a single piece of code to be given a "generic" type, using variables in place of actual types, and then instantiated with particular types as needed.
Parametrically polymorphic functions and data types are sometimes called generic functions and generic datatypes, respectively, and they form the basis of
generic programming
Generic programming is a style of computer programming in which algorithms are written in terms of types ''to-be-specified-later'' that are then ''instantiated'' when needed for specific types provided as parameters. This approach, pioneered b ...
.
Parametric polymorphism may be contrasted with
ad hoc polymorphism
In programming languages, ad hoc polymorphismC. StracheyFundamental concepts in programming languages Lecture notes for International Summer School in Computer Programming, Copenhagen, August 1967 is a kind of polymorphism in which polymorphic f ...
. Parametrically polymorphic definitions are ''uniform'': they behave identically regardless of the type they are instantiated at.
In contrast, ad hoc polymorphic definitions are given a distinct definition for each type. Thus, ad hoc polymorphism can generally only support a limited number of such distinct types, since a separate implementation has to be provided for each type.
Basic definition
It is possible to write functions that do not depend on the types of their arguments. For example, the
identity function
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
simply returns its argument unmodified. This naturally gives rise to a family of potential types, such as
,
,
, and so on. Parametric polymorphism allows
to be given a single,
most general type by introducing a
universally quantified
In mathematical logic, a universal quantification is a type of quantifier, a logical constant which is interpreted as "given any" or "for all". It expresses that a predicate can be satisfied by every member of a domain of discourse. In other ...
type variable In type theory and programming languages, a type variable is a mathematical variable ranging over types. Even in programming languages that allow mutable variables, a type variable remains an abstraction, in the sense that it does not correspond t ...
:
:
The polymorphic definition can then be ''instantiated'' by substituting any concrete type for
, yielding the full family of potential types.
The identity function is a particularly extreme example, but many other functions also benefit from parametric polymorphism. For example, an
function that
append
In computer programming, append is the operation for concatenating linked lists or arrays in some high-level programming languages.
Lisp
Append originates in the Lisp programming language. The append procedure takes zero or more (linked) lists a ...
s two
lists does not inspect the elements of the list, only the list structure itself. Therefore,
can be given a similar family of types, such as
,
, and so on, where