tweak
[lambda.git] / topics / week13_native_continuation_operators.mdwn
index 179b780..6f7a0eb 100644 (file)
@@ -1,3 +1,7 @@
+[[!toc]]
+
+## Explicit and Implicit ##
+
 Consider two kinds of video games. The first are 80s-style cabinets, that might suppress most awareness of your outside environment, but you can still directly perceive the controls, the "new game" button, and so on:
 
 [[/images/star-wars-arcade.gif]]
 Consider two kinds of video games. The first are 80s-style cabinets, that might suppress most awareness of your outside environment, but you can still directly perceive the controls, the "new game" button, and so on:
 
 [[/images/star-wars-arcade.gif]]
@@ -39,6 +43,9 @@ Here we explicitly pass around continuations in the `k` argument, beginning with
 
 What the **continuation or control operators** like `let/cc`, `reset`, `shift`, `abort`, and so on do is give us a "magic gesture" alternative, where we can let the continuations usually be *implicit* in the way our code is structured, but when we perform the magic gesture (that is, use some of these special operators), the continuation gets converted from its implicit form into an explicit function that's bound to a variable we supply.
 
 
 What the **continuation or control operators** like `let/cc`, `reset`, `shift`, `abort`, and so on do is give us a "magic gesture" alternative, where we can let the continuations usually be *implicit* in the way our code is structured, but when we perform the magic gesture (that is, use some of these special operators), the continuation gets converted from its implicit form into an explicit function that's bound to a variable we supply.
 
+
+## A Bestiary of operators for magically distilling implicit continuations into explicit functions ##
+
 The continuation operators come in a variety of forms. You'll only be using a few of them (if any) in a single application. But here we'll present a couple of them side-by-side.
 
 One issue is whether the continuation operators you're working with are "full-strength" or not. As we said, what these operators do is distill an implicit continuation into a function that you can explicitly invoke or manipulate (pass into or return from a function). If they're "full-strength", then there aren't constraints on _where_ or _how many times_ you can invoke that continuation function. Anywhere you have access to some variable that's bound to the continuation, you can invoke it as often as you like. More handicapped continuations are only invocable a single time, or only in certain regions of the code. Sometimes these handicapped continuations are provided because they're easier to implement, and the language designers haven't gotten around to implementing full-strength continuations yet. Or a language might provide _both_ handicapped and full-strength continuations, because the former can be implemented more efficiently. For applications like coroutines or exceptions/aborts, that we looked at before, typically all that's needed is a handicapped form of continuations. If your language has an `abort` operation, typically you'll only be invoking it once within a single execution path, and only inside the box that you want to abort from.
 The continuation operators come in a variety of forms. You'll only be using a few of them (if any) in a single application. But here we'll present a couple of them side-by-side.
 
 One issue is whether the continuation operators you're working with are "full-strength" or not. As we said, what these operators do is distill an implicit continuation into a function that you can explicitly invoke or manipulate (pass into or return from a function). If they're "full-strength", then there aren't constraints on _where_ or _how many times_ you can invoke that continuation function. Anywhere you have access to some variable that's bound to the continuation, you can invoke it as often as you like. More handicapped continuations are only invocable a single time, or only in certain regions of the code. Sometimes these handicapped continuations are provided because they're easier to implement, and the language designers haven't gotten around to implementing full-strength continuations yet. Or a language might provide _both_ handicapped and full-strength continuations, because the former can be implemented more efficiently. For applications like coroutines or exceptions/aborts, that we looked at before, typically all that's needed is a handicapped form of continuations. If your language has an `abort` operation, typically you'll only be invoking it once within a single execution path, and only inside the box that you want to abort from.
@@ -104,10 +111,11 @@ However, OCaml doesn't have any continuation operators in its standard deploymen
     # #directory "+../delimcc";;
     # #load "delimcc.cma";;
     # let reset_label = ref None;;
     # #directory "+../delimcc";;
     # #load "delimcc.cma";;
     # let reset_label = ref None;;
-    # let reset body = let p = Delimcc.new_prompt () in
-      let oldp = !reset_label in
-      reset_label := Some p; let res = Delimcc.push_prompt p body in
-      reset_label := oldp; res;;
+    # let reset body =
+        let p = Delimcc.new_prompt () in
+        let oldp = !reset_label in
+        reset_label := Some p; let res = Delimcc.push_prompt p body in
+        reset_label := oldp; res;;
     # let shift fun_k = match !reset_label with
       | None -> failwith "shift must be inside reset"
       | Some p -> Delimcc.shift p fun_k;;
     # let shift fun_k = match !reset_label with
       | None -> failwith "shift must be inside reset"
       | Some p -> Delimcc.shift p fun_k;;
@@ -131,12 +139,14 @@ That was all *delimited* continuation operators. There's also the **undelimited
 
 returns `101`, whereas:
 
 
 returns `101`, whereas:
 
-    (reset (+ 10 (shift k 1)))
+    (reset (+ 100 (shift k 1)))
 
 only returns `1`. It is possible to duplicate the behavior of `let/cc` using `reset`/`shift`, but you have to structure your code in certain ways to do it. In order to duplicate the behavior of `reset`/`shift` using `let/cc`, you need to also make use of a mutable reference cell. So in that sense delimited continuations are more powerful and undelimited continuations are sort-of a special case.
 
 (In the OCaml code above for using delimited continuations, there is a mutable reference cell `reset_label`, but this is just for convenience. Oleg's library is designed for use with _multiple_ reset blocks having different labels, then when you invoke `shift` you have to specify which labeled reset block you want to potentially skip the rest of. We haven't introduced that complexity into our discussion, so for convenience we worked around it in showing you how to use `reset` and `shift` in OCaml. And the mutable reference cell was only playing the role of enabling us to work around the need to explicitly specify the `reset` block's label.)
 
 
 only returns `1`. It is possible to duplicate the behavior of `let/cc` using `reset`/`shift`, but you have to structure your code in certain ways to do it. In order to duplicate the behavior of `reset`/`shift` using `let/cc`, you need to also make use of a mutable reference cell. So in that sense delimited continuations are more powerful and undelimited continuations are sort-of a special case.
 
 (In the OCaml code above for using delimited continuations, there is a mutable reference cell `reset_label`, but this is just for convenience. Oleg's library is designed for use with _multiple_ reset blocks having different labels, then when you invoke `shift` you have to specify which labeled reset block you want to potentially skip the rest of. We haven't introduced that complexity into our discussion, so for convenience we worked around it in showing you how to use `reset` and `shift` in OCaml. And the mutable reference cell was only playing the role of enabling us to work around the need to explicitly specify the `reset` block's label.)
 
+## Examples of using these continuation operators ##
+
 Here are some examples of using these different continuation operators. The continuation that gets bound to `k` will be in bold. I'll use an OCaml-ish syntax because that's easiest to read, but these examples don't work as-is in OCaml. The `reset`/`shift` examples need to be massaged into the form displayed above for OCaml; and the `let/cc` examples don't work in OCaml because that's not provided. Alternatively, you could massage all of these into Scheme syntax. You shouldn't find that hard.
 
 1.  <pre><b>100 + </b>let/cc k (10 + 1)</pre>
 Here are some examples of using these different continuation operators. The continuation that gets bound to `k` will be in bold. I'll use an OCaml-ish syntax because that's easiest to read, but these examples don't work as-is in OCaml. The `reset`/`shift` examples need to be massaged into the form displayed above for OCaml; and the `let/cc` examples don't work in OCaml because that's not provided. Alternatively, you could massage all of these into Scheme syntax. You shouldn't find that hard.
 
 1.  <pre><b>100 + </b>let/cc k (10 + 1)</pre>
@@ -185,3 +195,120 @@ Here are some examples of using these different continuation operators. The cont
     But this evaluates differently. In the `let/cc` example, `k` is bound to the rest of the computation *including its termination*, so after executing `k 1` we never come back and finish with `10 + < >`. A `let/cc`-bound `k` never returns to the context where it was invoked. Whereas the `shift`-bound `k` only includes up to the edge of the `reset` box --- here, the rest of the computation, but *not including* its termination. So after `k 1`, if there is still code inside the body of `shift`, as there is here, we continue executing it. Thus the `shift` code evaluates to `111` not to `101`.
 
     Thus code using `let/cc` can't be *straightforwardly* translated into code using `shift`. It can be translated, but the algorithm will be more complex.
     But this evaluates differently. In the `let/cc` example, `k` is bound to the rest of the computation *including its termination*, so after executing `k 1` we never come back and finish with `10 + < >`. A `let/cc`-bound `k` never returns to the context where it was invoked. Whereas the `shift`-bound `k` only includes up to the edge of the `reset` box --- here, the rest of the computation, but *not including* its termination. So after `k 1`, if there is still code inside the body of `shift`, as there is here, we continue executing it. Thus the `shift` code evaluates to `111` not to `101`.
 
     Thus code using `let/cc` can't be *straightforwardly* translated into code using `shift`. It can be translated, but the algorithm will be more complex.
+
+
+## Some call/cc (or let/cc) exercises from The Seasoned Schemer ##
+
+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.
+
+For reminders about Scheme syntax, see [[here|/exercises/assignment12/#scheme]], and [[here|/rosetta1]] and [[here|/rosetta3]]. Other resources are on our [[Learning Scheme]] page.
+
+Most of the examples assume the following preface:
+
+       #lang racket
+
+       (define (atom? x)
+         (and (not (pair? x)) (not (null? x))))
+
+Now try to figure out what this function does:
+
+       (define alpha
+         (lambda (a lst)
+           (let/cc k ; now what will happen when k is called?
+             (letrec ([aux (lambda (l)
+                             (cond
+                               [(null? l) '()]
+                               [(eq? (car l) a) (k (aux (cdr l)))]
+                               [else (cons (car l) (aux (cdr l)))]))])
+               (aux lst)))))
+       
+Here is [[the answer|cps_hint_1]], but try to figure it out for yourself.
+
+Next, try to figure out what this function does:
+
+       (define beta
+         (lambda (lst)
+           (let/cc k ; now what will happen when k is called?
+             (letrec ([aux (lambda (l)
+                             (cond
+                               [(null? l) '()]
+                               [(atom? (car l)) (k (car l))]
+                               [else (begin
+                                       ; what will the value of the next line be? why is it ignored?
+                                       (aux (car l))
+                                       (aux (cdr l)))]))])
+               (aux lst)))))
+
+Here is [[the answer|cps_hint_2]], but try to figure it out for yourself.
+
+Next, try to figure out what this function does:
+
+       (define gamma
+         (lambda (a lst)
+           (letrec ([aux (lambda (l k)
+                           (cond
+                             [(null? l) (k 'notfound)]
+                             [(eq? (car l) a) (cdr l)]
+                             [(atom? (car l)) (cons (car l) (aux (cdr l) k))]
+                             [else
+                              ; what happens when (car l) exists but isn't an atom?
+                              (let ([car2 (let/cc k2 ; now what will happen when k2 is called?
+                                            (aux (car l) k2))])
+                                (cond
+                                  ; when will the following condition be met? what happens then?
+                                  [(eq? car2 'notfound) (cons (car l) (aux (cdr l) k))]
+                                  [else (cons car2 (cdr l))]))]))]
+                    [lst2 (let/cc k1 ; now what will happen when k1 is called?
+                            (aux lst k1))])
+             (cond
+               ; when will the following condition be met?
+               [(eq? lst2 'notfound) lst]
+               [else lst2]))))
+
+Here is [[the answer|cps_hint_3]], but try to figure it out for yourself.
+
+Here is the hardest example. Try to figure out what this function does:
+
+       (define delta
+         (letrec ([yield (lambda (x) x)]
+                  [resume (lambda (x) x)]
+                  [walk (lambda (l)
+                          (cond
+                            ; is this the only case where walk returns a non-atom?
+                            [(null? l) '()]
+                            [(atom? (car l)) (begin
+                                               (let/cc k2 (begin
+                                                 (set! resume k2) ; now what will happen when resume is called?
+                                                 ; when the next line is executed, what will yield be bound to?
+                                                 (yield (car l))))
+                                               ; when will the next line be executed?
+                                               (walk (cdr l)))]
+                            [else (begin
+                                    ; what will the value of the next line be? why is it ignored?
+                                    (walk (car l))
+                                    (walk (cdr l)))]))]
+                  [next (lambda () ; next is a thunk
+                          (let/cc k3 (begin
+                            (set! yield k3) ; now what will happen when yield is called?
+                            ; when the next line is executed, what will resume be bound to?
+                            (resume 'blah))))]
+                  [check (lambda (prev)
+                           (let ([n (next)])
+                             (cond
+                               [(eq? n prev) #t]
+                               [(atom? n) (check n)]
+                               ; when will n fail to be an atom?
+                               [else #f])))])
+           (lambda (lst)
+             (let ([fst (let/cc k1 (begin
+                          (set! yield k1) ; now what will happen when yield is called?
+                          (walk lst)
+                          ; when will the next line be executed?
+                          (yield '())))])
+               (cond
+                 [(atom? fst) (check fst)]
+                 ; when will fst fail to be an atom?
+                 [else #f])
+               ))))
+
+Here is [[the answer|cps_hint_4]], but again, first try to figure it out for yourself.