Parametric polymorphism: Difference between revisions

Revision as of 22:43, 30 September 2022

Revision as of 00:08, 1 October 2022

Line 1:

{{Short description|Basis of generic programming}}

{{polymorphism}}

In [[programming language]]s and [[type theory]], '''parametric polymorphism''' isallows a waysingle topiece makeof acode languageto morebe expressive,given whilea still"generic" maintaining full static [[type-safety]]. Using parametric [[polymorphism (computer science)|polymorphism]], ausing functionvariables orin aplace dataof typeactual cantypes, beand writtenthen genericallyinstantiated sowith thatparticular ittypes canas handleneeded.<ref valuesname="TAPL" ''identically'' without depending on their type./>{{sfn|Piercerp|2002340}} SuchParametrically polymorphic functions and data types are sometimes called '''generic functions''' and '''generic datatypes''', respectively, and they form the basis of [[generic programming]].

Following [[Christopher Strachey]],{{sfn|Strachey|1967}} parametricParametric polymorphism may be contrasted with [[ad hoc polymorphism]],. inParametrically whichpolymorphic adefinitions singleare polymorphic''uniform'': functionthey canbehave haveidentically a numberregardless of distinctthe andtype potentiallythey heterogeneousare implementationsinstantiated dependingat.<ref onname="TAPL" the/>{{rp|340}}<ref typename="Strachey of1967" argument(s)/>{{rp|37}} toIn whichcontrast, itad ishoc appliedpolymorphic 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.

For example, a function <code>append</code> that joins two lists can be constructed so that it does not care about the type of elements: it can append lists of [[integer]]s, lists of [[real number]]s, lists of [[string (computer science)|string]]s, and so on. Let the ''type variable a'' denote the type of elements in the lists. Then <code>append</code> can be typed

:<code>forall a. [a] &times; [a] -> [a]</code>

where <code>[a]</code> denotes the type of lists with elements of type ''a''. We say that the type of <code>append</code> is ''parameterized by a'' for all values of ''a''. (Note that since there is only one type variable, the function cannot be applied to just any pair of lists: the pair, as well as the result list, must consist of the same type of elements) For each place where <code>append</code> is applied, a value is decided for ''a''.

== Basic definition ==

Following [[Christopher Strachey]],{{sfn|Strachey|1967}} parametric polymorphism may be contrasted with [[ad hoc polymorphism]], in which a single polymorphic function can have a number of distinct and potentially heterogeneous implementations depending on the type of argument(s) to which it is applied. 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.

It is possible to write functions that do not depend on the types of their arguments. For example, the [[identity function]] <math>\mathsf{id}(x) = x</math> simply returns its argument unmodified. This naturally gives rise to a family of potential types, such as <math>\mathsf{Int} \to \mathsf{Int}</math>, <math>\mathsf{Bool} \to \mathsf{Bool}</math>, <math>\mathsf{String} \to \mathsf{String}</math>, and so on. Parametric polymorphism allows <math>\mathsf{id}</math> to be given a single, [[most general unifier|most general]] type by introducing a [[universal quantification|universally quantified]] [[type variable]]:

:<math>\mathsf{id} : \forall \alpha. \alpha \to \alpha</math>

The polymorphic definition can then be ''instantiated'' by substituting any concrete type for <math>\alpha</math>, yielding the full family of potential types.<ref>{{cite web |last1=Yorgey |first1=Brent |title=More polymorphism and type classes |url=https://www.seas.upenn.edu/~cis1940/spring13/lectures/05-type-classes.html |website=www.seas.upenn.edu |access-date=1 October 2022}}</ref>

The identity function is a particularly extreme example, but many other functions also benefit from parametric polymorphism. For example, an <math>\mathsf{append}</math> function that [[append]]s two [[linked list|lists]] does not inspect the elements of the list, only the list structure itself. Therefore, <math>\mathsf{append}</math> can be given a similar family of types, such as <math>[\mathsf{Int}], [\mathsf{Int}] \to [\mathsf{Int}]</math>, <math>[\mathsf{Bool}], [\mathsf{Bool}] \to [\mathsf{Bool}]</math>, and so on, where <math>[T]</math> denotes a list of elements of type <math>T</math>. The most general type is therefore

:<math>\mathsf{append} : \forall \alpha. [\alpha], [\alpha] \to [\alpha]</math>

which can be instantiated to any type in the family.

Parametrically polymorphic functions like <math>\mathsf{id}</math> and <math>\mathsf{append}</math> are said to be ''parameterized over'' an arbitrary type <math>\alpha</math>.<ref>{{cite web |last1=Wu |first1=Brandon |title=Parametric Polymorphism - SML Help |url=https://smlhelp.github.io/book/concepts/poly.html |website=smlhelp.github.io |access-date=1 October 2022}}</ref> Both <math>\mathsf{id}</math> and <math>\mathsf{append}</math> are parameterized over a single type, but functions may be parameterized over arbitrarily many types. For example, the <math>\mathsf{fst}</math> and <math>\mathsf{snd}</math> functions that return the first and second elements of a [[product type|pair]], respectively, can be given the following types:

:<math>

\begin{aligned}

\mathsf{fst} & : \forall \alpha. \forall \beta. (\alpha, \beta) \to \alpha \\

\mathsf{snd} & : \forall \alpha. \forall \beta. (\alpha, \beta) \to \beta

\end{aligned}

</math>

In the expression <math>\mathsf{fst}((3, \mathsf{true}))</math>, <math>\alpha</math> is instantiated to <math>\mathsf{Int}</math> and <math>\beta</math> is instantiated to <math>\mathsf{Bool}</math> in the call to <math>\mathsf{fst}</math>, so the type of the overall expression is <math>\mathsf{Int}</math>.

The [[syntax (programming languages)|syntax]] used to introduce parametric polymorphism varies significantly between programming languages. For example, in some programming languages, such as [[Haskell]], the <math>\forall \alpha</math> [[quantifier (logic)|quantifier]] is implicit and may be omitted.<ref>{{cite web |title=Haskell 2010 Language Report § 4.1.2 Syntax of Types |url=https://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-650004.1.2 |website=www.haskell.org |access-date=1 October 2022 |quote=With one exception (that of the distinguished type variable in a class declaration (Section 4.3.1)), the type variables in a Haskell type expression are all assumed to be universally quantified; there is no explicit syntax for universal quantification.}}</ref> Other languages require types to be instantiated explicitly at some or all of a parametrically polymorphic function's [[call site]]s.

== History ==

Parametric polymorphism was first introduced to programming languages in [[ML programming language|ML]] in 1975.<ref>Milner, R., Morris, L., Newey, M. "A Logic for Computable Functions with reflexive and polymorphic types", ''Proc. Conference on Proving and Improving Programs'', Arc-et-Senans (1975)</ref> Today it exists in [[Standard ML]], [[OCaml]], [[F Sharp (programming language)|F#]], [[Ada (programming language)|Ada]], [[Haskell (programming language)|Haskell]], [[Mercury (programming language)|Mercury]], [[Visual Prolog]], [[Scala (programming language)|Scala]], [[Julia (programming language)|Julia]], [[Python (programming language)|Python]], [[TypeScript]], [[C++]] and others. [[Java (programming language)|Java]], [[C Sharp (programming language)|C#]], [[Visual Basic .NET]] and [[Object Pascal|Delphi]] have each introduced "generics" for parametric polymorphism. Some implementations of type polymorphism are superficially similar to parametric polymorphism while also introducing ad hoc aspects. One example is [[C++]] [[template specialization]].

The most general form of polymorphism is "higher-rank [[impredicative]] polymorphism". Two popular restrictions of this form are restricted rank polymorphism (for example, rank-1 or ''prenex'' polymorphism) and predicative polymorphism. Together, these restrictions give "predicative prenex polymorphism", which is essentially the form of polymorphism found in ML and early versions of Haskell.

== Predicativity, impredicativity, and higher-rank polymorphism ==

Line 50 ⟶ 71:

== Notes ==

{{reflist|2}}|refs=

*<ref name="Strachey 1967">{{citation|first=Christopher|last=Strachey|author-link=Christopher Strachey|year=1967|title=Fundamental Concepts in Programming Languages|type=Lecture notes|publisher=International Summer School in Computer Programming|___location=Copenhagen|title-link=Fundamental Concepts in Programming Languages}}. Republished in: {{cite journal |last1=Strachey |first1=Christopher |title=Fundamental Concepts in Programming Languages |journal=[[Higher-Order and Symbolic Computation]] |date=1 April 2000 |volume=13 |pagesissue=11–491 |yearpages=200011–49 |doi=10.1023/A:1010000313106 |last1url=Stracheyhttps://doi.org/10.1023/A:1010000313106 |first1language=Christopheren |s2cidissn=14124601 1573-0557}}</ref>

}}

== References ==

*

* {{citation|first=Christopher|last=Strachey|author-link=Christopher Strachey|year=1967|title=Fundamental Concepts in Programming Languages|type=Lecture notes|publisher=International Summer School in Computer Programming|___location=Copenhagen|title-link=Fundamental Concepts in Programming Languages}}. Republished in: {{cite journal|journal=[[Higher-Order and Symbolic Computation]]|volume=13|pages=11–49|year=2000|doi=10.1023/A:1010000313106|last1=Strachey|first1=Christopher|s2cid=14124601 }}

* {{citation

| last = Hindley | first = J. Roger