Parametricity
From Wikipedia, the free encyclopedia
In the theory of programming languages in computer science, parametricity is a theoretical result that states that functions that have types that are related to each other share certain properties in common.
Contents |
[edit] Theory of parametricity
 |
Please help improve this section by expanding it. Further information might be found on the talk page or at requests for expansion. |
The parametricity theorem was originally stated by John C. Reynolds, who called it the abstraction theorem. [1]
In his paper "Theorems for free!"[2], Philip Wadler described an application of parametricity to derive theorems about parametrically polymorphic functions based on their types.
[edit] Parametricity and programming language implementation
Parametricity is the basis for many program transformations implemented in compilers for the Haskell programming language. These transformations were traditionally thought to be correct in Haskell because of Haskell's non-strict semantics. Despite being a lazy programming language, Haskell does support certain primitive operations -- such as the function seq -- that enable so-called "selective strictness", allowing the programmer to force the evaluation of certain expressions. In their paper "Free theorems in the presence of seq"[3], Patricia Johann and Janis Voigtlaender showed that because of the presence of these operations, the general parametricity theorem does not hold for Haskell programs; thus, these transformations are unsound.
[edit] See also
[edit] References
- ^ Reynolds, J.C. (1983). "Types, abstraction, and parametric polymorphism". Information Processing: 513-523.
- ^ Wadler, Philip (September 1989). "Theorems for free!". 4th Int'l Conf. on Functional Programming and Computer Architecture.
- ^ Johann, Patricia; Janis Voigtlaender (January 2004). "Free theorems in the presence of seq". Proc., Principles of Programming Languages: 99-110.
