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
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 -->
For instance, in Scheme this:
(require racket/control)
-
+
(reset
(let ([x 1])
(+ 10 (shift k x))))
let reset = Delimcc.push_prompt p;;
let shift = Delimcc.shift p;;
let abort = Delimcc.abort p;;
-
+
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
Example 1:
- ; (+ 100 (+ 10 (abort 1))) ~~> 1
-
- app2 (op2 plus) (var hundred)
- (app2 (op2 plus) (var ten) (abort (var one)))
-
+ ; (+ 1000 (+ 100 (abort 11))) ~~> 11
+
+ 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
+ reset (
+ abort 11 >>= fun i ->
+ unit (100+i) >>= fun j ->
+ unit (1000+j))));;
+ - : int = 11
Example 2:
- ; (+ 100 (reset (+ 10 (abort 1)))) ~~> 101
-
- app2 (op2 plus) (var hundred)
- (reset (app2 (op2 plus) (var ten) (abort (var one))))
-
+ ; (+ 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 1 >>= fun i ->
- unit (10+i)) >>= fun j ->
- unit (100+j)));;
- - : int = 101
+ reset (
+ abort 11 >>= fun i ->
+ unit (100+i)
+ ) >>= fun j ->
+ unit (1000+j)));;
+ - : int = 1011
Example 3:
app2 (op2 plus) (var thousand)
(reset (app2 (op2 plus) (var hundred)
- (shift (\k. ((op2 plus) (var ten) (var one))))))
+ (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)
+ 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)))))))
-
+ (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 u >>= fun x -> unit (100 :: x)
) in let w = v >>= fun x -> unit (1000 :: x)
- in run0 w)
+ 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:
app2 (op2 plus) (var thousand)
(reset (app2 (op2 plus) (var hundred)
- (shift (\k. ((op2 plus) (var ten) (app (var k) (var one)))))))
+ (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]
- 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)
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))
+ (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
- (* not sure if this example can be typed as-is in OCaml. We may need a sum-type *)
+<!--
+# 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:
; (+ 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))))))
-
+ (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)
+ - : int = 121
<!--