Introduction

Controlling programmable devices

The first programmable devices, street organs and Jacquard weaving looms, appeared in Europe during the 18^th century. Both were controlled by punched cards. The presence or absence of holes in the card determines which notes are played and which threads are selected. The cards are divided into lines that are executed sequentially, one after the other. As shown in figure 0.1, often the cards form a loop, with the end of the last card being affixed to the beginning of the first card, so that the musical tune or the visual pattern repeats indefinitely.

Figure 0.1: Jacquard control unit for a weaving loom, with its punched cards arranged in a loop. (CC BY-NC-SA, Heinz Nixdorf MuseumsForum.)

I like to think that the notions of sequence and loop in computer programming stem directly from this handling of punched cards in organs and looms. In any case, these two notions have played a crucial role in the modern computer — the programmable electronic calculator whose program is stored in memory — ever since its appearance in the mid-1940s. Even today, machine-code programs still consist of processor instructions stored in memory and executed sequentially, one after the other, except for branch or jump instructions, which cause execution to continue at a specified code address. (See figure 0.2 for an example.)

Figure 0.2: x86 machine code that computes Fibonacci numbers and sends them to output port 32. The flow of control is shown by the arrows on the left side. The jump at PC 15 to PC 10 creates an infinite loop.

Control in programming languages

The first programming languages (assembly languages, autocoders, Fortran I, …) expose a machine-style view of control: base instructions are executed sequentially; unconditional and conditional jumps, like the famous goto command, allow computations to be repeated or skipped. By the end of the 1950s, the limitations of this approach had become apparent, prompting subsequent programming languages, such as Algol 60 and its many descendants, to introduce higher-level control structures:

first, subroutines, procedures and functions, to decompose the code into medium-sized units that can be developed and understood independently;
then, structured control constructs such as conditionals (if-then-else), counted loops (for), and general loops (while), which can be freely nested and give rise to elegant language grammars;
later, other forms of non-local control such as coroutines, cooperative or concurrent threads, exceptions, objects, and actors, which emphasize the interleaving of control between separately written code components.

Meanwhile, other programming paradigms emerged, such as functional programming (Lisp, 1960) and logic programming (Prolog, 1972). These languages leave control mostly implicit: source code focuses on defining which values or predicates to compute, rather than how to compute them. However, control is still present in these languages, only under different forms: in the evaluation and resolution strategies used for program execution; and, in the case of functional languages, in their ability to represent control flows as function values called continuations, and to program their own custom control structures as library functions that manipulate continuations.

Studying programming languages from the standpoint of control

This book is a journey through the design space and historical time of programming languages, guided by the notions and paradigms of control. We will attempt to answer questions such as:

What language constructs are provided to programmers to express and constrain the sequencing of computations? How expressive are these constructs? How do they compare across languages?
What structure, organization and styles of source programs are enabled or encouraged by these language constructs? Is structured programming about eliminating goto statements or making source code the primary description of programs instead of flowcharts? Is declarative programming about leaving control decisions to the compiler, or about bringing programs closer to mathematical specifications?
What can programming language theory say about control? What are the connections between program logics and control structures? How does control fit into more general frameworks for effects such as type and effect systems, monads, and the theory of algebraic effects?

Our approach is mainly descriptive, often comparative, and sometimes formal, but never prescriptive. It spans the timeline from 1947, when the first assembly language was developed, to 2022, when effect handlers were first integrated into a mainstream programming language. It also spans the spectrum from programming examples to programming language theory.

Book outline

The remainder of this book is divided in four parts.

Part I: Control structures for imperative languages describes, compares, and shows the historical evolution of control structures for conventional imperative and object-oriented languages.

Chapter 1 starts with unstructured jumps and continues with structured conditionals and loops, possibly with early exits.
Chapter 2 recalls the structured programming movement of the late 1960s and discusses the goto elimination problem, i.e. the question of programming with structured control only.
Chapter 3 describes subroutines, procedures, and functions, which provide language support for code structuring and reuse. It also discusses their interactions with non-local jumps and exceptions.
Chapter 4 studies mechanisms for inverting or symmetrizing control between independent program fragments, such as iterators, generators, coroutines, and cooperative multithreading.

Part II: Control operators for functional languages is devoted to functional programming languages and their ability to manipulate control flows as data called continuations, which makes it possible to define custom control structures as libraries.

Chapter 5 introduces pure functional programming in several steps, starting with spreadsheets, and discusses evaluation strategies and operational semantics.
Chapter 6 presents continuations as they were initially introduced: as a semantic device to express denotational and operational semantics.
Chapter 7 shows that continuations are useful for functional programming as well, enabling programs written in continuation-passing style (CPS) to define advanced control structures such as exceptions, iterators, coroutines, and threads.
Chapter 8 describes control operators such as call-with-current-continuation in Scheme, which gives all functional programs (even those not written in CPS) the ability to capture and manipulate continuations.

Part III: From exceptions and monads to algebraic effects and handlers describes a recent development in the area of control operators for functional languages, effect handlers, and their underlying theory, algebraic effects.

Chapter 9 starts our journey to algebraic effects and handlers by formalizing exceptions and exception handling in the context of a functional language, and discussing solutions to the uncaught exception problem.
Chapter 10 describes effect handlers for user-defined effects, a type of control operator that combines aspects of exceptions and delimited continuations, as well as their integration in the OCaml language.
Chapter 11 discusses monads, which provide a generic account of the propagation and sequencing of effects, and are a popular way to incorporate effects into otherwise pure functional languages such as Haskell.
Chapter 12 describes the theory of algebraic effects and their handlers, which extends the theory of monads with a generic account of the generation and the handling of effects. This forms the basis for the effect handlers described in chapter 10.

Part IV: reasoning about control and effects shows how to establish safety and correctness properties about control and effects, using type systems and program logics.

Chapter 13 describes type systems for languages with effects: simple type systems that ensure data safety in the presence of advanced control structures, and richer type and effect systems that also ensure control safety and the absence of uncaught exceptions and unhandled effects.
Chapter 14 recalls Hoare logic, the first program logic for deductive verification, and shows how to extend it to the various control structures discussed in part I.
Chapter 15 discusses the difficulty of defining program logics for control operators in functional and imperative languages, and describes several recent approaches based on separation logic, an extension of Hoare logic that facilitates reasoning about resources.

How to read this book

Readers are assumed to be familiar with one imperative programming language, such as C, C++, Java or Python, and one functional programming language, such as Haskell, OCaml, Scheme or SML. The companion website XXX collects the code examples given in this book and provides instructions for executing them. The more technical chapters also assume some knowledge of programming language theory, which can be found in the electronic textbook Programming Languages Foundations (Pierce et al., 2025), for example.

There are several ways to read this book. Readers who are mainly interested in the comparison between programming languages and their historical evolution can focus on chapters 1 to 5 and 8 to 10. Those interested in functional programming and the its uses of continuations can skip part I and focus on chapters 5 to 10. Those who are familiar with some of this material but want to learn more about recent developments around algebraic effects can start at part III and focus on chapters 9 to 15. Finally, readers interested in programming language foundations and their use to support program verification will enjoy chapters 6, 8, and 11 to 15.

The level of technical difficulty does not increase linearly throughout the book. Rather, it increases within each part, and often within each chapter. Readers who find a passage too technical are encouraged to skip to the next chapter or even to the next part.