consistently use k for continuations
[lambda.git] / assignment2.mdwn
index 85f63f3..5d75a85 100644 (file)
@@ -1,4 +1,4 @@
-For these assignments, you'll probably want to use a "lambda calculator" to check your work. This accepts any grammatical lambda expression and reduces it to normal form, when possible. See the page on [[using the programming languages]] for instructions and links about setting this up.
+For these assignments, you'll probably want to use our [[lambda evaluator]] to check your work. This accepts any grammatical lambda expression and reduces it to normal form, when possible.
 
 
 More Lambda Practice
@@ -33,6 +33,36 @@ Reduce to beta-normal forms:
 <LI>`(\x y z. x z (y z)) (\u v. u)`
 </OL>
 
+Combinatory Logic
+-----------------
+
+Reduce the following forms, if possible:
+
+<OL start=16>
+<LI> `Kxy`
+<LI> `KKxy`
+<LI> `KKKxy`
+<LI> `SKKxy`
+<LI> `SIII`
+<LI> `SII(SII)`
+
+<LI> Give Combinatory Logic combinators that behave like our boolean functions.
+  You'll need combinators for `true`, `false`, `neg`, `and`, `or`, and `xor`.
+</OL>
+
+Using the mapping specified in the lecture notes,
+translate the following lambda terms into combinatory logic:
+
+<OL start=23>
+<LI> `\x.x`
+<LI> `\xy.x`
+<LI> `\xy.y`
+<LI> `\xy.yx`
+<LI> `\x.xx`
+<LI> `\xyz.x(yz)`
+<LI> For each translation, how many I's are there?  Give a rule for 
+   describing what each I corresponds to in the original lambda term.
+</OL>
 
 Lists and Numbers
 -----------------
@@ -77,7 +107,7 @@ For these exercises, assume that `LIST` is the result of evaluating:
 
 
 <OL start=16>
-<LI>What would be the result of evaluating (see [[Assignment 2 hint 1]] for a hint):
+<LI>What would be the result of evaluating (see [[hints/Assignment 2 hint]] for a hint):
 
        LIST make-list empty