X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=cps_and_continuation_operators.mdwn;h=b1f6c69d7fef98fa4a064ab9984e175c06b568f6;hp=7b302c677d2361abb6366d7fdccb80c1fb81eb07;hb=edeaf26c809f2c20651d00b9edd54e42e5989e7a;hpb=7c8c0a52fdd3692f77be54fdafa19b34e47c0d60 diff --git a/cps_and_continuation_operators.mdwn b/cps_and_continuation_operators.mdwn index 7b302c67..b1f6c69d 100644 --- a/cps_and_continuation_operators.mdwn +++ b/cps_and_continuation_operators.mdwn @@ -173,15 +173,15 @@ So too will examples. We'll give some examples, and show you how to try them out let callcc body = fun outk -> body (fun v localk -> outk v) outk - + 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 @@ -268,11 +268,13 @@ That won't work because `k 1` doesn't have type `int`, but we're trying to add i 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 )) -If we figure this out later (or anyone else does), we'll come back and report. + @@ -308,7 +310,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) - + (reset (let ([x 1]) (+ 10 (shift k x)))) @@ -349,13 +351,13 @@ 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 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 @@ -401,40 +403,41 @@ Here are some more examples of using delimited control operators. We present eac 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: @@ -442,29 +445,31 @@ 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: @@ -472,37 +477,56 @@ To demonstrate the different adding order between Examples 4 and 5, we use `::` 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 *) + 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