-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.
-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, `Ky` 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 not have any lambdas in it, we can be sure that we won't end up applying rule 6 again in an infinite loop.)
+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* This is a different mapping from the Lambda Calculus to Combinatory Logic than we presented in class (and was posted here earlier). It now matches the presentation in Barendregt 1984, and in Hankin Chapter 4 (esp. pp. 61, 65) and in Hindley & Seldin Chapter 2 (esp. p. 26). In some ways this translation is cleaner and more elegant, which is why we're presenting it.)
+
+In order to establish the correspondence, we need to get a bit more
+official about what counts as an expression in CL. Of course, we count
+the primitive combinators `S`, `K`, and `I` as expressions in CL. But
+we will also endow CL with an infinite stock of *variable symbols*, just like the lambda
+calculus, including `x`, `y`, and `z`. Finally, `(XY)` is in CL for any CL
+expressions `X` and `Y`. So examples of CL expressions include
+`x`, `(xy)`, `Sx`, `SK`, `(x(SK))`, `(K(IS))`, and so on. When we
+omit parentheses, we assume left associativity, so
+`XYZ ≡ ((XY)Z)`.
+
+It may seem weird to allow variables in CL. The reason this 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 in CL for those free
+variables. As you might expect, it will turn out that whenever the
+lambda term in question contains *no* free variables (i.e., is a Lambda Calculus
+combinator), its translation in CL will *also* contain no variables, but will
+instead just be made up of primitive combinators and parentheses.
+
+Let's say that for any lambda term T, [T] is the equivalent Combinatory
+Logic term. Then we define the [.] mapping as follows.
+
+ 1. [a] = a
+ 2. [(\aX)] = @a[X]
+ 3. [(XY)] = ([X][Y])
+
+Wait, what is that `@a ...` business? Well, that's another operation on (a variable and) a CL expression, that we can define like this:
+
+ 4. @aa = I
+ 5. @aX = KX if a is not in X
+ 6. @a(Xa) = X if a is not in X
+ 7. @a(XY) = S(@aX)(@aY)
+
+Think of `@aX` as a pseudo-lambda abstract. (Hankin and Barendregt write it as <code>λ*a. X</code>; Hindley & Seldin write it as `[a] X`.) It is possible to omit line 6, and some presentations do, but Hindley & Seldin observe that this "enormously increases" the length of "most" translations.