X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week2.mdwn;h=49a7e8d5af7632592a80b80b6351058bb97c1a7c;hp=720ac1d81faaef9f9b6cfbf518bd730b0f62d05c;hb=8851b9a8232b479f166c711beae3cc6a665b047c;hpb=43e6cb0a08452826d9b0757f16e30e117df894b8 diff --git a/week2.mdwn b/week2.mdwn index 720ac1d8..49a7e8d5 100644 --- a/week2.mdwn +++ b/week2.mdwn @@ -1,27 +1,75 @@ +[[!toc]] + +Substitution and Alpha-Conversion +================================= + +Intuitively, (a) and (b) express the application of the same function to the argument `y`: + +
+
1. (\x. \z. z x) y +
2. (\x. \y. y x) y +
+ +One can't just rename variables freely. (a) and (b) are different than what's expressed by: + +
+
1. (\z. (\z. z z) y +
+ + +Substituting `y` into the body of (a) `(\x. \z. z x)` is unproblematic: + + (\x. \z. z x) y ~~> \z. z y + +However, with (b) we have to be more careful. If we just substituted blindly, then we might take the result to be `\y. y y`. But this is the self-application function, not the function which accepts an arbitrary argument and applies that argument to the free variable `y`. In fact, the self-application function is what (c) reduces to. So if we took (b) to reduce to `\y. y y`, we'd wrongly be counting (b) to be equivalent to (c), instead of (a). + +To reduce (b), then, we need to be careful to that no free variables in what we're substituting in get captured by binding λs that they shouldn't be captured by. + +In practical terms, you'd just replace (b) with (a) and do the unproblematic substitution into (a). + +How should we think about the explanation and justification for that practical procedure? + +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. + +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: + +

+	(λ. λ. _ _) y
+     ^  ^  | |
+     |  |__| |
+     |_______|
+
+ +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 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." + +(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: -
T ≡ (\x. x y) z ≡ (\z. z y) z
+
N ≡ (\x. x y) z ≡ (\z. z y) z

-[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. Look in the standard treatments for discussions of alpha -equivalence for more detail.] - 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 =================================== @@ -30,16 +78,22 @@ Lambda expressions that have no free variables are known as **combinators**. Her > **I** is defined to be `\x x` -> **K** is defined to be `\x y. x`, That is, it throws away its +> **K** is defined to be `\x y. x`. That is, it throws away its second argument. So `K x` is a constant function from any (further) argument to `x`. ("K" for "constant".) Compare K - to our definition of **true**. + to our definition of `true`. -> **get-first** was our function for extracting the first element of an ordered pair: `\fst snd. fst`. Compare this to **K** and **true** as well. +> **get-first** was our function for extracting the first element of an ordered pair: `\fst snd. fst`. Compare this to K and `true` as well. -> **get-second** was our function for extracting the second element of an ordered pair: `\fst snd. snd`. Compare this to our definition of **false**. +> **get-second** was our function for extracting the second element of an ordered pair: `\fst snd. snd`. Compare this to our definition of `false`. -> **ω** is defined to be: `\x. x x` +> **B** is defined to be: `\f g x. f (g x)`. (So `B f g` is the composition `\x. f (g x)` of `f` and `g`.) + +> **C** is defined to be: `\f x y. f y x`. (So `C f` is a function like `f` except it expects its first two arguments in swapped order.) + +> **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`?) + +> **ω** (that is, lower-case omega) is defined to be: `\x. x x` It's possible to build a logical system equally powerful as the lambda calculus (and readily intertranslatable with it) using just combinators, considered as atomic operations. Such a language doesn't have any variables in it: not just no free variables, but no variables at all. @@ -47,23 +101,154 @@ One can do that with a very spare set of basic combinators. These days the stand There are some well-known linguistic applications of Combinatory Logic, due to Anna Szabolcsi, Mark Steedman, and Pauline Jacobson. -Szabolcsi supposed that the meanings of certain expressions could be -insightfully expressed in the form of combinators. A couple more -combinators: - - **C** is defined to be: `\f x y. f y x` [swap arguments] - - **W** is defined to be: `\f x . f x x` [duplicate argument] +They claim that natural language semantics is a combinatory system: that every +natural language denotation is a combinator. For instance, Szabolcsi argues that reflexive pronouns are argument duplicators. -![test](./szabolcsi-reflexive.jpg) +![reflexive](http://lambda.jimpryor.net/szabolcsi-reflexive.jpg) + +Notice that the semantic value of *himself* is exactly `W`. +The reflexive pronoun in direct object position combines with the transitive verb. The result is an intransitive verb phrase that takes a subject argument, duplicates that argument, and feeds the two copies to the transitive verb meaning. + +Note that `W <~~> S(CI)`: + +
S(CI) ≡
+S((\fxy.fyx)(\x.x)) ~~>
+S(\xy.(\x.x)yx) ~~>
+S(\xy.yx) ≡
+(\fgx.fx(gx))(\xy.yx) ~~>
+\gx.(\xy.yx)x(gx) ~~>
+\gx.(gx)x ≡
+W
+ +Ok, here comes a shift in thinking. Instead of defining combinators as equivalent to certain lambda terms, +we can define combinators by what they do. If we have the I combinator followed by any expression X, +I will take that expression as its argument and return that same expression as the result. In pictures, + + IX ~~> X + +Thinking of this as a reduction rule, we can perform the following computation + + II(IX) ~~> IIX ~~> IX ~~> X + +The reduction rule for K is also straightforward: + + KXY ~~> X + +That is, K throws away its second argument. The reduction rule for S can be constructed by examining +the defining lambda term: -![Szabolcsi's analysis of *himself* as the duplicator combinator](szabolcsi-reflexive.jpg) +
S ≡ \fgx.fx(gx)