Foundations of Functional Programming/Pure type systems

Pure type systems are a wide class of explicitly typed λ-calculi which greatly generalize the systems of the λ-cube. They generalize them by relaxing restrictions on the number of sorts, and the rules governing the sorts.

The systems of the λ-cube had two sorts, ${\text{Type}}$ and ${\text{Type}}_{1}$, with ${\text{Type}}:{\text{Type}}_{1}$. They had $(s_{1},s_{2})$ rules which said how types of different sorts could be used to form function types.

In pure type systems, there can be any number of sorts, and any type relationships between them. The $(s_{1},s_{2})$ rules of the λ-cube systems are generalized to so-called $(s_{1},s_{2},s_{3})$ rules, which relax the restriction that function types formed from types of sorts $s_{1}$ and $s_{2}$ must have the sort $s_{2}$ of the codomain type.

Syntax

The syntax of pure type systems is the same as that of the systems of the λ-cube, except that the set of sorts may be different. Expressions have the same syntax, which we repeat here:

${\begin{array}{rcl}{\text{Expr}}&::=&{\text{Var}}\\&|&{\text{Const}}\\&|&{\text{Expr}}\ {\text{Expr}}\\&|&\lambda \ {\text{Var}}\ :\ {\text{Expr}}.\ {\text{Expr}}\\&|&({\text{Var}}\ :\ {\text{Expr}})\to {\text{Expr}}\end{array}}$

Recall that we denote denote variables by $a,b,c,...$, and when we need to refer to an arbitrary constant, we use bold lower case letters $\mathbf {a} ,\mathbf {b} ,...$. We use $A,B,C,...$ to denote arbitrary expressions.

Declarations and contexts are defined as with the λ-cube.

Specifications

A pure type system is defined by a "specification." The specification says what sorts the system has; what type relationships exist between the sorts; and what $(s_{1},s_{2},s_{3})$ rules the system has. Precisely, a specification is a tuple $(S,A,R)$, where:

• $S$ is a set of constants, the sorts.
• $A$ is the set of "axioms." It is a set of statements of the form $s_{1}:s_{2}$, where $s_{1}$ and $s_{2}$ are sorts.
• $R$ is the set of "rules." It is a set of triples $(s_{1},s_{2},s_{3})$, where $s_{1},s_{2},s_{2}$ are sorts.

Type theory

The notions of β-reduction and β-conversion are defined for pure type systems in the same way as for systems of the λ-cube.

Let $(S,A,R)$ be a specification for a pure type system. The typing rules for the system described by the specification are:

(axioms)	$\vdash s_{1}:s_{2}$	if $(s_{1}:s_{2})\in A$
(start)	${\frac {\Gamma \vdash A:s}{\Gamma ,\ x:A\vdash x:A}}$	if $x\notin \Gamma$
(weakening)	${\frac {\Gamma \vdash A:B\quad \Gamma \vdash C:s}{\Gamma ,\ x:C\vdash A:B}},\ {\text{if}}\ x\notin \Gamma$
(application)	${\frac {\Gamma \vdash F:(x:A)\to B\quad \Gamma \vdash C:A}{\Gamma \vdash FC:B[x/C]}}$
(abstraction)	${\frac {\Gamma ,x:A\vdash B:C\quad \Gamma \vdash (x:A)\to C:s}{\Gamma \vdash (\lambda x:A.B):(x:A)\to C}}$
(conversion)	${\frac {\Gamma \vdash A:B\quad \Gamma \vdash B':s\quad B\equiv _{\beta }B'}{\Gamma \vdash A:B'}}$
($(s_{1},s_{2},s_{3})$ rules)	${\frac {\Gamma \vdash A:s_{1}\quad \Gamma ,\ x:A\vdash B:s_{2}}{\Gamma \vdash (x:A)\to B:s_{3}}}$	if $(s_{1},s_{2},s_{3})\in R$

These rules are the same as the rules for the systems of the λ-cube, except that the axioms are suitably generalized and the $(s_{1},s_{2},s_{3})$ rules replace the $(s_{1},s_{2})$ rules.

Examples of pure type systems

Every explicitly typed λ-calculus we have described so far can be formulated as a pure type system. For example, the second-order λ-calculus can be formulated as follows:

$S$	${\text{Type}},{\text{Type}}_{1}$
$A$	${\text{Type}}:{\text{Type}}_{1}$
$R$	$({\text{Type}},{\text{Type}},{\text{Type}}),({\text{Type}}_{1},{\text{Type}},{\text{Type}})$

It is straightforward to formulate the rest of the systems of the λ-cube as pure type systems.

λ* (naïve type theory)

Another important pure type system is the system λ*, which we also refer to as naïve type theory. This system is distinguished by the fact that it has just a single sort, ${\text{Type}}$, with the axiom ${\text{Type}}:{\text{Type}}$. Here is the specification:

$S$	${\text{Type}}$
$A$	${\text{Type}}:{\text{Type}}$
$R$	$({\text{Type}},{\text{Type}},{\text{Type}})$

As we have already noted, the assumption that ${\text{Type}}:{\text{Type}}$ gives rise to Girard's paradox, which renders λ* inconsistent.

At first blush, one might think that this result is caused by the circularity of the assumption that ${\text{Type}}:{\text{Type}}$; many logical paradoxes, such as Russell's paradox and the liar paradox, are due to circularities of various kinds. However, Girard showed that the inconsistency also arises in the following pure type system, which has no obvious circularity (see Barendregt (1992)):

$S$	${\text{Type}}_{0},{\text{Type}}_{1},{\text{Type}}_{2}$
$A$	${\text{Type}}_{0}:{\text{Type}}_{1},{\text{Type}}_{1}:{\text{Type}}_{2}$
$R$	$({\text{Type}}_{0},{\text{Type}}_{0},{\text{Type}}_{0}),({\text{Type}}_{1},{\text{Type}}_{0},{\text{Type}}_{0}),({\text{Type}}_{1},{\text{Type}}_{1},{\text{Type}}_{1}),({\text{Type}}_{2},{\text{Type}}_{1},{\text{Type}}_{1}),({\text{Type}}_{2},{\text{Type}}_{0},{\text{Type}}_{0})$

Properties of pure type systems

The familiar properties we have seen in all the explicitly typed systems discussed so far do not always hold in the more general context of pure type systems. However, for each of them we can identify fairly broad classes of pure type systems for which they hold.

Of the properties we have discussed with previous systems, the only one that holds in all pure type systems is that β-reduction preserves type. That is, if $\Gamma \vdash A:T$ and and $A$ β-reduces to $A'$, then $\Gamma \vdash A':T$.

Not all pure type systems have the strong normalization property. In an inconsistent pure type system, there are terms of every type. It can be proven that an expression of a type which corresponds to an arbitrary false statement must have no normal form, meaning that not all typeable terms are normalizing.

If a pure type system has the strong normalization property, then the problems of type checking and typability are decidable for that pure type system.

Many pure type systems also preserve the property that every expression has at most one type, up to β-convertibility. Recall that this property states that for any expression $A$ and any context $\Gamma$, if two expressions $B$ and $B'$ are such that $\Gamma \vdash A:B$ and $\Gamma \vdash A:B'$, then $B\equiv _{\beta }B'$.

Though many pure type systems have this property, not all do. In particular, it is trivial to break this property using axioms, as in the following pure type system:

$S$	${\text{Type}},{\text{Type}}_{1}$
$A$	${\text{Type}}:{\text{Type}},{\text{Type}}:{\text{Type}}_{1}$
$R$	$({\text{Type}},{\text{Type}},{\text{Type}}),({\text{Type}}_{1},{\text{Type}},{\text{Type}})$

In this pure type system, ${\text{Type}}$ has two non-β-convertible types -- ${\text{Type}}$ and ${\text{Type}}_{1}$ -- by fiat.

However, it can also be shown that this kind of stipulation is the only thing that can break the unique typability property in pure type systems. If a pure type system $(S,A,R)$ is such that no sort appears on the left hand side of more than one statement in $A$, then every expression has at most one type up to β-conversion in that system. A pure type system with this property, that no sort is assigned more than one sort by the axioms, is called "singly sorted."