From: chris Date: Thu, 26 Feb 2015 02:43:42 +0000 (-0500) Subject: (no commit message) X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=9873c23f4967dc8a1dc03bd57a20bf73db1ac721 --- diff --git a/topics/_week5_system_F.mdwn b/topics/_week5_system_F.mdwn index 55f49aed..f7537090 100644 --- a/topics/_week5_system_F.mdwn +++ b/topics/_week5_system_F.mdwn @@ -118,7 +118,7 @@ relevant evaluator is called "fullpoly"): N = ∀α.(α->α)->α->α; Pair = (N->N->N)->N; - let zero = Λα.λs:α->α.λz:α. z 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 @@ -137,7 +137,7 @@ lambda). 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 @@ -164,14 +164,14 @@ Typing ω In fact, unlike in the simply-typed lambda calculus, it is even possible to give a type for ω in System F. -ω = λlambda x:(∀ α. α->α) . x [∀ α . α->α] x +ω = λx:(∀α.α->α).x [∀α.α->α] x In order to see how this works, we'll apply ω to the identity function. ω id == - (λx:(∀α. α->α) . x [∀α.α->α] x) (Λα.λx:α. x) + (λ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