<p>I think you might be misreading those rewrite rules.</p>

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

<p>The <a href="http://docs.racket-lang.org/reference/cont.html?q=shift&amp;=&amp;=#%28form._%28%28lib._racket%2Fcontrol..rkt%29._reset%29%29" rel="nofollow">Racket Reference</a> has a slightly different set of rewrite rules for reset/shift, that might make things a little clearer.</p>

<pre><code>(reset val) =&gt; val

(reset E[(shift k expr)]) =&gt;
  (reset ((lambda (k) expr)
          (lambda (v) (reset E[v]))))
</code></pre>

<p>Using your example:</p>

<pre><code>(reset (+ 1 (* 2 (shift k (k 42)))))
=&gt;
(reset ((lambda (k) (k 42))
          (lambda (v) (reset (+ 1 (* 2 v))))))
=&gt;
(reset (reset (+ 1 (* 2 42))))
=&gt; 85
</code></pre>

<p>I don't speak Mathematica, but it might be possible to transcribe the rewrite rules from the Racket Reference to get what you want.</p>

CC BY-SA 3.0
2016-01-01T20:05:01.263Z
2016-01-01T20:05:01.263Z
Richard Kallos
<p>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 <a href="https://github.com/lihaoyi/macropy" rel="nofollow">macropy</a>.  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 <code>call/cc</code>, which I can't translate into other languages [without a lot of compiler hacking or similar trouble]).</p>

<p>Here: <a href="http://tinyurl.com/nj23hzj" rel="nofollow">http://tinyurl.com/nj23hzj</a></p>

CC BY-SA 3.0
2015-12-25T21:21:31.913Z
2015-12-25T21:21:31.913Z
Reb.Cabin
<p>I'm looking at the following tutorial on delimited (or composable) continuations: </p>

<p><a href="http://community.schemewiki.org/?composable-continuations-tutorial" rel="nofollow">http://community.schemewiki.org/?composable-continuations-tutorial</a></p>

<p>The author(s) propose the following "rewrite rule"</p>

<pre><code> (reset (...A... (shift K E) ...B...)) 
 ; --&gt; 
 (let ((K (lambda (x) (reset (...A... x ...B...))))) 
   (reset E)) 

 (reset E) 
 ; --&gt; 
 E 
</code></pre>

<p>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.</p>

<p>If I fire up Racket, do <code>(require racket/control)</code> and then</p>

<pre><code>(reset (+ 1 (shift k (k 42)))  ~~&gt;  43
</code></pre>

<p>as expected and as consistent with the above.  If I do </p>

<pre><code>(reset (+ 1 (* 2 (shift k (k 42)))))  ~~&gt;  85
</code></pre>

<p>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 <code>(+ 1 (* 2 (shift k (k 42))))</code> because it can't "see" the <code>shift</code> at the second level, "inside" the <code>(* 2 (shift ...))</code> subexpression. </p>

<p>My straight transcription into Mathematica confirms this behavior,</p>

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

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

<pre><code>reset[1 + shift[k, k[42]]] ~~&gt;  
reset[Plus[1, shift[k, k[42]]]] ~~&gt;
(* h -&gt; Plus, As -&gt; {1}, E -&gt; k[42], Bs -&gt; {} *)
reset[Plus[1, 42]] ~~&gt;
43
</code></pre>

<p>But then I try this:</p>

<pre><code>reset[1 + (2 * shift[k, k[42]])] ~~&gt;
reset[Plus[1, Times[2, shift[k, k[42]]]]] ~~&gt;
1 + (2 * shift[k, k[42]])
</code></pre>

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

<p>So the final question is:</p>

<p>Can I just patch the rewrite rule above, perhaps like this:</p>

<pre><code> (reset (...A... (shift K E) ...B...)) 
 ; --&gt; 
 (let ((K (lambda (x) (reset ( (reset ...A...) x (reset ...B...)))))) 
   (reset E)) 

 (reset E) 
 ; --&gt; 
 E 
</code></pre>

<p>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?  </p>

<continuations><scheme>
reset and shift only one level deep (delimited continuations)?
Reb.Cabin
# reset and shift only one level deep (delimited continuations)?

(Asked by: username_0 on 2015-12-24)

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?

**Tags:** continuations, scheme


---

## 2 answers

### Answer by username_1 on 2016-01-01. Score: 1

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]))))

Using your example:
(reset (+ 1 (* 2 (shift k (k 42)))))
=>
(reset ((lambda (k) (k 42))
          (lambda (v) (reset (+ 1 (* 2 v))))))
=>
(reset (reset (+ 1 (* 2 42))))
=> 85

I don't speak Mathematica, but it might be possible to transcribe the rewrite rules from the Racket Reference to get what you want.


---

### Answer by username_0 on 2015-12-25. Score: 0

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](https://github.com/lihaoyi/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]).

Here: <http://tinyurl.com/nj23hzj>


---

