# reset and shift only one level deep (delimited continuations)? [closed]

I'm looking at the following tutorial on delimited (or composable) continuations:

http://community.schemewiki.org/?composable-continuations-tutorial

The author(s) propose the following "rewrite rule"

 (reset (...A... (shift K E) ...B...))
; -->
(let ((K (lambda (x) (reset (...A... x ...B...)))))
(reset E))

(reset E)
; -->
E


This is vastly smaller than anything else I've been able to find on delimited continuations, and doesn't rely on Haskell's Cont monad or on Scheme's call/cc and unique macro system. Therefore, it looks like I can implement this myself to play with outside of Haskell or Scheme / Racket, and that would be grand (see my Mathematica version below). Problem is that I don't think it's right.

If I fire up Racket, do (require racket/control) and then

(reset (+ 1 (shift k (k 42)))  ~~>  43


as expected and as consistent with the above. If I do

(reset (+ 1 (* 2 (shift k (k 42)))))  ~~>  85


this looks right, but doesn't match the prescription above. That prescription, if I read it correctly, should lead to the second rewrite rule and just produce (+ 1 (* 2 (shift k (k 42)))) because it can't "see" the shift at the second level, "inside" the (* 2 (shift ...)) subexpression.

My straight transcription into Mathematica confirms this behavior,

reset[h_[As___, shift[k_, E_], Bs___]] :=
Block[{K = Function[x, reset[h[As, x, Bs]]]},
reset[E /. {k -> K}]]
reset[E_] := E


One level deep (like almost all the concrete examples I've found in papers! so the wiki authors are exonerated), and everything is fine:

reset[1 + shift[k, k[42]]] ~~>
reset[Plus[1, shift[k, k[42]]]] ~~>
(* h -> Plus, As -> {1}, E -> k[42], Bs -> {} *)
reset[Plus[1, 42]] ~~>
43


But then I try this:

reset[1 + (2 * shift[k, k[42]])] ~~>
reset[Plus[1, Times[2, shift[k, k[42]]]]] ~~>
1 + (2 * shift[k, k[42]])


This fires the second, transparent rewrite rule because shift is too far down; the first pattern h[As___, shift[k_, E_], Bs___] can't see it -- it's inside Bs, which matches the second-level AST Times[2, shift[...]].

So the final question is:

Can I just patch the rewrite rule above, perhaps like this:

 (reset (...A... (shift K E) ...B...))
; -->
(let ((K (lambda (x) (reset ( (reset ...A...) x (reset ...B...))))))
(reset E))

(reset E)
; -->
E


or am I doomed to take the long, scenic tour through vast landscapes of Haskell and OchaCaml and call/cc and denotational semantics just so I can create a small, but correct, toy implementation?

I think you might be misreading those rewrite rules.

A call to shift will find to the nearest enclosing call to reset, regardless of how deeply nested it is. Other examples in the tutorial you linked to should confirm that.

The Racket Reference has a slightly different set of rewrite rules for reset/shift, that might make things a little clearer.

(reset val) => val

(reset E[(shift k expr)]) =>
(reset ((lambda (k) expr)
(lambda (v) (reset E[v]))))


(reset (+ 1 (* 2 (shift k (k 42)))))

I found an implementation in Clojure that's in terms of fairly elementary functions and macros (rewriters) that I can translate into other languages like Mathematica or C++ or even python with macropy. I think this will be easier for me to deal with than the implementations in Haskell (with its deep monad libraries, which I don't want to translate into other languages [too much work]) or Scheme (with its built-in call/cc, which I can't translate into other languages [without a lot of compiler hacking or similar trouble]).