From: Jim Pryor
Date: Sat, 18 Sep 2010 19:23:26 +0000 (-0400)
Subject: week2 tweaks
X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=commitdiff_plain;h=846488bfeb5f20947b983de2c3a1faca00d63b3a
week2 tweaks
Signed-off-by: Jim Pryor
---
diff --git a/week2.mdwn b/week2.mdwn
index 3b4e7eec..371435d4 100644
--- a/week2.mdwn
+++ b/week2.mdwn
@@ -33,11 +33,11 @@ Lambda expressions that have no free variables are known as **combinators**. Her
> **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`.
> **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`.)
@@ -49,7 +49,7 @@ Lambda expressions that have no free variables are known as **combinators**. Her
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.
-One can do that with a very spare set of basic combinators. These days the standard base is just three combinators: **K** and **I** from above, and also one more, **S**, which behaves the same as the lambda expression `\f g x. f x (g x)`. behaves. But it's possible to be even more minimalistic, and get by with only a single combinator. (And there are different single-combinator bases you can choose.)
+One can do that with a very spare set of basic combinators. These days the standard base is just three combinators: K and I from above, and also one more, **S**, which behaves the same as the lambda expression `\f g x. f x (g x)`. behaves. But it's possible to be even more minimalistic, and get by with only a single combinator. (And there are different single-combinator bases you can choose.)
There are some well-known linguistic applications of Combinatory
Logic, due to Anna Szabolcsi, Mark Steedman, and Pauline Jacobson.
@@ -62,7 +62,7 @@ duplicators.
![reflexive](http://lambda.jimpryor.net/szabolcsi-reflexive.jpg)
-Notice that the semantic value of *himself* is exactly W.
+Notice that the semantic value of *himself* is exactly `W`.
The reflexive pronoun in direct object position combines first with the transitive verb (through compositional magic we won't go into here). 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)`:
@@ -100,14 +100,14 @@ S takes three arguments, duplicates the third argument, and feeds one copy to th
SFGX ~~> FX(GX)
If the meaning of a function is nothing more than how it behaves with respect to its arguments,
-these reduction rules capture the behavior of the combinators S,K, and I completely.
-We can use these rules to compute without resorting to beta reduction. For instance, we can show how the I combinator is equivalent to a certain crafty combination of S's and K's:
+these reduction rules capture the behavior of the combinators S, K, and I completely.
+We can use these rules to compute without resorting to beta reduction. For instance, we can show how the I combinator is equivalent to a certain crafty combination of Ss and Ks:
SKKX ~~> KX(KX) ~~> X
-So the combinator SKK is equivalent to the combinator I.
+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. The most common system uses S, K, and I as defined here.
###The equivalence of the untyped lambda calculus and combinatory logic###