+ This evaluates to `111`. Nothing exotic happens here. + +2.100 +let/cc k (10 + 1)

+ This evaluates to `101`; `(+ 100 (let/cc k (+ 10 (k 1))))` is the same as `(reset (+ 100 (shift k (k 1))))`. + +3.100 +let/cc k (10 + k 1)

+ In the second line, we extract the continuation function (the bold part of the previous code) from the pair `p` and apply it to the argument `(2, ident)`. That results in the following code being run: +let p =let/cc k (1,k)in + let y = snd p (2, ident) in + (fst p, y)

+ which in turn results in the nested pair `(2, (2, ident))`. + +4.let p =(2, ident)in + let y = snd p (2, ident) in + (fst p, y)

+ Here the box is implicit, understood to be the rest of the code. The result is just the abort value `11`, because the bold code is skipped. + +5.1000 + (100 +abort 11)

1000 + reset+ Here the box or delimiter is explicitly specified. The bold code is skipped, but the outside code `1000 + < >` is still executed, so we get `1011`. + +6.(100 +abort 11)

1000 + reset+ Equivalent to preceding; results in `1011`. + +7.(100 +shift k (10 + 1))

1000 + reset+ Here we do invoke the captured continuation, so what gets passed to the outside code `1000 + < >` is `k (10 + 1)`, that is, `(100 + (10 + 1))`. Result is `1111`. + +8.(100 +shift k (k (10 + 1)))

1000 + reset+ This also results in `1111`, but via a different path than the preceding. First, note that `k` is bound to `100 + < >`. So `k 1` is `101`. Then `10 + k 1` is `10 + 101`. Then we exit the body of `shift k ( ... )`, without invoking `k` again, so we don't anymore add `100`. Thus we pass `10 + 101` to the outside code `1000 + < >`. So the result is `1000 + (10 + 101)` or `1111`. (Whereas in the preceding example, the result was `1000 + (100 + 11)`. The order in which the operations are performed is different. If we used a non-commutative operation instead of `+`, the results of these two examples would be different from each other.) + +9.(100 +shift k (10 + k 1))

1000 + reset+ Here `k` is bound to `100 + < >`. That's what's returned by the `shift k ( ... )` block, and since `k` isn't invoked (applied) when doing so, the rest of the bold `reset` block is skipped (for now). So we resume the outside code `1000 + < > 1`, with what fills the gap `< >` being the function that was bound to `k`. Thus this is equivalent to `1000 + (fun x -> 100 + x) 1` or `1000 + 101` or `1101`. + +10.(100 +shift k (k))1

1000 + reset+ Here `k` is bound to `100 + < >`. Thus `k 1` is `101`. Now there are two ways to think about what happens next. (Both are valid.) One way to think is that since the `shift` block ends with an additional outermost application of `k`, we continue through the bold code with the value `k 1` or `101`. Thus we get `100 + 101`, and then we continue with the outermost code `1000 + < >`, getting `1000 + (100 + 101)`, or `1201`. The other way to think is that since `k` is `100 + < >`, and `k 1` is `101`, then `k (k 1)` is `201`. Now we leave the `shift` block *without* executing the bold code a third time (we've already taken account of the two applications of `k`), resuming with the outside code `1000 + < >`, thereby getting `1000 + 201` as before. - (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](/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: - - (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](/hints/cps_hint_4), but again, first try to figure it out for yourself. - - -Delimited control operators -=========================== - -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. - -(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.) - -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: - - (1) outer code - ------- reset ------- - | (2) | - | +----shift k ---+ | - | | (3) | | - | | | | - | | | | - | +---------------+ | - | (4) | - +-------------------+ - (5) more outer code - -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. - -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). - -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). - -For instance, in Scheme this: - - (require racket/control) - - (reset - (let ([x 1]) - (+ 10 (shift k x)))) - -will return 1. The `(let ([x 1]) ...` part is evaluated, but the `(+ 10 ...` part is not. - -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. - -This pattern should look somewhat familiar. Recall from our discussion of aborts, and repeated at the top of this page: - - let foo x = - +---try begin----------------+ - | (if x = 1 then 10 | - | else abort 20 | - | ) + 100 | - +---end----------------------+ - in (foo 2) + 1000;; - -The box is working like a reset. The `abort` is implemented with a `shift`. Earlier, we refactored our code into a more CPS form: - - let x = 2 - in let snapshot = fun box -> - let foo_result = box - in (foo_result) + 1000 - in let continue_normally = fun from_value -> - let value = from_value + 100 - in snapshot value - in - if x = 1 then continue_normally 10 - else snapshot 20;; - -`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. - ---- - -Examples of shift/reset/abort ------------------------------ - -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: - - ; (+ 1000 (+ 100 (abort 11))) ~~> 11 - - app2 (op2 plus) (var thousand) - (app2 (op2 plus) (var hundred) (abort (var eleven))) - - # Continuation_monad.(run0( - abort 11 >>= fun i -> - unit (100+i) >>= fun j -> - unit (1000+j)));; - - : int = 11 - -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 11 >>= fun i -> - unit (100+i) >>= fun j -> - unit (1000+j))));; - - : int = 11 - - -Example 2: - - ; (+ 1000 (reset (+ 100 (abort 11)))) ~~> 1011 - - app2 (op2 plus) (var thousand) - (reset (app2 (op2 plus) (var hundred) (abort (var eleven)))) - - # Continuation_monad.(run0( - reset ( - abort 11 >>= fun i -> - unit (100+i) - ) >>= fun j -> - unit (1000+j)));; - - : int = 1011 - -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... this is the best I an do at the moment... *) - - # type 'x either = Left of (int -> ('x,'x either) Continuation_monad.m) | Right of int;; - # Continuation_monad.(let v = reset ( - shift (fun k -> unit (Left k)) >>= fun i -> unit (Right (10+i)) - ) in let w = v >>= fun (Left k) -> - k 1 >>= fun (Right i) -> - unit (100+i) - in run0 w);; - - : int = 111 - - - -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 - - -- 2.11.0(100 +shift k (k (k 1)))