From Seo Wiki - Search Engine Optimization and Programming Languages

Jump to: navigation, search

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.

Theory of parametricity

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.

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 operator 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 in general.

See also


  1. Reynolds, J.C. (1983). "Types, abstraction, and parametric polymorphism". Information Processing. North Holland, Amsterdam. pp. 513–523. 
  2. Wadler, Philip (September 1989). "Theorems for free!". 4th Int'l Conf. on Functional Programming and Computer Architecture. London. 
  3. Johann, Patricia; Janis Voigtlaender (January 2004). "Free theorems in the presence of seq". Proc., Principles of Programming Languages. pp. 99–110. 


Personal tools

Served in 0.197 secs.