assignment2.mdwn

   1 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.
   2
   3
   4 More Lambda Practice
   5 --------------------
   6
   7 Insert all the implicit `( )`s and <code>&lambda;</code>s into the following abbreviated expressions:
   8
   9 1.      `x x (x x x) x`
  10 2.      `v w (\x y. v x)`
  11 3.      `(\x y. x) u v`
  12 4.      `w (\x y z. x z (y z)) u v`
  13
  14 Mark all occurrences of `x y` in the following terms:
  15
  16 <OL start=5>
  17 <LI>`(\x y. x y) x y`
  18 <LI>`(\x y. x y) (x y)`
  19 <LI> `\x y. x y (x y)`
  20 </OL>
  21
  22 Reduce to beta-normal forms:
  23
  24 <OL start=8>
  25 <LI>`(\x. x (\y. y x)) (v w)`
  26 <LI>`(\x. x (\x. y x)) (v w)`
  27 <LI>`(\x. x (\y. y x)) (v x)`
  28 <LI>`(\x. x (\y. y x)) (v y)`
  29
  30 <LI>`(\x y. x y y) u v`
  31 <LI>`(\x y. y x) (u v) z w`
  32 <LI>`(\x y. x) (\u u)`
  33 <LI>`(\x y z. x z (y z)) (\u v. u)`
  34 </OL>
  35
  36 Combinatory Logic
  37 -----------------
  38
  39 Reduce the following forms, if possible:
  40
  41 1.   Kxy
  42 2.   KKxy
  43 3.   KKKxy
  44 4.   SKKxy
  45 5.   SIII
  46 6.   SII(SII)
  47
  48 * Give Combinatory Logic combinators that behave like our boolean functions.
  49   You'll need combinators for true, false, neg, and, or, and xor.
  50
  51 Using the mapping specified in the lecture notes,
  52 translate the following lambda terms into combinatory logic:
  53
  54 1.   \x.x
  55 2.   \xy.x
  56 3.   \xy.y
  57 4.   \xy.yx
  58 5.   \x.xx
  59 6.   \xyz.x(yz)
  60
  61 *  For each translation, how many I's are there?  Give a rule for
  62    describing what each I corresponds to in the original lambda term.
  63
  64 Lists and Numbers
  65 -----------------
  66
  67 We'll assume the "Version 3" implementation of lists and numbers throughout. So:
  68
  69 <pre><code>zero &equiv; \s z. z
  70 succ &equiv; \n. \s z. s (n s z)
  71 iszero &equiv; \n. n (\x. false) true
  72 add &equiv; \m \n. m succ n
  73 mul &equiv; \m \n. \s. m (n s)</code></pre>
  74
  75 And:
  76
  77 <pre><code>empty &equiv; \f z. z
  78 make-list &equiv; \hd tl. \f z. f hd (tl f z)
  79 isempty &equiv; \lst. lst (\hd sofar. false) true
  80 extract-head &equiv; \lst. lst (\hd sofar. hd) junk</code></pre>
  81
  82 The `junk` in `extract-head` is what you get back if you evaluate:
  83
  84         extract-head empty
  85
  86 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.
  87
  88 <pre><code>predecesor &equiv; (\shift n. n shift (make-pair zero junk) get-second) (\pair. pair (\fst snd. make-pair (successor fst) fst))
  89
  90 extract-tail &equiv; (\shift lst. lst shift (make-pair empty junk) get-second) (\hd pair. pair (\fst snd. make-pair (make-list hd fst) fst))</code></pre>
  91
  92 The `junk` is what you get back if you evaluate:
  93
  94         predecessor zero
  95
  96         extract-tail empty
  97
  98 Alternatively, we might reasonably declare the predecessor of zero to be zero (this is a common construal of the predecessor function in discrete math), and the tail of the empty list to be the empty list.
  99
 100
 101 For these exercises, assume that `LIST` is the result of evaluating:
 102
 103         (make-list a (make-list b (make-list c (make-list d (make-list e empty)))))
 104
 105
 106 <OL start=16>
 107 <LI>What would be the result of evaluating (see [[Assignment 2 hint 1]] for a hint):
 108
 109         LIST make-list empty
 110
 111 <LI>Based on your answer to question 16, how might you implement the **map** function? Expected behavior:
 112
 113         map f LIST <~~> (make-list (f a) (make-list (f b) (make-list (f c) (make-list (f d) (make-list (f e) empty)))))
 114
 115 <LI>Based on your answer to question 16, how might you implement the **filter** function? The expected behavior is that:
 116
 117         filter f LIST
 118
 119 should evaluate to a list containing just those of `a`, `b`, `c`, `d`, and `e` such that `f` applied to them evaluates to `true`.
 120
 121 <LI>What goes wrong when we try to apply these techniques using the version 1 or version 2 implementation of lists?
 122
 123 <LI>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.
 124
 125 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)`.
 126
 127         less-than-or-equal zero zero ~~> true
 128         less-than-or-equal zero one ~~> true
 129         less-than-or-equal zero two ~~> true
 130         less-than-or-equal one zero ~~> false
 131         less-than-or-equal one one ~~> true
 132         less-than-or-equal one two ~~> true
 133         less-than-or-equal two zero ~~> false
 134         less-than-or-equal two one ~~> false
 135         less-than-or-equal two two ~~> true
 136
 137 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.
 138 </OL>
 139