Control operators are language constructs provided by some functional languages that allow expressions to capture their continuations, manipulate them as first-class values, and restart them later.
Control operators make it possible to program advanced control structures (exceptions, backtracking, cooperative threads, etc.) as library functions that can be used in programs written in direct style. With control operators, there is no need to rewrite programs in continuation-passing style, as we did in chapter 7, to use these user-defined advanced control structures.
The first published control operator appears in the work of Landin (1965) on a semantics of Algol 60 based on a translation into his ISWIM language.
ISWIM is a precursor to all modern strict functional languages (Scheme, Common Lisp, SML, OCaml, etc). It is based on the call-by-value lambda-calculus extended with primitive data types and operations. Like the lambda-calculus, and unlike early Lisp systems, ISWIM guarantees static scoping of free variables in function abstractions. The semantics of ISWIM is defined in an operational style, using an abstract machine called the SECD (Landin, 1966). The SECD was the first implementation of a functional language to use function closures to represent first-class functions with static scoping of free variables.
Landin (1965) outlines an explanation of Algol 60 by translating it to ISWIM with some extensions. To handle mutable variables that are shared between multiple function environments, Landin adds ML-style references. To handle non-local goto jumps, he adds a control operator named J (as in “jump”).
The J operator can be thought of as a generalization of the return statement in languages like C or Java. The evaluation of J (λ x . e) v computes the value of (λ x . e) v and returns it directly to the caller of the current function, skipping the computations that remain to be done in the body of the current function. For example, consider:
| let f = λ n. n + J (λ x . x × 2) 3 in f 4 |
Evaluating J (λ x . x × 2) 3 will return the value 6 = 3 × 2 as the result of f 4, ignoring the computation of n + … Thielecke (1998) describes the J operator as modifying the function it receives as argument (here, λ x . x × 2) so that the modified function no longer returns to the point where it was called, but to the point where the enclosing function (here, λ n …) was called.
As a special case, J (λ x . x) v behaves like return v in C or Java. For example, here is a convoluted way to return the absolute value of an integer n:
| λ n. − (if n >= 0 then J (λ x . x) n else n) |
This is the ISWIM equivalent to the following C code:
The J operator can be used to encode Algol-style labels and goto statements.
|
A label L becomes a unit → unit function that jumps out of the block that defines L. A block that defines a label L becomes a unit → unit function that is immediately applied to the unit value, binding L to a function that executes the labeled statement s2 and exits the function. The binding of L is recursive so that s2 can jump to L.
Compare this translation of goto jumps with the continuation-based denotational semantics described in section 6.3. In both cases, a label is interpreted as a function that executes the labeled statement and exits the block that defines the label. Thanks to the control operator J, continuations remain implicit in the translation, while they are made explicit in the denotational semantics, as additional parameters to the denotation function.
The most well-known control operator is “call-with-current-continuation” from the Scheme language, often abbreviated to call/cc or callcc. It allows an expression to capture its own continuation in the form of a function. This operator has appeared in the literature under various names: escape in Reynolds (1998) (originally published in 1972), catch and throw in Sussman and Steele (1975), and call-with-current-continuation in the Scheme language, around 1982.
The expression callcc(λ k . e) is evaluated as follows:
The presentation above, where continuations are abstract values and a throw operator is required to invoke them, is the one used in ML-style languages. In Scheme, there is no throw operator: continuations are functions and can be invoked simply by applying them.
For example, here is the convoluted way of computing the absolute value of an integer n mentioned in section 8.1, written using callcc and throw:
If n is nonnegative, the throw k n construct returns directly n from abs, skipping the “opposite” operation.
Here is a more interesting example. Suppose we have an imperative internal iterator on a data structure such as binary trees:
| tree_iter : ∀ α, (α → unit) → α tree → unit |
Using callcc, we can use this iterator to traverse a tree, stopping as soon as it finds an element that satisfies the predicate pred, and returning the element found:
The continuation captured by callcc and bound to k is the continuation of the call to tree_search. If none of the elements of the tree t satisfies pred, the traversal tree_iter terminates normally and returns None to the caller. On the other hand, if the traversal hits an element x such that pred x is true, the continuation k is invoked with Some x as argument, aborting the traversal and returning Some x as the value of tree_search pred t.
The same effect could be achieved by using an exception:
Unlike exceptions, callcc also provides the ability to suspend a computation and restart it later. Let us add a second callcc that captures the continuation of the traversal at the point where we produce the Some x result:
Now, the caller of tree_search receives not only the first element x that satisfies pred, but also a continuation k’ which, when invoked, restarts the traversal where it left off, causing tree_search to return again with the next element of the tree that satisfies pred. For example:
Despite the lack of recursion, this code prints all the elements of t that satisfy pred one by one, and then prints “Done”. Each time an element x is found, it is printed and the continuation k’ is invoked, restarting the match with the next result of tree_search pred t. The match terminates only when tree_search returns None.
We now show three examples of control structures that can be defined as libraries using callcc: exceptions, cooperative threads, and nondeterminism implemented via backtracking.
Exceptions. Exception handlers can be represented as continuations expecting an exception descriptor. (In OCaml, exception descriptors have type exn, and we write exn cont for the type of continuations expecting a value of type exn.) We maintain a stack of active handlers in a global variable:
To raise an exception, we pop a handler from this stack and restart it with the given exception value:
The following trywith body handler is equivalent to try body() with exn -> handler exn in OCaml: it evaluates body(), catches exceptions raised during this evaluation and passes them to handler.
Two continuations are captured: k1 to return the value of body() if it terminates normally, and k2 to pass an exception value to handler. The latter continuation, k2, is pushed onto the stack of handlers for the duration of the evaluation of body(). Note that handler is not called if body() returns normally, as the throw k1 res skips over the application of handler; it is called only if the continuation k2 is thrown, i.e. if an exception is raised.
Cooperative multithreading. The following implementation of cooperative threads is similar to that of section 7.3, with the crucial difference that yield uses callcc to recover its continuation, rather than taking that continuation as an explicit argument.
Consequently, the callers of yield do not need to be written in CPS: they are written in direct style, as plain imperative computations. For example, here is a process that prints integers from 1 to count, with the given prefix, yielding control after each print:
We can still interleave the execution of several such processes:
This prints C1 A1 B1 C2 A2 B2 C3 A3 B3 C4 A4 C5 A5 C6.
Choice points and backtracking. A Prolog-style search for a solution can be presented as a non-deterministic functional program: choice chooses one possibility among several, in such a way that future assertions are satisfied. Here is an example (courtesy of Matt Might): find a right triangle whose sides a, b, c are integers.
This can be implemented using backtracking: a failed assert_ backtracks to the last choose point, causing it to pick the next value from the list of alternatives provided by the programmer and to reexecute the subsequent computations. If the list is exhausted, execution backtracks to the previous choose point. We maintain a stack of backtrack points, represented as continuations expecting unit values:
The fail function jumps to the last backtrack point. Unlike the raise function for exceptions, fail does not remove the backtrack point from the stack, since it can be backtracked to again in the future. Assertion checking (the assert_ function) simply fails if the Boolean condition is false.
The choose function uses callcc to capture a continuation and push it onto the backtrack stack. This continuation branches to the match construct shown above, which returns the next possible value in the list reference l, after removing it from the list. If l is empty, choose removes its continuation from the backtrack stack and calls fail, causing the previous choice point to be backtracked. The net effect is that choose l enumerates the elements of l and returns them to its caller one by one.
CPS transformation. One way to give semantics to callcc is to perform a CPS transformation, making continuations explicit in the transformed program. We start with the call-by-value CPS transformation from section 6.5:
|
and extend it as follows to handle callcc and throw:
|
For callcc e, the continuation k is duplicated: it is used once as an argument to e and once as the continuation for the application of f to k. For throw e1 e2, the continuation k is discarded: execution continues with the continuation k1 obtained by evaluating e1. This contrasts with the other language constructs (variables, abstractions, applications), whose CPS transformations use continuations linearly: each k parameter is used exactly once.
For example, consider the function yield from the cooperative multithreading library in section 8.3:
After CPS transformation and simplification of administrative redexes, we obtain
The function yield now receives its continuation as an explicit parameter k. The function that is pushed onto the ready queue restarts k, ignoring its own continuation parameter k’.
Reduction semantics. The semantics of callcc can also be defined in operational style, using reductions under context, as in section 5.5.
Continuations and reduction contexts are closely related: if a program p can be decomposed as p = C[e], where C is a reduction context and e can be reduced by a head reduction rule, then the continuation of e in p is exactly λ x . C[x] (with x a variable not bound by C), i.e., the context C reified as a function. Consequently, we have the following reduction rules for callcc and throw:
|
These two rules are not head reductions →ε: they apply to whole programs, not under a context.
Note how the callcc rule duplicates the context C, using it once as an argument to λ k . e and once as the context for (λ k . e) (λ x . C[x]). Likewise, the throw rule discards the context C entirely, bringing the application (λ x. k) v to the top level of the program.
For example, consider the program
| p = 2 × callcc (λ k . 1 + throw k 0) |
Using the callcc rule with the context C = 2 × [ ], it is reduced as follows:
|
At this point, we use the throw rule with the context C = 2 × (1 + [ ]), obtaining
|
The continuations captured by callcc are undelimited: they extend all the way to the end of the program execution. Invoking one of these continuation never returns a value, like raising an exception never returns a value.
For some applications of continuations, such as the “generate, filter and count” examples in section 7.6, it is necessary to use delimited continuations. A delimited continuation returns a value when invoked, just like an ordinary function. Moreover, it represents the computations from the current point A to a later point B in the program execution, rather than to the end of the program execution. Point B is called “the prompt” in the literature, and a special construct delim is provided to “set the prompt” during the evaluation of an expression.
In other words, just like the undelimited continuation of an expression e is the function
| value of e ↦ value of the whole program |
the delimited continuation of e is the function
| value of e ↦ value of the enclosing delim expression. |
Many control operators have been proposed to work with delimited, composable continuations, such as control/prompt by Felleisen (1988), shift/reset by Danvy and Filinski (1990), and the effect handlers described in chapter 10. These approaches provide two operators for delimiting and capturing continuations, which we write delim and capture in the following.
| value of capture (λ k . e) → value of the enclosing delim e0 |
As an artificial example, consider the program
| p = 2 × delim (1 + capture (λ k . k (k 0))) |
The continuation k that is captured is λ x . 1 + x. It represents the computations that remain to be done once we have the value x of capture (…) to produce the value of the argument to delim (…). Then, k (k 0) is evaluated, resulting in the value 2. This value is returned directly as the result of delim (…). Thus, the whole program evaluates to 2 × 2 = 4. More specifically, we have the following reduction sequence:
|
The semantics of capture outlined above is that of the control operator of Felleisen (1988). As discussed in the next section, other semantics have been proposed.
Other proposals support multiple prompts, with delim and capture taking a prompt identifier as an argument, so that capture can choose between multiple prompts to delimit the captured continuation. This is the case for the cupto proposal by Gunter et al. (1995) and the delim/cc extension of OCaml by Kiselyov (2012).
Just as undelimited, whole-program continuations correspond closely to reduction contexts, delimited continuations correspond closely to reduction subcontexts that contain no delimiters. Consider the following grammar for two types of reduction contexts:
| Full reduction contexts: C | ::= | [ ] ∣ C e ∣ v C ∣ if C then e1 else e2 ∣ delim C | |||
| Delimiter-free reduction contexts: D | ::= | [ ] ∣ D e ∣ v D ∣ if D then e1 else e2 |
If we can decompose a whole program p as p = C[delim D[e]], where e is an expression that can be head-reduced, we have identified the delimited continuation of e: it is λ x . D[x], that is, the reification of the subcontext D. The fact that D contains no delim constructs guarantees that this delimited continuation stops at the nearest enclosing delim.
This discussion suggests two head reduction rules for delim:
|
Although the second rule involves a subcontext D, these two rules are head-reduction rules: they can be applied under any evaluation context C.
The first rule, delim v →ε v, is obvious: delim can be deleted when its argument is fully evaluated and will no longer capture any continuation. The second rule, which defines the semantics of capture, comes in four different flavors, reflecting four different delimited control operators that have been studied in the literature:
|
The rules differ in two aspects, highlighted in red above: whether the original enclosing delim is kept (control, shift) or removed (control0, shift0); and whether the captured continuation is wrapped in a delim (shift, shift0) or not (control, control0). The first choice matters if the body e of the capture contains other capture operations. The second choice matters if the captured continuation contains other capture operations.
In particular, the control operator of Felleisen (1988) keeps the delim that encloses the capture, but does not add a delimiter around the captured continuation. This is the semantics used in the artificial example of section 8.5.
In contrast, the shift operator of Danvy and Filinski (1990) not only keeps the delim that encloses the capture, but also wraps a new delim around the captured continuation. This enforces a form of static scoping for delimiters, and allows fine-grained, static type checking of the shift operator (see section 13.2).
The “zero” forms (shift0, control0) are less convenient for programming but more suitable as building blocks for a formal study or a low-level implementation. In particular, control, shift and shift0 can be trivially defined in terms of control0.
Continuing section 8.3, we now illustrate the use of delimited control operators to implement control inversion, nondeterminism with backtracking, and generation and counting. These examples use the shift semantics for the capture operator.
Control inversion of an iterator. As in section 7.2, consider an internal iterator over binary trees:
Using delimited continuations, we can reuse tree_iter to obtain a purely functional, external iterator for trees:
For each element x of the tree, the capture operator captures a continuation k and causes More(x, k) to be returned as the value of the entire delim expression, i.e. as the result of the tree_enumerator function. The k continuation extends from the return point of the capture expression — the next step in the tree traversal — to the end of the delimited expression — the final Done value. Thus, applying the continuation k restarts the tree_iter traversal, producing the next More enumeration element, or Done if the traversal is over and tree_iter terminates normally.
The control inversion above follows the same logic as the one shown in section 7.2, except that we did not have to rewrite tree_iter in continuation-passing style (CPS). Instead, we work with the direct-style tree_iter and rely on capture and delim to build the necessary continuations.
Choice points and backtracking. The choose, fail and assert_ for Prolog-style searching and backtracking introduced in section 8.3 are easily implemented using delimited continuations:
The nondeterministic computation must be enclosed in the delim construct:
The computations captured by choose, fail and assert_ start at the return point of these functions and extend to the end of the delim block. choose replaces its continuation with a List.iter, executing the continuation once for each of the possible values. For example, the first choose becomes
Likewise, fail (), which is equivalent to choose [], just replaces its continuation with (), causing the rest of the computation up to the point delimited by delim to be skipped and the next round of List.iter to begin. For example, if assert_ (c * c = a * a + b * b) fails, assert_ (a < b) and the printf statement are not executed, and the next value for c is tried.
In contrast to the implementation based on callcc shown in section 8.3, we do not need to use mutable data structures to represent the stack of backtracking points and the current state of the iteration in the choose points: the composition of delimited continuations implemented by choose and fail is sufficient to capture the current state of the search.
Generating and counting. Section 7.6 showed how to use explicit integer-valued continuations to generate sets of values, run each value through the continuation, and combine the counts returned by the continuation, typically by summing them. Delimited continuation operators make it easy to implement this idiom in direct style, without making continuations explicit in the program. For example, here are two generating functions, one for Booleans and the other for integers in the [lo, hi] range.
We can use the int generator to enumerate all the throws of three 6-sided dice and count how many throws result in 16 or more:
This reads very much like “pick one d1 in [1,6], one d2 in [1,6], and one d3 in [1,6], then return 1 if d1 + d2 + d3 ≥ 16 and 0 otherwise”. But what happens is that all possible values of d1, d2 and d3 are tried, and all the 0/1 results are summed.
Generating functions can also be recursive. For example, here is a generator for binary trees of height h with the heights at the nodes.
For the recursive case h > 0, we separately generate trees with a left subtree of height h − 1 and a right subtree of height ≤ h−1, and trees with a right subtree of height h − 1 and a left subtree of height < h−1. This produces all the trees of height h, without repetitions.
The usual CPS transformation of a term e takes one continuation k as an argument. This continuation extends from the end of e’s evaluation to the end of the whole program. To handle delimited continuation operators, this continuation k needs to be decomposed in a list of partial continuations k0, …, kn, where n is the number of enclosing delimiters. Continuation k0 extends from the end of e’s evaluation to the first enclosing delimiter; k1 extends from here to the next enclosing delimiter; all the way to kn, which extends to the end of the whole program.
We could group these n+1 partial continuations into a list [k0, …, kn] that is passed as a single argument to CPS-transformed expressions. Instead, Materzok and Biernacki (2011) choose to pass the continuations as n+1 distinct arguments, in curried form. In other words, the CPS transform 𝒞(e) of an expression e surrounded by n delimiters should be applied n+1 times to the continuations k0, …, kn:
| 𝒞(e) k0 k1 … kn |
Moreover, when the continuation k0 is finally triggered, it expects not only the value of e as argument but also the remaining continuations k1, …, kn. In other words, if e reduces to the constant c without using a control operator, we should have
| 𝒞(e) k0 k1 … kn →* k0 c k1 … kn |
This generalizes a property of the standard CPS transformation: 𝒞(e) k →* k c if e →* c.
For core language constructs, the transformation is the standard call-by-value transformation of section 6.5:
|
By the magic of curried function application, this translation remains correct when 𝒞(e) is applied to more than one continuation. For example, if e is a constant c,
| 𝒞(c) k0 k1 … kn = (λ k . k c) k0 k1 … kn → k0 c k1 … kn |
A delimiter adds a trivial continuation at the top of the list:
| 𝒞(delim e) = 𝒞(e) (λ x . λ k . k x) |
If e reduces to a constant without capturing a continuation, we have the expected reduction sequence:
|
Symmetrically, the capture operator reifies the first continuation to a value, and removes it from the list of continuations:
| 𝒞(capture (λ k . e)) = λ k . 𝒞(e) |
With this definition, we have
| 𝒞(capture (λ k. e)) k0 k1 … kn → 𝒞(e) [k := k0] k1 … kn |
In other words, the evaluation of e continues with k1, the continuation “after” the nearest delimiter. The continuation up to that delimiter, k0, is captured as the k parameter to e. This implements the control0 semantics for capture.
The “Continuations” chapter of Butterick (2025) is a good starting point for exploring call/cc and other control operators in Scheme. Friedman (1988) is a classic tutorial on call/cc and its many applications. Appendix A of Hillerström (2021) gives a unified presentation of the many control operators that have been proposed, both for undelimited continuations and for delimited continuations.
The efficient implementation of callcc and other control operators is challenging. Clinger et al. (1999) describe several approaches that combine first-class continuations with a traditional call stack. Gasbichler and Sperber (2002) show how delimited continuations can be implemented more efficiently than callcc. Kiselyov (2012) describes the delimcc implementation of delimited continuations for OCaml that was used for the examples in this chapter. The SML/NJ compiler (Appel, 1992) uses CPS transformation and a stackless implementation to provide zero-cost callcc.