Composable continuations are a means of inverting control by reification of continuation segments. This sounds like a horrible mouthful of jargon to express a disgustingly complex concept, but it's actually not. This is why.
We shall begin by introducing two new special forms, reset and shift.[1] (reset expression) sets up a special continuation, or mark on the stack, and evaluates expression. This means simply that, as expression is evaluated, there is some information during its evaluation which we can refer back to later. Shift, in fact, refers back to this information. (shift variable expression) jumps back to where that mark was, i.e. where you used reset, and saves the portion of the program between that and where you called shift; it reifies that segment of the program, known as a `composable continuation', into a composable procedure, binds variable to that procedure, and evaluates expression.
`Composable' means that the procedure will return, and so it can be composed with other procedures. There are other names for `composable continuations' as well, such as `delimited continuations' and `partial continuations,' but we shall consistently use the term `composable' here. This property of composability differs from the `escape procedures' that call-with-current-continuation constructs. While an escape procedure does not return -- rather, it has the effect of returning control to another point in the program --, a composable continuation procedure does.
Calling a composable continuation procedure has the effect of returning control to the point where shift was called. However, when control subsequently returns to where the thunk passed to reset was called, instead of returning then to where reset was called, it rather returns to where the composable continuation procedure was called!
Another way to explain it is by code transformation:[2]
(reset (...A... (shift V E) ...B...)) ; --> (let ((V (lambda (x) (...A... x ...B...)))) E) (reset E) ; --> E
A string of examples may help to elucidate. In the first place, (reset expression) with no shift has the same effect as evaluating expression, ignoring tail recursion.
(+ 1 (reset (+ 2 3))) ;Value: 6 (cons 1 (reset (cons 2 '()))) ;Value: (1 2)
Let us add a shift, then, to the example. If we do not call the composable continuation procedure created by shift, then shift has the effect of discarding everything between it and the dynamically enclosing reset.
(+ 1 (reset (+ 2 (shift k ;; Ignore K. 3)))) ;Value: 4 (cons 1 (reset (cons 2 (shift k ;; Ignore K. (cons 3 '()))))) ;Value: (1 3)
Question: What if the application of k is within the (reset ... shift) portion of the code?
Now let us use the composable continuation. It has the effect of (lambda (x) (+ 2 x)) or (lambda (x) (cons 2 x)); we can see this by creating a procedure of one argument whose body mirrors that of the expression we passed to reset, but with the value of the argument, x, substituted for the call to shift. This is what is meant by `inverting control': a portion of a program's evaluation becomes reified into a function.
(+ 1 (reset (+ 2 (shift k (+ 3 (k 4)))))) ; --> (+ 1 (let ((k (lambda (x) (+ 2 x)))) (+ 3 (k 4)))) ; --> (+ 1 (+ 3 (+ 2 4))) ;Value: 10 (cons 1 (reset (cons 2 (shift k (cons 3 (k (cons 4 '()))))))) ; --> (cons 1 (let ((k (lambda (x) (cons 2 x)))) (cons 3 (k (cons 4 '()))))) ; --> (cons 1 (cons 3 (cons 2 (cons 4 '())))) ;Value: (1 3 2 4)
We can, in fact, call composable continuation procedures multiple times; they are simply functions that run through portions of a program, and we can run through those portions more than once.
(+ 1 (reset (+ 2 (shift k (+ 3 (k 5) (k 1)))))) ; --> (+ 1 (let ((k (lambda (x) (+ 2 x)))) (+ 3 (k 5) (k 1)))) ; --> (+ 1 (+ 3 (+ 2 5) (+ 2 1))) ;Value: 14 (cons 1 (reset (cons 2 (shift k (cons 3 (k (k (cons 4 '())))))))) ; --> (cons 1 (let ((k (lambda (x) (cons 2 x)))) (cons 3 (k (k (cons 4 '())))))) ; --> (cons 1 (cons 3 (cons 2 (cons 2 (cons 4 '()))))) ;Value: (1 3 2 2 4)
These examples probably seem contrived and not very useful. Indeed, they are contrived, but their purpose was to elucidate the explanation of shift and reset by way of simplicity. We could have manually performed the code transformation, but the great power of shift and reset lies in the fact that they do not require global code transformation. We can use shift and reset to cross boundaries of abstractions in order to invert dynamic control of program sections over which we have no lexical control; that is, we can use this to turn dynamic program segments into functions without knowing anything about many parts of the programs.
Let us take a more sophisticated example now. Suppose we have a procedure like for-each, and we want to create a procedure that accepts a collection, of the sort accepted by for-each or any procedure like it, and returns a lazy stream of the collection's elements. We can accomplish this using call-with-current-continuation thrice and set! as well. Those weak of stomach or heart should avert their eyes from this Scheme procedure.
(define (for-each->stream-maker for-each)
(stream-lambda (collection)
(call-with-current-continuation
(lambda (return-cdr)
(for-each
(lambda (element)
(call-with-current-continuation
(lambda (return-to-for-each)
(return-cdr
(stream-cons element
(call-with-current-continuation
(lambda (return-next-cdr)
(set! return-cdr return-next-cdr)
(return-to-for-each))))))))
collection)
(return-cdr stream-null)))))
Clearly, this is clumsy. While there is a very nice slope of indentation as one follows code down into the depths of nesting, that is about the only notion of elegance that could possibly come to one's mind when considering this code. However, this pattern is actually very similar to what shift and reset abstract.
Return-cdr represents the continuation of the expression evaluated in a reset; as we go through the collection, it is set to return-next-cdr to return to successive cdrs of the output stream. Like shift, as we enter the point we want to save the program fragment to, we reify a continuation -- return-to-for-each -- and then abort out to the next reset point, i.e. return-cdr. When we want to use the program fragment, as if invoking a composable continuation, we reify the continuation -- which is that of the stream's next cdr -- into return-next-cdr, set return-cdr to that so that the program fragment can find where to return next, and then call return-to-for-each to re-enter the program fragment.
This can all be expressed much more easily using shift and reset:
(define (for-each->stream-maker for-each)
(stream-lambda (collection)
(reset (begin
(for-each (lambda (element)
(shift k
(stream-cons element (k 'ignored))))
collection)
stream-null))))
[1] We could have used procedures (reset thunk) and (shift receiver) instead of special forms, but we chose not to for the sake of simplicity and columns, and to keep in-line with the common use of these constructs. Note also that there are control and prompt -- two other known control operators that will produce the same results with most of the examples on this 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
(The reset inside the lambda expression is the only difference between this and the control/prompt operators.)
There is Riastradh's implementation of shift and reset in terms of call-with-current-continuation, which is very heavy-weight and slow for the purpose, but which is portable.
Oleg's version uses a trampoline to capture only the part of the continuation needed. This has the advantage of not leaking memory, but the trampoline should be placed in an 'empty' continuation and call/cc needs to be changed to work as expected.
PLT Scheme has shift/reset and numerous others in its scheme/control library, with links to the corresponding papers.
Gasbichler and Sperber's paper "Final Shift for Call/cc: Direct Implementation of Shift and Reset" goes into detail on the various implementation techniques. (Sperber's papers online)