In programming languages and type theory, parametric polymorphism is a way to make a language more expressive, while still maintaining full static type-safety. Using parametric polymorphism, a function or a data type can be written generically so that it can handle values identically without depending on their type.[1] Such functions and data types are called generic functions and generic datatypes respectively and form the basis of generic programming.
For example, a function append that joins two lists can be constructed so that it does not care about the type of elements: it can append lists of integers, lists of real numbers, lists of strings, and so on. Let the type variable a denote the type of elements in the lists. Then append can be typed
forall a. [a] × [a] -> [a]
where [a] denotes the type of lists with elements of type a. We say that the type of append 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 append is applied, a value is decided for a.
Following Christopher Strachey,[2] 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.
History
Parametric polymorphism was first introduced to programming languages in ML in 1975.[3] Today it exists in Standard ML, OCaml, F#, Ada, Haskell, Mercury, Visual Prolog, Scala, Julia, Python, TypeScript, C++ and others. Java, C#, Visual Basic .NET and 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
Rank-1 (predicative) polymorphism
This section needs additional citations for verification. (February 2019) |
In a predicative type system (also known as a prenex polymorphic system), type variables may not be instantiated with polymorphic types.[4]: 359–360 Predicative type theories include Martin-Löf type theory and NuPRL. This is very similar to what is called "ML-style" or "Let-polymorphism" (technically ML's Let-polymorphism has a few other syntactic restrictions).
This restriction makes the distinction between polymorphic and non-polymorphic types very important; thus in predicative systems polymorphic types are sometimes referred to as type schemas to distinguish them from ordinary (monomorphic) types, which are sometimes called monotypes. A consequence is that all types can be written in a form that places all quantifiers at the outermost (prenex) position.
For example, consider the append function described above, which has type
forall a. [a] × [a] -> [a]
In order to apply this function to a pair of lists, a type must be substituted for the variable a in the type of the function such that the type of the arguments matches up with the resulting function type. In an impredicative system, the type being substituted may be any type whatsoever, including a type that is itself polymorphic; thus append can be applied to pairs of lists with elements of any type—even to lists of polymorphic functions such as append itself.
Polymorphism in the language ML is predicative.[citation needed] This is because predicativity, together with other restrictions, makes the type system simple enough that full type inference is always possible.
As a practical example, OCaml (a descendant or dialect of ML) performs type inference and supports impredicative polymorphism, but in some cases when impredicative polymorphism is used, the system's type inference is incomplete unless some explicit type annotations are provided by the programmer.
Higher-rank polymorphism
Some type systems support an impredicative function type constructor even though other type constructors remain predicative. For example, the type is permitted in a system that supports higher-rank polymorphism, even though may not be.[5]
![{\displaystyle [\forall \alpha .\alpha \rightarrow \alpha ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c90e9eda4c5e4b9196d2d3311ca6b8f7fcb5241)
A type is said to be of rank k (for some fixed integer k) if no path from its root to a quantifier passes to the left of k or more arrows, when the type is drawn as a tree.[4]: 359 A type system is said to support rank-k polymorphism if it admits types with rank less than or equal to k. For example, a type system that supports rank-2 polymorphism would allow but not . A type system that admits types of arbitrary rank is said to be "rank-n polymorphic".
Type inference for rank-2 polymorphism is decidable, but for rank-3 and above, it is not.[6][4]: 359
Impredicative polymorphism
Impredicative polymorphism (also called first-class polymorphism) is the most powerful form of parametric polymorphism.[4]: 340 In formal logic, a definition is said to be impredicative if it is self-referential; in type theory, it refers to the ability for a type to be in the ___domain of a quantifier it contains. This allows the instantiation of any type variable with any type, including polymorphic types. An example of a system supporting full impredicativity is System F, which allows instantiating at any type, including itself.
In type theory, the most frequently studied impredicative typed λ-calculi are based on those of the lambda cube, especially System F.
Bounded parametric polymorphism
In 1985, Luca Cardelli and Peter Wegner recognized the advantages of allowing bounds on the type parameters.[7] Many operations require some knowledge of the data types, but can otherwise work parametrically. For example, to check whether an item is included in a list, we need to compare the items for equality. In Standard ML, type parameters of the form ’’a are restricted so that the equality operation is available, thus the function would have the type ’’a × ’’a list → bool and ’’a can only be a type with defined equality. In Haskell, bounding is achieved by requiring types to belong to a type class; thus the same function has the type in Haskell. In most object-oriented programming languages that support parametric polymorphism, parameters can be constrained to be subtypes of a given type (see Subtype polymorphism and the article on Generic programming).
![{\textstyle \mathrm {Eq} \,\alpha \,\Rightarrow \alpha \,\rightarrow \left[\alpha \right]\rightarrow \mathrm {Bool} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c71d9c77a957c312767e7af5eccb082c66a3892)
See also
Notes
- ^ Pierce 2002.
- ^ Strachey 1967.
- ^ 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)
- ^ a b c d Benjamin C. Pierce; Benjamin C. (Professor Pierce, University of Pennsylvania) (2002). Types and Programming Languages. MIT Press. ISBN 978-0-262-16209-8.
- ^ Kwang Yul Seo. "Kwang's Haskell Blog - Higher rank polymorphism". kseo.github.io. Retrieved 30 September 2022.
- ^ Kfoury, A. J.; Wells, J. B. (1 January 1999). "Principality and decidable type inference for finite-rank intersection types". Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. Association for Computing Machinery: 161–174. doi:10.1145/292540.292556.
- ^ Cardelli & Wegner 1985.
References
- Strachey, Christopher (1967), Fundamental Concepts in Programming Languages (Lecture notes), Copenhagen: International Summer School in Computer Programming. Republished in: Strachey, Christopher (2000). Higher-Order and Symbolic Computation. 13: 11–49. doi:10.1023/A:1010000313106. S2CID 14124601.
{{cite journal}}: Missing or empty|title=(help) - Hindley, J. Roger (1969), "The principal type scheme of an object in combinatory logic", Transactions of the American Mathematical Society, 146: 29–60, doi:10.2307/1995158, JSTOR 1995158, MR 0253905.
- Girard, Jean-Yves (1971). "Une Extension de l'Interpretation de Gödel à l'Analyse, et son Application à l'Élimination des Coupures dans l'Analyse et la Théorie des Types". Proceedings of the Second Scandinavian Logic Symposium. Studies in Logic and the Foundations of Mathematics (in French). Vol. 63. Amsterdam. pp. 63–92. doi:10.1016/S0049-237X(08)70843-7. ISBN 9780720422597.
- Girard, Jean-Yves (1972), Interprétation fonctionnelle et élimination des coupures de l'arithmétique d'ordre supérieur (Ph.D. thesis) (in French), Université Paris 7.
- Reynolds, John C. (1974), "Towards a Theory of Type Structure", Colloque Sur la Programmation, Lecture Notes in Computer Science, 19, Paris: 408–425, doi:10.1007/3-540-06859-7_148, ISBN 978-3-540-06859-4.
- Milner, Robin (1978). "A Theory of Type Polymorphism in Programming" (PDF). Journal of Computer and System Sciences. 17 (3): 348–375. doi:10.1016/0022-0000(78)90014-4. S2CID 388583.
- Cardelli, Luca; Wegner, Peter (December 1985). "On Understanding Types, Data Abstraction, and Polymorphism" (PDF). ACM Computing Surveys. 17 (4): 471–523. CiteSeerX 10.1.1.117.695. doi:10.1145/6041.6042. ISSN 0360-0300. S2CID 2921816.
- Pierce, Benjamin C. (2002). Types and Programming Languages. MIT Press. ISBN 978-0-262-16209-8.