> **T** is defined to be: `\x y. y x`. (So `C` and `T` both reorder arguments, just in different ways.)
-> **W** is defined to be: `\f x . f x x`. (So `W f` accepts one argument and gives it to `f` twice. What is the meaning of `W multiply`?) <!-- \x. multiply x x === \x. square x -->
+> **W** is defined to be: `\f x . f x x`. (So `W f` accepts one argument and gives it to `f` twice. What is the meaning of `W multiply`?) <!-- \x. multiply x x ≡ \x. square x -->
-> **ω** (that is, lower-case omega) is defined to be: `\x. x x`. Sometimes this combinator is called **M**. It and `W` both duplicate arguments, just in different ways. <!-- L is \uv.u(vv) -->
+> **ω** (that is, lower-case omega) is defined to be: `\x. x x`. Sometimes this combinator is called **M**. It and `W` both duplicate arguments, just in different ways. <!-- L is \hu.h(uu) -->
It's possible to build a logical system equally powerful as the Lambda
SKKX ~~> KX(KX) ~~> X
-So the combinator `SKK` is equivalent to the combinator `I`. (Really, it could be `SKY` for any `Y`.)
+So the combinator `SKK` is equivalent to the combinator `I`. (Really, it could be `SKY` for any `Y`. Hindley & Seldin p. 26 points to discussion later in their book of why it's theoretically more elegant to keep `I` around, anyway.)
These reduction rule have the same status with respect to Combinatory
Logic as beta-reduction and eta-reduction have with respect to
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
-cleaner, and more elegant. If you spent a lot of time working to
-understand the original version, there's good news and bad news. The
-bad news is that things have changed. The good news is that the new
-version described the same mapping as before, but does it in a cleaner
-way. That is, the CL term that a given lambda term maps onto hasn't
-changed, only the details of how that CL term gets computed. Sorry if
-the changeup causes any distress!]
+(*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. We'll endow CL
-with an infinite stock of variable symbols, just like the lambda
-calculus, including `x`, `y`, and `z`. In addition, `S`, `K`, and `I`
-are expressions in CL. Finally, `(XY)` is in CL for any CL
+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, the assumption will be left associativity, so that
-`XYZ == ((XY)Z)`.
+omit parentheses, we assume left associativity, so
+`XYZ ≡ ((XY)Z)`.
-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
+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 for 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
-combinator), its translation in CL will also contain no variables.
+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.
-Assume that for any lambda term T, [T] is the equivalent Combinatory
-Logic term. Then we can define the [.] mapping as follows.
+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])
+ 1. [a] = a
+ 2. [(\aX)] = @a[X]
+ 3. [(XY)] = ([X][Y])
- 4. @aa I
- 5. @aX KX if a is not in X
- 6. @a(XY) S(@aX)(@aY)
+Wait, what is that `@a ...` business? Well, that's another operation on (a variable and) a CL expression, that we can define like this:
-Think of `@aX` as a psuedo-lambda abstract.
+ 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.
It's easy to understand these rules based on what `S`, `K` and `I` do.
temporary psuedo-lambda built from `@` and the original variable.
Rule (3) says that the translation of an application of `X` to `Y` is
-the application of the transtlation of `X` to the translation of `Y`.
+the application of the translation of `X` to the translation of `Y`.
As we'll see, the first three rules sweep through the lambda term,
changing each lambda to an @.
-Rules (4) through (6) tell us how to eliminate all the `@`'s.
+Rules (4) through (7) tell us how to eliminate all the `@`'s.
In rule (4), if we have `@aa`, we need a CL expression that behaves
like the lambda term `\aa`. Obviously, `I` is the right choice here.
constant function returning `X`, which is exactly the behavior
we get by prefixing `K`.
-The easiest way to grasp rule (6) is to consider the following claim:
+Rule (6) should be intuitive; and as we said, we could in principle omit it and just handle such cases under the final rule.
+
+The easiest way to grasp rule (7) is to consider the following claim:
\a(XY) <~~> S(\aX)(\aY)
-To prove it to yourself, just substitute `(\xyz.xz(yz))` in for `S`
+To prove it to yourself, just consider what would happen when each term is applied to an argument `a`. Or substitute `\x y a. x a (y a)` in for `S`
and reduce.
Persuade yourself that if the original lambda term contains no free
-variables --- i.e., is a combinator --- then the translation will
+variables --- i.e., is a Lambda Calculus combinator --- then the translation will
consist only of `S`, `K`, and `I` (plus parentheses).
Various, slightly differing translation schemes from Combinatory Logic to the
-Lambda Calculus are also possible. These generate different metatheoretical
-correspondences between the two calculi. Consult Hindley and Seldin for
+Lambda Calculus are also possible. These generate different meta-theoretical
+correspondences between the two calculi. Consult Hindley & 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
+`[M]` convertible with `[N]` whenever the original lambda-terms `M` and `N` are
convertible. But then, we've been a bit cavalier about giving the full set of
reduction rules for the Lambda Calculus in a similar way. <!-- FIXME -->
Let's see the translation rules in action. We'll start by translating
the combinator we use to represent false:
- [\t\ff]
- == @t[\ff] rule 2
- == @t(@ff) rule 2
- == @tI rule 4
- == KI rule 5
+ [\y (\n n)]
+ == @y [\n n] rule 2
+ == @y (@n n) rule 2
+ == @y I rule 4
+ == KI rule 5
Let's check that the translation of the `false` boolean behaves as expected by feeding it two arbitrary arguments:
to establish that combinators can reverse order, so we set out to
translate the **T** combinator (`\x y. y x`):
- [\x\y(yx)]
- == @x[\y(yx)]
- == @x(@y[(yx)])
- == @x(@y([y][x]))
- == @x(@y(yx))
- == @x(S(@yy)(@yx))
- == @x(SI(@yx))
- == @x(SI(Kx))
- == S (@x(SI)) (@x(Kx))
- == S (K(SI)) (S (@xK) (@xx))
- == S (K(SI)) (S (KK) I)
+ [\x(\y(yx))]
+ == @x[\y(yx)]
+ == @x(@y[yx])
+ == @x(@y([y][x]))
+ == @x(@y(yx))
+ == @x(S(@yy)(@yx))
+ == @x(S I (@yx))
+ == @x(S I (Kx))
+ == S(@x(SI))(@x(Kx))
+ == S (K(SI))(S(@xK)(@xx))
+ == S (K(SI))(S (KK) I)
By now, you should realize that all rules (1) through (3) do is sweep
through the lambda term turning lambdas into @'s.
We can test this translation by seeing if it behaves like the original lambda term does.
-The orginal lambda term lifts its first argument (think of it as reversing the order of its two arguments):
+The original lambda term "lifts" its first argument `x`, in the sense of wrapping it into a "one-tuple" or a package that accepts an operation `y` as a further argument, and then applies `y` to `x`. (Or just think of **T** as reversing the order of its two arguments.)
S (K(SI)) (S(KK)I) X Y ~~>
(K(SI))X ((S(KK)I) X) Y ~~>