update
[lambda.git] / topics / week13_control_operators.mdwn
1 * [Example of an not-fully-immersive game](http://www.i-mockery.com/minimocks/50arcadecabinets/star-wars-arcade.gif)
2 * [A more immersive game](http://upload.wikimedia.org/wikipedia/commons/7/78/AC89-0437-20_a.jpeg)
3
4
5 3.      `callcc` was originally introduced in Scheme. There it's written `call/cc` and is an abbreviation of `call-with-current-continuation`. Instead of the somewhat bulky form:
6
7                 (call/cc (lambda (k) ...))
8
9         I prefer instead to use the lighter, and equivalent, shorthand:
10
11                 (let/cc k ...)
12
13
14 Callcc/letcc examples
15 ---------------------
16
17 First, here are two examples in Scheme:
18
19         (+ 100 (let/cc k (+ 10 1)))
20                |-----------------|
21
22 This binds the continuation `outk` of the underlined expression to `k`, then computes `(+ 10 1)` and delivers that to `outk` in the normal way (not through `k`). No unusual behavior. It evaluates to `111`.
23
24 What if we do instead:
25
26         (+ 100 (let/cc k (+ 10 (k 1))))
27                |---------------------|
28
29 This time, during the evaluation of `(+ 10 (k 1))`, we supply `1` to `k`. So then the local continuation, which delivers the value up to `(+ 10 [_])` and so on, is discarded. Instead `1` gets supplied to the outer continuation in place when `let/cc` was invoked. That will be `(+ 100 [_])`. When `(+ 100 1)` is evaluated, there's no more of the computation left to evaluate. So the answer here is `101`.
30
31 You are not restricted to calling a bound continuation only once, nor are you restricted to calling it only inside of the `call/cc` (or `let/cc`) block. For example, you can do this:
32
33         (let ([p (let/cc k (cons 1 k))])
34           (cons (car p) ((cdr p) (cons 2 (lambda (x) x)))))
35         ; evaluates to '(2 2 . #<procedure>)
36
37 What happens here? First, we capture the continuation where `p` is about to be assigned a value. Inside the `let/cc` block, we create a pair consisting of `1` and the captured continuation. This pair is bound to p. We then proceed to extract the components of the pair. The head (`car`) goes into the start of a tuple we're building up. To get the next piece of the tuple, we extract the second component of `p` (this is the bound continuation `k`) and we apply it to a pair consisting of `2` and the identity function. Supplying arguments to `k` takes us back to the point where `p` is about to be assigned a value. The tuple we had formerly been building, starting with `1`, will no longer be accessible because we didn't bring along with us any way to refer to it, and we'll never get back to the context where we supplied an argument to `k`. Now `p` gets assigned not the result of `(let/cc k (cons 1 k))` again, but instead, the new pair that we provided: `'(2 . #<identity procedure>)`. Again we proceed to build up a tuple: we take the first element `2`, then we take the second element (now the identity function), and feed it a pair `'(2 . #<identity procedure>)`, and since it's an argument to the identity procedure that's also the result. So our final result is a nested pair, whose first element is `2` and whose second element is the pair `'(2 . #<identity procedure>)`. Racket displays this nested pair like this:
38
39         '(2 2 . #<procedure>)
40
41
42 ---
43
44 Some callcc/letcc exercises
45 ---------------------------
46
47 Here are a series of examples from *The Seasoned Schemer*, which we recommended at the start of term. It's not necessary to have the book to follow the exercises, though if you do have it, its walkthroughs will give you useful assistance.
48
49 For reminders about Scheme syntax, see [here](/assignment8/) and [here](/week1/) and [here](/translating_between_ocaml_scheme_and_haskell). Other resources are on our [[Learning Scheme]] page.
50
51 Most of the examples assume the following preface:
52
53         #lang racket
54
55         (define (atom? x)
56           (and (not (pair? x)) (not (null? x))))
57
58 Now try to figure out what this function does:
59
60         (define alpha
61           (lambda (a lst)
62             (let/cc k ; now what will happen when k is called?
63               (letrec ([aux (lambda (l)
64                               (cond
65                                 [(null? l) '()]
66                                 [(eq? (car l) a) (k (aux (cdr l)))]
67                                 [else (cons (car l) (aux (cdr l)))]))])
68                 (aux lst)))))
69         
70 Here is [the answer](/hints/cps_hint_1), but try to figure it out for yourself.
71
72 Next, try to figure out what this function does:
73
74         (define beta
75           (lambda (lst)
76             (let/cc k ; now what will happen when k is called?
77               (letrec ([aux (lambda (l)
78                               (cond
79                                 [(null? l) '()]
80                                 [(atom? (car l)) (k (car l))]
81                                 [else (begin
82                                         ; what will the value of the next line be? why is it ignored?
83                                         (aux (car l))
84                                         (aux (cdr l)))]))])
85                 (aux lst)))))
86
87 Here is [the answer](/hints/cps_hint_2), but try to figure it out for yourself.
88
89 Next, try to figure out what this function does:
90
91         (define gamma
92           (lambda (a lst)
93             (letrec ([aux (lambda (l k)
94                             (cond
95                               [(null? l) (k 'notfound)]
96                               [(eq? (car l) a) (cdr l)]
97                               [(atom? (car l)) (cons (car l) (aux (cdr l) k))]
98                               [else
99                                ; what happens when (car l) exists but isn't an atom?
100                                (let ([car2 (let/cc k2 ; now what will happen when k2 is called?
101                                              (aux (car l) k2))])
102                                  (cond
103                                    ; when will the following condition be met? what happens then?
104                                    [(eq? car2 'notfound) (cons (car l) (aux (cdr l) k))]
105                                    [else (cons car2 (cdr l))]))]))]
106                      [lst2 (let/cc k1 ; now what will happen when k1 is called?
107                              (aux lst k1))])
108               (cond
109                 ; when will the following condition be met?
110                 [(eq? lst2 'notfound) lst]
111                 [else lst2]))))
112
113 Here is [the answer](/hints/cps_hint_3), but try to figure it out for yourself.
114
115 Here is the hardest example. Try to figure out what this function does:
116
117         (define delta
118           (letrec ([yield (lambda (x) x)]
119                    [resume (lambda (x) x)]
120                    [walk (lambda (l)
121                            (cond
122                              ; is this the only case where walk returns a non-atom?
123                              [(null? l) '()]
124                              [(atom? (car l)) (begin
125                                                 (let/cc k2 (begin
126                                                   (set! resume k2) ; now what will happen when resume is called?
127                                                   ; when the next line is executed, what will yield be bound to?
128                                                   (yield (car l))))
129                                                 ; when will the next line be executed?
130                                                 (walk (cdr l)))]
131                              [else (begin
132                                      ; what will the value of the next line be? why is it ignored?
133                                      (walk (car l))
134                                      (walk (cdr l)))]))]
135                    [next (lambda () ; next is a thunk
136                            (let/cc k3 (begin
137                              (set! yield k3) ; now what will happen when yield is called?
138                              ; when the next line is executed, what will resume be bound to?
139                              (resume 'blah))))]
140                    [check (lambda (prev)
141                             (let ([n (next)])
142                               (cond
143                                 [(eq? n prev) #t]
144                                 [(atom? n) (check n)]
145                                 ; when will n fail to be an atom?
146                                 [else #f])))])
147             (lambda (lst)
148               (let ([fst (let/cc k1 (begin
149                            (set! yield k1) ; now what will happen when yield is called?
150                            (walk lst)
151                            ; when will the next line be executed?
152                            (yield '())))])
153                 (cond
154                   [(atom? fst) (check fst)]
155                   ; when will fst fail to be an atom?
156                   [else #f])
157                 ))))
158
159 Here is [the answer](/hints/cps_hint_4), but again, first try to figure it out for yourself.
160
161
162 Delimited control operators
163 ===========================
164
165 Here again is the CPS transform for `callcc`:
166
167         [callcc (\k. body)] = \outk. (\k. [body] outk) (\v localk. outk v)
168
169 `callcc` is what's known as an *undelimited control operator*. That is, the continuations `outk` that get bound into our `k`s include all the code from the `call/cc ...` out to *and including* the end of the program. Calling such a continuation will never return any value to the call site.
170
171 (See the technique employed in the `delta` example above, with the `(begin (let/cc k2 ...) ...)`, for a work-around. Also. if you've got a copy of *The Seasoned Schemer*, see the comparison of let/cc vs. "collector-using" (that is, partly CPS) functions at pp. 155-164.)
172
173 Often times it's more useful to use a different pattern, where we instead capture only the code from the invocation of our control operator out to a certain boundary, not including the end of the program. These are called *delimited control operators*. A variety of these have been formulated. The most well-behaved from where we're coming from is the pair `reset` and `shift`. `reset` sets the boundary, and `shift` binds the continuation from the position where it's invoked out to that boundary.
174
175 It works like this:
176
177         (1) outer code
178         ------- reset -------
179         | (2)               |
180         | +----shift k ---+ |
181         | | (3)           | |
182         | |               | |
183         | |               | |
184         | +---------------+ |
185         | (4)               |
186         +-------------------+
187         (5) more outer code
188
189 First, the code in position (1) runs. Ignore position (2) for the moment. When we hit the `shift k`, the continuation between the `shift` and the `reset` will be captured and bound to `k`. Then the code in position (3) will run, with `k` so bound. The code in position (4) will never run, unless it's invoked through `k`. If the code in position (3) just ends with a regular value, and doesn't apply `k`, then the value returned by (3) is passed to (5) and the computation continues.
190
191 So it's as though the middle box---the (2) and (4) region---is by default not evaluated. This code is instead bound to `k`, and it's up to other code whether and when to apply `k` to any argument. If `k` is applied to an argument, then what happens? Well it will be as if that were the argument supplied by (3) only now that argument does go to the code (4) syntactically enclosing (3). When (4) is finished, that value also goes to (5) (just as (3)'s value did when it ended with a regular value). `k` can be applied repeatedly, and every time the computation will traverse that same path from (4) into (5).
192
193 I set (2) aside a moment ago. The story we just told is a bit too simple because the code in (2) needs to be evaluated because some of it may be relied on in (3).
194
195 For instance, in Scheme this:
196
197         (require racket/control)
198         
199         (reset
200          (let ([x 1])
201            (+ 10 (shift k x))))
202
203 will return 1. The `(let ([x 1]) ...` part is evaluated, but the `(+ 10 ...` part is not.
204
205 Notice we had to preface the Scheme code with `(require racket/control)`. You don't have to do anything special to use `call/cc` or `let/cc`; but to use the other control operators we'll discuss you do have to include that preface in Racket.
206
207 This pattern should look somewhat familiar. Recall from our discussion of aborts, and repeated at the top of this page:
208
209         let foo x =
210         +---try begin----------------+
211         |       (if x = 1 then 10    |
212         |       else abort 20        |
213         |       ) + 100              |
214         +---end----------------------+
215         in (foo 2) + 1000;;
216
217 The box is working like a reset. The `abort` is implemented with a `shift`. Earlier, we refactored our code into a more CPS form:
218
219         let x = 2
220         in let snapshot = fun box ->
221             let foo_result = box
222             in (foo_result) + 1000
223         in let continue_normally = fun from_value ->
224             let value = from_value + 100
225             in snapshot value
226         in
227             if x = 1 then continue_normally 10
228             else snapshot 20;;
229
230 `snapshot` here corresponds to the code outside the `reset`. `continue_normally` is the middle block of code, between the `shift` and its surrounding `reset`. This is what gets bound to the `k` in our `shift`. The `if...` statement is inside a `shift`. Notice there that we invoke the bound continuation to "continue normally". We just invoke the outer continuation, saved in `snapshot` when we placed the `reset`, to skip the "continue normally" code and immediately abort to outside the box.
231
232 ---
233
234 Examples of shift/reset/abort
235 -----------------------------
236
237 Here are some more examples of using delimited control operators. We present each example three ways: first a Scheme formulation; then we compute the same result using CPS and the lambda evaluator; then we do the same using the Continuation monad in OCaml. (We don't demonstrate the use of Oleg's delimcc library.)
238
239
240 Example 1:
241
242         ; (+ 1000 (+ 100 (abort 11))) ~~> 11
243         
244         app2 (op2 plus) (var thousand)
245           (app2 (op2 plus) (var hundred) (abort (var eleven)))
246         
247         # Continuation_monad.(run0(
248             abort 11 >>= fun i ->
249             unit (100+i) >>= fun j ->
250             unit (1000+j)));;
251         - : int = 11
252
253 When no `reset` is specified, there's understood to be an implicit one surrounding the entire computation (but unlike in the case of `callcc`, you still can't capture up to *and including* the end of the computation). So it makes no difference if we say instead:
254
255         # Continuation_monad.(run0(
256             reset (
257               abort 11 >>= fun i ->
258               unit (100+i) >>= fun j ->
259               unit (1000+j))));;
260         - : int = 11
261
262
263 Example 2:
264         
265         ; (+ 1000 (reset (+ 100 (abort 11)))) ~~> 1011
266         
267         app2 (op2 plus) (var thousand)
268           (reset (app2 (op2 plus) (var hundred) (abort (var eleven))))
269         
270         # Continuation_monad.(run0(
271             reset (
272               abort 11 >>= fun i ->
273               unit (100+i)
274             ) >>= fun j ->
275             unit (1000+j)));;
276         - : int = 1011
277
278 Example 3:
279
280         ; (+ 1000 (reset (+ 100 (shift k (+ 10 1))))) ~~> 1011
281
282         app2 (op2 plus) (var thousand)
283           (reset (app2 (op2 plus) (var hundred)
284             (shift (\k. ((op2 plus) (var ten) (var one))))))
285
286         Continuation_monad.(
287           let v = reset (
288             let u = shift (fun k -> unit (10 + 1))
289             in u >>= fun x -> unit (100 + x)
290           ) in let w = v >>= fun x -> unit (1000 + x)
291           in run0 w);;
292         - : int = 1011
293
294 Example 4:
295
296         ; (+ 1000 (reset (+ 100 (shift k (k (+ 10 1)))))) ~~> 1111
297         
298         app2 (op2 plus) (var thousand)
299           (reset (app2 (op2 plus) (var hundred)
300             (shift (\k. (app (var k) ((op2 plus) (var ten) (var one)))))))
301         
302         Continuation_monad.(
303           let v = reset (
304             let u = shift (fun k -> k (10 :: [1]))
305             in u >>= fun x -> unit (100 :: x)
306           ) in let w = v >>= fun x -> unit (1000 :: x)
307           in run0 w);;
308         - : int list = [1000; 100; 10; 1]
309
310 To demonstrate the different adding order between Examples 4 and 5, we use `::` in the OCaml version instead of `+`. Here is Example 5:
311
312         ; (+ 1000 (reset (+ 100 (shift k (+ 10 (k 1)))))) ~~> 1111 but added differently
313
314         app2 (op2 plus) (var thousand)
315           (reset (app2 (op2 plus) (var hundred)
316             (shift (\k. ((op2 plus) (var ten) (app (var k) (var one)))))))
317         
318         Continuation_monad.(let v = reset (
319             let u = shift (fun k -> k [1] >>= fun x -> unit (10 :: x))
320             in u >>= fun x -> unit (100 :: x)
321           ) in let w = v >>= fun x -> unit (1000 :: x)
322           in run0  w);;
323         - : int list = [1000; 10; 100; 1]
324
325
326 Example 6:
327
328         ; (+ 100 ((reset (+ 10 (shift k k))) 1)) ~~> 111
329         
330         app2 (op2 plus) (var hundred)
331           (app (reset (app2 (op2 plus) (var ten)
332             (shift (\k. (var k))))) (var one))
333         
334         (* not sure if this example can be typed as-is in OCaml... this is the best I an do at the moment... *)
335
336         # type 'x either = Left of (int -> ('x,'x either) Continuation_monad.m) | Right of int;;
337         # Continuation_monad.(let v = reset (
338             shift (fun k -> unit (Left k)) >>= fun i -> unit (Right (10+i))
339           ) in let w = v >>= fun (Left k) ->
340               k 1 >>= fun (Right i) ->
341               unit (100+i)
342           in run0 w);;
343         - : int = 111
344
345 <!--
346 # type either = Left of (int -> either) | Right of int;;
347 # let getleft e = match e with Left lft -> lft | Right _ -> failwith "not a Left";;
348 # let getright e = match e with Right rt -> rt | Left _ -> failwith "not a Right";;
349 # 100 + getright (let v = reset (fun p () -> Right (10 + shift p (fun k -> Left k))) in getleft v 1);;
350 -->
351
352 Example 7:
353
354         ; (+ 100 (reset (+ 10 (shift k (k (k 1)))))) ~~> 121
355         
356         app2 (op2 plus) (var hundred)
357           (reset (app2 (op2 plus) (var ten)
358             (shift (\k. app (var k) (app (var k) (var one))))))
359         
360         Continuation_monad.(let v = reset (
361             let u = shift (fun k -> k 1 >>= fun x -> k x)
362             in u >>= fun x -> unit (10 + x)
363           ) in let w = v >>= fun x -> unit (100 + x)
364           in run0 w)
365         - : int = 121
366
367 <!--
368
369         print_endline "=== pa_monad's Continuation Tests ============";;
370
371         (1, 5 = C.(run0 (unit 1 >>= fun x -> unit (x+4))) );;
372         (2, 9 = C.(run0 (reset (unit 5 >>= fun x -> unit (x+4)))) );;
373         (3, 9 = C.(run0 (reset (abort 5 >>= fun y -> unit (y+6)) >>= fun x -> unit (x+4))) );;
374         (4, 9 = C.(run0 (reset (reset (abort 5 >>= fun y -> unit (y+6))) >>= fun x -> unit (x+4))) );;
375         (5, 27 = C.(run0 (
376                                   let c = reset(abort 5 >>= fun y -> unit (y+6))
377                                   in reset(c >>= fun v1 -> abort 7 >>= fun v2 -> unit (v2+10) ) >>= fun x -> unit (x+20))) );;
378
379         (7, 117 = C.(run0 (reset (shift (fun sk -> sk 3 >>= sk >>= fun v3 -> unit (v3+100) ) >>= fun v1 -> unit (v1+2)) >>= fun x -> unit (x+10))) );;
380
381         (8, 115 = C.(run0 (reset (shift (fun sk -> sk 3 >>= fun v3 -> unit (v3+100)) >>= fun v1 -> unit (v1+2)) >>= fun x -> unit (x+10))) );;
382
383         (12, ["a"] = C.(run0 (reset (shift (fun f -> f [] >>= fun t -> unit ("a"::t)  ) >>= fun xv -> shift (fun _ -> unit xv)))) );;
384
385
386         (0, 15 = C.(run0 (let f k = k 10 >>= fun v-> unit (v+100) in reset (callcc f >>= fun v -> unit (v+5)))) );;
387
388 -->