Search code examples
schemeracketcontinuationsdelimited-continuations

Nested delimited continuations transformations

I'm trying to understand delimited continuations, and I was reading this article:

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

And I found this reset/shift transformation

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

For example, I tried the transformation on this expression (I think append-map is from Racket)

(reset (list (
(lambda (x) (* x x)) (shift k (append-map k '(1 2))) )))

and got this

(append-map 
(lambda (y) (list ((lambda (x) (* x x)) y))) '(1 2))

with the same result '(1 4)

I was wondering if the same kind of transformation (that will eliminate the reset/shift), could be applied to an expression like this:

(reset (list (+ 
(shift k (append-map k '(1 2))) 
(shift k (append-map k '(3 4))) )))

and how would the result look like (it evaluates to '(4 5 5 6)).

Solution

  • Take a look at the footnote on that page:

    [2] This transformation is not strictly correct. In actuality, there are a few more resets placed throughout the output. The details of this fall outside the scope of this introductory text, however, and it is relevant only if we were to use nested shift and reset.

    For the sake of completeness, though, here is the correct transformation, if you want it:

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

 (reset E) 
 ; --> 
 E

    So:

    (reset (list (+ (shift k (append-map k '(1 2))) (shift k (append-map k '(3 4))))))

    is transformed to:

    (let ((k (lambda (x) (reset (list (+ x (shift k (append-map k '(3 4))))))))) 
  (reset (append-map k '(1 2))))

    And 

    (reset (list (+ x (shift k (append-map k '(3 4))))))

    is in turn transformed to:

    (let ((c (lambda (y) (reset (list (+ x y)))))) 
  (reset (append-map c '(3 4))))

    By using the second rule to remove reset, we have:

    (let ((k (lambda (x) (let ((c (lambda (y) (list (+ x y))))) 
                       (append-map c '(3 4))) ))) 
  (append-map k '(1 2)))

    as the final result.