These transforms have some interesting properties. One is that---assuming we never reduce inside a lambda term, but only when redexes are present in the outermost level---the formulas generated by these transforms will always only have a single candidate redex to be reduced at any stage. In other words, the generated expressions dictate in what order the components from the original expressions will be evaluated. As it happens, the first transform above forces a *call-by-name* reduction order: assuming `M N` to be a redex, redexes inside `N` will be evaluated only after `N` has been substituted into `M`. And the second transform forces a *call-by-value* reduction order. These reduction orders will be forced no matter what the native reduction order of the interpreter is, just so long as we're only allowed to reduce redexes not underneath lambdas.
-Plotkin did important early work with CPS transforms (around 1975), and they are now a staple of academic computer science.
+Plotkin did important early work with CPS transforms, and they are now a staple of academic computer science. (See the end of his 1975 paper [Call-by-name, call-by-value, and the lambda-calculus](http://homepages.inf.ed.ac.uk/gdp/publications/cbn_cbv_lambda.pdf).)
Here's another interesting fact about these transforms. Compare the translations for variables and applications in the call-by-value transform:
[x] --> \k. k x
[M N] --> \k. [M] (\m. [N] (\n. m n k))
-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:
+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 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 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 -->
+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 are related as they are.) <!-- 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:
let callcc body = fun outk -> body (fun v localk -> outk v) outk
-<!-- GOTCHAS?? -->
+ <!-- GOTCHAS?? -->
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) ...))
-I prefer instead to use the lighter, and equivalent, shorthand:
+ I prefer instead to use the lighter, and equivalent, shorthand:
- (let/cc k ...)
+ (let/cc k ...)
-Callcc examples
----------------
+Callcc/letcc examples
+---------------------
First, here are two examples in Scheme:
This also works and as you can see, delivers the expected answer `101`.
-At the moment, I'm not able to get the third example working with the monadic library. I thought that this should do it, but it doesn't type-check:
+The third example is more difficult to make work with the monadic library, because its types are tricky. I was able to get this to work, which uses OCaml's "polymorphic variants." These are generally more relaxed about typing. There may be a version that works with regular OCaml types, but I haven't yet been able to identify it. Here's what does work:
- # C.(run0 (callcc (fun k -> unit (1,k)) >>= fun (p1,p2) -> p2 (2,unit) >>= fun p2' -> unit (p1,p2')));;
+ # C.(run0 (callcc (fun k -> unit (1,`Box k)) >>= fun (p1,`Box p2) -> p2 (2,`Box unit) >>= fun p2' -> unit (p1,p2')));;
+ - : int * (int * [ `Box of 'b -> ('a, 'b) C.m ] as 'b) as 'a =
+ (2, (2, `Box <fun>))
-If we figure this out later (or anyone else does), we'll come back and report. <!-- FIXME -->
+<!-- FIXME -->
+Some callcc/letcc exercises
+---------------------------
+
+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](/assignment8/) and [here](/week1/) and [here](/translating_between_ocaml_scheme_and_haskell). 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](/hints/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](/hints/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](/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
===========================
-`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 for `callcc`:
-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.
+ [callcc (\k. body)] = \outk. (\k. [body] outk) (\v localk. outk v)
-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.
+`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.)
+
+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:
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
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).)
Example 1:
- ; (+ 100 (+ 10 (abort 1))) ~~> 1
+ ; (+ 1000 (+ 100 (abort 11))) ~~> 11
- app2 (op2 plus) (var hundred)
- (app2 (op2 plus) (var ten) (abort (var one)))
+ app2 (op2 plus) (var thousand)
+ (app2 (op2 plus) (var hundred) (abort (var eleven)))
# Continuation_monad.(run0(
- abort 1 >>= fun i ->
- unit (10+i) >>= fun j ->
- unit (100+j)));;
- - : int = 1
+ 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 1 >>= fun i ->
- unit (10+i) >>= fun j ->
- unit (100+j))));;
- - : int = 1
+ abort 11 >>= fun i ->
+ unit (100+i) >>= fun j ->
+ unit (1000+j))));;
+ - : int = 11
Example 2:
- ; (+ 100 (reset (+ 10 (abort 1)))) ~~> 101
+ ; (+ 1000 (reset (+ 100 (abort 11)))) ~~> 1011
- app2 (op2 plus) (var hundred)
- (reset (app2 (op2 plus) (var ten) (abort (var one))))
+ app2 (op2 plus) (var thousand)
+ (reset (app2 (op2 plus) (var hundred) (abort (var eleven))))
# Continuation_monad.(run0(
reset (
- abort 1 >>= fun i ->
- unit (10+i)
+ abort 11 >>= fun i ->
+ unit (100+i)
) >>= fun j ->
- unit (100+j)));;
- - : int = 101
+ unit (1000+j)));;
+ - : int = 1011
Example 3:
(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))
+ 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)
+ in run0 w);;
- : int list = [1000; 10; 100; 1]
(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 *)
+ (* 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
+
+<!--
+# type either = Left of (int -> either) | Right of int;;
+# let getleft e = match e with Left lft -> lft | Right _ -> failwith "not a Left";;
+# let getright e = match e with Right rt -> rt | Left _ -> failwith "not a Right";;
+# 100 + getright (let v = reset (fun p () -> Right (10 + shift p (fun k -> Left k))) in getleft v 1);;
+-->
Example 7:
(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)
+ 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)