X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=assignment2.mdwn;h=5d75a855a5a09ef187dcdd9b6e4e22bb11b6ee7a;hp=04c3a282de2d35b47efc56d066d6a1291a49acc8;hb=060198e29e2a13552ee64c1e489eea555c8b1cae;hpb=f6ffcb0a876f3e27d478217390ff2874c6b12dfb diff --git a/assignment2.mdwn b/assignment2.mdwn index 04c3a282..5d75a855 100644 --- a/assignment2.mdwn +++ b/assignment2.mdwn @@ -1,3 +1,72 @@ +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 +-------------------- + +Insert all the implicit `( )`s and λs into the following abbreviated expressions: + +1. `x x (x x x) x` +2. `v w (\x y. v x)` +3. `(\x y. x) u v` +4. `w (\x y z. x z (y z)) u v` + +Mark all occurrences of `x y` in the following terms: + +
    +
  1. `(\x y. x y) x y` +
  2. `(\x y. x y) (x y)` +
  3. `\x y. x y (x y)` +
+ +Reduce to beta-normal forms: + +
    +
  1. `(\x. x (\y. y x)) (v w)` +
  2. `(\x. x (\x. y x)) (v w)` +
  3. `(\x. x (\y. y x)) (v x)` +
  4. `(\x. x (\y. y x)) (v y)` + +
  5. `(\x y. x y y) u v` +
  6. `(\x y. y x) (u v) z w` +
  7. `(\x y. x) (\u u)` +
  8. `(\x y z. x z (y z)) (\u v. u)` +
+ +Combinatory Logic +----------------- + +Reduce the following forms, if possible: + +
    +
  1. `Kxy` +
  2. `KKxy` +
  3. `KKKxy` +
  4. `SKKxy` +
  5. `SIII` +
  6. `SII(SII)` + +
  7. 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: + +
    +
  1. `\x.x` +
  2. `\xy.x` +
  3. `\xy.y` +
  4. `\xy.yx` +
  5. `\x.xx` +
  6. `\xyz.x(yz)` +
  7. 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 +----------------- + We'll assume the "Version 3" implementation of lists and numbers throughout. So: 
zero ≡ \s z. z
@@ -20,6 +89,7 @@ The `junk` in `extract-head` is what you get back if you evaluate:
 As we said, the predecessor and the extract-tail functions are harder to define. We'll just give you one implementation of these, so that you'll be able to test and evaluate lambda-expressions using them in Scheme or OCaml.
 
 
predecesor ≡ (\shift n. n shift (make-pair zero junk) get-second) (\pair. pair (\fst snd. make-pair (successor fst) fst))
+
 extract-tail ≡ (\shift lst. lst shift (make-pair empty junk) get-second) (\hd pair. pair (\fst snd. make-pair (make-list hd fst) fst))

 
 The `junk` is what you get back if you evaluate:
@@ -36,35 +106,37 @@ For these exercises, assume that `LIST` is the result of evaluating:
 	(make-list a (make-list b (make-list c (make-list d (make-list e empty)))))
 
 
-1.	What would be the result of evaluating:
+
    
+
  1. What would be the result of evaluating (see [[hints/Assignment 2 hint]] for a hint):
 
-		LIST make-list empty
+	LIST make-list empty
 
-2.	Based on your answer to question 1, how might you implement the **map** function? Expected behavior:
+
  2. Based on your answer to question 16, how might you implement the **map** function? Expected behavior:
 
-	
    map f LIST <~~> (make-list (f a) (make-list (f b) (make-list (f c) (make-list (f d) (make-list (f e) empty)))))
    
+	map f LIST <~~> (make-list (f a) (make-list (f b) (make-list (f c) (make-list (f d) (make-list (f e) empty)))))
 
-3.	Based on your answer to question 1, how might you implement the **filter** function? The expected behavior is that:
+
  3. 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?
+
  4. 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.
+
  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.
 
-	Given the primitive arithmetic functions above, how would you implement the less-than-or-equal 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 less-than-or-equal function? Here is the expected behavior, where `one` abbreviates `succ zero`, and `two` abbreviates `succ (succ zero)`.
 
-		less-than-or-equal zero zero ~~> true
-		less-than-or-equal zero one ~~> true
-		less-than-or-equal zero two ~~> true
-		less-than-or-equal one zero ~~> false
-		less-than-or-equal one one ~~> true
-		less-than-or-equal one two ~~> true
-		less-than-or-equal two zero ~~> false
-		less-than-or-equal two one ~~> false
-		less-than-or-equal two two ~~> true
+	less-than-or-equal zero zero ~~> true
+	less-than-or-equal zero one ~~> true
+	less-than-or-equal zero two ~~> true
+	less-than-or-equal one zero ~~> false
+	less-than-or-equal one one ~~> true
+	less-than-or-equal one two ~~> true
+	less-than-or-equal two zero ~~> false
+	less-than-or-equal two one ~~> false
+	less-than-or-equal 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.
+