[[!toc levels=2]]
-# System F and recursive types
+# System F: the polymorphic lambda calculus
-In the simply-typed lambda calculus, we write types like <code>σ
--> τ</code>. This looks like logical implication. We'll take
-that resemblance seriously when we discuss the Curry-Howard
-correspondence. In the meantime, note that types respect modus
-ponens:
-
-<pre>
-Expression Type Implication
------------------------------------
-fn α -> β α ⊃ β
-arg α α
------- ------ --------
-(fn arg) β β
-</pre>
-
-The implication in the right-hand column is modus ponens, of course.
+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.
System F was discovered by Girard (the same guy who invented Linear
Logic), but it was independently proposed around the same time by
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 succ = λn:N. Λα. λs:α->α. λz:α. s (n [α] s z) in
+ let shift = λp:Pair. pair (succ (p fst)) (p fst) in
+ let pred = λ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
-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 the typing imposed by the definition of `pred`. The variable `n`
+is typed as a Church number, i.e., as `N ≡ ∀α.(α->α)->α->α`.
+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 certain
pair-manipulating function, which is the heart of the strategy for
-this version of predecessor.
-
-Could we try to build a system for doing Church arithmetic in which
-the type for numbers always manipulated ordered pairs? The problem is
-that the ordered pairs we need here are pairs of numbers. If we tried
-to replace the type for Church numbers with a concrete (simple) type,
-we would have to replace each `X` with the type for Pairs, `(N -> N ->
-N) -> N`. But then we'd have to replace each of these `N`'s with the
-type for Church numbers, `(α -> α) -> α -> α`. And then we'd have to
-replace each of these `α`'s with... ad infinitum. If we had to choose
-a concrete type built entirely from explicit base types, we'd be
-unable to proceed.
+this version of computing the predecessor function.
+
+Could we try to accommodate the needs of the predecessor function by
+building a system for doing Church arithmetic in which the type for
+numbers always manipulated ordered pairs? The problem is that the
+ordered pairs we need here are pairs of numbers. If we tried to
+replace the type for Church numbers with a concrete (simple) type, we
+would have to replace each `N` with the type for Pairs, `(N -> N -> N)
+-> N`. But then we'd have to replace each of these `N`'s with the
+type for Church numbers, which we're imagining is `(Pair -> Pair) ->
+Pair -> Pair`. And then we'd have to replace each of these `Pairs`'s
+with... ad infinitum. If we had to choose a concrete type built
+entirely from explicit base types, we'd be unable to proceed.
[See Benjamin C. Pierce. 2002. *Types and Programming Languages*, MIT
Press, chapter 23.]
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>
-
- (λx:(∀α. α->α) . x [∀α.α->α] x) (Λα.λx:α. x)
+<code>ω id ≡ (λx:(∀α.α->α). x [∀α.α->α] x) (Λα.λx:α.x)</code>
Since the type of the identity function is `∀α.α->α`, it's the
right type to serve as the argument to ω. The definition of
Not only does a fixed-point combinator remain out of reach, we can't
even construct an infinite loop. This means that although we found a
type for ω, there is no general type for Ω ≡ ω
-ω. Furthermore, it turns out that no Turing complete system can
-be strongly normalizing, from which it follows that System F is not
+ω. In fact, it turns out that no Turing complete system can be
+strongly normalizing, from which it follows that System F is not
Turing complete.
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
+The idea is that the basic *and* (the one defined in the first line)
+conjoins expressions of type `t`. But when *and* conjoins functional
+types (the definition in the second line), it builds a function that
distributes its argument across the two conjuncts and conjoins the two
-results. So `Ann left and slept` will evaluate to `(\x.and(left
-x)(slept x)) ann`. Following the terminology of Partee and Rooth, the
-strategy of defining the coordination of expressions with complex
-types in terms of the coordination of expressions with less complex
-types is known as Generalized Coordination.
+results. The intention is that `Ann left and slept` will evaluate to
+`(\x.and(left x)(slept x)) ann`. Following the terminology of Partee
+and Rooth, this strategy of defining the coordination of expressions
+with complex types in terms of the coordination of expressions with
+less complex types is known as Generalized Coordination.
But the definitions just given are not well-formed expressions in
System F. There are three problems. The first is that we have two
definitions to be operative when the type of its arguments is type
`t`, but we have no way of conditioning evaluation on the *type* of an
argument. The second is that for the polymorphic definition, the term
-*and* occurs inside of the definition. System F does not have
-recursion.
+*and* occurs inside of the definition. We know how to handle some
+cases of using a function name inside of its own definition in the
+untyped lambda calculus, but System F does not have
+recursion. [Exercise: convince yourself that the fixed-point
+combinator `Y` can't be typed in System F.]
The third problem is more subtle. The defintion as given takes two
types as parameters: the type of the first argument expected by each
conjunct, and the type of the result of applying each conjunct to an
argument of that type. We would like to instantiate the recursive use
-of *and* in the definition by using the result type. But fully
-instantiating the definition as given requires type application to a
-pair of types, not to just a single type. We want to somehow
-guarantee that β will always itself be a complex type.
+of *and* in the definition by using the result type, so that
+"<code>and [β]</code>" evaluates to the kind of *and* that
+coordinates expressions of type β. But fully instantiating the
+definition as given requires type application to a *pair* of types,
+not to just to a single type. We want to somehow guarantee that β
+will always itself be a complex type. This goes beyond the expressive
+power of System F.
So conjunction and disjunction provide a compelling motivation for
polymorphism in natural language, but we don't yet have the ability to
implemented as a method for generating a suitable set of translation
rules, which are in turn expressed in a simply-typed grammar.
+There is some work using System F to express generalizations about
+natural language: Ponvert, Elias. 2005. Polymorphism in English Logical
+Grammar. In *Lambda Calculus Type Theory and Natural Language*: 47--60.
+
Not incidentally, we're not aware of any programming language that
makes generalized coordination available, despite is naturalness and
ubiquity in natural language. That is, coordination in programming