What exactly is a “continuation prompt?”

Question

I'm trying to decipher the documentation

call-with-continuation-prompt

Applies proc to the given args with the current continuation extended by a prompt. The prompt is tagged by prompt-tag, which must be a result from either default-continuation-prompt-tag (the default) or make-continuation-prompt-tag. The result of proc is the result of the call-with-continuation-prompt call.

I understand the part where it says "Applies proc to the given args with the current continuation" and then it's just gibberish from there.

What does it even mean for a continuation to be "extended," and how does a "prompt" do this "extending?"

Answer 1

What is a prompt, conceptually?

Scheme in general has the idea of continuations, but Racket extends this with the idea of delimited continuations. The idea of a continuation is that it captures the remaining computation left to be evaluated. I will not attempt to explain continuations in general, since that is outside the scope of this question.

However, I will explain what makes delimited continuations special. Usually, capturing a continuation captures the entire computation, all the way up to the top level. This makes their usages relatively limited for implementing complicated control structures because applying a continuation will completely release control of program execution.

With delimited continuations, you can capture only a certain portion of the continuation. The parts of the evaluation that are actually captured are delimited by prompts, which act like markers along the current continuation that specify how much of the continuation to capture.

Okay, but what does any of that mean?

The concept of delimited continuations is not really clear without actually seeing it in action compared with undelimited continuations.

Standard (non-delimited) continuations

Consider the following example code.

(define *k* #f)

(sqrt
 (+ 1 2 3
    (call/cc
     (λ (k)
       (set! *k* k)
       0))))

This code is very straightforward—it captures a continuation and stores in to the global binding *k*. The continuation itself looks like this:

(sqrt (+ 1 2 3 _))

(Where the _ represents the "hole" to be filled in when calling the continuation.)

Applying this continuation would work precisely as one would expect.

> (*k* 3) ; evaluates (sqrt (+ 1 2 3 3))
3

This is all very ordinary. So what's the difference introduced by delimited continuations?

Delimited continuations

What if we only wanted to capture part of the continuation in *k*. For example, what if we only wanted to capture this continuation?

(+ 1 2 3 _) ; the inner portion of the last continuation

We can do this by establishing a continuation prompt, which will adjust how much of the continuation is actually captured.

(sqrt
 (call-with-continuation-prompt
  (λ ()
    (+ 1 2 3
       (call/cc
        (λ (k)
          (set! *k* k)
          0))))))

Now, applying *k* gives the inner result:

> (*k* 3)
9

An analogy for delimited continuations

Continuations can be a somewhat abstract concept, so if the above code sample isn't perfectly clear, consider this analogy.

The evaluation model is a stack—every function call pushes a new frame onto the stack, and returning from a function pops that frame off the stack. We can visualize the call stack as a stack of cards.

Normally, when a continuation is captured, it captures the current frame and all the frames below it, as visualized below.

The top level, represented in blue, is not captured. It is effectively the default prompt in a delimited system.

However, installing a new prompt creates a sort of transparent divider between the frames, which affects which frames are captured as part of the continuation.

This divider delimits the extent of the continuation.

Appendix: Prompt tags and continuation barriers

This is the basics of delimited continuations, but there are other ways to control continuations that give even more power to the continuation system (as well as protecting it from malicious code), and these are prompt tags and continuation barriers.

The idea of a prompt tag is essentially a "label" that tags a given prompt. Using the card analogy above, each transparent divider can be given a label. Then, when you capture a continuation, you can specify to capture all the way back to that specific label, even if there are other prompts with other labels in between.

Continuation barriers, on the other hand, are a security measure. Just like prompts, they can be visualized as "dividers" sitting between elements of the call stack, but rather than being used as marks to control how much of the stack is captured, they serve as guards to prevent continuations from jumping "through" the barrier.

For more details on this, consider reading the section in the Racket reference on continuation barriers. Here's an excerpt:

Specifically, a continuation can be replaced by another only when the replacement does not introduce any continuation barriers. It may remove continuation barriers only through jumps to continuations that are a tail of the current continuation. A continuation barrier thus prevents “downward jumps” into a continuation that is protected by a barrier.