merge working
[lambda.git] / topics / _week5_system_F.mdwn
index 5b2e297..242ada4 100644 (file)
@@ -1,23 +1,13 @@
 [[!toc levels=2]]
 
 [[!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>&sigma;
--> &tau;</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            &alpha; -> &beta;    &alpha; &sup; &beta;
-arg           &alpha;         &alpha;
-------        ------    --------
-(fn arg)      &beta;         &beta;
-</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
 
 System F was discovered by Girard (the same guy who invented Linear
 Logic), but it was independently proposed around the same time by
@@ -44,16 +34,16 @@ Then System F can be specified as follows:
 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
 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 variables
-can be distinguished by using letters from the greek alphabet
-(&alpha;, &beta;, 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 (&alpha;, &beta;, 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 `&alpha;`.  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
 
 In the definition of the expressions, we have variables "`x`" as usual.
 Abstracts "`λx:τ.e`" are similar to abstracts in the simply-typed lambda
@@ -72,24 +62,19 @@ variables.  So in the expression
 <code>&Lambda; α (&lambda; x:α. x)</code>
 
 the <code>&Lambda;</code> binds the type variable `α` that occurs in
 <code>&Lambda; α (&lambda; x:α. x)</code>
 
 the <code>&Lambda;</code> binds the type variable `α` that occurs in
-the <code>&lambda;</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>&lambda;</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>(&Lambda; α (&lambda; 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
 
 <code>(&Lambda; α (&lambda; 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>((&Lambda;α (&lambda; x:α . x)) [t]): (b->b)</code>    
 
 
 <code>((&Lambda;α (&lambda; x:α . x)) [t]): (b->b)</code>    
 
@@ -104,56 +89,57 @@ instantiated as a function from expresions of type `α` to expressions
 of type `α`.  In general, then, the type of the uninstantiated
 (polymorphic) identity function is
 
 of type `α`.  In general, then, the type of the uninstantiated
 (polymorphic) identity function is
 
-<code>(&Lambda;α (&lambda;x:α . x)): (&forall;α. α-α)</code>
+<code>(&Lambda;α (&lambda;x:α . x)): (&forall;α. α->α)</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,
 
 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.Λα.λ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)));
 
 
     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
 
 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 &equiv; ∀α.(α->α)->α->α`.
+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
 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.]
  
 [See Benjamin C. Pierce. 2002. *Types and Programming Languages*, MIT
 Press, chapter 23.]
@@ -164,14 +150,12 @@ Typing &omega;
 In fact, unlike in the simply-typed lambda calculus, 
 it is even possible to give a type for &omega; in System F. 
 
 In fact, unlike in the simply-typed lambda calculus, 
 it is even possible to give a type for &omega; in System F. 
 
-<code>&omega; = λx:(∀α.α->α).x [∀α.α->α] x</code>
+<code>&omega; = λx:(∀α.α->α). x [∀α.α->α] x</code>
 
 In order to see how this works, we'll apply &omega; to the identity
 function.  
 
 
 In order to see how this works, we'll apply &omega; to the identity
 function.  
 
-<code>&omega; id ==</code>
-
-    (λx:(∀α.α->α). x [∀α.α->α] x) (Λα.λx:α.x)
+<code>&omega; id &equiv; (λ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 &omega;.  The definition of
 
 Since the type of the identity function is `∀α.α->α`, it's the
 right type to serve as the argument to &omega;.  The definition of
@@ -194,8 +178,8 @@ form in a finite number of steps.
 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 &omega;, there is no general type for &Omega; &equiv; &omega;
 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 &omega;, there is no general type for &Omega; &equiv; &omega;
-&omega;.  Furthermore, it turns out that no Turing complete system can
-be strongly normalizing, from which it follows that System F is not
+&omega;.  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.
 
 
 Turing complete.
 
 
@@ -208,10 +192,11 @@ The classic case study motivating polymorphism in natural language
 comes from coordination.  (The locus classicus is Partee and Rooth
 1983.)
 
 comes from coordination.  (The locus classicus is Partee and Rooth
 1983.)
 
-    Ann left and Bill left.
-    Ann left and slept.
-    Ann and Bill left.
-    Ann read and reviewed the book.
+                                      Type of the argument of "and":
+    Ann left and Bill left.           t
+    Ann left and slept.               e->t
+    Ann and Bill left.                (e->t)-t  (i.e, generalize quantifiers)
+    Ann read and reviewed the book.   e->e->t
 
 In English (likewise, many other languages), *and* can coordinate
 clauses, verb phrases, determiner phrases, transitive verbs, and many
 
 In English (likewise, many other languages), *and* can coordinate
 clauses, verb phrases, determiner phrases, transitive verbs, and many
@@ -219,7 +204,9 @@ other phrase types.  In a garden-variety simply-typed grammar, each
 kind of conjunct has a different semantic type, and so we would need
 an independent rule for each one.  Yet there is a strong intuition
 that the contribution of *and* remains constant across all of these
 kind of conjunct has a different semantic type, and so we would need
 an independent rule for each one.  Yet there is a strong intuition
 that the contribution of *and* remains constant across all of these
-uses.  Can we capture this using polymorphic types?
+uses.  
+
+Can we capture this using polymorphic types?
 
     Ann, Bill      e
     left, slept    e -> t    
 
     Ann, Bill      e
     left, slept    e -> t    
@@ -228,38 +215,41 @@ uses.  Can we capture this using polymorphic types?
 With these basic types, we want to say something like this:
 
     and:t->t->t = λl:t. λr:t. l r false
 With these basic types, we want to say something like this:
 
     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
-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.
-
-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 of the same word.  The intention is for one of the
-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.  
-
-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.
-
-So conjunction and disjunction provide a compelling motivation for
-polymorphism in natural language, but we don't yet have the ability to
-build the polymorphism into a formal system.
+    gen_and = Λα.Λβ.λf:(β->t).λl:α->β.λr:α->β.λx:α. f (l x) (r x)
+
+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 then applies the
+appropriate lower-order instance of *and*.
+
+    and (Ann left) (Bill left)
+    gen_and [e] [t] and left slept
+    gen_and [e] [e->t] (gen_and [e] [t] and) read reviewed
+
+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, which is why we call the polymorphic part of
+the definition `gen_and`.
+
+In the first line, the basic *and* is ready to conjoin two truth
+values.  In the second line, the polymorphic definition of `gen_and`
+makes explicit exactly how the meaning of *and* when it coordinates
+verb phrases depends on the meaning of the basic truth connective.
+Likewise, when *and* coordinates transitive verbs of type `e->e->t`,
+the generalized *and* depends on the `e->t` version constructed for
+dealing with coordinated verb phrases.
+
+On the one hand, this definition accurately expresses the way in which
+the meaning of the conjunction of more complex types relates to the
+meaning of the conjunction of simpler types.  On the other hand, it's
+awkward to have to explicitly supply an expression each time that
+builds up the meaning of the *and* that coordinates the expressions of
+the simpler types.  We'd like to have that automatically handled by
+the polymorphic definition; but that would require writing code that
+behaved differently depending on the types of its type arguments,
+which goes beyond the expressive power of System F.
 
 And in fact, discussions of generalized coordination in the
 linguistics literature are almost always left as a meta-level
 
 And in fact, discussions of generalized coordination in the
 linguistics literature are almost always left as a meta-level
@@ -268,6 +258,10 @@ Hendriks' 1992:74 dissertation, generalized coordination is
 implemented as a method for generating a suitable set of translation
 rules, which are in turn expressed in a simply-typed grammar.
 
 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
 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