author barker Sat, 18 Sep 2010 20:07:58 +0000 (16:07 -0400) committer Lambda Wiki Sat, 18 Sep 2010 20:07:58 +0000 (16:07 -0400)
 week2.mdwn patch | blob | history

index 659ffe7..f7bb440 100644 (file)
@@ -140,6 +140,36 @@ Here's an example of the translation:

[\x\y.yx] = [\x[\y.yx]] = [\x.S[\y.y][\y.x]] = [\x.(SI)(Kx)] = S[\x.SI][\x.Kx] = S(K(SI))(S[\x.K][\x.x]) = S(K(SI))(S(KK)I)

+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):
+
+   S(K(SI))(S(KK)I) X Y =
+   (K(SI))X ((S(KK)I) X) Y =
+   SI ((KK)X (IX)) Y =
+   SI (KX) Y =
+   IY (KX)Y =
+   Y X
+
+Viola: the combinator takes any X and Y as arguments, and returns Y applied to X.
+
+Back to linguistic applications: one consequence of the equivalence between the lambda calculus and combinatory
+logic is that anything that can be done by binding variables can just as well be done with combinators.
+This has given rise to a style of semantic analysis called Variable Free Semantics (in addition to
+Szabolcsi's papers, see, for instance,
+Pauline Jacobson's 1999 *Linguistics and Philosophy* paper, `Towards a variable-free Semantics').
+Somewhat ironically, reading strings of combinators is so difficult that most practitioners of variable-free semantics
+express there meanings using the lambda-calculus rather than combinatory logic; perhaps they should call their
+enterprise Free Variable Free Semantics.
+
+A philosophical application: Quine went through a phase in which he developed a variable free logic.
+
+
+
+
+
+
+
+

[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 `\x.\y.y` is `[\x[\y.y]] = [\x.I] = KI`.  In that intermediate stage, we have `\x.I`.  It's possible to avoid this, but it takes some careful thought.  See, e.g., Barendregt 1984, page 156.]