X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week2.mdwn;h=659ffe75458b450e7a262ad21a6cd09f3667d6e7;hp=47a46667d21e675ff4aaab03bffa80a63180df87;hb=c03eda2ac73fee36b28ef3f81520c688f9cc8a3c;hpb=7743c45c8440825886fa216aadf1f788b1b2783e diff --git a/week2.mdwn b/week2.mdwn index 47a46667..659ffe75 100644 --- a/week2.mdwn +++ b/week2.mdwn @@ -36,11 +36,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`.) @@ -48,7 +48,7 @@ Lambda expressions that have no free variables are known as **combinators**. Her > **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`?) -> **ω** is defined to be: `\x. x x` +> **ω** (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. @@ -65,7 +65,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)`: @@ -103,14 +103,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###