From: jim <jim@web>
Date: Wed, 18 Feb 2015 03:16:07 +0000 (-0500)
Subject: Add old translation scheme back in (commented out), for reference
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=e7e25cbb6455da295bfc0d84f0b243dff3db29dc

Add old translation scheme back in (commented out), for reference
---

diff --git a/topics/week3_combinatory_logic.mdwn b/topics/week3_combinatory_logic.mdwn
index 0ddb4469..8a453cde 100644
--- a/topics/week3_combinatory_logic.mdwn
+++ b/topics/week3_combinatory_logic.mdwn
@@ -165,7 +165,7 @@ combinators in Combinatory Logic can be exactly reproduced by a lambda term.
 
 How about the other direction?  Here is a method for converting an arbitrary
 lambda term into an equivalent Combinatory Logic term using only `S`, `K`, and `I`.
-Besides the intrinsic beauty of this mapping, and the importance of what it
+Besides the intrinsic beauty of such mappings, and the importance of what it
 says about the nature of binding and computation, it is possible to hear an
 echo of computing with continuations in this conversion strategy (though you
 wouldn't be able to hear these echos until we've covered a considerable portion
@@ -175,6 +175,48 @@ used to establish a correspondence between two natural language grammars, one
 of which is based on lambda-like abstraction, the other of which is based on
 Combinatory Logic-like manipulations.
 
+<!--
+Assume that for any lambda term T, [T] is the equivalent Combinatory Logic term.  Then we can define the [.] mapping as follows:
+ 
+    1. [a]               a
+    2. [(M N)]           ([M][N])
+    3. [\a.a]            I
+    4. [\a.M]            K[M]                 when a does not occur free in M
+    5. [\a.(M N)]        S[\a.M][\a.N]
+    6. [\a\b.M]          [\a[\b.M]]
+ 
+If the recursive unpacking of these rules ever direct you to "translate" an `S` or a `K` or an `I`, introduced at an earlier stage of translation, those symbols translate themselves.
+ 
+It's easy to understand these rules based on what `S`, `K` and `I` do.
+ 
+The first rule says that variables are mapped to themselves. If the original lambda expression had no free variables in it, then any such translations will only be temporary. The variable will later get eliminated by the application of other rules. (If the original lambda term *does* have free variables in it, so too will the final Combinatory Logic translation.  Feel free to worry about this, though you should be confident that it makes sense.)
+ 
+The second rule says that the way to translate an application is to translate the first element and the second element separately.
+ 
+The third rule should be obvious.
+ 
+The fourth rule should also be fairly self-evident: since what a lambda term such as `\x. y` does it throw away its first argument and return `y`, that's exactly what the Combinatory Logic translation should do.  And indeed, `K y` is a function that throws away its argument and returns `y`.
+
+The fifth rule deals with an abstract whose body is an application: the `S` combinator takes its next argument (which will fill the role of the original variable a) and copies it, feeding one copy to the translation of `\a. M`, and the other copy to the translation of `\a. N`.  This ensures that any free occurrences of a inside `M` or `N` will end up taking on the appropriate value.
+
+Finally, the last rule says that if the body of an abstract is itself an abstract, translate the inner abstract first, and then do the outermost.  (Since the translation of `[\b. M]` will have eliminated any inner lambdas, we can be sure that we won't end up applying rule 6 again in an infinite loop.)
+ 
+Persuade 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).
+
+(Fussy note: this translation algorithm builds intermediate expressions that combine lambdas with primitive 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 has a combinator 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.)
+
+...
+Here's a more elaborate example of the translation.  Let's say we want to establish that combinators can reverse order, so we use the **T** combinator (`\x y. y x`):
+
+    [\x y. y x] =
+    [\x [\y. y x]] =
+    [\x. S [\y. y] [\y. x]] = 
+    [\x. (SI) (K x)] =
+    S [\x. SI] [\x. K x] =
+    S (K(SI)) (S [\x. K] [\x. x]) =
+    S (K(SI)) (S(KK)I)
+-->
+
 [WARNING: the mapping from the lambda calculus to Combinatory Logic
 has been changed since the class in which it was presented.  It now
 matches the presentation in Barendregt.  The revised version is
@@ -196,7 +238,7 @@ expressions `X` and `Y`.  So examples of CL expressions include
 omit parentheses, the assumption will be left associativity, so that
 `XYZ == ((XY)Z)`.
 
-It may seem wierd to allow variables in CL.  The reason that is
+It may seem weird to allow variables in CL.  The reason that is
 necessary is because we're trying to show that every lambda term can
 be translated into an equivalent CL term.  Since some lambda terms
 contain free variables, we need to provide a translation for free