System F is a typed lambda calculus. It is also known as the second-order or polymorphic lambda calculus. It was discovered independently by the logician Jean-Yves Girard and the computer scientist John C. Reynolds. System F formalizes the notion of parametric polymorphism in programming languages. The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ... The article titled Logicians treats the ancient Chinese philosophers known by that name (with a capital L). List of logicians (with a lower-case l) treats philosophers, mathematicians, and others whose topic of scholarly study is logic. ... Jean-Yves Girard is a French mathematician working in proof theory. ... Computer science (informally: CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. ... John C. Reynolds is a American computer scientist (born June 1, 1935). ... In computer science, polymorphism is the idea of allowing the same definitions to be used with different types of data (specifically, different classes of objects), resulting in more general and abstract implementations. ... A programming language or computer language is a standardized communication technique for expressing instructions to a computer. ...

Just as the lambda calculus has variables ranging over functions, and binders for them, the second-order lambda calculus has variables ranging over types, and binders for them. The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...

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 judgement

where α is a type variable. In computer science and mathematics, a variable is a symbol denoting a quantity or symbolic representation. ...

Under the Curry-Howard isomorphism, System F corresponds to a second-order logic. The Curry-Howard correspondence is the close relationship between computer programs and mathematical proofs; the correspondence is also known as the Curry-Howard isomorphism, or the formulae-as-types correspondence. ... Jump to: navigation, search In mathematical logic, second-order logic is an extension of either propositional logic or first-order logic which contains variables in predicate positions (rather than only in term positions, as in first-order logic), and quantifiers binding them. ...

System F, together with even more expressive lambda calculi, can be seen as part of the lambda cube. In mathematical logic and type theory, the λ-cube is a framework for exploring the axes of refinement in Coquands Calculus of Constructions, starting from the simply typed lambda calculus as the vertex of a (3-D) cube placed at the origin, and the calculus of constructions (= higher order...

Logic and predicates

The Boolean type is defined as: , where α is a type variable. . This produces the following two definitions for the boolean values TRUE and FALSE: In computer science and mathematics, a variable is a symbol denoting a quantity or symbolic representation. ...

TRUE := Λα.λx^αλy^α.x

FALSE := Λα.λx^αλy^α.y

Then, with these two λ-terms, we can define some logic operators:

AND := λx^Booleanλy^Boolean.((x(Boolean))y)FALSE

OR := λx^Booleanλy^Boolean.((x(Boolean))TRUE)y

NOT := λx^Boolean.((x(Boolean))FALSE)TRUE

There really is no need for a IFTHENELSE function as one can just use raw Boolean typed terms as decision functions. However, if one is requested:

IFTHENELSE := Λα.λx^Booleanλy^αλz^α.((x(α))y)z

will do.

A predicate is a function which returns a boolean value. The most fundamental predicate is ISZERO which returns TRUE if and only if its argument is the Church numeral 0:

ISZERO := λ n. n (λ x. FALSE) TRUE

External links

• Proofs and Types - New link
• [1]