From 172783a2998a2d2d6a0e1cbda2e4f68710099fe3 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Sun, 12 Dec 2010 14:18:26 -0500 Subject: [PATCH] tweak new_stuff, post raw cps file Signed-off-by: Jim Pryor --- cps.mdwn | 61 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ new_stuff.mdwn | 2 -- 2 files changed, 61 insertions(+), 2 deletions(-) create mode 100644 cps.mdwn diff --git a/cps.mdwn b/cps.mdwn new file mode 100644 index 00000000..605e86a5 --- /dev/null +++ b/cps.mdwn @@ -0,0 +1,61 @@ +;; call-by-value CPS +; see Dancy and Filinski, "Representing control: a study of the CPS transformation" (1992) +; and Sabry, "Note on axiomatizing the semantics of control operators" (1996) + +; [x] = var x +let var = \x (\k. k x) in +; [\x. body] = lam (\x. [body]) +let lam = \x_body (\k. k (\x. x_body x)) in +; [M N] = app [M] [N] +let app = \m n. (\k. m (\m. n (\n. m n k))) in + +; helpers +let app3 = \a b c. app (app a b) c in +let app4 = \a b c d. app (app (app a b) c) d in +; [succ] = op1 succ +let op1 = \op. \u. u (\a k. k (op a)) in +; [plus] = op2 plus +let op2 = \op. \u. u (\a v. v (\b k. k (op a b))) in +let op3 = \op. \u. u (\a v. v (\b w. w (\c k. k (op a b c)))) in + +;; continuation operators +; [let/cc k M] = letcc (\k. [M]) +let callcc = \k. k (\f u. (\j. f j u) (\y w. u y)) in +let letcc = \x_body. app callcc (lam x_body) in +let letcc = \k_body. \k. (\j. (k_body j) k) (\y w. k y) in + +; [abort M] = abort [M] +let abort = \body. \k. body (\m m) in +; [prompt M] = prompt [M] +let prompt = \body. \k. k (body (\m m)) in +; [shift k M] = shift (\k. [M]) +let shift = \k_body. \k. (\j. (k_body j) (\m m)) (\y w. w (k y)) in + +;; examples +; (+ 100 (let/cc k (+ 10 1))) ~~> 111 +; app3 (op2 plus) (var hundred) (letcc (\k. app3 (op2 plus) (var ten) (var one))) + +; (+ 100 (let/cc k (+ 10 (k 1)))) ~~> 101 +; app3 (op2 plus) (var hundred) (letcc (\k. app3 (op2 plus) (var ten) (app (var k) (var one)))) + +; (+ 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)))))) + diff --git a/new_stuff.mdwn b/new_stuff.mdwn index d153848e..ba7e51a1 100644 --- a/new_stuff.mdwn +++ b/new_stuff.mdwn @@ -24,8 +24,6 @@ New stuff, fairly stable: In progress: * [[Curry-Howard]] -* [[Curry-Howard-note]] is this current? -* [[Using Continuations to Solve Same Fringe]] * [[Monad Transformers]] * [[Assignment10]] * [[CPS]] -- 2.11.0