A continuation in information technology is an abstract representation of the future of a computation—the remaining steps to be performed after a given point in a program’s execution. It captures the entire state of the program's control flow, including the call stack and the bindings of local variables, allowing the computation to be saved, passed, and later resumed.

The concept originated in the 1960s and 1970s within the field of denotational semantics. Christopher Strachey and Christopher Wadsworth first used continuations to give a precise meaning to control structures in programming languages. The term "continuation" itself was popularized by John C. Reynolds in his 1972 paper "Definitional Interpreters for Higher-Order Programming Languages." Later, in the early 1980s, the functional language Scheme introduced call/cc (call with current continuation), making continuations a first-class language feature. This innovation influenced subsequent language design, compiler optimization, and the development of advanced control-flow mechanisms such as coroutines and backtracking.

Continuation‑passing style (CPS) is a programming style in which every function explicitly receives a continuation—a function representing the rest of the computation—as an additional argument. Instead of returning a result in the usual way, a CPS function passes its result to the continuation. This style makes the program’s control flow completely explicit and eliminates the need for an implicit call stack.

2.1 Motivation and key ideas

The primary motivation for CPS is to give the programmer (or compiler) fine-grained control over the order of evaluation and to facilitate transformations that improve performance or enable new language features. In CPS, there are no implicit returns; every procedure call ends with a tail call to a continuation. This property ensures that all calls are tail calls, which simplifies the implementation of non‑local jumps, exceptions, and backtracking. CPS also serves as an intermediate representation in compilers, making it easier to perform optimizations such as inlining, constant propagation, and register allocation.

2.2 Transformation from direct style

A direct‑style program (where functions return values normally) can be mechanically transformed into CPS. The transformation introduces a continuation parameter for each function and replaces every expression that produces a value with a call that passes that value to the continuation. The resulting CPS code is often longer but fully tail‑recursive.

2.2.1 Example: factorial in CPS

Consider a direct‑style factorial function:

(define (fact n)
  (if (= n 0) 1 (* n (fact (- n 1)))))

In CPS, it becomes:

(define (fact-cps n k)
  (if (= n 0)
      (k 1)
      (fact-cps (- n 1) (λ (v) (k (* n v))))))

Here k is the continuation. When n is zero, the base result 1 is passed to k. Otherwise, fact-cps is called with a new continuation that multiplies the result by n and passes that to the original k.

2.2.2 Tail‑call optimization

In CPS, all function calls are in tail position—there is no implicit stack frame left after a call. This means that a proper tail‑call‑aware implementation can reuse the current stack frame, avoiding stack growth and enabling loops to be expressed as recursion without memory overhead. Tail‑call optimization (TCO) is a key benefit of CPS: a program that would normally cause a stack overflow can run indefinitely in constant space.

2.3 Applications in compilers

Many compilers for functional languages (e.g., SML/NJ, Haskell via the STG machine) use CPS as an intermediate representation. By converting a source program to CPS, the compiler can unify the handling of function calls, jumps, and exception handlers. Optimizations such as CPS conversion, closure conversion, and register allocation can be applied in a systematic manner. Additionally, CPS makes it straightforward to implement the call/cc primitive because the current continuation is already represented as an explicit argument.

First‑class continuations are continuations that can be created, stored in data structures, passed as arguments, and invoked at any time. They allow the programmer to capture the entire future of a computation at a specific point and later resume it from that point, possibly multiple times. The most well‑known construct for obtaining a first‑class continuation is call/cc (call with current continuation).

3.1 The call/cc construct

call/cc is a higher‑order function that takes a single argument (a procedure). It captures the current continuation (the rest of the computation at the point of the call) and passes it to that procedure. The continuation is itself a procedure of one argument; invoking it with a value causes the program to jump back to the captured point, effectively discarding the current state.

3.1.1 Semantics and typical usage

When (call/cc f) is evaluated, f receives a continuation object k. If f returns normally, the result of the entire expression is that return value. However, if f invokes k with some value v, then the computation immediately jumps to the point where call/cc was called, and v becomes the result of the entire call/cc expression. This allows powerful control flow, such as implementing early exits, loops, and ambiguous choice.

A classic example is simulating the or operator: if a function f returns a false value, we can use a continuation to try an alternative.

(define (try f)
  (call/cc (λ (k)
             (let ((result (f)))
               (if result result (k #f))))))

Here k is a continuation that aborts the rest of try and returns #f.

3.1.2 Comparison with call/cc in Scheme vs. other languages

Scheme is the canonical language with call/cc; it is part of the language standard. In Scheme, continuations are full, meaning they capture the entire call stack including dynamic environment (e.g., exception handlers). Other languages with first‑class continuations include Standard ML of New Jersey (SML/NJ) and Racket. In contrast, languages like Java and C++ do not expose continuations directly, though libraries or runtime techniques (e.g., bytecode manipulation) can simulate them. The semantics of call/cc may vary in details such as whether the continuation is one‑shot (can be used only once) or multi‑shot (can be reused). Scheme’s call/cc is multi‑shot, while some implementations (e.g., in some experimental languages) restrict to one‑shot for efficiency.

3.2 Control‑flow applications

First‑class continuations enable many advanced control‑flow paradigms that are difficult to express in languages without them.

3.2.1 Non‑local exits and exceptions

A continuation can be used to implement non‑local exits, similar to longjmp in C or exceptions in modern languages. By capturing a continuation at the top level of a computation, one can abort from nested function calls and resume at that top level. This allows a lightweight form of exception handling without language‑level support.

3.2.2 Coroutines and generators

Coroutines are cooperative multitasking units that can suspend and resume execution. Using call/cc, one can implement coroutines by capturing a continuation at the point of suspension and later resuming it. Similarly, generators (iterators that yield values lazily) can be built: a generator function captures its continuation when yielding, and the consumer invokes that continuation to request the next value.

3.2.3 Backtracking (e.g., amb operator)

The amb operator, introduced by John McCarthy in the context of nondeterministic programming, allows a program to choose among alternative values and automatically backtrack on failure. With call/cc, one can implement amb by maintaining a list of continuations representing unexplored choices. When a branch fails, the program invokes the next saved continuation, effectively undoing the state and trying a different alternative.

3.2.4 Cooperative multitasking

First‑class continuations can be used to implement user‑level threads (also called green threads or coroutines) without relying on OS‑level preemption. Each thread is represented by a continuation; a scheduler can switch between threads by saving and restoring continuations. This is the basis of many early functional‑language concurrency libraries and influenced more recent constructs such as fibers in Ruby and Go’s goroutines (though the latter use a different mechanism).

Implementing first‑class continuations efficiently requires careful handling of the program’s stack and memory.

4.1 Representing continuations (stack vs. heap)

A continuation essentially captures the current execution stack. In many systems, the stack is a contiguous memory segment. A naive implementation would copy the entire stack into a heap‑allocated object when a continuation is captured, and restore it when the continuation is invoked. This is called stack copying and was used in early Scheme systems. However, stack copying is expensive and can lead to fragmentation. An alternative is to store continuations on the heap from the beginning, using continuation frames that are allocated on the heap like other data. This is the approach taken by the Standard ML of New Jersey compiler, which uses a CPS‑based intermediate representation where all code is written in continuation‑passing style. In such a system, capturing a continuation is as simple as making a copy of a closure pointer, and no stack copying is needed.

4.2 Garbage collection of continuations

Since continuations are regular heap objects in many implementations, they are subject to garbage collection. The key challenge is that a continuation may capture references to variables that are no longer reachable from the rest of the program. The garbage collector must be able to traverse a continuation’s captured environment accurately. Additionally, if continuations are used for backtracking (e.g., storing multiple continuations), they can hold onto large amounts of memory. Generational or incremental collectors are often used to manage these objects efficiently.

4.3 Performance considerations

First‑class continuations impose overhead in general. Each continuation capture can involve copying a significant amount of state. Furthermore, the ability to jump arbitrarily may inhibit compiler optimizations such as inlining and register allocation. To mitigate these costs, many language implementations provide continuations only through a library or restrict them to delimited forms (see §5.1). For example, the Racket language provides both call/cc and more efficient delimited continuations, encouraging programmers to use the latter for better performance.

Over time, researchers and language designers have developed several variants of continuations that offer a controlled form of control‑flow manipulation while avoiding some of the costs and complexities of full first‑class continuations.

5.1 Delimited continuations (shift/reset)

Delimited continuations (also called composable continuations) capture only a portion of the computation, bounded by a delimiter (e.g., reset). The captured part is represented as a function that can be composed with other computations. The shift operator captures the current delimited continuation. This approach is more modular and easier to implement efficiently than full continuations. Delimited continuations are used in languages like Racket (via reset and shift), and they form the basis of algebraic effect handlers.

5.2 Continuation‑based concurrency (e.g., fibers)

Fibers are lightweight, cooperative threads that use continuations internally for suspension and resume. Rather than exposing full continuations to the programmer, the language or runtime provides a coroutine‑like abstraction. For example, Ruby’s Fiber class and the async/await pattern in C# both rely on a continuation‑like mechanism under the hood, but the user sees a simpler interface. These constructs are easier to optimize and do not suffer from the same memory and performance issues as unrestricted call/cc.

5.3 Coroutines compared with generators

Generators are a restricted form of coroutines that only allow yielding values upward to a caller. In contrast, full coroutines allow symmetric communication between two or more routines. Continuations provide the underlying mechanism for both; generators can be implemented with a single saved continuation, while coroutines require multiple continuations for each execution context. Many modern languages (Python, JavaScript, C#) offer generators and/or async functions that are built on a continuation‑like state machine, but they do not expose call/cc to the programmer.

5.4 Effect handlers

Effect handlers, popularized by languages like Eff and OCaml’s multicore extension, generalize delimited continuations by allowing programmers to define and intercept custom computational effects (e.g., state, nondeterminism, I/O). An effect handler uses a delimited continuation to resume the computation after handling an effect. This approach provides a cleaner and more composable alternative to first‑class continuations for many use cases.

Different programming languages support continuations to varying degrees, from full first‑class status to limited, library‑based implementations.

6.1 Languages with first‑class continuations (Scheme, SML/NJ)

  • Scheme (R⁵RS, R⁶RS): Provides call/cc as a standard primitive. Many Scheme implementations also offer delimited continuations via libraries or built‑ins (e.g., shift/reset in Racket).
  • Standard ML of New Jersey (SML/NJ): Offers first‑class continuations via the SMLofNJ.Cont module. The compiler uses CPS internally, making continuation capture efficient.
  • Racket: Inherits call/cc from Scheme but also provides delimited continuations (let/cc, shift/reset) and a variety of control‑flow operators.

6.2 Languages with limited continuations (C# async/await, Python yield)

  • C#: The async/await pattern is syntactic sugar over a state machine that implicitly uses continuations to suspend and resume tasks. Programmers do not manipulate continuations directly.
  • Python: The yield statement in generators captures a continuation of the generator’s execution. Python’s asyncio library uses a similar mechanism for coroutines.
  • JavaScript: async/await and generator functions (function*) are built on a continuation‑like model, but the language does not expose call/cc.
  • Java: No direct continuation support, but libraries like Quasar and Kilim implement continuations through bytecode instrumentation.

6.3 Libraries and compiler transformations (e.g., Racket, OCaml)

  • Racket: Provides a rich set of control‑flow libraries, including racket/control for delimited continuations and racket/place for parallel execution.
  • OCaml: The ocaml‑effect library (and more recently, the multicore extension) offers effect handlers, which are a form of delimited continuations. OCaml also has limited support for first‑class continuations via the Cont module.
  • Haskell: The Cont monad provides a type‑safe way to work with continuations in CPS. The shift and reset operators are available in the Cont monad transformers. Haskell also uses continuations internally for exception handling and concurrency (e.g., async).

Research on continuations continues, focusing on efficiency, scalability, and integration with modern language design.

  • Efficient implementations of delimited continuations: Work on one‑shot continuations and “segmented” stacks helps reduce the overhead of capturing and restoring control state. Projects such as OCaml’s multicore runtime use segmented stacks for lightweight threads.
  • Algebraic effect handlers: The combination of delimited continuations with effect systems is an active area. Languages like Eff, Koka, and F* (with effect handlers) aim to provide a clean, composable approach to side effects without sacrificing performance.
  • Continuations in distributed and parallel computing: Researchers explore using continuations to model distributed computation, where capturing a continuation of a remote computation can simplify failure recovery and migration.
  • Formal semantics and verification: Continuations remain a fundamental tool in denotational and operational semantics. Recent work applies continuations to reason about correctness of compiler transformations and to design new type systems for control effects.
  • Continuations in web programming: The inversion of control in web applications has been addressed using continuations (e.g., the Scheme‑based web server, or the “continuation‑based” web frameworks). While not mainstream, the idea persists in research on server‑side programming.

Overall, continuations—both full and delimited—remain a powerful concept in computer science, underpinning many advanced programming language features and compiler optimizations. As languages evolve, the balance between expressiveness and performance continues to shape how continuations are offered to programmers.