X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=cps_and_continuation_operators.mdwn;h=314fb4341e6142aa1d7c2914d827f7a383e6112c;hp=5aa56f60d9c6979f643741e810064be2f1fa7bbf;hb=6f77f31cdd1687494ce1f52277e5486ff4293540;hpb=d969671e87949a2b71ff37ff28ab269bc0172a1b

diff --git a/cps_and_continuation_operators.mdwn b/cps_and_continuation_operators.mdwn
index 5aa56f60..314fb434 100644
--- a/cps_and_continuation_operators.mdwn
+++ b/cps_and_continuation_operators.mdwn
@@ -397,154 +397,160 @@ Examples of shift/reset/abort
 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)))) );;