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)))) );;
+ ; (+ 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))))))
+
+
+More:
+
+ (* (+ 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)
+
+More:
+
+ 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)
+
+ ;;
+
+More:
+
+ 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)))) );;