From 114bb41bc1654608633596c9fe426e01bff98913 Mon Sep 17 00:00:00 2001 From: Chris Date: Thu, 26 Feb 2015 13:41:24 -0500 Subject: [PATCH] edits --- topics/_week5_system_F.mdwn | 86 +++++++++++++++++++++++++-------------------- 1 file changed, 48 insertions(+), 38 deletions(-) diff --git a/topics/_week5_system_F.mdwn b/topics/_week5_system_F.mdwn index 539017ea..24f0dad0 100644 --- a/topics/_week5_system_F.mdwn +++ b/topics/_week5_system_F.mdwn @@ -105,9 +105,9 @@ however. Here is one way: 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 + 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))); @@ -121,24 +121,25 @@ 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.] @@ -154,9 +155,7 @@ it is even possible to give a type for ω in System F. In order to see how this works, we'll apply ω to the identity function. -ω id == - - (λx:(∀α.α->α). x [∀α.α->α] x) (Λα.λx:α.x) +ω id ≡ (λx:(∀α.α->α). x [∀α.α->α] x) (Λα.λx:α.x) Since the type of the identity function is `∀α.α->α`, it's the right type to serve as the argument to ω. The definition of @@ -179,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 ω, 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. @@ -215,14 +214,15 @@ 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 +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 @@ -230,17 +230,23 @@ 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. +*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 +"and [β]" 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 @@ -253,6 +259,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. +There is some work using System F to express generalization 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 -- 2.11.0