3
$\begingroup$

Apologies in advance for the length of this question, but this is as short as I have been able to make it.

The Prescription

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 rules"

;; RULE 1 ;;
 (reset (...A... (shift K E) ...B...))
 ; -->
 (let ((K (lambda (x) (reset (...A... x ...B...)))))
   (reset E)) ;; You may call K in here!

;; RULE 2 ;;
 (reset E)
 ; -->
 E

This is somewhat backed up by equations 2 and 3 on page 100 of Shan's paper, http://tinyurl.com/q7ebt4a. Qualifications of "somewhat" make up the center of my question below, after some more motivation and examples.

Motivating Examples

I can rephrase the above in a pair of slogans:

  1. The argument of a delimited continuation K replaces the shift in a fresh copy of the original reset
  2. The body E of the shift, in a fresh reset, replaces the original reset.

The rules above can be directly written and played with in Mathematica, and that would be grand. Here is a first attempt:

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

Here are a few examples pulled from papers:

reset[1 + shift[k, k[42]]]
reset[1 + shift[k, k[k[42]]]]
{a, reset[{b, shift[k, k[k[{1, {c}}}]]}]}
ClearAll[$g$];
reset[1 + shift[k, Function[$g$ = k]]][];
$g$[42]
reset[1 + shift[k, "zork"]]
reset[{1, shift[k, k[20]], shift[k, k[30]]}]

 > 43
 > 44
 > {a, {b, {b, {1, {c}}}}}
 > 43
 > "zork"
 > {1, 20, 30}

This would be really cool for concurrent state machines or lazy streams or reactive patterns and more.

It May Not Be Right

The problem is that I don't think it's right because it doesn't look any deeper than first level. Ironically, every example I have seen in the literature only has shifts at level 1 of the expression inside the reset, BUT

If I fire up Racket (a modernized Scheme), 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 intuitively 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.

Of course, my Mathematica version matches the prescription:

reset[1 + 2 * shift[k, k[42]]]

 > 1 + 2 shift[k, k[42]]

Is an Easy Solution Possible?

I now think that Shan's paper above is being too glib, with an imaginary context operator that lets shift refer to a reset at higher levels.

Everything else I've been able to find on implementing delimited continuations is vastly larger and would be a lot of very sideways work (http://tinyurl.com/oec83ky, http://lambda-the-ultimate.org/node/4313), requiring one ore more of the following:

  1. Haskell's monad library
  2. Scheme's call/cc or idiosyncratic macro system
  3. Building your own VM for stack-hacking and caching (http://tinyurl.com/n9kz5fb)
  4. Rewriting your whole program into CPS (continuation-passing style), either manually or by writing a metacircular translator, e.g., http://tinyurl.com/bo8zl9c)
  5. Building your language up from a tiny lambda calculus in CPS (fig. 1, p. 101 in http://tinyurl.com/q7ebt4a)
  6. Throw and Catch, considered desirable to avoid

I have spent a lot of time trying to get the above working with recursive equations (see junk code below), but I am now despairing that it's not easy. A shift at a lower level might refer to a matching reset at a higher level, which must be threaded around the equations in one way or another.

Now, finally to the actual question of this post:

Am I blindly missing an easy way in Mathematica?

I would like to avoid Throw and Catch in favor of a functional solution, because I have been led to believe that delimited continuations are actual, ordinary functions, unlike continuations, which are jumps that (confusingly) look like functions, and because Throw and Catch are too close to Scheme's call/cc, which I definitely want to avoid (if I don't avoid it, I might as well use Scheme and not Mathematica, after all).

Broken Junk Code

May have some useful ideas, however.

ClearAll[u, v, r, q, s];
v[cc_, cc_[E_]] := E;
u[cc_, cc_[E_]] := E;
u[cc_, h_[As___]] :=
  With[{xs = Select[{As}, Head[#] === cc &]},
   If[{} =!= xs,
    v[cc, First[xs]],
    xs]];
u[cc_, E_] := E;

r[E_] := Module[{cc = Unique["cc"]},
   u[cc, q[cc, E]]];

q[cc_, h_[As___, s[k_, E_], Bs___]] :=
  Module[{K = x \[Function] r[h[As, x, Bs]]},
   r[cc[E /. {k -> K}]]];

q[cc_, h_[As___]] :=
  With[{qs = q[cc, #] & /@ {As}},
   h[Sequence @@ qs]];

q[cc_, Function[E_]] := Function[E]

q[cc_, E_] := cc[E]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.