# Parametricity

### From Seo Wiki - Search Engine Optimization and Programming Languages

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

File:Wiki letter w.svg | This section requires 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.

## 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

## References

- ↑ Reynolds, J.C. (1983). "Types, abstraction, and parametric polymorphism". Information Processing. North Holland, Amsterdam. pp. 513–523.
- ↑ Wadler, Philip (September 1989). "Theorems for free!". 4th Int'l Conf. on Functional Programming and Computer Architecture. London. http://citeseer.ist.psu.edu/wadler89theorems.html.
- ↑ Johann, Patricia; Janis Voigtlaender (January 2004). "Free theorems in the presence of
*seq*". Proc., Principles of Programming Languages. pp. 99–110. http://citeseer.ist.psu.edu/johann04free.html.