Foundations of Functional Programming/Second-order λ-calculus

The second-order λ-calculus is a typed λ-calculus which extends the simply typed λ-calculus with parametric polymorphism. One can write a single type which says, for example, that the identity function has type $\alpha \to \alpha$, for any type $\alpha$. This type is written $\forall \alpha (\alpha \to \alpha )$. This type is pronounced, "for all alpha, alpha to alpha." It means the same as the type a -> a in Haskell or ML. The piece of syntax $\forall \alpha$ is called a "type quantifier."

Like the simply typed λ-calculus, the second-order λ-calculus comes in two flavors: an implicitly typed flavor, and an explicitly typed flavor. Neither flavor is Turing complete. Type checking is undecidable in the implicitly typed calculus, but decidable in the explicitly typed calculus.

The Hindley-Milner type system is another polymorphic type system which addresses the shortcomings of the implicitly typed second-order λ-calculus that we have just mentioned (namely, Turing incompleteness and undecidability of type checking). It is an implicitly typed, polymorphic type system which is Turing complete, and which enjoys decidable type checking.

Type syntax

Both flavors of the second-order λ-calculus have the same syntax for types, which just augments the syntax of the simply typed λ-calculus with type quantifiers.

${\begin{array}{rcl}{\text{TypeVar}}&::=&\alpha \ |\ \beta \ |\ \cdots \\{\text{TypeExpr}}&::=&{\text{TypeVar}}\\&|&{\text{TypeExpr}}\to {\text{TypeExpr}}\\&|&\forall \ {\text{TypeVar}}\ .\ {\text{TypeExpr}}\end{array}}$

As usual, parentheses can be used to disambiguate scope. When there are nested quantifiers over the same variable, variables bind to the innermost quantifier. E.g., in $\forall \alpha \forall \beta \forall \alpha (\beta \to \alpha )$, the $\alpha$ in $\beta \to \alpha$ binds to the innermost quantifier, not the outermost quantifier.

We distinguish between free occurrences and bound occurrences of type variables, much as we distinguished between free and bound occurrences of variables in the untyped λ-calculus. A free occurrence of a type variable $\alpha$ is one does not occur in the scope of a quantifier over $\alpha$.

If $\mathbf {A}$ is a type expression which might have free occurrences of $\alpha$, and $\mathbf {B}$ is a type expression, we define the substitution $\mathbf {A} [\alpha /\mathbf {B} ]$ as the result of replacing all free occurrences of $\alpha$ in $\mathbf {A}$ with $\mathbf {B}$, possibly renaming bound variables in $\mathbf {A}$ if necessary to avoid variable capture.

Implicitly typed second-order λ-calculus

The definitions of value expressions, statements, declarations, and contexts are the same for the implicitly typed second-order λ-calculus as for the implicitly simply typed λ-calculus.

Type theory

The following rules define the valid type entailments in the implicitly typed calculus:

(axiom)	$\Gamma \vdash x:\mathbf {T}$	if $x:\mathbf {T}$ is a member of $\Gamma$.
(→-elimination)	${\frac {\Gamma \vdash A:\mathbf {T} \to \mathbf {U} \ \ \ \Gamma \vdash B:\mathbf {T} }{\Gamma \vdash AB:\mathbf {U} }}$
(→-introduction)	${\frac {\Gamma ,x:\mathbf {T} \vdash A:\mathbf {U} }{\Gamma \vdash \lambda x.A:\mathbf {T} \to \mathbf {U} }}$
($\forall$-elimination)	${\frac {\Gamma \vdash A:\forall \alpha .\mathbf {T} }{\Gamma \vdash A:\mathbf {T} [\alpha /\mathbf {U} ]}}$
($\forall$-introduction	${\frac {\Gamma \vdash A:\mathbf {T} }{\Gamma \vdash A:\forall \alpha .\mathbf {T} }}$	if $\alpha$ does not occur free in $\Gamma$.

The new rules are the rules for the quantifier. The first new rule allows us to instantiate polymorphic types; it says that if an expression has a polymorphic type, then it has every instance of that type.

The second new rule allows us to prove that an expression has a polymorphic type. The idea is that if we can derive that an expression has a type involving $\alpha$ without making any special assumptions about $\alpha$, then the expression's type can be made polymorphic in $\alpha$.

Example type derivation

Now we give an example type derivation using the new rules. We will show that the function $A=\lambda x\lambda y.xy$ has the polymorphic type $\forall \alpha \forall \beta ((\alpha \to \beta )\to \alpha \to \beta )$. This is the same as the similar derivation we did for the simply typed λ-calculus, except for two added steps at the end.

1. $x:\alpha \to \beta ,y:\alpha \vdash x:\alpha \to \beta$ (axiom)
2. $x:\alpha \to \beta ,y:\alpha \vdash y:\alpha$ (axiom)
3. $x:\alpha \to \beta ,y:\alpha \vdash xy:\beta$ (→-elimination, from 1 and 2)
4. $x:\alpha \to \beta \vdash \lambda y.xy:\alpha \to \beta$ (→-introduction, from 3)
5. $\vdash \lambda x\lambda y.xy:(\alpha \to \beta )\to \alpha \to \beta$ (→-introduction, from 4)
6. $\vdash \lambda x\lambda y.xy:\forall \beta ((\alpha \to \beta )\to \alpha \to \beta$ ($\forall$-introduction, from 5)
7. $\vdash \lambda x\lambda y.xy:\forall \alpha \forall \beta ((\alpha \to \beta )\to \alpha \to \beta$ ($\forall$-introduction, from 6)

Properties of the calculus

• β-reduction preserves type: if $\Gamma \vdash A:\mathbf {T}$ and and $A$ β-reduces to $A'$, then $\Gamma \vdash A':\mathbf {T}$.
• The strong normalization property holds, so that all functions typeable in the calculus halt, and the calculus is not Turing complete.
• The problems of type checking and typability are undecidable (though they are semidecidable, i.e. computably enumerable). See Wells (1993).

Explicitly typed second-order λ-calculus

In the case of the simply typed λ-calculi, the differences between the implicitly typed and explicitly typed versions were not very large. The differences between the implicitly and explicitly typed versions of second-order λ-calculus are more substantial.

In the explicitly typed calculus, we think of a value of type $\forall \alpha .\mathbf {A}$ as a function from types to values. For instance, the identity function ${\text{id}}:\forall \alpha .\ \alpha \to \alpha$ is a function which takes a type $\mathbf {T}$ and returns a function ${\text{id}}\ \mathbf {T} :\mathbf {T} \to \mathbf {T}$. Such functions from types to values are denoted by "Λ-abstractions." For example, here is the definition of the polymorphic identity function in the explicitly typed calculus:

${\text{id}}=\Lambda \alpha \lambda x:\alpha .\ x$

Values and β-reduction

The syntax for types has already been described. The new syntax for values is as follows:

${\begin{array}{rcl}{\text{Var}}&::=&a\ |\ b\ |\ c\ |\ \cdots \\{\text{Expr}}&::=&{\text{Var}}\\&|&{\text{Expr}}\ {\text{Expr}}\\&|&{\text{Expr}}\ {\text{TypeExpr}}\\&|&\lambda \ {\text{Var}}\ :\ {\text{TypeExpr}}.\ {\text{Expr}}\\&|&\Lambda \ {\text{TypeVar}}.\ {\text{Expr}}\\\end{array}}$

The rules for β-reduction are now expanded to include rules for β-reducing Λ-abstractions:

• $(\lambda x.A)B\to _{\beta }A[x/B]$
• $(\Lambda \alpha .A)\mathbf {T} \to _{\beta }A[\alpha /\mathbf {T} ]$

As before, one can β-reduce an expression by performing either of the above transformations on any of its subexpressions.

Type theory

Here are the rules defining the valid type entailments in the explicitly typed calculus:

(axiom)	$\Gamma \vdash x:\mathbf {T}$	if $x:\mathbf {T}$ is a member of $\Gamma$.
(→-elimination)	${\frac {\Gamma \vdash A:\mathbf {T} \to \mathbf {U} \ \ \ \Gamma \vdash B:\mathbf {T} }{\Gamma \vdash AB:\mathbf {U} }}$
(→-introduction)	${\frac {\Gamma ,x:\mathbf {T} \vdash A:\mathbf {U} }{\Gamma \vdash (\lambda x:\mathbf {T} .A):\mathbf {T} \to \mathbf {U} }}$
($\forall$-elimination)	${\frac {\Gamma \vdash A:\forall \alpha .\mathbf {T} }{\Gamma \vdash A\mathbf {U} :\mathbf {T} [\alpha /\mathbf {U} ]}}$
($\forall$-introduction	${\frac {\Gamma \vdash A:\mathbf {T} }{\Gamma \vdash (\Lambda \alpha .A):\forall \alpha .\mathbf {T} }}$	if $\alpha$ does not occur free in $\Gamma$.

Example type derivation

Now we repeat our usual example, giving a type derivation using the new rules. We will show that the function $A=\Lambda \alpha \Lambda \beta \lambda x:\alpha \lambda y:\beta .xy$ has the polymorphic type $\forall \alpha \forall \beta ((\alpha \to \beta )\to \alpha \to \beta )$.

1. $x:\alpha \to \beta ,y:\alpha \vdash x:\alpha \to \beta$ (axiom)
2. $x:\alpha \to \beta ,y:\alpha \vdash y:\alpha$ (axiom)
3. $x:\alpha \to \beta ,y:\alpha \vdash xy:\beta$ (→-elimination, from 1 and 2)
4. $x:\alpha \to \beta \vdash \lambda y:\alpha .xy:\alpha \to \beta$ (→-introduction, from 3)
5. $\vdash \lambda x:\alpha \to \beta \lambda y:\alpha .xy:(\alpha \to \beta )\to \alpha \to \beta$ (→-introduction, from 4)
6. $\vdash \Lambda \beta \lambda x\lambda y.xy:\forall \beta ((\alpha \to \beta )\to \alpha \to \beta$ ($\forall$-introduction, from 5)
7. $\vdash \Lambda \alpha \Lambda \beta \lambda x\lambda y.xy:\forall \alpha \forall \beta ((\alpha \to \beta )\to \alpha \to \beta$ ($\forall$-introduction, from 6)

To show how application of $\forall$-elimination works, we show that $A\gamma \delta :(\gamma \to \delta )\to \gamma \to \delta$:

1. $\vdash \Lambda \alpha \Lambda \beta \lambda x\lambda y.xy:\forall \alpha \forall \beta ((\alpha \to \beta )\to \alpha \to \beta$ (from previous derivation)
2. $\vdash (\Lambda \alpha \Lambda \beta \lambda x\lambda y.xy)\gamma :\forall \beta ((\gamma \to \beta )\to \gamma \to \beta$ ($\forall$-elimination, from 1)
3. $\vdash (\Lambda \alpha \Lambda \beta \lambda x\lambda y.xy)\gamma \delta :(\gamma \to \delta )\to \gamma \to \delta$ ($\forall$-elimination, from 2)

Properties of the calculus

• β-reduction preserves type: if $\Gamma \vdash A:\mathbf {T}$ and and $A$ β-reduces to $A'$, then $\Gamma \vdash A':\mathbf {T}$.
• The strong normalization property holds, so that all functions typeable in the calculus halt, and the calculus is not Turing complete.
• The problems of type checking and typability are decidable.
• Every value expression has at most one type.