Parametricity

In programming language theory, parametricity is an abstract uniformity property enjoyed by parametrically polymorphic functions, which captures the intuition that all instances of a polymorphic function act the same way.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In programming language theory, parametricity is an abstract uniformity property enjoyed by parametrically polymorphic functions, which captures the intuition that all instances of a polymorphic function act the same way. Consider this example, based on a set X and the type T(X) = [X → X] of functions from X to itself.

The higher-order function twice X : T(X) → T(X) given by twice X (f) = f ∘ f, is intuitively independent of the set X. The family of all such functions twice X , parametrized by sets X, is called a "parametrically polymorphic function". We simply write twice for the entire family of these functions and write its type as \forall X. T(X) → T(X). The individual functions twice X are called the components or instances of the polymorphic function.

Notice that all the component functions twice X act "the same way" because they are given by the same rule. Other families of functions obtained by picking one arbitrary function from each T(X) → T(X) would not have such uniformity. They are called "ad hoc polymorphic functions".

Parametricity is the abstract property enjoyed by the uniformly acting families such as twice, which distinguishes them from ad hoc families. With an adequate formalization of parametricity, it is possible to prove that the parametrically polymorphic functions of type \forall X. T(X) → T(X) are one-to-one with natural numbers.

The function corresponding to the natural number n is given by the rule f \mapsto f n , i.e., the polymorphic Church numeral for n. In contrast, the collection of all ad hoc families would be too large to be a set.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1305144130 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.