XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment2.mdwn;h=5d75a855a5a09ef187dcdd9b6e4e22bb11b6ee7a;hp=bcfba912fc6dfd28a4a37df1590370a9b764f4b6;hb=109034aa514a67fcaed0607b4deb4b339f67ab76;hpb=c7978bc281c36093f85f5c478f2844fc124919a5
diff git a/assignment2.mdwn b/assignment2.mdwn
index bcfba912..5d75a855 100644
 a/assignment2.mdwn
+++ b/assignment2.mdwn
@@ 1,3 +1,6 @@
+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

@@ 30,6 +33,36 @@ Reduce to betanormal forms:
`(\x y z. x z (y z)) (\u v. u)`
+Combinatory Logic
+
+
+Reduce the following forms, if possible:
+
+
+ `Kxy`
+
 `KKxy`
+
 `KKKxy`
+
 `SKKxy`
+
 `SIII`
+
 `SII(SII)`
+
+
 Give Combinatory Logic combinators that behave like our boolean functions.
+ You'll need combinators for `true`, `false`, `neg`, `and`, `or`, and `xor`.
+
+
+Using the mapping specified in the lecture notes,
+translate the following lambda terms into combinatory logic:
+
+
+ `\x.x`
+
 `\xy.x`
+
 `\xy.y`
+
 `\xy.yx`
+
 `\x.xx`
+
 `\xyz.x(yz)`
+
 For each translation, how many I's are there? Give a rule for
+ describing what each I corresponds to in the original lambda term.
+
Lists and Numbers

@@ 56,6 +89,7 @@ The `junk` in `extracthead` is what you get back if you evaluate:
As we said, the predecessor and the extracttail functions are harder to define. We'll just give you one implementation of these, so that you'll be able to test and evaluate lambdaexpressions using them in Scheme or OCaml.
predecesor ≡ (\shift n. n shift (makepair zero junk) getsecond) (\pair. pair (\fst snd. makepair (successor fst) fst))
+
extracttail ≡ (\shift lst. lst shift (makepair empty junk) getsecond) (\hd pair. pair (\fst snd. makepair (makelist hd fst) fst))
The `junk` is what you get back if you evaluate:
@@ 72,35 +106,37 @@ For these exercises, assume that `LIST` is the result of evaluating:
(makelist a (makelist b (makelist c (makelist d (makelist e empty)))))
16. What would be the result of evaluating [[Assignment 2 hint 1]]:
+
+ What would be the result of evaluating (see [[hints/Assignment 2 hint]] for a hint):
 LIST makelist empty
+ LIST makelist empty
17. Based on your answer to question 1, how might you implement the **map** function? Expected behavior:
+
 Based on your answer to question 16, how might you implement the **map** function? Expected behavior:

map f LIST <~~> (makelist (f a) (makelist (f b) (makelist (f c) (makelist (f d) (makelist (f e) empty)))))
+ map f LIST <~~> (makelist (f a) (makelist (f b) (makelist (f c) (makelist (f d) (makelist (f e) empty)))))
18. Based on your answer to question 1, how might you implement the **filter** function? The expected behavior is that:
+  Based on your answer to question 16, how might you implement the **filter** function? The expected behavior is that:
 filter f LIST
+ filter f LIST
 should evaluate to a list containing just those of `a`, `b`, `c`, `d`, and `e` such that `f` applied to them evaluates to `true`.
+should evaluate to a list containing just those of `a`, `b`, `c`, `d`, and `e` such that `f` applied to them evaluates to `true`.
4. How would you implement map using the either the version 1 or the version 2 implementation of lists?
+
 What goes wrong when we try to apply these techniques using the version 1 or version 2 implementation of lists?
5. Our version 3 implementation of the numbers are usually called "Church numerals". If `m` is a Church numeral, then `m s z` applies the function `s` to the result of applying `s` to ... to `z`, for a total of *m* applications of `s`, where *m* is the number that `m` represents or encodes.
+
 Our version 3 implementation of the numbers are usually called "Church numerals". If `m` is a Church numeral, then `m s z` applies the function `s` to the result of applying `s` to ... to `z`, for a total of *m* applications of `s`, where *m* is the number that `m` represents or encodes.
 Given the primitive arithmetic functions above, how would you implement the lessthanorequal function? Here is the expected behavior, where `one` abbreviates `succ zero`, and `two` abbreviates `succ (succ zero)`.
+Given the primitive arithmetic functions above, how would you implement the lessthanorequal function? Here is the expected behavior, where `one` abbreviates `succ zero`, and `two` abbreviates `succ (succ zero)`.
 lessthanorequal zero zero ~~> true
 lessthanorequal zero one ~~> true
 lessthanorequal zero two ~~> true
 lessthanorequal one zero ~~> false
 lessthanorequal one one ~~> true
 lessthanorequal one two ~~> true
 lessthanorequal two zero ~~> false
 lessthanorequal two one ~~> false
 lessthanorequal two two ~~> true
+ lessthanorequal zero zero ~~> true
+ lessthanorequal zero one ~~> true
+ lessthanorequal zero two ~~> true
+ lessthanorequal one zero ~~> false
+ lessthanorequal one one ~~> true
+ lessthanorequal one two ~~> true
+ lessthanorequal two zero ~~> false
+ lessthanorequal two one ~~> false
+ lessthanorequal two two ~~> true
 You'll need to make use of the predecessor function, but it's not important to understand how the implementation we gave above works. You can treat it as a black box.
+You'll need to make use of the predecessor function, but it's not essential to understand how the implementation we gave above works. You can treat it as a black box.
+