cps tweaks

[lambda.git] / cps_and_continuation_operators.mdwn

diff --git a/cps_and_continuation_operators.mdwn b/cps_and_continuation_operators.mdwn
index 5aa56f6..3b0dda7 100644 (file)
--- a/cps_and_continuation_operators.mdwn
+++ b/cps_and_continuation_operators.mdwn
@@ -3,7 +3,8 @@
 CPS Transforms
 ==============
 
 CPS Transforms
 ==============
 

-We've already approached some tasks now by programming in **continuation-passing style.** We first did that with tuples at the start of term, and then with the v5 lists in [[week4]], and now more recently and self-consciously when discussing [aborts](/couroutines_and_aborts), and [the "abSd" task](from_list_zippers_to_continuations/). and the use of `tree_monadize` specialized to the Continuation monad, which required us to supply an initial continuation.
+We've already approached some tasks now by programming in **continuation-passing style.** We first did that with tuples at the start of term, and then with the v5 lists in [[week4]], and now more recently and self-consciously when discussing [aborts](/couroutines_and_aborts), 
+and [the "abSd" task](/from_list_zippers_to_continuations). and the use of `tree_monadize` specialized to the Continuation monad, which required us to supply an initial continuation.

 
 In our discussion of aborts, we showed how to rearrange code like this:
 
 
 In our discussion of aborts, we showed how to rearrange code like this:
 


@@ -96,9 +97,9 @@ Here's another interesting fact about these transforms. Compare the translations
 To the implementations we proposed for `unit` and `bind` when developing a Continuation monads, for example [here](/list_monad_as_continuation_monad). I'll relabel some of the variable names to help the comparison:
 
        let cont_unit x = fun k -> k x
 To the implementations we proposed for `unit` and `bind` when developing a Continuation monads, for example [here](/list_monad_as_continuation_monad). I'll relabel some of the variable names to help the comparison:
 
        let cont_unit x = fun k -> k x

-       let cont_bind M N = fun k -> M (fun m -> N m k)
+       let cont_bind N M = fun k -> N (fun n -> M n k)

 
 

-The transform for `x` is just `cont_unit x`! And the transform for `M N` is, though not here exactly the same as `cont_bind M N`, quite reminiscent of it. (I don't yet know whether there's an easy and satisfying explanation of why these two diverge as they do.) <!-- FIXME -->
+The transform for `x` is just `cont_unit x`! And the transform for `M N` is, though not here exactly the same as `cont_bind N M`, quite reminiscent of it. (I don't yet know whether there's an easy and satisfying explanation of why these two diverge as they do.) <!-- FIXME -->

 
 Doing CPS transforms by hand is very cumbersome. (Try it.) But you can leverage our lambda evaluator to help you out. Here's how to do it. From here on out, we'll be working with and extending the call-by-value CPS transform set out above:
 
 
 Doing CPS transforms by hand is very cumbersome. (Try it.) But you can leverage our lambda evaluator to help you out. Here's how to do it. From here on out, we'll be working with and extending the call-by-value CPS transform set out above:
 


@@ -124,15 +125,16 @@ Or, using the lambda evaluator, that is:
        ~~> \k. k (succ x)
 
 Some other handy tools: 
        ~~> \k. k (succ x)
 
 Some other handy tools: 

-       let app3 = \a b c. app (app a b) c in
-       let app4 = \a b c d. app (app (app a b) c) d in
+
+       let app2 = \a b c. app (app a b) c in
+       let app3 = \a b c d. app (app (app a b) c) d in

        let op2 = \op. \u. u (\a v. v (\b k. k (op a b))) in
        let op3 = \op. \u. u (\a v. v (\b w. w (\c k. k (op a b c)))) in
        ...
 
 Then, for instance, [plus x y] would be rendered in the lambda evaluator as:
 
        let op2 = \op. \u. u (\a v. v (\b k. k (op a b))) in
        let op3 = \op. \u. u (\a v. v (\b w. w (\c k. k (op a b c)))) in
        ...
 
 Then, for instance, [plus x y] would be rendered in the lambda evaluator as:
 

-       app3 (op2 plus) (var x) (var y)
+       app2 (op2 plus) (var x) (var y)

        ~~> \k. k (plus x y)
 
 To finish off a CPS computation, you have to supply it with an "initial" or "outermost" continuation. (This is somewhat like "running" a monadic computation.) Usually you'll give the identity function, representing that nothing further happens to the continuation-expecting value.
        ~~> \k. k (plus x y)
 
 To finish off a CPS computation, you have to supply it with an "initial" or "outermost" continuation. (This is somewhat like "running" a monadic computation.) Usually you'll give the identity function, representing that nothing further happens to the continuation-expecting value.


@@ -148,7 +150,7 @@ I won't give the CPS transform for `callcc` itself, but instead for the complex
 
        [callcc (\k. body)] = \outk. (\k. [body] outk) (\v localk. outk v)
 
 
        [callcc (\k. body)] = \outk. (\k. [body] outk) (\v localk. outk v)
 

-The behavior of `callcc` is this. The whole expression `callcc (\k. body)`, call it C, is being evaluated in a context, call it E[\_]. When we convert to CPS form, the continuation of this occurrence of C will be bound to the variable `outk`. What happens then is that we bind the expression `\v localk. outk v` to the variable `k` and evaluate [body], passing through to it the existing continuation `outk`. Now if `body` is just, for example, `x`, then its CPS transform [x] will be `\j. j x` and this will accept the continuation `outk` and feed it `x`, and we'll continue on with nothing unusual occurring. If on the other hand `body` makes use of the variable `k`, what happens then? For example, suppose `body` includes `foo (k v)`. In the reduction of the CPS transform `[foo (k v)]`, `v` will be passed to `k` which as we said is now `\v localk. outk v`. The continuation of that application---what happens to `k v` after it's evaluated and `foo` gets access to it---will be bound next to `localk`. But notice that this `localk` is discarded. The computation goes on without it. Instead, it just continues evaluating `outk v`, where as we said `outk` is the outside continuation E[\_] of the whole `callcc (\k. body)` invocation.
+The behavior of `callcc` is this. The whole expression `callcc (\k. body)`, call it C, is being evaluated in a context, call it E[\_]. When we convert to CPS form, the continuation of this occurrence of C will be bound to the variable `outk`. What happens then is that we bind the expression `\v localk. outk v` to the variable `k` and evaluate [body], passing through to it the existing continuation `outk`. Now if `body` is just, for example, `x`, then its CPS transform [x] will be `\j. j x` and this will accept the continuation `outk` and feed it `x`, and we'll continue on with nothing unusual occurring. If on the other hand `body` makes use of the variable `k`, what happens then? For example, suppose `body` includes `foo (k v)`. In the reduction of the CPS transform `[foo (k v)]`, `v` will be passed to `k` which as we said is now `\v localk. outk v`. The continuation of that application---what is scheduled to happen to `k v` after it's evaluated and `foo` gets access to it---will be bound next to `localk`. But notice that this `localk` is discarded. The computation goes on without it. Instead, it just continues evaluating `outk v`, where as we said `outk` is the outside continuation E[\_] of the whole `callcc (\k. body)` invocation.

 
 So in other words, since the continuation in which `foo` was to be applied to the value of `k v` was discarded, that application never gets evaluated. We escape from that whole block of code.
 
 
 So in other words, since the continuation in which `foo` was to be applied to the value of `k v` was discarded, that application never gets evaluated. We escape from that whole block of code.
 


@@ -156,7 +158,7 @@ It's important to understand that `callcc` binds `k` to a pipe into the continua
 
 So too will examples. We'll give some examples, and show you how to try them out in a variety of formats:
 
 
 So too will examples. We'll give some examples, and show you how to try them out in a variety of formats:
 

-(i)    using the lambda evaluator to check how the CPS transforms reduce
+1.     using the lambda evaluator to check how the CPS transforms reduce

 
        To do this, you can use the following helper function:
 
 
        To do this, you can use the following helper function:
 


@@ -165,15 +167,15 @@ So too will examples. We'll give some examples, and show you how to try them out
 
        Used like this: [callcc (\k. body)] = `callcc (\k. BODY)`, where `BODY` is [body].
 
 
        Used like this: [callcc (\k. body)] = `callcc (\k. BODY)`, where `BODY` is [body].
 

-(ii) using a `callcc` operation on our Continuation monad
+2.     using a `callcc` operation on our Continuation monad

 
        This is implemented like this:
 
                let callcc body = fun outk -> body (fun v localk -> outk v) outk
 
 
        This is implemented like this:
 
                let callcc body = fun outk -> body (fun v localk -> outk v) outk
 

-       GOTCHAS??
+<!-- GOTCHAS?? -->

 
 

-(iii)  `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:
+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:

 
        (call/cc (lambda (k) ...))
 
 
        (call/cc (lambda (k) ...))
 


@@ -190,14 +192,14 @@ First, here are two examples in Scheme:
        (+ 100 (let/cc k (+ 10 1)))
               |-----------------|
 
        (+ 100 (let/cc k (+ 10 1)))
               |-----------------|
 

-This binds the continuation `outk` of the underlined expression to `k`, the computes `(+ 10 1) and delivers that to `outk` in the normal way (not through `k`). No unusual behavior. It evaluates to `111.
+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`.

 
 

-Now if we do instead:
+What if we do instead:

 
        (+ 100 (let/cc k (+ 10 (k 1))))
               |---------------------|
 
 
        (+ 100 (let/cc k (+ 10 (k 1))))
               |---------------------|
 

-Now, 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`.
+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`.

 
 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:
 
 
 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:
 


@@ -205,7 +207,7 @@ You are not restricted to calling a bound continuation only once, nor are you re
          (cons (car p) ((cdr p) (cons 2 (lambda (x) x)))))
        ; evaluates to '(2 2 . #<procedure>)
 
          (cons (car p) ((cdr p) (cons 2 (lambda (x) x)))))
        ; evaluates to '(2 2 . #<procedure>)
 

-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 nest pair, whose first element is `2` and whose second element is the pair `'(2 . #<identity procedure>)`. Racket displays this nested pair like this:
+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:

 
        '(2 2 . #<procedure>)
 
 
        '(2 2 . #<procedure>)
 


@@ -216,21 +218,21 @@ In the lambda evaluator:
        let var = \x (\k. k x) in
        let lam = \x_body (\k. k (\x. x_body x)) in
        let app = \m n. (\k. m (\m. n (\n. m n k))) in
        let var = \x (\k. k x) in
        let lam = \x_body (\k. k (\x. x_body x)) in
        let app = \m n. (\k. m (\m. n (\n. m n k))) in

-       let app3 = \a b c. app (app a b) c in
-       let app4 = \a b c d. app (app (app a b) c) d in
+       let app2 = \a b c. app (app a b) c in
+       let app3 = \a b c d. app (app (app a b) c) d in

        let op1 = \op. \u. u (\a k. k (op a)) in
        let op2 = \op. \u. u (\a v. v (\b k. k (op a b))) in
        let op3 = \op. \u. u (\a v. v (\b w. w (\c k. k (op a b c)))) in
        let callcc = \k_body. \outk. (\k. (k_body k) outk) (\v localk. outk v) in
 
        ; (+ 100 (let/cc k (+ 10 1))) ~~> 111
        let op1 = \op. \u. u (\a k. k (op a)) in
        let op2 = \op. \u. u (\a v. v (\b k. k (op a b))) in
        let op3 = \op. \u. u (\a v. v (\b w. w (\c k. k (op a b c)))) in
        let callcc = \k_body. \outk. (\k. (k_body k) outk) (\v localk. outk v) in
 
        ; (+ 100 (let/cc k (+ 10 1))) ~~> 111

-       app3 (op2 plus) (var hundred) (callcc (\k. app3 (op2 plus) (var ten) (var one)))
+       app2 (op2 plus) (var hundred) (callcc (\k. app2 (op2 plus) (var ten) (var one)))

        ; evaluates to \k. k (plus hundred (plus ten one))
 
 Next:
 
        ; (+ 100 (let/cc k (+ 10 (k 1)))) ~~> 101
        ; evaluates to \k. k (plus hundred (plus ten one))
 
 Next:
 
        ; (+ 100 (let/cc k (+ 10 (k 1)))) ~~> 101

-       app3 (op2 plus) (var hundred) (callcc (\k. app3 (op2 plus) (var ten) (app (var k) (var one))))
+       app2 (op2 plus) (var hundred) (callcc (\k. app2 (op2 plus) (var ten) (app (var k) (var one))))

        ; evaluates to \k. k (plus hundred one)
 
 We won't try to do the third example in this framework.
        ; evaluates to \k. k (plus hundred one)
 
 We won't try to do the third example in this framework.


@@ -244,7 +246,7 @@ Now what we want to do is something like this:
 
        # C.(run0 (100 + callcc (fun k -> 10 + 1)));;
 
 
        # C.(run0 (100 + callcc (fun k -> 10 + 1)));;
 

-`run0` is a special function in the Continuation monad that runs a value of that monad using the identity function as its initial continuation. The above expression won't typee-check, for several reasons. First, we're trying to add 100 to `callcc (...)` but the latter is a `Continuation.m` value, not an `int`. So we have to do this instead:
+`run0` is a special function in the Continuation monad that runs a value of that monad using the identity function as its initial continuation. The above expression won't type-check, for several reasons. First, we're trying to add 100 to `callcc (...)` but the latter is a `Continuation.m` value, not an `int`. So we have to do this instead:

 
        # C.(run0 (callcc (fun k -> 10 + 1) >>= fun i -> 100 + i));;
 
 
        # C.(run0 (callcc (fun k -> 10 + 1) >>= fun i -> 100 + i));;
 


@@ -277,7 +279,7 @@ If we figure this out later (or anyone else does), we'll come back and report. <
 Delimited control operators
 ===========================
 
 Delimited control operators
 ===========================
 

-`callcc` is what's known as an *undelimited control operator*. That is, the continuations `outk` that get bound inside our `k`s behave as though they include all the code from the `call/cc ...` out to *and including* the end of the program.
+`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.

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


@@ -306,7 +308,7 @@ I set (2) aside a moment ago. The story we just told is a bit too simple because
 For instance, in Scheme this:
 
        (require racket/control)
 For instance, in Scheme this:
 
        (require racket/control)

-
+       

        (reset
         (let ([x 1])
           (+ 10 (shift k x))))
        (reset
         (let ([x 1])
           (+ 10 (shift k x))))


@@ -347,18 +349,18 @@ Using `shift` and `reset` operators in OCaml, this would look like this:
        let reset = Delimcc.push_prompt p;;
        let shift = Delimcc.shift p;;
        let abort = Delimcc.abort p;;
        let reset = Delimcc.push_prompt p;;
        let shift = Delimcc.shift p;;
        let abort = Delimcc.abort p;;

-
+       

        let foo x =
          reset(fun () ->
        let foo x =
          reset(fun () ->

-               shift(fun continue ->
-                       if x = 1 then continue 10
-                       else 20
-               ) + 100
+           shift(fun continue ->
+               if x = 1 then continue 10
+               else 20
+           ) + 100

          )
        in foo 2 + 1000;;
        - : int = 1020
 
          )
        in foo 2 + 1000;;
        - : int = 1020
 

-If instead at the end we did `in foo 1 + 1000`, we'd get the result `1110`.
+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.
 


@@ -371,7 +373,7 @@ The relevant CPS transforms will be performed by these helper functions:
 
 You use these like so:
 
 
 You use these like so:
 

-*      [prompt m] is `prompt M` where `M` is [m]
+*      [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]
        
 *      [shift k M] is `shift (\k. M)` where `M` is [m]
 *      and [abort M] is `abort M` where `M` is [m]
        


@@ -394,157 +396,138 @@ In collecting these CPS transforms and implementing the monadic versions, we've
 Examples of shift/reset/abort
 -----------------------------
 
 Examples of shift/reset/abort
 -----------------------------
 

-Here are some more examples of using delimited control operators. We present first a Scheme formulation; then we compute the same result using CPS and the lambda evaluator.
-
-
-; (+ 100 (+ 10 (abort 1))) ~~> 1
-app3 (op2 plus) (var hundred)
-  (app3 (op2 plus) (var ten) (abort (var one)))
-
-; (+ 100 (prompt (+ 10 (abort 1)))) ~~> 101
-app3 (op2 plus) (var hundred)
-  (prompt (app3 (op2 plus) (var ten) (abort (var one))))
-
-; (+ 1000 (prompt (+ 100 (shift k (+ 10 1))))) ~~> 1011
-app3 (op2 plus) (var thousand)
-  (prompt (app3 (op2 plus) (var hundred)
-    (shift (\k. ((op2 plus) (var ten) (var one))))))
-
-; (+ 1000 (prompt (+ 100 (shift k (k (+ 10 1)))))) ~~> 1111
-app3 (op2 plus) (var thousand)
-  (prompt (app3 (op2 plus) (var hundred)
-    (shift (\k. (app (var k) ((op2 plus) (var ten) (var one)))))))
-
-; (+ 1000 (prompt (+ 100 (shift k (+ 10 (k 1)))))) ~~> 1111 but added differently
-app3 (op2 plus) (var thousand)
-  (prompt (app3 (op2 plus) (var hundred)
-    (shift (\k. ((op2 plus) (var ten) (app (var k) (var one)))))))
-
-; (+ 100 ((prompt (+ 10 (shift k k))) 1)) ~~> 111
-app3 (op2 plus) (var hundred)
-  (app (prompt (app3 (op2 plus) (var ten)
-    (shift (\k. (var k))))) (var one))
-
-; (+ 100 (prompt (+ 10 (shift k (k (k 1)))))) ~~> 121
-app3 (op2 plus) (var hundred)
-  (prompt (app3 (op2 plus) (var ten)
-    (shift (\k. app (var k) (app (var k) (var one))))))
-
-
- * (* (+ 1000 (prompt (+ 100 (shift k (+ 10 1))))) ~~> 1011 *)
- * let example1 () : int =
- *   Continuation_monad.(let v = reset (
- *       let u = shift (fun k -> unit (10 + 1))
- *       in u >>= fun x -> unit (100 + x)
- *     ) in let w = v >>= fun x -> unit (1000 + x)
- *     in run w)
- *
- * (* (+ 1000 (prompt (+ 100 (shift k (k (+ 10 1)))))) ~~> 1111 *)
- * let example2 () =
- *   Continuation_monad.(let v = reset (
- *       let u = shift (fun k -> k (10 :: [1]))
- *       in u >>= fun x -> unit (100 :: x)
- *     ) in let w = v >>= fun x -> unit (1000 :: x)
- *     in run w)
- *
- * (* (+ 1000 (prompt (+ 100 (shift k (+ 10 (k 1)))))) ~~> 1111 but added differently *)
- * let example3 () =
- *   Continuation_monad.(let v = reset (
- *       let u = shift (fun k -> k [1] >>= fun x -> unit (10 :: x))
- *       in u >>= fun x -> unit (100 :: x)
- *     ) in let w = v >>= fun x -> unit (1000 :: x)
- *     in run w)
- *
- * (* (+ 100 ((prompt (+ 10 (shift k k))) 1)) ~~> 111 *)
- * (* not sure if this example can be typed without a sum-type *)
- *
- * (* (+ 100 (prompt (+ 10 (shift k (k (k 1)))))) ~~> 121 *)
- * let example5 () : int =
- *   Continuation_monad.(let v = reset (
- *       let u = shift (fun k -> k 1 >>= fun x -> k x)
- *       in u >>= fun x -> unit (10 + x)
- *     ) in let w = v >>= fun x -> unit (100 + x)
- *     in run w)
-
-module C = Continuation_monad;;
-
-
-print_endline "=== test TreeT(Continuation).distribute ==================";;
-
-let id : 'z. 'z -> 'z = fun x -> x
-
-let example n : (int * int) =
-  Continuation_monad.(let u = callcc (fun k ->
-      (if n < 0 then k 0 else unit [n + 100])
-      (* all of the following is skipped by k 0; the end type int is k's input type *)
-      >>= fun [x] -> unit (x + 1)
-  )
-  (* k 0 starts again here, outside the callcc (...); the end type int * int is k's output type *)
-  >>= fun x -> unit (x, 0)
-  in run0 u)
-
-
-(* (+ 1000 (prompt (+ 100 (shift k (+ 10 1))))) ~~> 1011 *)
-let example1 () : int =
-  Continuation_monad.(let v = reset (
-      let u = shift (fun k -> unit (10 + 1))
-      in u >>= fun x -> unit (100 + x)
-    ) in let w = v >>= fun x -> unit (1000 + x)
-    in run0 w)
-
-(* (+ 1000 (prompt (+ 100 (shift k (k (+ 10 1)))))) ~~> 1111 *)
-let example2 () =
-  Continuation_monad.(let v = reset (
-      let u = shift (fun k -> k (10 :: [1]))
-      in u >>= fun x -> unit (100 :: x)
-    ) in let w = v >>= fun x -> unit (1000 :: x)
-    in run0 w)
-
-(* (+ 1000 (prompt (+ 100 (shift k (+ 10 (k 1)))))) ~~> 1111 but added differently *)
-let example3 () =
-  Continuation_monad.(let v = reset (
-      let u = shift (fun k -> k [1] >>= fun x -> unit (10 :: x))
-      in u >>= fun x -> unit (100 :: x)
-    ) in let w = v >>= fun x -> unit (1000 :: x)
-    in run0 w)
-
-(* (+ 100 ((prompt (+ 10 (shift k k))) 1)) ~~> 111 *)
-(* not sure if this example can be typed without a sum-type *)
-
-(* (+ 100 (prompt (+ 10 (shift k (k (k 1)))))) ~~> 121 *)
-let example5 () : int =
-  Continuation_monad.(let v = reset (
-      let u = shift (fun k -> k 1 >>= k)
-      in u >>= fun x -> unit (10 + x)
-    ) in let w = v >>= fun x -> unit (100 + x)
-    in run0 w)
-
-;;
-
-print_endline "=== test bare Continuation ============";;
-
-(1011, 1111, 1111, 121);;
-(example1(), example2(), example3(), example5());;
-((111,0), (0,0));;
-(example ~+10, example ~-10);;
-
-
-print_endline "=== pa_monad's Continuation Tests ============";;
-
-(1, 5 = C.(run0 (unit 1 >>= fun x -> unit (x+4))) );;
-(2, 9 = C.(run0 (reset (unit 5 >>= fun x -> unit (x+4)))) );;
-(3, 9 = C.(run0 (reset (abort 5 >>= fun y -> unit (y+6)) >>= fun x -> unit (x+4))) );;
-(4, 9 = C.(run0 (reset (reset (abort 5 >>= fun y -> unit (y+6))) >>= fun x -> unit (x+4))) );;
-(5, 27 = C.(run0 (
-              let c = reset(abort 5 >>= fun y -> unit (y+6))
-              in reset(c >>= fun v1 -> abort 7 >>= fun v2 -> unit (v2+10) ) >>= fun x -> unit (x+20))) );;
-
-(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))) );;
-
-(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))) );;
-
-(12, ["a"] = C.(run0 (reset (shift (fun f -> f [] >>= fun t -> unit ("a"::t)  ) >>= fun xv -> shift (fun _ -> unit xv)))) );;
-
-
-(0, 15 = C.(run0 (let f k = k 10 >>= fun v-> unit (v+100) in reset (callcc f >>= fun v -> unit (v+5)))) );;
+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.)
+
+
+Example 1:
+
+       ; (+ 100 (+ 10 (abort 1))) ~~> 1
+       
+       app2 (op2 plus) (var hundred)
+         (app2 (op2 plus) (var ten) (abort (var one)))
+       
+       # Continuation_monad.(run0(
+           abort 1 >>= fun i ->
+           unit (10+i) >>= fun j ->
+           unit (100+j)));;
+       - : int = 1
+
+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:
+
+       # Continuation_monad.(run0(
+           reset (
+             abort 1 >>= fun i ->
+             unit (10+i) >>= fun j ->
+             unit (100+j))));;
+       - : int = 1
+

 
 

+Example 2:
+       
+       ; (+ 100 (reset (+ 10 (abort 1)))) ~~> 101
+       
+       app2 (op2 plus) (var hundred)
+         (reset (app2 (op2 plus) (var ten) (abort (var one))))
+       
+       # Continuation_monad.(run0(
+           reset (
+             abort 1 >>= fun i ->
+             unit (10+i)) >>= fun j ->
+              unit (100+j)));;
+       - : int = 101
+
+Example 3:
+
+       ; (+ 1000 (reset (+ 100 (shift k (+ 10 1))))) ~~> 1011
+
+       app2 (op2 plus) (var thousand)
+         (reset (app2 (op2 plus) (var hundred)
+           (shift (\k. ((op2 plus) (var ten) (var one))))))
+
+       Continuation_monad.(
+         let v = reset (
+           let u = shift (fun k -> unit (10 + 1))
+           in u >>= fun x -> unit (100 + x)
+         ) in let w = v >>= fun x -> unit (1000 + x)
+         in run0 w);;
+       - : int = 1011
+
+Example 4:
+
+       ; (+ 1000 (reset (+ 100 (shift k (k (+ 10 1)))))) ~~> 1111
+       
+       app2 (op2 plus) (var thousand)
+         (reset (app2 (op2 plus) (var hundred)
+           (shift (\k. (app (var k) ((op2 plus) (var ten) (var one)))))))
+       
+       Continuation_monad.(
+         let v = reset (
+           let u = shift (fun k -> k (10 :: [1]))
+           in u >>= fun x -> unit (100 :: x)
+         ) in let w = v >>= fun x -> unit (1000 :: x)
+         in run0 w);;
+       - : int list = [1000; 100; 10; 1]
+
+To demonstrate the different adding order between Examples 4 and 5, we use `::` in the OCaml version instead of `+`. Here is Example 5:
+
+       ; (+ 1000 (reset (+ 100 (shift k (+ 10 (k 1)))))) ~~> 1111 but added differently
+
+       app2 (op2 plus) (var thousand)
+         (reset (app2 (op2 plus) (var hundred)
+           (shift (\k. ((op2 plus) (var ten) (app (var k) (var one)))))))
+       
+       Continuation_monad.(let v = reset (
+         let u = shift (fun k -> k [1] >>= fun x -> unit (10 :: x))
+           in u >>= fun x -> unit (100 :: x)
+         ) in let w = v >>= fun x -> unit (1000 :: x)
+         in run0  w)
+       - : int list = [1000; 10; 100; 1]
+
+
+Example 6:
+
+       ; (+ 100 ((reset (+ 10 (shift k k))) 1)) ~~> 111
+       
+       app2 (op2 plus) (var hundred)
+         (app (reset (app2 (op2 plus) (var ten)
+           (shift (\k. (var k))))) (var one))
+       
+       (* not sure if this example can be typed as-is in OCaml. We may need a sum-type *)
+
+Example 7:
+
+       ; (+ 100 (reset (+ 10 (shift k (k (k 1)))))) ~~> 121
+       
+       app2 (op2 plus) (var hundred)
+         (reset (app2 (op2 plus) (var ten)
+           (shift (\k. app (var k) (app (var k) (var one))))))
+       
+       Continuation_monad.(let v = reset (
+         let u = shift (fun k -> k 1 >>= fun x -> k x)
+           in u >>= fun x -> unit (10 + x)
+         ) in let w = v >>= fun x -> unit (100 + x)
+         in run0 w)
+       - : int = 121
+
+<!--
+
+       print_endline "=== pa_monad's Continuation Tests ============";;
+
+       (1, 5 = C.(run0 (unit 1 >>= fun x -> unit (x+4))) );;
+       (2, 9 = C.(run0 (reset (unit 5 >>= fun x -> unit (x+4)))) );;
+       (3, 9 = C.(run0 (reset (abort 5 >>= fun y -> unit (y+6)) >>= fun x -> unit (x+4))) );;
+       (4, 9 = C.(run0 (reset (reset (abort 5 >>= fun y -> unit (y+6))) >>= fun x -> unit (x+4))) );;
+       (5, 27 = C.(run0 (
+                                 let c = reset(abort 5 >>= fun y -> unit (y+6))
+                                 in reset(c >>= fun v1 -> abort 7 >>= fun v2 -> unit (v2+10) ) >>= fun x -> unit (x+20))) );;
+
+       (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))) );;
+
+       (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))) );;
+
+       (12, ["a"] = C.(run0 (reset (shift (fun f -> f [] >>= fun t -> unit ("a"::t)  ) >>= fun xv -> shift (fun _ -> unit xv)))) );;
+
+
+       (0, 15 = C.(run0 (let f k = k 10 >>= fun v-> unit (v+100) in reset (callcc f >>= fun v -> unit (v+5)))) );;
+
+-->