13.11 Thematic Takeaways

• First-class continuations are ideal for programming abnormal flows of control (e.g., nonlocal exits) and, more generally, for control abstraction— implementing user-defined control abstractions.

• The call/cc function captures the current continuation with a representation of the environment, including the run-time stack, at the time call/cc is invoked.

• Unlike goto, continuation replacement in Scheme [i.e., (k v)] is not just a transfer of control, but also a restoration of the environment, including the run-time stack, at the time the continuation was captured.

• First-class continuations are sufficient to create a variety of control abstractions, including any desired sequential control structure (Haynes, Friedman, and Wand 1986, p. 143).

• It is the unlimited extent of closures that unleashes the power of first-class continuations for control abstraction. The unlimited lifetime of closures enables control to be transferred to stack frames—called heap-allocated stack frames—that seemingly no longer exist.

• A limited extent of closures puts a limit on the scope of control abstraction possible through application of operators for transfer of control (e.g., setjmp/longjmp in C) and restricts their use for handling exceptions to, for example, nonlocal exits.

• Using first-class continuations to create new control structures and abstractions is an art requiring creativity.

• Use of tail recursion trades off function writability for improved space complexity.

• The call/cc function automatically reifies the implicit continuation that the programmer of a function using CPS manually reifies.

• In a program written in continuation-passing style, the continuation of every function call is passed as an additional argument representing the continuation of the call. In consequence, every function call is in tail position.

• In continuation-passing style, the continuation passed to the function defined using CPS must both exclusively use tail calls and be invoked in tail position itself.

• Continuation-passing style implies tail calls, but tail calls do not imply continuation-passing style.

• Tail-call optimization eliminates the run-time stack, thereby enabling (recursive) functions to run in constant space—and rendering recursion as efficient as iteration.

• A stack is unnecessary for a language to support functions.

• Tail-call optimization is applicable to all tail calls, not just tail-recursive ones.

• There is a trade-off between time complexity and space complexity in programming (Table 13.14).