extract closures discussion to separate page
[lambda.git] / exercises / assignment3_answers.mdwn
1 ## Lists and List Comprehensions
2
3 1.  In Kapulet, what does `[ [x, 2*x] | x from [1, 2, 3] ]` evaluate to?
4
5     >     [[1,2], [2,4], [3,6]]
6
7 2.  What does `[ 10*x + y | y from [4], x from [1, 2, 3] ]` evalaute to?
8
9     >     [14, 24, 34]
10
11 3.  Using either Kapulet's or Haskell's list comprehension syntax, write an expression that transforms `[3, 1, 0, 2]` into `[3, 3, 3, 1, 2, 2]`. [[Here is a hint|assignment3 hint1]], if you need it.
12
13     >     letrec
14     >       dup (n, x) = case n of
15     >                      0 then [];
16     >                      _ then x & dup (n-1, x)
17     >                    end;
18     >       # you can assume join is already defined, but we'll redefine it here anyway
19     >       join xss   = fold_right ((&&), []) xss    # we help ourselves to &&/append
20     >     in join [dup(x, x) | x from [3, 1, 0, 2]]
21
22 4.  Last week you defined `head` in terms of `fold_right`. Your solution should be straightforwardly translatable into one that uses our proposed right-fold encoding of lists in the Lambda Calculus. Now define `empty?` in the Lambda Calculus. (It should require only small modifications to your solution for `head`.)
23
24     >     let empty? = \xs. xs (\x z. false) true in
25     >     ...
26
27 5.  If we encode lists in terms of their *left*-folds, instead, `[a, b, c]` would be encoded as `\f z. f (f (f z a) b) c`. The empty list `[]` would still be encoded as `\f z. z`. What should `cons` be, for this encoding?
28
29     >     let left_cons = \x xs. \f z. xs f (f z x) in
30     >     ...
31
32 6.  Continuing to encode lists in terms of their left-folds, what should `last` be, where `last [a, b, c]` should result in `c`. Let `last []` result in whatever `err` is bound to.
33
34     >     let left_last = \xs. xs (\z x. x) err in
35     >     ...
36
37 7.  Continuing to encode lists in terms of their left-folds, how should we write `head`? This is challenging.
38
39     > The [[hint/solution|assignment3 hint2]] gave this answer:
40
41     >     let m = \a. \n b. n a in
42     >     let f = \w b. w m b in
43     >     let left_head = \xs. (xs f I) I err in
44     >     ...
45
46     > Here's another, more straightforward answer. We [[observed before|/topics/week2_encodings#flipped-cons]] that left-folding the `cons` function over a list reverses it. Hence, it is easy to reverse a list defined in terms of its left-fold:
47
48     >     let left_empty = \f z. z in    ; this the same as for the right-fold encoding of lists
49     >     let flipped_left_cons = \xs x. \f z. xs f (f z x) in    ; left-folding supplies arguments in a different order than cons expects
50     >     let left_reverse = \xs. xs flipped_left_cons left_empty in
51     >     ...
52
53     > Then we can get the list's head by reversing it and getting the last member of the result, which we saw in the previous problem is easy:
54
55     >     let left_head = \xs. left_last (left_reverse xs) in
56     >     ...
57
58     > I'm not sure which of the two solutions presented here is better. The one given in the hint traverses the list only once; whereas the one gotten by reversing the list and getting the last member of the result traverses the list twice. But the former strategy does more complicated stuff at each step of the traversal (both conceptually and more applications), so in the end it might be computationally "cheaper" to use the latter strategy.
59
60     > Here is yet a third solution, which is probably the most efficient:
61
62     >     let box = \a. \v. v a in 
63     >     let left_head = \xs. xs (\b x. (K (b (K x)))) (box err) I in
64     >     ...
65
66 8.  Suppose you have two lists of integers, `left` and `right`. You want to determine whether those lists are equal, that is, whether they have all the same members in the same order. How would you implement such a list comparison? You can write it in Scheme or Kapulet using `letrec`, or if you want more of a challenge, in the Lambda Calculus using your preferred encoding for lists. If you write it in Scheme, don't rely on applying the built-in comparison operator `equal?` to the lists themselves. (Nor on the operator `eqv?`, which might not do what you expect.) You can however rely on the comparison operator `=` which accepts only number arguments. If you write it in the Lambda Calculus, you can use your implementation of `leq?`, requested below, to write an equality operator for Church-encoded numbers. [[Here is a hint|assignment3 hint3]], if you need it.
67
68     (The function you're trying to define here is like `eqlist?` in Chapter 5 of *The Little Schemer*, though you are only concerned with lists of numbers, whereas the function from *The Little Schemer* also works on lists containing symbolic atoms --- and in the final version from that Chapter, also on lists that contain other, embedded lists.)
69
70     > In Kapulet:
71
72     >     letrec
73     >       list_eq? (left, right) = case (left, right) of
74     >                                  ([], []) then 'true;
75     >                                  ([],  _) then 'false;
76     >                                  (_,  []) then 'false;
77     >                                  (x&xs, y&ys) when x == y then list_eq? (xs, ys);
78     >                                  (_, _)   then 'false
79     >                                end
80     >     in list_eq?
81
82     > In Scheme:
83
84     >     (define list_eq? (lambda (left right)
85     >                        (cond
86     >                          ((null? left) (null? right))
87     >                          ((null? right) #f)
88     >                          ((= (car left) (car right)) (list_eq? (cdr left) (cdr right)))
89     >                          (else #f))))
90
91     > In the Lambda Calculus, helping ourselves to definitions of `leq?`, `0`, `succ`, `head`, `tail`, and `reverse`:
92
93     >     let true = \y n. y in
94     >     let and = \p q. p q p in
95     >     let pair = \a b. \f. f a b in
96     >     let fst = \x y. x in
97     >     let num_eq? = \l r. and (leq? l r) (leq? r l) in
98     >     let length = \xs. xs (\x z. succ z) 0 in
99     >     let check = \x p. p (\b ys. pair (and b (num_eq? x (head ys))) (tail ys)) in
100     >     let list_eq? = \xs ys. and (num_eq? (length xs) (length ys)) ; this step could be skipped
101     >                                                                  ; if you were prepared to assume the lists always have the same length
102     >                                (xs check (pair true (reverse ys)) fst) in
103     >     ...
104
105
106 ## Numbers
107
108 9.  Recall our proposed encoding for the numbers, called "Church's encoding". As we explained last week, it's similar to our proposed encoding of lists in terms of their folds. Give a Lambda Calculus definition of `zero?` for numbers so encoded. (It should require only small modifications to your solution for `empty?`, above.)
109
110     >     let zero? = \n. n (\z. false) true in
111     >     ...
112
113 10. In last week's homework, you gave a Lambda Calculus definition of `succ` for Church-encoded numbers. Can you now define `pred`? Let `pred 0` result in whatever `err` is bound to. This is challenging. For some time theorists weren't sure it could be done. (Here is [some interesting commentary](http://okmij.org/ftp/Computation/lambda-calc.html#predecessor).) However, in this week's notes we examined one strategy for defining `tail` for our chosen encodings of lists, and given the similarities we explained between lists and numbers, perhaps that will give you some guidance in defining `pred` for numbers.
114
115     > Here is the solution we were guiding you towards, due to Paul Bernays:
116
117     >     ; helping ourselves to 0 and succ
118     >     let pair = \a b. \f. f a b in
119     >     let snd = \x y. y in
120     >     let shift = \p. p (\x y. pair (succ x) x) in
121     >     let pred = \n. n shift (pair 0 err) snd in
122     >     ...
123
124     > Here is another solution, that is attributed variously to Martin Bunder and F. Urbanek, or J. Velmans:
125
126     >     let box = \a. \v. v a in
127     >     let pred = \n. \s z. n (\b. box (b s)) (K z) I in
128     >     ...
129
130     > That can be hard to wrap your head around. If you trace this expression through, you'll see that:
131
132     > * when `n == 0`, it reduces to `\s z. (K z) I`, or `\s z. z`
133     > * when `n == 1`, it reduces to `\s z. (box z) I`, or `\s z. z`
134     > * when `n == 2`, it reduces to `\s z. (box (s z)) I`, or `\s z. s z`
135     > * when `n == 3`, it reduces to `\s z. (box (s (s z))) I`, or `\s z. s (s z)`
136
137     > `box a` is `\v. v a`; this stands to `pair a b` as one stands to two. Since boxes (like pairs) are really just functions, the technique used in this definition of `pred` is akin to that used in [[the hint for last week's `reverse`|assignment2_answers#cps-reverse]].
138
139     (Want a further challenge? Define `map2` in the Lambda Calculus, using our right-fold encoding for lists, where `map2 g [a, b, c] [d, e, f]` should evaluate to `[g a d, g b e, g c f]`. Doing this will require drawing on a number of different tools we've developed, including that same strategy for defining `tail`. Purely extra credit.)
140
141     >     let next = \g. \x p. p (\zs ys. pair (cons (g x (head ys)) zs) (tail ys)) in
142     >     let finish = \zs ys. (empty? ys) zs
143     >                          ; else ys are too long
144     >                          err_different_lengths in
145     >     let map2 = \g. \xs ys. (leq? (length xs) (length ys))
146     >                            (xs (next g) (pair empty (reverse ys)) finish)
147     >                            ; else ys are too short
148     >                            err_different_lengths in
149     >     ...
150
151
152 11. Define `leq?` for numbers (that is, ≤) in the Lambda Calculus. Here is the expected behavior,
153 where `one` abbreviates `succ zero`, and `two` abbreviates `succ (succ zero)`.
154
155         leq? zero zero ~~> true
156         leq? zero one ~~> true
157         leq? zero two ~~> true
158         leq? one zero ~~> false
159         leq? one one ~~> true
160         leq? one two ~~> true
161         leq? two zero ~~> false
162         leq? two one ~~> false
163         leq? two two ~~> true
164         ...
165
166     You'll need to make use of the predecessor function, but it's not essential to understanding this problem that you have successfully implemented it yet. You can treat it as a black box.
167
168     > It's easiest to do this if you define `pred` so that `pred 0 ~~> 0`:
169
170     >      let pred = \n. n shift (pair 0 0) snd in
171     >      let sub = \l r. r pred l in
172     >      let leq? = \l r. zero? (sub l r) in
173     >      ...
174
175     > Here is another solution. Jim crafted this particular implementation, but like a great deal of the CS knowledge he's gained over the past eight years, Oleg Kiselyov pointed the way. <!-- see "lambda-calc-opposites.txt" at http://okmij.org/ftp/Computation/lambda-calc.html#neg -->
176
177     >     let leq? = (\base build consume. \l r. r consume (l build base) fst)
178     >             ; where base is
179     >             (pair true junk)
180     >             ; and build is
181     >             (\p. pair false p)
182     >             ; and consume is
183     >             (\p. p fst p (p snd)) in
184     >     ...
185
186     > That can be generalized to give this nice implementation of `num_eq?`:
187
188     >     ; `num_cmp x y lt eq gt` returns lt when x<y, eq when x==y, gt when x>y
189     >     let num_cmp = (\base build consume. \l r. r consume (l build base) fst)
190     >             ; where base is
191     >             (pair (\a b c. b) (K (\a b c. a)))
192     >             ; and build is
193     >             (\p. pair (\a b c. c) p)
194     >             ; and consume is
195     >             (\p. p fst p (p snd) (p snd)) in
196     >     let num_eq? = \x y. num_cmp x y false true false in
197     >     ...
198
199
200 ## Combinatory Logic
201
202 Reduce the following forms, if possible:
203
204 <ol start=12>
205 <li><code>Kxy ~~> x</code>
206 <li><code>KKxy ~~> Ky</code>
207 <li><code>KKKxy ~~> Kxy ~~> x</code>
208 <li><code>SKKxy ~~> Kx(Kx)y ~~> xy</code>
209 <li><code>SIII ~~> II(II) ~~> II ~~> I</code>
210 <li><code>SII(SII) ~~> I(SII)(I(SII)) ~~> SII(SII) ~~> ...</code>; the reduction never terminates
211 </ol>
212
213 <!-- -->
214
215 18. Give Combinatory Logic combinators (that is, expressed in terms of `S`, `K`, and `I`) that behave like our boolean functions. Provide combinators for `true`, `false`, `neg`, `and`, `or`, and `xor`.
216
217     > As Dan pointed out in the Wednesday session, this problem is easy to solve if you first come up with a Combinatory translation of the schema `\p. if p then M else N`:
218
219     >     [\p. p M N] =
220     >     @p. p [M] [N] =
221     >     S (@p. p [M]) (@p [N]) =
222     >     S (S (@p p) (@p [M])) (@p [N]) =
223     >     S (S I (@p [M])) (@p [N]) =
224     >     S (S I (K [M])) (K [N])
225
226     > The last step assumes that `p` does not occur free in the expressions `M` and `N`.
227         
228     > Next, we translate `true ≡ \y n. y` as `K`, and `false ≡ \y n. n` as `KI`. Then we rely on the following equivalences:
229
230     >     neg   ≡ \p. if p then false else true
231     >     and   ≡ \p. if p then I else K false
232     >     ; then:    and p q <~~> if p then I q else K false q ~~> if p then q else false
233     >     or    ≡ \p. if p then K true else I
234     >     ; then:    or p q  <~~> if p then K true q else I q  ~~> if p then true else q
235     >     xor   ≡ \p. if p then neg else I
236     >     ; then:    xor p q <~~> if p then neg q else I q     ~~> if p then neg q else q
237
238     > Then we just make use of the schema derived above to complete the translations. For example, `and ≡ \p. if p then I else K false` becomes <code>S (SI (K <b>I</b>)) (K <b>(K false)</b>) ≡ S (SI (K <b>I</b>)) (K <b>(K (KI))</b>)</code>.
239
240     > In the case of `neg`, this produces <code>S (SI (K <b>false</b>)) (K <b>true</b>) ≡ S (SI (K <b>(KI)</b>)) (K <b>K</b>)</code>. A more compact result here can be obtained here by observing that for boolean arguments, `neg` can also be defined as `\p y n. p n y`, which is just the `C` combinator.
241
242
243 Using the mapping specified in this week's notes, translate the following lambda terms into combinatory logic:
244
245
246 <ol start=19>
247 <li><code>[\x x] = @x x = I</code>
248 <li><code>[\x y. x] = @x [\y. x] = @x. (@y x) = @x (Kx) = S (@x K) (@x x) = S (KK) I</code>; in general expressions of this form <code>S(K<i>M</i>)I</code> will behave just like <code><i>M</i></code> for any expression <code><i>M</i></code>
249 <li><code>[\x y. y] = @x [\y. y] = @x (@y y) = @x I = KI</code>
250 <li><code>[\x y. y x] = @x [\y. y x] = @x (@y (y x)) = @x (S (@y y) (@y x)) = @x (S I (Kx)) = S (@x (SI)) (@x (Kx)) = S (K(SI)) K</code> ; this is the <b>T</b> combinator
251 <li><code>[\x. x x] = @x (x x) = S (@x x) (@x x) = SII</code>
252 <li><code>[\x y z. x (y z)] =<br>
253 @x (@y (@z (x (y z)))) =<br>
254 @x (@y (S (@z x) (@z (y z)))) =<br>
255 @x (@y (S (Kx) (@z (y z)))) =<br>
256 @x (@y (S (Kx) y)) =<br>
257 @x (S (@y (S (Kx))) (@y y)) =<br>
258 @x (S (K (S (Kx))) (@y y)) =<br>
259 @x (S (K (S (Kx))) I) =<br>
260 S (@x (S (K (S (Kx))))) (@x I) =<br>
261 S (S (@x S) (@x (K (S (Kx))))) (@x I) =<br>
262 S (S (KS) (@x (K (S (Kx))))) (@x I) =<br>
263 S (S (KS) (S (@x K) (@x (S (Kx))))) (@x I) =<br>
264 S (S (KS) (S (KK) (@x (S (Kx))))) (@x I) =<br>
265 S (S (KS) (S (KK) (S (@x S) (@x (Kx))))) (@x I) =<br>
266 S (S (KS) (S (KK) (S (KS) (@x (Kx))))) (@x I) =<br>
267 S (S (KS) (S (KK) (S (KS) K))) (@x I) =<br>
268 S (S (KS) (S (KK) (S (KS) K))) (KI)</code>; this is the <b>B</b> combinator, which can also be expressed more concisely as <code>S (K S) K</code>
269 </ol>
270
271 <!-- -->
272
273 25. For each of the above translations, how many `I`s are there? Give a rule for describing what each `I` corresponds to in the original lambda term.
274
275     This generalization depends on you omitting the translation rule:
276
277         6. @a(Xa)       =   X            if a is not in X
278
279     > With that shortcut rule omitted, then there turn out to be one `I` in the result corresponding to each occurrence of a bound variable in the original term.
280
281 Evaluation strategies in Combinatory Logic
282 ------------------------------------------
283
284 26. Find a term in CL that behaves like Omega does in the Lambda
285 Calculus.  Call it `Skomega`.
286
287     >     SII(SII)
288
289 27. Are there evaluation strategies in CL corresponding to leftmost
290 reduction and rightmost reduction in the Lambda Calculus?
291 What counts as a redex in CL?
292
293     > A redex is any `I` with one argument, or `K` with two arguments, or `S` with three arguments.
294
295     > Leftmost reduction corresponds to applying the rules for an `I` or `K` or `S` in head position *before* reducing any of their arguments; rightmost reduction corresponds to reducing the arguments first.
296
297 28. Consider the CL term `K I Skomega`.  Does leftmost (alternatively,
298 rightmost) evaluation give results similar to the behavior of `K I
299 Omega` in the Lambda Calculus, or different?  What features of the
300 Lambda Calculus and CL determine this answer?
301
302     > Leftmost reduction terminates with `I`; rightmost reduction never terminates. This is because "leftmost reduction" corresponds to "head-redex first", which gives the head combinator the opportunity to ignore some of its (in this case, unreducible) arguments without trying to reduce them. If the arguments are reduced first, the head combinator loses that opportunity.
303
304 29. What should count as a thunk in CL?  What is the equivalent
305 constraint in CL to forbidding evaluation inside of a lambda abstract?
306
307     > Recall that a thunk is a function of the form `\(). EXPRESSION`, where `EXPRESSION` won't be evaluated until the function is applied (to the uninformative argument `()`). We don't really have `()` in the Lambda Calculus. The closest approximation would be `I`, since a triple is `\f. f a b c`, a pair is `\f. f a b`, and following the same pattern a one-tuple would be `\f. f a` (not the same as `a`), and the zero-tuple would be `\f. f` or `I`. But really in the untyped Lambda Calculus, it doesn't matter whether you supply `I` to an abstract that's going to ignore its argument, or any other argument. Instead, you could get the same effect as a thunk by just using `\x. EXPRESSION`, where `x` is a variable that doesn't occur free in `EXPRESSION`.
308
309     > The way to do the same thing in Combinatory Logic is `K (EXPRESSION)`. The constraint we need is that arguments to `S` and `K` are never reduced until there are enough of them to apply the rule for `S` and `K`. (If we furthermore insist on leftmost reduction, then expressions will *never* be reduced when in the position of an argument to another combinator. Only the reduction rules for the outermost head combinator are ever followed.)
310
311
312 More Lambda Practice
313 --------------------
314
315 Reduce to beta-normal forms:
316
317 <OL start=30>
318 <LI><code>(\x. x (\y. y x)) (v w) ~~> v w (\y. y (v w))</code>
319 <LI><code>(\x. x (\x. y x)) (v w) ~~> v w (\x. y x)</code>
320 <LI><code>(\x. x (\y. y x)) (v x) ~~> v x (\y. y (v x))</code>
321 <LI><code>(\x. x (\y. y x)) (v y) ~~> v y (\u. u (v y))</code>
322
323 <LI><code>(\x y. x y y) u v ~~> u v v</code>
324 <LI><code>(\x y. y x) (u v) z w ~~> z (u v) w</code>
325 <LI><code>(\x y. x) (\u u) ~~> \y u. u</code>, also known as <code>false</code>
326 <LI><code>(\x y z. x z (y z)) (\u v. u) ~~> \y z. (\u v. u) z (y z) ~~> \y z. z</code>, also known as <code>false</code>
327 </OL>
328