13.12 Chapter Summary

This chapter is concerned with imparting control to a computer program. We used first-class continuations (captured, for example, through call/cc), tail recursion, and continuation-passing style to tease out ideas about control and how to affect it in programming. While evaluating an expression, the interpreter must keep track of what to do with the return value of the expression it is currently evaluating. The actions entailed in the “what to do with the return value” are the pending computations or the continuation of the computation. A continuation is a one-argument function that represents the remainder of a computation from a given point in a program. The argument passed to a continuation is the return value of the prior computation—the one value for which the continuation is waiting to complete the next computation.

The call/cc function in Scheme captures the current continuation with a representation of the environment, including the run-time stack, at the time call/cc is invoked. The expression (k v), where k is a first-class continuation captured through (call/cc (lambda (k) ...)) and v is a value, does not just transfer program control. The expression (k v) transfers program control and restores the environment, including the stack, that was active at the time call/cc captured k, even if it is not active when k is invoked. This capture and restoration of the call stack is the ingredient necessary for supporting the creation of a wide variety of new control constructs. More specifically, it is the unlimited extent of lexical closures that unleash the power of first-class continuations for control abstraction: The unlimited lifetime of closures enable control to be transferred to stack frames that seemingly no longer exist, called heap-allocated stack frames.

Mechanisms for transferring control in programming languages are typically used for handling exceptions in programming. These mechanisms include function calls, stack unwinding/crawling operators, exception-handling systems, and first-class continuations. In the absence of heap-allocated stack frames, once the stack frames between the function that caused/raised an exception and the function handling that exception have been popped off the stack, they are gone forever. For instance, the setjmp/longjmp stack unwinding/crawling functions in C allow a programmer to perform a nonlocal exit from several functions on the stack in a single jump. Without heap-allocated stack frames, these stack unwinding/crawling operators transfer control down the stack, but not back up it. Thus, these mechanisms are simply for nonlocal exits and, unlike first-class continuations, are limited in their support for implementing other types of control structures (e.g., breakpoints).

We have also defined recursive functions in a manner that maintains the natural correspondence between the recursive specification or mathematical definition of the function [e.g., ] and the program code implementing the function (e.g., factorial). This congruence is a main theme running throughout Chapter 5. When such a function runs, the activation records for all of the recursive calls are pushed onto the run-time stack while building up pending computations. Such functions typically require an ever-increasing amount of memory and exhibit recursive control behavior. When the base case is reached, the computation required to compute the function is performed as these pending computations are executed while the activation records for the recursive calls pop off the stack and the memory is reclaimed. In a function using tail recursion, the recursive call is the last operation that the function must perform. Such a recursive call is in tail position [e.g., ] in contrast to operand position [e.g., ]. A function call is a tail call if there is no promise to do anything with the returned value. Recursive functions using tail recursion exhibit iterative control behavior. However, the structure of the program code implementing a function using tail recursion no longer reflects the recursive specification of the function—the symmetry is broken. Thus, the use of tail recursion trades off function writability for improved space complexity.

We can turn all function calls into tail calls by encapsulating any computation remaining after each call—the “what to do next”—into an explicit, reified continuation and passing that continuation as an extra argument in each tail call. In other words, we can make the implicit continuation of each called function explicit by packaging it as an additional argument passed in each function call. Functions written in this manner use continuation-passing style (CPS). The continuation that the programmer of a function using CPS manually reifies is the continuation that the call/cc function automatically reifies. A function defined using CPS can accept multiple continuations; this property helps us cleanly factor the various ways a program might complete its computation. A function defined in CPS can pass multiple results to its continuation; this property provides us with flexibility in communicating results to continuations.

A desired result of CPS is that the recursive function defined in CPS run in constant memory space. This means that no computations are waiting for the return value of each recursive call, which in turn means the function that made the recursive call can be popped off the stack. The growing stack of pending computations can be transmuted through CPS as a growing continuation parameter. We desire a function embracing the spirit of CPS, where, ideally, the passed continuation is not growing. Continuation-passing style with a bounded continuation parameter and tail-call optimization eliminates the run-time stack, thereby ensuring the recursive function can run in constant space—and rendering recursion as efficient as iteration.

There is a trade-off between time complexity and space complexity in programming. We can be either (1) time efficient, by waiting until we know for certain that we will not encounter any exceptions before beginning the necessary computation (which requires us to store the pending computations on the call stack or in a continuation parameter), or (2) space efficient, by incrementally computing intermediate results (in, for example, an accumulator parameter) in the presence of the uncertainty of encountering any exceptional situations. It is challenging to do both (Table 13.14).

Table 13.14 The Approaches to Function Definition as Related to Control Presented in This Chapter Based on the Presence and Absence of a Variety of Desired Properties. Theme:We cannot be both time and space efficient.

Programming abnormal flows of control and running recursive functions in constant space are two issues that can easily get conflated in the study of program control. Continuation-passing style with tail-call optimization can be used to achieve both. Tail-call optimization realizes the constant space complexity. Passing and invoking the continuation parameter (e.g., the identity function) is used to program abnormal flows of control. If the continuation parameter is growing, then it is used to program the normal flow of control—albeit in a cluttered manner. In contrast, call/cc is primarily used for programming abnormal flows of control. For instance, the call/cc function can be used to unwind the stack in the case of exceptional values (e.g., a 0 in the list input to a product function; see the versions of product using call/cc in Sections 13.3.1 and 13.7.2). (Programming abnormal flows of control with first-class continuations in this manner can be easily confused with improving time complexity of a function by obviating the need to return through layers of pending computations on the stack in the case of a non-tail-recursive function.) Unlike with CPS, the continuation captured through call/cc is neither necessary nor helpful for programming normal control flow: If the function uses a tail call, it is already capable of being run in constant space; if the function is not tail recursive, then it must not run in constant space because the stack is truly needed to perform the computation of the function. In that case, the normal flow of control in the recursive call remains uncluttered—unlike in CPS. Table 13.15 summarizes the effects of these control techniques. Table 13.14 classifies some of the example functions presented in this chapter based on factors involved in these trade-offs.

Table 13.15 Effects of the Techniques Discussed in This Chapter

The CPS transformation and subsequent tail-call optimization applied to a program exhibiting recursive control behavior leads to a program exhibiting iterative control behavior that was both originally readable and writable (see the top-right quadrant of Figure 13.10). In other words, the CPS transformation (from recursive control behavior to iterative control behavior) maintains the natural reflection of the program code with the mathematical definition of the function.

First-class continuations, tail recursion, CPS, and tail-call optimization bring us more fully into the third layer of functional programming: More Efficient and Abstract Functional Programming (shown in Figure 5.10).