start linking to lambda calculators
[lambda.git] / week2.mdwn
index 0aa23fc..d1d02fa 100644 (file)
@@ -17,7 +17,7 @@ One can't just rename variables freely. (a) and (b) are different than what's ex
 </OL>
 
 
-Substituting `y` into the body of `(\x. \z. z x)` is unproblematic:
+Substituting `y` into the body of (a) `(\x. \z. z x)` is unproblematic:
 
        (\x. \z. z x) y ~~> \z. z y
 
@@ -27,58 +27,49 @@ To reduce (b), then, we need to be careful to that no free variables in what we'
 
 In practical terms, you'd just replace (b) with (a) and do the unproblematic substitution into (a).
 
-What attitude should we have to this?
+How should we think about the explanation and justification for that practical procedure?
 
-One way to think of it is to identify expressions of the lambda calculus with particular alphabetic sequences. Then (a) and (b) would be distinct expressions, and we'd have to explicitly articulate a rule permitting you to do the kind of variable-renaming that would take you from (a) to (b) (or vice versa). This kind of renaming is called "alpha-conversion."
+One way to think about things here is to identify expressions of the lambda calculus with *particular alphabetic sequences*. Then (a) and (b) would be distinct expressions, and we'd have to have an explicit rule permitting us to do the kind of variable-renaming that takes us from (a) to (b) (or vice versa). This kind of renaming is called "alpha-conversion." Look in the standard treatments of the lambda calculus for detailed discussion of this.
 
-Another way to think of it is to identify expressions not with particular alphabetic sequences, but rather with classes of alphabetic sequences, which stand to each other in the way that (a) and (b) do. That's the way we'll talk. We say that (a) and (b) are just typographically different notations for a *single* lambda formula. As we'll say, the lambda formula written with (a) and the lambda formula written with (b) are literally syntactically identical.
+Another way to think of it is to identify expressions not with particular alphabetic sequences, but rather with *classes* of alphabetic sequences, which stand to each other in the way that (a) and (b) do. That's the way we'll talk. We say that (a) and (b) are just typographically different notations for a *single* lambda formula. As we'll say, the lambda formula written with (a) and the lambda formula written with (b) are literally syntactically identical.
 
 A third way to think is to identify the lambda formula not with classes of alphabetic sequences, but rather with abstract structures that we might draw like this:
 
 <pre><code>
-       &lambda; ... ___ ...
-       ^      |
-       |______|
+       (&lambda;. &lambda;. _ _) y
+     ^  ^  | |
+     |  |__| |
+     |_______|
 </code></pre>
 
 Here there are no bound variables, but there are *bound positions*. We can regard formula like (a) and (b) as just helpfully readable ways to designate these abstract structures.
 
 A version of this last approach is known as **de Bruijn notation** for the lambda calculus.
 
-It doesn't matter which of these approaches one takes; the logical properties of the systems are exactly the same. It just affects the particulars of how one states the rules for substitution, and so on. And whether one talks about expressions being literally "syntactically identical," or whether one instead counts them as "equivalent modulu alpha-conversion."
+It doesn't seem to matter which of these approaches one takes; the logical properties of the systems are exactly the same. It just affects the particulars of how one states the rules for substitution, and so on. And whether one talks about expressions being literally "syntactically identical," or whether one instead counts them as "equivalent modulu alpha-conversion."
 
-(In a bit, we'll discuss other systems that lack variables. Those systems will not just lack variables in the sense that de Bruijn notation does; they will furthermore lack any notion of a bound position.)
+(Linguistic trivia: however, some linguistic discussions do suppose that alphabetic variance has important linguistic consequences; see Ivan Sag's dissertation.)
 
+In a bit, we'll discuss other systems that lack variables. Those systems will not just lack variables in the sense that de Bruijn notation does; they will furthermore lack any notion of a bound position.
 
 
 Syntactic equality, reduction, convertibility
 =============================================
 
-Define T to be `(\x. x y) z`. Then T and `(\x. x y) z` are syntactically equal, and we're counting them as syntactically equal to `(\z. z y) z` as well, which we will write as:
+Define N to be `(\x. x y) z`. Then N and `(\x. x y) z` are syntactically equal, and we're counting them as syntactically equal to `(\z. z y) z` as well, which we will write as:
 
-<pre><code>T &equiv; (\x. x y) z &equiv; (\z. z y) z
+<pre><code>N &equiv; (\x. x y) z &equiv; (\z. z y) z
 </code></pre>
 
-[Fussy note: the justification for counting `(\x. x y) z` as
-equivalent to `(\z. z y) z` is that when a lambda binds a set of
-occurrences, it doesn't matter which variable serves to carry out the
-binding.  Either way, the function does the same thing and means the
-same thing.  
-Linguistic trivia: some linguistic discussions suppose that alphabetic variance 
-has important linguistic consequences (notably Ivan Sag's dissertation).
-Look in the standard treatments for discussions of alpha
-equivalence for more detail.  Also, as mentioned below, one of the intriguing 
-properties of Combinatory Logic is that alpha equivalence is not an issue.]
-
 This:
 
-       T ~~> z y
+       N ~~> z y
 
-means that T beta-reduces to `z y`. This:
+means that N beta-reduces to `z y`. This:
 
-       M <~~> T
+       M <~~> N
 
-means that M and T are beta-convertible, that is, that there's something they both reduce to in zero or more steps.
+means that M and N are beta-convertible, that is, that there's something they both reduce to in zero or more steps.
 
 Combinators and Combinatorial Logic
 ===================================
@@ -150,7 +141,7 @@ The reduction rule for K is also straightforward:
 That is, K throws away its second argument.  The reduction rule for S can be constructed by examining 
 the defining lambda term:
 
-    S = \fgx.fx(gx)
+<pre><code>S &equiv; \fgx.fx(gx)</code></pre>
 
 S takes three arguments, duplicates the third argument, and feeds one copy to the first argument and the second copy to the second argument.  So:
 
@@ -164,7 +155,7 @@ We can use these rules to compute without resorting to beta reduction.  For inst
 
 So the combinator `SKK` is equivalent to the combinator I.
 
-Combinatory Logic is what you have when you choose a set of combinators and regulate their behavior with a set of reduction rules.  The most common system uses S, K, and I as defined here.
+Combinatory Logic is what you have when you choose a set of combinators and regulate their behavior with a set of reduction rules. As we said, the most common system uses S, K, and I as defined here.
 
 ###The equivalence of the untyped lambda calculus and combinatory logic###
 
@@ -192,27 +183,30 @@ 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
 
 Throws away the first argument, returns the second argument---yep, it works.
 
-Here's a more elaborate example of the translation.  The goal is to establish that combinators can reverse order, so we use the T combinator, where `T = \x\y.yx`:
+Here's a more elaborate example of the translation.  The goal is to establish that combinators can reverse order, so we use the **T** combinator, where  <code>T &equiv; \x\y.yx</code>:
 
     [\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
+       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 (KXY) ~~>
+       Y X
 
-Viola: the combinator takes any X and Y as arguments, and returns Y applied to X.
+Voil&agrave;: the combinator takes any X and Y as arguments, and returns Y applied to X.
 
 One very nice property of combinatory logic is that there is no need to worry about alphabetic variance, or
 variable collision---since there are no (bound) variables, there is no possibility of accidental variable capture, 
@@ -224,35 +218,33 @@ Back to linguistic applications: one consequence of the equivalence between the
 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').  
+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
+express their 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.
+A philosophical connection: Quine went through a phase in which he developed a variable free logic.
 
-  Quine, Willard. 1960.  Variables explained away.  {\it Proceedings of                                                                                                                                
-  the American Philosophical Society}.  Volume 104: 343--347.  Also in
-  W.~V.~Quine.  1960. {\it Selected Logical Papers}.  Random House: New
+  Quine, Willard. 1960. "Variables explained away" <cite>Proceedings of the American Philosophical Society</cite>.  Volume 104: 343--347.  Also in W. V. Quine.  1960. <cite>Selected Logical Papers</cite>.  Random House: New
   York.  227--235.
 
 The reason this was important to Quine is similar to the worries that Jim was talking about
-in the first class in which using non-referring expressions such as Santa Clause might commit 
-one to believing in non-existant things.  Quine's slogan was that `to be is to be the value of a variable'.
+in the first class in which using non-referring expressions such as Santa Claus might commit 
+one to believing in non-existant things.  Quine's slogan was that "to be is to be the value of a variable."
 What this was supposed to mean is that if and only if an object could serve as the value of some variable, we 
 are committed to recognizing the existence of that object in our ontology.
 Obviously, if there ARE no variables, this slogan has to be rethought.
 
 Quine did not appear to appreciate that Shoenfinkel had already invented combinatory logic, though
 he later wrote an introduction to Shoenfinkel's key paper reprinted in Jean
-van Heijenoort (ed) 1967 *From Frege to Goedel,                                                                                                                               
-  a source book in mathematical logic, 1879--1931*.
+van Heijenoort (ed) 1967 <cite>From Frege to Goedel, a source book in mathematical logic, 1879--1931</cite>.
+
 Cresswell has also developed a variable-free approach of some philosophical and linguistic interest
 in two books in the 1990's.
 
 A final linguistic application: Steedman's Combinatory Categorial Grammar, where the "Combinatory" is 
-from combinatory logic (see especially his 2000 book, *The Syntactic Process*).  Steedman attempts to build
-a syntax/semantics interface using a small number of combinators, including T = \xy.yx, B = \fxy.f(xy),
+from combinatory logic (see especially his 2000 book, <cite>The Syntactic Processs</cite>).  Steedman attempts to build
+a syntax/semantics interface using a small number of combinators, including T &equiv; `\xy.yx`, B &equiv; `\fxy.f(xy)`,
 and our friend S.  Steedman used Smullyan's fanciful bird 
 names for the combinators, Thrush, Bluebird, and Starling.
 
@@ -329,20 +321,24 @@ will eta-reduce by n steps to:
 
        \x. M
 
+When we add eta-reduction to our proof system, we end up reconstruing the meaning of `~~>` and `<~~>` and "normal form", all in terms that permit eta-reduction as well. Sometimes these expressions will be annotated to indicate whether only beta-reduction is allowed (<code>~~><sub>&beta;</sub></code>) or whether both beta- and eta-reduction is allowed (<code>~~><sub>&beta;&eta;</sub></code>).
+
 The logical system you get when eta-reduction is added to the proof system has the following property:
 
 >      if `M`, `N` are normal forms with no free variables, then <code>M &equiv; N</code> iff `M` and `N` behave the same with respect to every possible sequence of arguments.
 
-That is, when `M` and `N` are (closed normal forms that are) syntactically distinct, there will always be some sequences of arguments <code>L<sub>1</sub>, ..., L<sub>n</sub></code> such that:
+This implies that, when `M` and `N` are (closed normal forms that are) syntactically distinct, there will always be some sequences of arguments <code>L<sub>1</sub>, ..., L<sub>n</sub></code> such that:
 
 <pre><code>M L<sub>1</sub> ... L<sub>n</sub> x y ~~> x
 N L<sub>1</sub> ... L<sub>n</sub> x y ~~> y
 </code></pre>
 
-That is, closed normal forms that are not just beta-reduced but also fully eta-reduced, will be syntactically different iff they yield different values for some arguments. That is, iff their extensions differ.
+So closed beta-plus-eta-normal forms will be syntactically different iff they yield different values for some arguments. That is, iff their extensions differ.
 
 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).
 
@@ -441,6 +437,7 @@ But is there any method for doing this in general---for telling, of any given co
 
 *      [Scooping the Loop Snooper](http://www.cl.cam.ac.uk/teaching/0910/CompTheory/scooping.pdf), a proof of the undecidability of the halting problem in the style of Dr Seuss by Geoffrey K. Pullum
 
+Interestingly, Church also set up an association between the lambda calculus and first-order predicate logic, such that, for arbitrary lambda formulas `M` and `N`, some formula would be provable in predicate logic iff `M` and `N` were convertible. So since the right-hand side is not decidable, questions of provability in first-order predicate logic must not be decidable either. This was the first proof of the undecidability of first-order predicate logic.
 
 
 ##[[Lists and Numbers]]##