X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week2.mdwn;h=d1d02faf0a9159ac7de0adc510a54047d21e5fe5;hp=a8e3ca4e6968aa393b6de9e0a7a8c1d74724d7be;hb=98652627403eaa920f51cedc4d0cc68c1103b972;hpb=6e55a9652a8a082eceb8efaa0eedbce91a79716f diff --git a/week2.mdwn b/week2.mdwn index a8e3ca4e..d1d02faf 100644 --- a/week2.mdwn +++ b/week2.mdwn @@ -183,6 +183,9 @@ The fifth rule deals with an abstract whose body is an application: the S combin [Fussy notes: if the original lambda term has free variables in it, so will the combinatory logic translation. Feel free to worry about this, though you should be confident that it makes sense. You should also convince yourself that if the original lambda term contains no free variables---i.e., is a combinator---then the translation will consist only of S, K, and I (plus parentheses). One other detail: this translation algorithm builds expressions that combine lambdas with combinators. For instance, the translation of our boolean false `\x.\y.y` is `[\x[\y.y]] = [\x.I] = KI`. In the intermediate stage, we have `\x.I`, which mixes combinators in the body of a lambda abstract. It's possible to avoid this if you want to, but it takes some careful thought. See, e.g., Barendregt 1984, page 156.] +[Various, slightly differing translation schemes from combinatorial logic to the lambda calculus are also possible. These generate different metatheoretical correspondences between the two calculii. Consult Hindley and Seldin for details. Also, note that the combinatorial proof theory needs to be strengthened with axioms beyond anything we've here described in order to make [M] convertible with [N] whenever the original lambda-terms M and N are convertible.] + + Let's check that the translation of the false boolean behaves as expected by feeding it two arbitrary arguments: KIXY ~~> IY ~~> Y @@ -334,6 +337,8 @@ So closed beta-plus-eta-normal forms will be syntactically different iff they yi So the proof theory with eta-reduction added is called "extensional," because its notion of normal form makes syntactic identity of closed normal forms coincide with extensional equivalence. +See Hindley and Seldin, Chapters 7-8 and 14, for discussion of what should count as capturing the "extensionality" of these systems, and some outstanding issues. + The evaluation strategy which answers Q1 by saying "reduce arguments first" is known as **call-by-value**. The evaluation strategy which answers Q1 by saying "substitute arguments in unreduced" is known as **call-by-name** or **call-by-need** (the difference between these has to do with efficiency, not semantics).