ass10 hint tweaks

[lambda.git] / cps_and_continuation_operators.mdwn

diff --git a/cps_and_continuation_operators.mdwn b/cps_and_continuation_operators.mdwn
index df27db7..72b0034 100644 (file)
--- a/cps_and_continuation_operators.mdwn
+++ b/cps_and_continuation_operators.mdwn
@@ -283,7 +283,7 @@ Here are a series of examples from *The Seasoned Schemer*, which we recommended
 
 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.
 
 
 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.
 

-All of the examples assume the following preface:
+Most of the examples assume the following preface:

 
        #lang racket
 
 
        #lang racket
 


@@ -330,13 +330,14 @@ Next, try to figure out what this function does:
                              [(null? l) (k 'notfound)]
                              [(eq? (car l) a) (cdr l)]
                              [(atom? (car l)) (cons (car l) (aux (cdr l) k))]
                              [(null? l) (k 'notfound)]
                              [(eq? (car l) a) (cdr l)]
                              [(atom? (car l)) (cons (car l) (aux (cdr l) k))]

-                             ; what happens when (car l) exists but isn't an atom?
-                             [else (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))]))]))]
+                             [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
                     [lst2 (let/cc k1 ; now what will happen when k1 is called?
                             (aux lst k1))])
              (cond


@@ -344,7 +345,6 @@ Next, try to figure out what this function does:
                [(eq? lst2 'notfound) lst]
                [else lst2]))))
 
                [(eq? lst2 'notfound) lst]
                [else lst2]))))
 

-

 Here is [the answer](/hints/cps_hint_3), but try to figure it out for yourself.
 
 Here is the hardest example. Try to figure out what this function does:
 Here is [the answer](/hints/cps_hint_3), but try to figure it out for yourself.
 
 Here is the hardest example. Try to figure out what this function does:


@@ -357,10 +357,10 @@ Here is the hardest example. Try to figure out what this function does:
                             ; is this the only case where walk returns a non-atom?
                             [(null? l) '()]
                             [(atom? (car l)) (begin
                             ; is this the only case where walk returns a non-atom?
                             [(null? l) '()]
                             [(atom? (car l)) (begin

-                                               (let/cc k2
+                                               (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?
                                                  (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)))
+                                                 (yield (car l))))

                                                ; when will the next line be executed?
                                                (walk (cdr l)))]
                             [else (begin
                                                ; when will the next line be executed?
                                                (walk (cdr l)))]
                             [else (begin


@@ -368,10 +368,10 @@ Here is the hardest example. Try to figure out what this function does:
                                     (walk (car l))
                                     (walk (cdr l)))]))]
                   [next (lambda () ; next is a thunk
                                     (walk (car l))
                                     (walk (cdr l)))]))]
                   [next (lambda () ; next is a thunk

-                          (let/cc k3
+                          (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?
                             (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)))]
+                            (resume 'blah))))]

                   [check (lambda (prev)
                            (let ([n (next)])
                              (cond
                   [check (lambda (prev)
                            (let ([n (next)])
                              (cond


@@ -380,11 +380,11 @@ Here is the hardest example. Try to figure out what this function does:
                                ; when will n fail to be an atom?
                                [else #f])))])
            (lambda (lst)
                                ; when will n fail to be an atom?
                                [else #f])))])
            (lambda (lst)

-             (let ([fst (let/cc k1
+             (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?
                           (set! yield k1) ; now what will happen when yield is called?
                           (walk lst)
                           ; when will the next line be executed?

-                          (yield '()))])
+                          (yield '())))])

                (cond
                  [(atom? fst) (check fst)]
                  ; when will fst fail to be an atom?
                (cond
                  [(atom? fst) (check fst)]
                  ; when will fst fail to be an atom?


@@ -397,11 +397,15 @@ Here is [the answer](/hints/cps_hint_4), but again, first try to figure it out f
 Delimited control operators
 ===========================
 
 Delimited control operators
 ===========================
 

-`callcc` is what's known as an *undelimited control operator*. That is, the continuations `outk` that get bound to our `k`s behave as though they include all the code from the `call/cc ...` out to *and including* the end of the program.
+Here again is the CPS transform for `callcc`:
+
+       [callcc (\k. body)] = \outk. (\k. [body] outk) (\v localk. outk v)
+
+`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.

 
 

-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 the latter have been formulated.
+(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.)

 
 

-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.
+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.

 
 It works like this:
 
 
 It works like this:
 


@@ -482,7 +486,7 @@ If instead at the end we did `... foo 1 + 1000`, we'd get the result `1110`.
 
 The above OCaml code won't work out of the box; you have to compile and install a special library that Oleg wrote. We discuss it on our [translation page](/translating_between_ocaml_scheme_and_haskell). If you can't get it working, then you can play around with `shift` and `reset` in Scheme instead. Or in the Continuation monad. Or using CPS transforms of your code, with the help of the lambda evaluator.
 
 
 The above OCaml code won't work out of the box; you have to compile and install a special library that Oleg wrote. We discuss it on our [translation page](/translating_between_ocaml_scheme_and_haskell). If you can't get it working, then you can play around with `shift` and `reset` in Scheme instead. Or in the Continuation monad. Or using CPS transforms of your code, with the help of the lambda evaluator.
 

-The relevant CPS transforms will be performed by these helper functions:
+You can make the lambda evaluator perform the required CPS transforms with these helper functions:

 
        let reset = \body. \outk. outk (body (\i i)) in
        let shift = \k_body. \midk. (\k. (k_body k) (\i i)) (\a localk. localk (midk a)) in
 
        let reset = \body. \outk. outk (body (\i i)) in
        let shift = \k_body. \midk. (\k. (k_body k) (\i i)) (\a localk. localk (midk a)) in


@@ -491,14 +495,14 @@ The relevant CPS transforms will be performed by these helper functions:
 
 You use these like so:
 
 
 You use these like so:
 

-*      [reset m] is `reset M` where `M` is [m]
-*      [shift k M] is `shift (\k. M)` where `M` is [m]
-*      and [abort M] is `abort M` where `M` is [m]
+*      [reset body] is `reset BODY` where `BODY` is [body]
+*      [shift k body] is `shift (\k. BODY)` where `BODY` is [body]
+*      and [abort value] is `abort VALUE` where `VALUE` is [value]

        
 There are also `reset` and `shift` and `abort` operations in the Continuation monad in our OCaml [[monad library]]. You can check the code for details.
 
 
        
 There are also `reset` and `shift` and `abort` operations in the Continuation monad in our OCaml [[monad library]]. You can check the code for details.
 
 

-As we said, there are many varieties of delimited continuations. Another common pair is `prompt` and `control`. There's no difference in meaning between `prompt` and `reset`; it's just that people tend to say `reset` when talking about `shift` and `prompt` when talking about `control`. `control` acts subtly differently from `shift`. In the uses you're likely to make as you're just learning about continuations, you won't see any difference. If you'll do more research in this vicinity, you'll soon enough learn about the differences.
+As we said, there are many varieties of delimited continuations. Another common pair is `prompt` and `control`. There's no difference in meaning between `prompt` and `reset`; it's just that people tend to say `reset` when talking about `shift`, and `prompt` when talking about `control`. `control` acts subtly differently from `shift`. In the uses you're likely to make as you're just learning about continuations, you won't see any difference. If you'll do more research in this vicinity, you'll soon enough learn about the differences.

 
 (You can start by reading [the Racket docs](http://docs.racket-lang.org/reference/cont.html?q=shift&q=do#%28part._.Classical_.Control_.Operators%29).)
 
 
 (You can start by reading [the Racket docs](http://docs.racket-lang.org/reference/cont.html?q=shift&q=do#%28part._.Classical_.Control_.Operators%29).)