what determines the outer boundary of a Scheme continuation?

Question

It’s common for explanations of continuations to say that a continuation represents the “rest of the program” (or similar phrasing). But there’s plainly a boundary at which the continuation stops collecting these remaining computation steps. What is that boundary? The top level of the program? Or something else?

These explanations tend to start with a toy example like this.

(+ 1 (call/cc
      (lambda (cc)
        (cc 2))))

This evaluates to 3 because (cc 2) means “put 2 in the hole in the expression carved out by the call/cc form.” The expression becomes (+ 1 2), aka 3.

Now consider this example:

(define lc #f)
(+ 1 (call/cc
      (lambda (cc)
        (set! lc cc)
        (cc 2))))
(displayln "done")
(lc 42)

Here, we stash the continuation cc in the variable lc. After the expression is evaluated, we display done and use the continuation again as (lc 42). What do we get?

3
done
43

But … why? If a continuation is the “rest of the program”, why doesn’t the continuation capture everything that happens after call/cc, which includes the subsequent calls to displayln and lc? Under this interpretation, the continuation would create an infinite loop.

Plainly, that’s not what happens. Rather, it appears that the continuation is capturing the rest of the program until it reaches a subsequent expression, which it ignores (along with any others).

But now consider this example:

(define lc #f)
(define (f)
  (displayln (+ 1 (call/cc
                   (lambda (cc)
                     (set! lc cc)
                     (cc 2)))))
  (displayln "done"))
(f)
(displayln "outer")
(lc 42)

The result in this case is:

3
done
outer
43
done

Meaning, the continuation does capture the (displayln "done") in f, though it still does not capture the (displayln "outer") and (lc 42) following the invocation of f.

One final example — we move everything into a new function g:

(define lc #f)
(define (g)
  (define (f)
    (displayln (+ 1 (call/cc
                     (lambda (cc)
                       (set! lc cc)
                       (cc 2)))))
    (displayln "done"))
  (f)
  (displayln "outer")
  (lc 42))
(g)

This time, we get the infinite loop predicted in the earlier example:

3
done
outer
43
done
outer
43
···

So the original intuition was not completely off-base. Is this just another instance of the top level being hopeless? Or is there a more succinct explanation of how far a continuation reaches?

Answer 1

As far as I know, this is intentional in Racket. The doc of module states:

Each evaluation of an expression or definition is wrapped with a continuation prompt (see call-with-continuation-prompt) for the default prompt tag and using a prompt handler that re-aborts and propagates its argument to the next enclosing prompt.

My guess (which could be totally wrong) is that this is done to mimic the behavior in the REPL.

#lang racket
1
2

prints 1 and 2, just like:

> 1
1
> 2
2

And since we have this, installing the prompt for each expression seems like a logical next step to do.

Other implementations that don't have the module system seem to have the behavior that you expect. For example, in Guile, if you run the above program (changing displayln to display and call/cc to call-with-current-continuation, since Guile doesn't have those functions), you get the the infinite loop of 3doneouter43doneouter43doneouter....

By the way: as I understand, "toplevel being hopeless" doesn't refer to toplevel inside a module. It refers to those outside a module. E.g., when you use the REPL, or when you use implementations that don't have the module system.

Answer 2

I'm guessing that you're typing this into a file and then loading it into a Scheme interpreter. The Scheme interpreter doesn't see that as a program, it sees it at a series of mostly independent expressions that it evaluates one after another.

In your first example, when the interpreter gets to the expression:

(+ 1 (call/cc
      (lambda (cc)
        (set! lc cc)
        (cc 2))))

it has no idea that (displayln "done") is coming next. So when it creates the continuation in there, the continuation for the entire expression is simply a return to the interpreter. When the last expression (lc 42) invokes the continuation again, the "rest of the program" at the time that continuation was created was simply doing the +1 and then returning to the Scheme interpreter. At that point the interpreter has read all of the input stream and there's no more to read so there's no infinite loop.

So basically it comes down to the fact that the I/O system has internal state that's not captured by the continuation. It has already read to the end of the input and the continuation does not rewind that bit of state.

Answer 3

The phrase "the top level is hopeless" usually refers to problems arising from the combination of (1) a single top-level environment that allows mutual recursion and (2) expansion and evaluation of each top-level form (eg, REPL interaction) in order. In contrast, in a module, the entire module body is partially expanded to uncover definitions first, then that whole environment is used to expand all of the expressions. The difference in expansion order means that the expander is more likely to already know about a binding when it encounters a forward reference to it.

---

Your observation about "the rest of the program" is one of the reasons for the invention of prompts, which delimit continuations. See for example the discussion about an "interactive interpreter" in Section 4.1 of "The Theory and Practice of First-Class Prompts" (Felleisen, POPL 1988).

In Racket there is a prompt around every REPL interaction and around each module-level form. (See the quote in Sorawee's answer.)

You can use prompts yourself to further delimit the continuations captured by call/cc. Here's a little example:

> (require racket/control)
> (define c #f)
> (list 'a (prompt
            (* 1000
               (let/cc k
                 (set! c k)
                 5))))
'(a 5000)
> (list 'b (c 6))
6000

Notice that in the final interaction, there is no (list 'a _) wrapper because of the prompt, and there is no (list 'b _) wrapper because the captured continuation aborts that part of the use-site continuation. We can protect parts of the use-site continuation from being aborted by using prompt too:

> (list 'c (prompt (list 'd (c 7))))
'(c 7000)

Only the part "after" the prompt gets discarded.

The way people sometimes talk about "capturing a delimited continuation" is wrong and misleading. In Racket all continuation capture operations, even call/cc, are delimited by prompts. Some operations, like control and shift, though, capture composable continuations that can be used without aborting the use-site continuation. Thus the Racket primitive is call-with-composable-continuation rather than call-with-delimited-continuation.

Here's the same example as above but with control instead of let/cc:

> (require racket/control)
> (define c #f)
> (list 'a (prompt
            (* 1000
               (control k
                 (set! c k)
                 5))))
'(a 5)
> (list 'b (c 6))
'(b 6000)