System F, also known as the
polymorphic lambda calculus or the
second-order lambda calculus, is a
typed lambda calculus that differs from
simply typed lambda calculus by the introduction of a mechanism of universal quantification over types. System F thus formalizes the notion of
parametric polymorphism in
programming languages, and forms a theoretical basis for languages such as
Haskell,
ML, and
F_. System F was discovered independently by the
logician Jean-Yves Girard and the
computer scientist John C. Reynolds.
Whereas simply typed lambda calculus has variables ranging over functions, and binders for them, System F additionally has variables ranging over types, and binders for them. As an example, the fact that the identity function can have any type of the form A? A would be formalized in System F as the judgment
where a is a type variable. The upper-case ? is traditionally used to denote type-level functions, as opposed to the lower-case ? which is used for value-level functions.
As a term rewriting system, System F is strongly normalizing. Type inference in System F is undecidable however. Under the Curry-Howard isomorphism, System F corresponds to fragment of second-order intuitionistic logic that uses only universal quantification. System F can be seen as part of the lambda cube, together with even more expressive typed lambda calculi, including those with dependent types.
