Continuations in Racket
In Scheme, Continuations are procedure-like values used for advanced flow control. They are created using the built-in
Consider the top-level expression
(+ 1 (+ 2 (+ 3 4))).
+ has the reduction
(+ ?1 ?2) => ?3, where
?2 are integer literals, and
?3 is an integer literal equal to their sum.
Our expression has the form
(+ 1 ?), but
? = (+ 2 (+ 3 4)) is not syntactically an integer. In order to evaluate it, we must first reduce
? to an integer. There is only one possible sequence of reductions:
(+ 1 ?) is awaiting reduction of
9. After, the continuation is resumed by substituting
In principle, we could consider an alternate version of the program where
? reduced to
3 instead. Then, the top-level expression would evaluate to
Scheme makes this concept a first-class language feature with Continuations. They are created using
call/cc). Continuations can be resumed multiple times: Each time
? is replaced with a possibly-different value.
k is the expression
(+ 1 ?) above. The
? takes the place of the entire
0, but also remembers the continuation so that we can use a different return value later.
(*c* (+ 2 (+ 3 4))) evaluates the smaller
(+ 2 (+ 3 4)) and then resumes the
(+ 1 ?) computation with its result.
Here is a more advanced example. Think about how it is evaluated, or click the spoiler:
Continuations can be used to implement C-style
return; exceptions; coroutines; and more.
(return ?) within the body causes the entire
call/cc to be immediately replaced with
Old Scheme interpreters ran each top-level expression one-by-one as in a REPL, so a continuation that reaches the top-level does not automatically go to the next expression. This is surprising because it seems to violate the β-reduction rule:
Evaluation steps such as procedure applications create new Continuation Frames, with the top-level being a Prompt. Continuations created within a prompt are completed when they reach the prompt, and do not proceed to the next expression. Racket’s default behavior with non-void top-level expressions is to print them.
Because prompts cause a computation to complete, a prompt-level
call/cc generates a continuation
? that is equivalent to the identity function.
begin does not create a new continuation frame, so its expressions are in the top-level prompt.
*c* is a prompt-level continuation, so it is equivalent to the identity function:
(*c* 0) reduces to
(*c* 0) prints
0 because it evaluates to
0 and then the top-level handler prints it. Neither the continuation nor the prompt handle the print behavior:
This prints only a single
0 because the continuation only evaluates to 0, and does not print the value. Here is how that last expression is evaluated:
Because the final value is
0, the top-level expression handler then prints it.
However, in the second block of the Noted Example, the extra
λ does create a new continuation frame. Since it’s no longer a prompt-level expression, the continuation
*c* captures the next one too:
The β-reduction violation happens because the top-level prompt truncates continuations. This is a pretty strange concept for just the top-level to have, isn’t it?
Standard Scheme only has the one top-level prompt, but Racket supports Delimited Continuations:
(call-with-continuation-prompt) adds a prompt to the stack of continuation frames.
Here is the Noted Example using an explicit continuation prompt:
Continuations saved under such a prompt don’t need to store the stack past the prompt, and have a smaller scope that is easier for the optimizer to understand.
There is one last subtlety:
This program outputs nothing.
call/cc first rolls back continuation frames until it reaches a prompt with the same tag as the continuation, then it applies the frames stored in the continuation.
(*c* 0) is rolled back to the empty continuation, and then an identity continuation is applied. The result is
void, and so nothing is printed.
This can be corrected by either using a different prompt tag or by using
call-with-composable-continuation, which applies the continuation without rolling back any frames.
(+ 1 (+ 2 (+ 3 4))) have nested continuations
(+ 1 ?) and
(+ 1 (+ 2 ?)). So
call-with-composable-continuation is “composable” because it can be used in expressions easily, since it nests continuations just like ordinary expressions.