[[!toc levels=2]]
-# System F and recursive types
+# System F: the polymorphic lambda calculus
+
+The simply-typed lambda calculus is beautifully simple, but it can't
+even express the predecessor function, let alone full recursion. And
+we'll see shortly that there is good reason to be unsatisfied with the
+simply-typed lambda calculus as a way of expressing natural language
+meaning. So we will need to get more sophisticated about types. The
+next step in that journey will be to consider System F.
In the simply-typed lambda calculus, we write types like <code>σ
-> τ</code>. This looks like logical implication. We'll take
course) that "<code>x:α</code>" represents an expression `x`
whose type is <code>α</code>.
-Then System F can be specified as follows (choosing notation that will
-match up with usage in O'Caml, whose type system is based on System F):
+Then System F can be specified as follows:
System F:
---------
In the definition of the types, "`c`" is a type constant. Type
constants play the role in System F that base types play in the
simply-typed lambda calculus. So in a lingusitics context, type
-constants might include `e` and `t`. "α" is a type variable. The
-tick mark just indicates that the variable ranges over types rather
-than over values; in various discussion below and later, type variable
-can be distinguished by using letters from the greek alphabet
-(α, β, etc.), or by using capital roman letters (X, Y,
-etc.). "`τ1 -> τ2`" is the type of a function from expressions of
-type `τ1` to expressions of type `τ2`. And "`∀α.τ`" is called a
-universal type, since it universally quantifies over the type variable
-`'a`. You can expect that in `∀α.τ`, the type `τ` will usually
-have at least one free occurrence of `α` somewhere inside of it.
+constants might include `e` and `t`. "α" is a type variable. In
+various discussions, type variables are distinguished by using letters
+from the greek alphabet (α, β, etc.), as we do here, or by
+using capital roman letters (X, Y, etc.), or by adding a tick mark
+(`'a`, `'b`, etc.), as in OCaml. "`τ1 -> τ2`" is the type of a
+function from expressions of type `τ1` to expressions of type `τ2`.
+And "`∀α.τ`" is called a universal type, since it universally
+quantifies over the type variable `α`. You can expect that in
+`∀α.τ`, the type `τ` will usually have at least one free occurrence of
+`α` somewhere inside of it.
In the definition of the expressions, we have variables "`x`" as usual.
-Abstracts "`λx:τ. e`" are similar to abstracts in the simply-typed lambda
+Abstracts "`λx:τ.e`" are similar to abstracts in the simply-typed lambda
calculus, except that they have their shrug variable annotated with a
type. Applications "`e1 e2`" are just like in the simply-typed lambda calculus.
<code>Λ α (λ x:α. x)</code>
the <code>Λ</code> binds the type variable `α` that occurs in
-the <code>λ</code> abstract. Of course, as long as type
-variables are carefully distinguished from expression variables (by
-tick marks, Grecification, or capitalization), there is no need to
-distinguish expression abstraction from type abstraction by also
-changing the shape of the lambda.
-
-The expression immediately below is a polymorphic version of the
-identity function. It defines one general identity function that can
-be adapted for use with expressions of any type. In order to get it
-ready to apply this identity function to, say, a variable of type
-boolean, just do this:
+the <code>λ</code> abstract.
+
+This expression is a polymorphic version of the identity function. It
+defines one general identity function that can be adapted for use with
+expressions of any type. In order to get it ready to apply this
+identity function to, say, a variable of type boolean, just do this:
<code>(Λ α (λ x:α. x)) [t]</code>
This type application (where `t` is a type constant for Boolean truth
values) specifies the value of the type variable `α`. Not
-surprisingly, the type of this type application is a function from
-Booleans to Booleans:
+surprisingly, the type of the expression that results from this type
+application is a function from Booleans to Booleans:
<code>((Λα (λ x:α . x)) [t]): (b->b)</code>
of type `α`. In general, then, the type of the uninstantiated
(polymorphic) identity function is
-<code>(Λα (λx:α . x)): (∀α. α-α)</code>
+<code>(Λα (λx:α . x)): (∀α. α->α)</code>
Pred in System F
----------------
We saw that the predecessor function couldn't be expressed in the
simply-typed lambda calculus. It *can* be expressed in System F,
-however. Here is one way, coded in
-[[Benjamin Pierce's type-checker and evaluator for
-System F|http://www.cis.upenn.edu/~bcpierce/tapl/index.html]] (the
-relevant evaluator is called "fullpoly"):
-
- N = ∀α. (α->α)->α->α;
- Pair = (N->N->N) -> N;
- let zero = α . λs:α->α . λz:α. z in
- let fst = λx:N . λy:N . x in
- let snd = λx:N . λy:N . y in
- let pair = λx:N . λy:N . λz:N->N->N . z x y in
- let suc = λn:N . λα . λlambda s:α->α . λz:α . s (n [α] s z) in
- let shift = λp:Pair . pair (suc (p fst)) (p fst) in
- let pre = λn:N . n [Pair] shift (pair zero zero) snd in
+however. Here is one way:
+
+ let N = ∀α.(α->α)->α->α in
+ let Pair = (N->N->N)->N in
+
+ let zero = Λα. λs:α->α. λz:α. z in
+ let fst = λx:N. λy:N. x in
+ let snd = λx:N. λy:N. y in
+ let pair = λx:N. λy:N. λz:N->N->N. z x y in
+ let suc = λn:N. Λα. λs:α->α. λz:α. s (n [α] s z) in
+ let shift = λp:Pair. pair (suc (p fst)) (p fst) in
+ let pre = λn:N. n [Pair] shift (pair zero zero) snd in
pre (suc (suc (suc zero)));
-We've truncated the names of "suc(c)" and "pre(d)", since those are
-reserved words in Pierce's system. Note that in this code, there is
-no typographic distinction between ordinary lambda and type-level
-lambda, though the difference is encoded in whether the variables are
-lower case (for ordinary lambda) or upper case (for type-level
-lambda).
+[If you want to run this code in
+[[Benjamin Pierce's type-checker and evaluator for
+System F|http://www.cis.upenn.edu/~bcpierce/tapl/index.html]], the
+relevant evaluator is called "fullpoly", and you'll need to
+truncate the names of "suc(c)" and "pre(d)", since those are
+reserved words in Pierce's system.]
+
+Exercise: convince yourself that `zero` has type `N`.
The key to the extra expressive power provided by System F is evident
in the typing imposed by the definition of `pre`. The variable `n` is
-typed as a Church number, i.e., as `∀ α . (α->α)->α->α`. The type
+typed as a Church number, i.e., as `∀α.(α->α)->α->α`. The type
application `n [Pair]` instantiates `n` in a way that allows it to
manipulate ordered pairs: `n [Pair]: (Pair->Pair)->Pair->Pair`. In
other words, the instantiation turns a Church number into a
In fact, unlike in the simply-typed lambda calculus,
it is even possible to give a type for ω in System F.
-<code>ω = lambda x:(∀ α. α->α) . x [∀ α . α->α] x</code>
+<code>ω = λx:(∀α.α->α). x [∀α.α->α] x</code>
In order to see how this works, we'll apply ω to the identity
function.
<code>ω id ==</code>
- (lambda x:(∀ α . α->α) . x [∀ α . α->α] x) (lambda α . lambda x:α . x)
+ (λx:(∀α.α->α). x [∀α.α->α] x) (Λα.λx:α.x)
-Since the type of the identity function is `(∀ α . α->α)`, it's the
+Since the type of the identity function is `∀α.α->α`, it's the
right type to serve as the argument to ω. The definition of
ω instantiates the identity function by binding the type
-variable `α` to the universal type `∀ α . α->α`. Instantiating the
+variable `α` to the universal type `∀α.α->α`. Instantiating the
identity function in this way results in an identity function whose
type is (in some sense, only accidentally) the same as the original
fully polymorphic identity function.
With these basic types, we want to say something like this:
- and:t->t->t = lambda l:t . lambda r:t . l r false
- and = lambda α . lambda β .
- lambda l:α->β . lambda r:α->β .
- lambda x:α . and:β (l x) (r x)
+ and:t->t->t = λl:t. λr:t. l r false
+ and = Λα.Λβ.λl:α->β.λr:α->β.λx:α. and [β] (l x) (r x)
The idea is that the basic *and* conjoins expressions of type `t`, and
when *and* conjoins functional types, it builds a function that