About This Book

This is an introduction to the concepts used to design programming languages — paradigms, scope, binding, types, evaluation — taught not by touring a handful of languages but by building one. Over the course of the book you implement an interpreter, in Rust, for a single language that grows from a calculator into a small multi-paradigm language named Bridger, with imperative, functional, and declarative features.

It grew out of an undergraduate programming-languages course, but it is written to stand on its own. If you read the chapters and build the interpreter as you go, you will learn the material and end up with a working language.

Why an interpreter?

There are two ways to give a programming language a precise meaning, and they lead to two different kinds of book.

• A compiler foregrounds translation: it turns your program into another language (machine code, bytecode, a lower-level IR) and cares deeply about code generation, optimization, and the constraints of the target machine.
• An interpreter foregrounds meaning: it says directly what a program is and does. You write down a rule like $e\Downarrow v$ (“expression $e$ evaluates to value $v$”), and the evaluator you build is that rule, made executable.

This book takes the semantics lens. That single choice explains most of what follows — including why we hand you a parser instead of making you write one: parsing is a translation problem that belongs to the compiler’s world, and a course on it already exists in most curricula. Here we start from the abstract syntax tree and spend our time on what programs mean. Code generation, optimization, and register allocation are real and important; they are simply a different book, and we point you to good ones where the boundary comes up.

Who this book is for

Anyone who wants to learn how programming languages work, with a practical flair. This text is designed to be self-contained: the concepts, the specifications, and the build are all here, and the scaffolding you build on top of is publicly available. It assumes you can program in some language and are curious about what is going on underneath — not that you already know Rust, type theory, or logic programming.

How the book is organized

The chapters follow the arc of the language as it grows, and each part from Part II onward closes with a project milestone (M1–M8). Treat the milestones as a learning structure: a checkpoint that says “build this much next, and here is how to know it works.” By the end you will have built:

• a tree-walking evaluator with clear runtime errors,
• lexical scope, and the closures that make it observable,
• first-class functions and closures,
• a static type checker that rules out whole classes of runtime errors before a program runs,
• a relational (Datalog-style) sublanguage you can query from ordinary code,
• algebraic data types with pattern matching, and
• objects built as structs with methods and traits.

Every chapter follows a similar narrative. Each chapter will broadly introduce the relevant programming-language concepts: what they are meant to capture, and the history of how they emerged and changed over time and across communities. It will then discuss how those concepts shape the design decisions underlying Bridger. Then the lens widens to the design space: how ML, Rust, Prolog, or Python answer the same questions, and the pros and cons of each design. Some of those questions Bridger answers by declining — negation in logic rules, full type inference, classical inheritance — and those forks get the same treatment, with pointers for reading further.

The starter repository

Because the book is meant to be self-contained, the scaffolding you build on top of ships publicly: the Value type, the environment structure, error and source-span types, the AST, and the parser. You implement semantics — the evaluator, the type checker, unification — not the memory plumbing that would otherwise have you fighting the borrow checker instead of learning what a closure is. The starter is the bridger-interpreter repository; its README covers setup, and each milestone says what to build next.

How to read this book

• Code you implement is shown in Rust. Where a snippet is self-contained you can press the play button to run it.

  fn main() {
      println!("Hello from the metalanguage.");
  }

  You do not need to know Rust first. Each construct is introduced where the interpreter first needs it (enum/match at the AST, Rc<RefCell> at closures, Result/Option at error handling), as a short aside you can skip if you’re already familiar with Rust. For those looking for a slightly more in-depth introduction, Appendix A is a self-contained tutorial with an M0 warm-up milestone.

• Programs in Bridger are shown in monospace:

  fn fib(n: Int) -> Int =
      if n < 2 { n } else { fib(n - 1) + fib(n - 2) };
  
  fn main() { println(fib(10)); }
  

• Specifications are written as inference rules. For example, addition evaluates its operands and adds the results:

  $$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2}{e_1+e_2\Downarrow v_1+v_2}(\text{E-Add})$$

  The notation reference collects the symbols and rule shapes we use.

A note on tools and AI assistants

Syntax is the part that varies. Every language spells the same idea differently, and the spelling changes with every release — which is exactly the kind of detail a coding assistant handles well. It handles semantics well too: ask one to explain closures or type inference and you will usually get a fluent and largely correct answer. The limit is not that these tools only know syntax.

The limit is accountability. An assistant can make a design decision; it cannot be answerable for one. Whether a problem wants a relation or a fold, what a representation choice will cost three modules later, which trade-off a language made and whether it was the right one for your system — those are judgments you own, and owning them means understanding the concepts well enough to evaluate an answer rather than accept it.

The test arrives when someone asks why a system is built the way it is. “The assistant did that” reports only that nobody decided; the engineer who can explain the reasoning understood the choice, whether or not an assistant helped reach it.

That is what this book is for: the concepts, where they came from, and the pros and cons that make one design fit where another fights. It is what you need in order to design and assess systems — including the ones you build with an assistant’s help.

Why Build an Interpreter?

A program, before anything runs it, is text. A file of characters that means nothing to the machine and — strictly speaking — nothing at all until something decides what it means. The field of programming languages focuses on that gap: between a string somebody typed and a behaviour they intended. Broadly speaking, there are two extremes for how that gap is closed: interpretation and compilation. Interpretation directly evaluates the program as written; compilation rewrites it into a different language (e.g., assembly or machine code) and runs that instead.

The shape of a language implementation

Nearly every language implementation, of every kind, begins the same way. The text is broken into tokens, and the tokens are assembled into a tree that reflects the program’s structure — an abstract syntax tree, or AST:

  source text
      │
      │   lexing — characters into tokens
      ▼
    tokens
      │
      │   parsing — tokens into structure
      ▼
     AST   ◄─── this book starts here
      │
      ├────────────►  evaluate it directly           (interpretation)
      │
      └────────────►  translate it into another      (compilation)
                      language, then run that

Everything above the AST is a translation problem: recovering structure from text. It is a well-understood and genuinely interesting body of work, and it is where a compilers course begins. This book starts at the AST and works down from there — on what the program means, and how to make a machine carry that meaning out.

Interpretation and compilation

A compiler turns your program into another program. The output might be machine code for a particular processor, bytecode for an abstract machine, or another high-level language entirely. The defining move is translation, and the compiler’s work is finished before your program ever runs. Its central concerns follow from that: which instruction sequences are efficient, how to allocate registers, which optimizations are safe.

An interpreter does not translate. It walks the program and carries out what the program says, directly. Ask it to evaluate 1 + 2 and it evaluates 1, evaluates 2, and adds them. Its central concern is not what instructions to emit but what each construct means.

That difference is why this book builds an interpreter. When you write the case that handles addition, you are not describing addition to a machine that will handle it later — you are writing down what addition is, in a form that runs. Specification and implementation become the same artifact. We will make this explicit in Program semantics, where the rule

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2}{e_1+e_2\Downarrow v_1+v_2}(\text{E-Add})$$

and the code implementing it turn out to be the same statement written twice.

It is worth being precise about what interpretation means, because it is broader than simply running a program. To interpret a piece of syntax is to map it to a mathematical object — its meaning. Which object depends on what you are interpreting it as. The expression 1 + 2 might mean the number 3. A function definition might mean an actual mathematical function, from arguments to results. A whole program might mean a map from inputs to outputs, or a set of possible behaviours. The evaluator you build in this book is the concrete case: the object is the value the expression produces when it runs.

But the domain is a choice, and coarser choices are useful. Interpret 1 + 2 as positive rather than as 3, and you have a program that reasons about signs without computing anything. Interpret it as Int, and you have a type checker. This is abstract interpretation — the same syntax-to-meaning mapping, aimed at a domain that deliberately forgets some detail so that questions can be answered without running the program. It is how a great deal of static analysis works, and it is exactly what the type checker in Part VI does: interpret every expression as a type rather than as a value, and reject the program if the types do not fit. The evaluator and the type checker are two interpretations of the same syntax, over different domains.

This is not a modern observation. When John McCarthy published the definition of Lisp in 1960, it included a function called eval — a Lisp program describing how to evaluate Lisp programs. He intended it as a theoretical device, written to show that Lisp was tidier than a universal Turing machine; by his own account the notation behind it was devised “with no thought that it would be used to express LISP programs in practice.” Then S. R. Russell noticed that eval could serve as an interpreter, hand-coded it, and Lisp had an interpreter nobody had set out to write. The definition was the implementation. This book leans on that same fact throughout.

A spectrum of implementations

The two branches above are a useful simplification, and like most useful simplifications it is false at the edges. Real implementations mix strategies freely:

• A tree-walking interpreter evaluates the AST directly, node by node. The simplest design, the easiest to read, the slowest to run, and the subject of this book.
• A bytecode interpreter first compiles the AST into a compact instruction set for an abstract machine, then interprets those instructions. CPython works this way: your source is compiled to bytecode, and a virtual machine executes it.
• A just-in-time compiler begins by interpreting, watches which code runs hot, and compiles those parts to native code while the program is still running. The JVM and JavaScript engines such as V8 both do this, with an interpreter and one or more optimizing compilers cooperating at run time.
• An ahead-of-time compiler translates the whole program to native code before it runs and ships the result. This is what gcc, clang, and rustc do.

So “is Java compiled or interpreted?” has no clean answer. javac compiles source to bytecode, a virtual machine interprets that bytecode, and a JIT compiler translates the frequently executed parts to machine code during execution — all three in one system. The honest description is that implementations sit somewhere on a spectrum from decide everything before running to decide everything while running, and the interesting ones occupy several points at once.

The tree-walking end of that spectrum is where meaning is most visible, because nothing has been translated away yet. Moving along the spectrum gains speed by moving toward the machine: bytecode and native code run fast because they are closer to what the hardware already knows how to do. That translation discards the program’s original structure and intent: a loop becomes a jump, a function becomes an address, a type vanishes once it has been checked. Those high-level structures — and what they were meant to express — are precisely this book’s subject. So we work at the end of the spectrum where they are still intact.

What you will build

Over the following parts you will build a tree-walking interpreter for Bridger, a language that starts out able to add two numbers and ends up with closures, a static type checker, algebraic data types, objects, and a relational sublanguage.

The interpreter will be slow — meaningfully slower than any production implementation, because walking a tree re-examines the program’s structure at every step. It will also be legible: small enough to read straight through and hold in your head, with every language feature and programming language concept corresponding to a piece of code you can point at.

Performance returns in Cost semantics, where we measure programs by counting evaluation steps rather than seconds — a measure that says something about your algorithm that a stopwatch obscures.

Further reading

Lisp, and the interpreter nobody set out to write: John McCarthy’s “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I” (1960) defines Lisp, eval included. His “History of Lisp”, a 1979 Stanford Artificial Intelligence Laboratory draft, is his own account of the period, including the moment itself: “S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter.”

Abstract interpretation: Patrick Cousot and Radhia Cousot’s “Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints” (1977) is the paper that made abstract interpretation a theory rather than a collection of tricks. It sets up the lattices, the abstraction and concretization maps, and the fixpoint construction that the sign and type examples above only sketch. The argument is carried almost entirely in the algebra, and it assumes you are comfortable with partial orders and least fixpoints. Xavier Rival and Kwangkeun Yi’s Introduction to Static Analysis: An Abstract Interpretation Perspective (MIT Press, 2020) covers the same ground at book length, starting from example analyses.

The compiling end of the spectrum: Aho, Lam, Sethi, and Ullman’s Compilers: Principles, Techniques, and Tools, 2nd ed. (2006) — the “Dragon Book” — works through the pipeline this book starts in the middle of: lexing, parsing, semantic analysis, intermediate representations, optimization, and code generation. John Aycock’s “A Brief History of Just-In-Time” (2003) traces how interpretation and compilation stopped being alternatives and began cooperating inside a single system, from Smalltalk-80 onward. For the current shape of a production pipeline, V8’s own accounts of Ignition and TurboFan and of the later Sparkplug baseline compiler describe a JIT with several tiers.

Building one yourself: Robert Nystrom’s Crafting Interpreters (2021) builds the same language twice, once as a tree-walker and once as a bytecode virtual machine — the same program at two points on the spectrum described above.

Concept checks

From Machine Code to High-Level Languages

A program today is written in a high-level language and reaches the processor through a stack of abstractions: libraries, a compiler or an interpreter, an instruction set, and a microarchitecture underneath that. Every one of those layers was put there by somebody, for a reason, and often over somebody else’s objection.

These abstractions have not always existed. The earliest stored-program machines were programmed by putting bits into the store directly. On the Manchester Baby, in June 1948, that meant stepping through the store word by word and setting each bit to 0 or 1 on a device of 32 buttons and switches: the first program to run there was seventeen instructions long and written one bit at a time.

Those bits formed a language. They were broken up into words, each corresponding to a single instruction, which the machine read and executed one by one. Every word had a fixed shape, each part of that shape meant something, and the machine combined those meanings by fixed rules — a vocabulary and a grammar.

What makes this language of bits low-level is that its vocabulary is the machine’s own. The only thing a word can say is that the hardware should carry out one of its operations, and a program is a sequence of such words — so there is no shortage of computations you can express in it. What has nowhere to go is everything you understand about the program besides the operations themselves. That these twelve words are a routine for computing a square root; that location 90 holds a running total; that this jump is the one closing a loop; that the words further down are data rather than instructions — none of it is recorded in the store, because the notation has nothing to record it with. It lived in pencil annotations on the paper beside the machine, and in the programmer’s memory. The rest of this chapter explores how languages evolved to move more of that intent into the program itself.

Consider one of the earliest machines to make such a move. The EDSAC ran at Cambridge from May 1949. The EDSAC took about 1.5 milliseconds to execute an order (approximately 650 orders a second). On the first morning the EDSAC was running, it took two minutes and thirty-five seconds to compute and print a table of the first 100 perfect squares (0 to 9801).

The EDSAC’s store held words consisting of 17 bits. An instruction — an order, in the vocabulary of the time — occupied exactly one such word, divided into four fields:

      5 bits      1        10 bits       1
   ┌───────────┬───────┬──────────────┬────────┐
   │  function │ spare │   address    │ length │
   └───────────┴───────┴──────────────┴────────┘

Here is an example of one such order as a sequence of 17 bits:

   1 1 1 0 0    0    0 0 0 1 0 1 1 0 1 0    0
   ─────────    ─    ───────────────────    ─
    function  spare         address       length

Function 11100, address 0001011010 — 90 in decimal — and a length bit of 0. The order instructs the machine to add the number held in location 90 to the accumulator. While this is how orders are represented and understood by the machine, it is not how one wrote programs for EDSAC. A programmer would write a sequence of characters representing the orders to be executed onto a paper tape that EDSAC read into its store and then ran. Below is an example program that represents a small routine that divides by repeated subtraction, leaving the remainder in location 92. The left-hand column depicts where the order is stored, the middle column is the sequence of characters that encode the order, and the right column describes what the order does.

 store     order      description
   56      A 90 F     add the number in location 90 into the accumulator
   57      S 91 F     subtract the number in location 91 from the accumulator
   58      E 57 F     if the accumulator is positive, continue at location 57
   59      T 92 F     store the accumulator into location 92 and clear it

While the above structured representation is helpful to understanding the procedure, the actual program written to the paper tape didn’t contain the store location of instructions, the description or any white space. The tape would simply read A90FS91FE57FT92F and then relied on being loaded into the store from location 56 onward.

The description in that third column, and everything else a reader would need, sat outside the tape entirely. What a routine was for lived on its manuscript — a separate sheet, written out by hand, setting out the same orders with commentary beside them. Even the program’s name was kept outside the program: the practice was to write it on the tape in pencil.

The gap between the bits in the store and the characters on the tape is smaller than it appears. A paper tape records characters as five-bit teleprinter codes, and an order’s function field is five bits wide — so the order code was numbered to make the two coincide. 11100 is at once the function code for add and the teleprinter code for the letter A; 01100 is both subtract and the letter S. The letter punched on the tape was the function field, already in binary, with nothing to convert. As Martin Campbell-Kelly writes in his Tutorial Guide to the EDSAC Simulator, this “simplified the translation of the symbolic program considerably.” It is an early instance of hardware being shaped around the convenience of programming: the order code was numbered to suit the notation a person would write on the tape.

The addresses got no such help, and that is where the difficulty lived. 90, 91, 92, and 57 are absolute store locations, fixed at the moment the routine was written. Suppose you now need one more order between the ones at 57 and 58. Everything below the insertion shifts down a word: the two remaining orders move to 59 and 60, and the three numbers this routine works on, held after the program, move to 91, 92, and 93. So A 90 F, S 91 F, and T 92 F must each have their address increased by one, by hand, in the listing. The jump E 57 F points backward, to a location before the insertion, and must be left exactly as it is.

Note which orders those were. The branch is the one you would think to check, and it is the one that turns out to be fine; the arithmetic orders are what broke, because the data moved even though nothing about the arithmetic changed. That is the whole difficulty in one observation, and it is the documented reason the machine’s loading program was rewritten within months of its first run. In Campbell-Kelly’s account, addresses “had to be coded in absolute form: this meant, for example, that if an extra instruction had to be inserted in a program then the addresses in many of the branch instructions would need to be altered. This made program debugging very tedious.”

And the store itself records none of the distinctions you are relying on. An order is a 17-bit word; so is a number. Which words in the store are instructions is settled by which of them the machine is told to execute, and nothing marks a word one way or the other — which was not merely a theoretical point, because the EDSAC had no index registers. To walk along an array in a loop, a program had to reach into its own orders and increment the address field, treating an instruction as arithmetic data because that was the only way to do it.

From here on, each development moves some piece of bookkeeping off the programmer and into the machine, the program, or the notation itself: where an order sits in the store, which routine performs a standard task, which instructions compute an expression, which declaration a name refers to. Each was also resisted by the programmers who had been doing that bookkeeping by hand, for reasons that were generally sound at the time.

Names for places

The EDSAC’s order code had already made the operation symbolic. The next step was to do the same for the address: let a program work out where things ended up, so that a person does not have to.

The machine’s earliest loading program, the initial orders of spring 1949, read the tape and placed orders in the store, converting decimal addresses to binary. It lasted about three months before its limitations — the absolute addresses above, and the difficulty of keeping a library of subroutines when nothing could be moved — became intolerable. Wilkes handed the problem to David Wheeler, then a research student, with the constraint that the replacement fit in 42 orders. Wheeler’s Initial Orders 2, in service by September 1949, is what Campbell-Kelly calls “the forerunner of the modern assembler,” and was celebrated at the time as “the leading example of programming virtuosity.”

Initial Orders 2 introduced named locations. Fifteen words of store, locations 41 to 55, are each named by a letter, and every order on the tape ends with one of those letters. As an order is loaded, the value held in the named location is added to it, and the sum is what goes into the store. This is why programs are loaded from location 56 onward: the fifteen names sit immediately below.

Three of the names have a fixed convention. F names a location holding the constant value 0, so an order ending in F is stored exactly as written. D names a location holding the constant value 1, so an order ending in D is stored with its length bit set, which denotes its operand as long. θ names a location holding the origin of the routine currently being loaded, set by a directive at the head of each routine. When used, θ makes the address bits of an order relative to the routine’s start rather than absolute.

  the tape says          loaded at 56          loaded at 200
     A 5 θ          →       A 61          or       A 205

This allows one to write a program and have it be correct no matter which location the program is written to. This is relocation, and it is what makes writing a subroutine library possible: a routine can be written once, by someone with no idea which program will use it or what else will be in the store, and can be stored in any available region of the store.

In addition to the three above names, there are twelve names that by convention can be set by the programmer before a subroutine is written to the store and used to denote a region of store locations. For example, a programmer might use the name M to hold the location 90 (where they want to store their program’s data) and then use M within their program to access data elements without worrying where exactly that region of data lives within the store. Using these named locations, we can rewrite the division routine from earlier as follows:

 order       description
 A 0 M       add the number at M+0 into the accumulator
 S 1 M       subtract the number at M+1 from the accumulator
 E 1 θ       if the accumulator is positive, continue at θ+1
 T 2 M       store the accumulator at M+2 and clear it

No absolute location appears anywhere in it. The branch says back to the second order of this routine rather than back to 57; the operands say the first three words of my data rather than 90, 91, and 92. The routine can now be loaded anywhere. Its data can be moved by changing the one value held for M, and the arithmetic orders that broke in the earlier version — the ones that broke because the data had moved rather than because the arithmetic had changed — need no editing at all.

Branches within a routine are not covered. Insert an order ahead of the target and E 1 θ must still become E 2 θ by hand: the position is relative to the routine, but it is still a position. Code letters removed the surprising half of the problem and left the half a programmer would think to check. Removing the rest takes names for the positions themselves — labels, as every assembler since has had — which the EDSAC never acquired.

The same idea was arriving elsewhere. Kathleen Britten and Andrew Booth’s 1947 report Coding for A.R.C., written for the relay machine they had built at Birkbeck College, is among the earliest documented descriptions of a symbolic notation for a machine’s orders together with the program that translated it. Wilkes, Wheeler, and Gill’s 1951 account of the Cambridge system is both the first programming textbook and the first published description of a library of reusable subroutines.

What this step leaves alone is as important as what it changes. One order on the tape is still one order in the store. The program says, in sequence, what the machine is to do, and a programmer reading it can still predict every instruction that will execute. That correspondence is why the objections to this step were mild, and why the objections to the next one were not.

Automatic programming, and the first serious objection

The abstraction so far has been about where: a code letter stands for a location and the loader works out the number, though a programmer still writes every order that runs. The next step abstracts what. If a loading program can place a subroutine and fix up its addresses, it can also be asked for one by name — write take a square root, and the routine computing it is supplied and fitted in. From here a program is assembled out of routines, and which orders carry them out is settled by the program doing the loading. In 1952 Grace Hopper described a system doing exactly that — the A-0, running on the UNIVAC — in a paper called “The Education of a Computer”. The argument she makes there is about where the labour goes:

This situation remains static until the novelty of inventing programs wears off and degenerates into the dull labor of writing and checking programs. This duty now looms as an imposition on the human brain. Also, with the computer paid for, the cost of programming and the time consumed, comes to the notice of vice-presidents and project directors.

Her conclusion is that the programmer, handed a catalogue of subroutines, “may return to being a mathematician” and “does not even need to know the particular instruction code used by the computer.” The machine assembles the program; the person states the problem.

The objection to this was immediate, widespread, and for the time correct. Writing about the same period, John Backus is blunt about how the systems actually performed: “All of the early ‘automatic programming’ systems were costly to use, since they slowed the machine down by a factor of five or ten.” A factor of five is not a rounding error on a machine whose time is billed by the hour. And the people objecting were not being territorial. Backus’s own summary claims that these positions were justified:

Before 1954 almost all programming was done in machine language or assembly language. Programmers rightly regarded their work as a complex, creative art that required human inventiveness to produce an efficient program.

From that viewpoint, it was efficiency in particular that looked impossible to automate:

Experience with slow “automatic programming” systems, plus their own experience with the problems of organizing loops and address modification, had convinced programmers that efficient programming was something that could not be automated.

Both halves of the debate were grounded in daily experience. The “address modification” mentioned is the problem from earlier in this chapter — a loop over an array rewriting its own orders — and Backus lists the lack of index registers first among the difficulties the computers of that era created. The objection came from people who had been doing that work by hand for years.

So there were two true statements in circulation. Automatic programming produced programs several times slower than a competent person would write. And, as Backus notes elsewhere in the same paper, the cost of the programmers at a computing centre was “usually at least as great as the cost of the computer itself,” with programming and debugging accounting for as much as three quarters of the cost of operating one. Both facts are correct. The disagreement was over which cost dominated, which is an empirical question about the state of the world. As machines got cheaper, programs got larger, and translators got better, the answer moved towards supporting the abstraction Hopper argued for.

Expressions

Fortran began at IBM in 1954, and its name is a contraction of “FORmula TRANslating System.” Backus had proposed the project in a letter to his manager in late 1953, giving the cost of programmers as one of his prime motivations. What it let a program state was a formula:

A + B * C

In the EDSAC orders earlier in this chapter, the sequence of orders is the order of operations: the programmer decides that the multiplication happens before the addition, finds a location to keep the product in until the addition needs it, and writes the orders that carry that out. The line above sequences nothing. It records which operations combine which values, and the translator derives a sequence from it. For an array element such as A(I,J) it also generates the arithmetic that turns two subscripts into the single address an instruction can name. Each of those had been done by hand, in a notebook, and redone after every edit.

The Fortran team understood the objections they were up against, and organized the entire project around answering them rather than around the language. Backus, looking back in 1978:

It was our belief that if FORTRAN, during its first months, were to translate any reasonable “scientific” source program into an object program only half as fast as its hand coded counterpart, then acceptance of our system would be in serious danger. This belief caused us to regard the design of the translator as the real challenge, not the simple task of designing the language.

While the above quote noted that half speed was the point of expected failure, the target for acceptance was much higher: Backus writes that a system of this kind would be widely used only if it could be shown to produce programs “almost as efficient as hand coded ones” and to do so “on virtually every job.” Fortran shipped in 1957 with an optimizing compiler because that target was far beyond anything an automatic system had reached; the earlier ones ran five to ten times slower than hand coding.

The earlier systems’ slowdown had gone mostly into floating-point subroutines, which let those systems get away with crude housekeeping: simulated indexing and loop control cost far less time than the floating-point arithmetic they surrounded. The IBM 704 incorporated hardware instructions for floating-point operations and indexing, speeding the arithmetic up by a factor of ten and, in Backus’s phrase, “leaving inefficiencies nowhere to hide.” The largest component of the old slowdown was gone, and the bookkeeping left over — loops, tests, subscript arithmetic — was now a visible share of the program’s running time.

Generating good code for the 704 was the hard problem, and designing the language looked like the simple part in 1954. The rest of this book is a record of how much was hiding in language design — scope, binding, types, evaluation order, and what a function even is. Backus, writing in 1978, still held that the priority had been the right one: had they failed to produce efficient programs, “the widespread use of languages like FORTRAN would have been seriously delayed.” Later languages could afford to sit further from the instruction set, and to give up more against hand-optimized code, because a translator had already been shown to close that gap.

Fortran I did what it set out to do, and it did it for one machine: the compiler turned formulas into IBM 704 instructions. However, the formulas that programmers wrote (e.g., A + B * C) were just arithmetic expressions; which instructions computed them was left to the translator. This is what later made it possible to run the same program on a different machine, and it is what this book relies on when it asks what a construct means separately from how it runs.

Structure

Algol 60 arrives at the start of the next decade. The abstractions so far had mechanized the bookkeeping that programmers were already doing. Algol 60 introduced ideas about programs that had no counterpart in machine code, in assembly, or in Fortran I. Hoare, in “Hints on Programming Language Design” thirteen years after the ALGOL 60 report and with no particular reason for flattery, wrote:

The more I ponder the principles of language design, and the techniques which put them into practice, the more is my amazement and admiration of ALGOL 60. Here is a language so far ahead of its time, that it was not only an improvement on its predecessors, but also on nearly all its successors.

Algol’s practical reach was narrower than Fortran’s — scientific and industrial computing ran on Fortran for decades — but the report’s influence on how languages are described and designed is hard to overstate.

Algol 60 introduced block structure: a program has nested regions, and a name declared inside a region means something there and not outside it. On the EDSAC, location 90 was location 90 for the whole run; a code letter held one value at a time, for whoever was loading. There was no notion of a name having a region of validity, because there was nothing for such a region to be made of. Block structure made “where does this name refer to?” a question with a principled answer, determined by the program’s own shape. Part III of this book is spent on that answer and on what it takes to implement it.

The Algol 60 report specified the language’s syntax in a formal notation — what is now called Backus–Naur Form (BNF) — rather than in prose and examples alone. Syntax and semantics picks this up directly; for now the relevant point is that it became possible to ask whether a program belonged to the language, and the answer did not depend on any particular compiler. Algol 60 was defined by an international committee, in a report, before there was a compiler for it. That inverted the previous arrangement, under which a language was whatever the translator happened to accept and the manual described that translator’s behaviour. Once the definition is the document, several implementations can exist and be compared against it, and the question “is this a compiler bug or a program bug?” becomes answerable.

What does it mean to be “high-level”?

The label “high-level” has moved at every step in the history this chapter describes and has not stopped since. Assembly was the automatic programming of 1950 and became the baseline against which Fortran was accused of inefficiency. C was classed among the high-level languages when it took shape in 1972, though Kernighan and Ritchie hedged even then: The C Programming Language (1978) calls it “a relatively ‘low level’ language.” Today the hedge is gone; C is simply a low-level language, and not much about C itself has changed.

The reason is that “high-level” measures a distance from the machine, and both ends of that measurement move: the languages rise, and the machine itself becomes an abstraction. A modern processor’s instruction set is an interface over a microarchitecture that pipelines and reorders instructions, renames registers, predicts branches and speculates past them, and — on a multiprocessor — allows one core to observe another’s writes in an order the program never wrote. Even hand-written assembly no longer says what will physically happen, let alone in what order another core will see it happen. The bottom of the stack is a moving target too.

Which suggests that “how high-level is this language?” is a weaker question than the two it usually stands in for:

• What does this notation let me stop saying? Every step above answers this concretely: addresses, instruction selection, temporaries and evaluation order, the region in which a name is valid.
• What does the language now decide on my behalf, and can I predict what it will decide?

The second question is where every objection in this chapter lived. “It will be five times slower” and “efficient programming cannot be automated” are both versions of I can no longer predict what the machine will do, which in 1954 was the same worry: what the translator decided was exactly which instructions ran. That concern never went away, and it should not: it has only changed granularity. Whether a line allocates, whether a loop will vectorize, when the collector will stop the program, what an optimizing compiler is permitted to assume, which language to write a kernel in — each is the same question asked about a taller stack. What changes is the answer, and the answer depends on facts about hardware, program size, and what people’s time is worth.

How language features come to be

Every abstraction built in the rest of this book arrived by the route just described. Scope, static types, first-class functions, pattern matching, automatic memory management: each was once a proposal that someone had to argue for, against people who could point at a real cost and were not wrong to. By the time an idea reaches a textbook it looks as if it were inevitable, and that appearance hides both how the idea came about and what the alternatives to it were.

When this book introduces a concept, it starts where the concept started: with the problem it solves, the objections raised against it, and the different answers other languages settled on, many of them still in use. Appendix F lays the same material out in date order, for readers who want the arc in one place.

Further reading

Before there were languages: Williams and Kilburn’s letter “Electronic Digital Computers” (Nature, 25 September 1948) runs a few hundred words and announces that a machine in Manchester had been running stored programs for some weeks. That machine is the Manchester Baby, which opens this chapter, and the letter is the first public notice that a program held in a machine’s own memory had actually run. For the machine in detail, including the input device and the surviving text of the first program, see Simon Lavington, A History of Manchester Computers, 2nd ed. (British Computer Society, 1998), and the University of Manchester’s Computer 50 archive. Kathleen Britten and Andrew Booth’s Coding for A.R.C. (1947) is an early written account of a symbolic notation for a machine’s orders and the program that translated it; Britten — later Kathleen Booth — wrote it as a research assistant at Birkbeck College. It is frequently called the first assembly language.

Programming the EDSAC: Cambridge’s EDSAC collection holds the machine’s order code and its operating log, kept by chief engineer W. S. Renwick and transcribed by David Wheeler; the entry for 6 May 1949 reads in full: “Machine in operation for first time. Printed table of squares (0-99), time for programme 2 mins. 35 secs. Four tanks of battery 1 in operation.” Wilkes, Wheeler, and Gill’s The Preparation of Programs for an Electronic Digital Computer (1951) is the first programming textbook and the first published description of a subroutine library: its second half catalogues the EDSAC library subroutines by category, Chapter 7 works through five complete programs, and Chapter 8, “Automatic Programming,” covers assembly, floating addresses, and formula recognition — in 1951. Martin Campbell-Kelly’s Tutorial Guide to the EDSAC Simulator (EDSAC Replica Project, The National Museum of Computing) is the source of the order code and instruction format described above, and comes with a simulator that runs the historical programs and any you write yourself.

Automatic programming and its critics: Grace Hopper’s “The Education of a Computer” (1952) makes the case for automatic programming, argued from the economics of programmer time rather than from elegance. Backus’s “The History of Fortran I, II, and III” (1978, delivered at the first of the HOPL conferences below) records what the objectors said and why they were not being foolish; its opening sections on attitudes toward “automatic programming” and on the economics of programming in the early 1950s are the best short account of why this was a real dispute. For the system as its authors presented it at the time, before it had a history, see “The FORTRAN Automatic Coding System” (1957).

Defining a language: Naur’s “Report on the Algorithmic Language ALGOL 60” (1960) is short and still readable — skim §1 to see a language’s syntax being specified formally for the first time. Hoare’s “Hints on Programming Language Design” (1973) is design advice from the era when designing the language had stopped looking like the simple part, and the annotated reading list in its appendix is a short opinionated bibliography of the field as it stood then.

Designers on their own work, and surveys: Dennis Ritchie’s “The Development of the C Language” (1993) traces C to its BCPL and B lineage and to the PDP-11, a designer describing decisions rather than defending them. It appeared at the second of the History of Programming Languages conferences, whose proceedings — HOPL I (1978), HOPL II (1993), HOPL III (2007), and HOPL IV (2021) — are the standard place to find designers writing the history of their own languages, with the partiality that implies and the detail nobody else could supply. For a survey of the whole field rather than a single language, Jean Sammet’s Programming Languages: History and Fundamentals (Prentice-Hall, 1969) covers more than a hundred languages while most of them were still in use, and records what the field thought it was doing before anyone knew which lines would matter. Donald Knuth and Luis Trabb Pardo’s “The Early Development of Programming Languages” — Encyclopedia of Computer Science and Technology, vol. 7 (1977): 419–493, reprinted in Knuth’s Selected Papers on Computer Languages (CSLI, 2003) — is a systematic survey of the pre-Fortran systems this chapter compresses into a paragraph, including several that were ahead of anything described here but left no descendants.

Concept checks

The Paradigm Branches

The previous chapter followed a single idea of what a program is. Machine code gave way to assembly, assembly to Fortran and Algol, and each step handed more bookkeeping to the translator — addresses, instruction selection, the region in which a name is valid. What none of those steps touched was the idea underneath: a program is a sequence of commands that change the machine’s state, one after another. Fortran raised the level of the commands and Algol organized them into blocks, but a program was still a list of commands to modify the machine’s store.

That idea is an answer to a question the languages in that chapter never stopped to ask, because the machine answered it for them. The question is: what is a program? The store-and-command picture is one answer, and it is the machine’s own answer, lifted through levels of abstraction; however, there are other notions of what a program is. These notions differ from the store-and-command notion, and from each other, not in how their programs are spelled but in what they take a program to be. This chapter lays out the main answers and the communities that gave them, and marks which part of the book describes each one.

What does it mean to be a program?

The word paradigm entered programming through Robert Floyd’s 1978 Turing Award lecture, which borrowed it from Thomas Kuhn’s account of how a scientific field settles on a shared way of framing its problems. A programming paradigm is that: a shared idea of what a program is and how you go about writing one. Four such ideas organize most of the languages in use, and each can be stated as an answer to what is a program?

A sequence of commands. A program is a list of instructions that read and change a shared, mutable state, carried out in order. This is the imperative view of what a program is. This view derives from the machine’s model of a program, often abstracted to higher-level notation: assigning to a variable, looping, iterating through an array. Each of these operations is about doing something to the state of the program that persists between each step of the program.

Consider the following task: given a set of directed edges and a starting node, which nodes can be reached? Below is an imperative program that accomplishes this task. The program works by keeping two pieces of state: a set of nodes already visited, and a frontier of reached nodes whose outgoing edges it has not yet examined.

visited  = { start }
frontier = [ start ]
while frontier is not empty:
    n = frontier.pop()
    for each edge (n, m):
        if m not in visited:
            visited.add(m)
            frontier.push(m)
return visited

Both visited and frontier hold only the start node in the beginning. Each pass through the loop takes a node off the frontier, looks at every edge leaving it, and for each target it has not seen before adds that target to the visited set and pushes it onto the frontier to examine later. When the frontier is empty, every reachable node has been visited, and visited is the set of nodes reachable from start.

The application of functions to values. A program is an expression, and running it means evaluating that expression to a value. There is no store being modified in the background; a name stands for a value and is not modified. This is the functional view of programming. Its origins predate any computer, in Alonzo Church’s λ-calculus of the 1930s, a formalism in which everything is a function and computation is substitution. John McCarthy’s Lisp, whose eval we discussed previously, was the first functional language, borrowing Church’s notation for functions if not the whole calculus. Where the imperative program says do this, and update that, the functional program says the answer is this expression, and leaves the order of evaluation as a detail.

Below is a functional program for the same graph reachability task. It names the reachable set as the result of growing a set of reached nodes one edge-step at a time, until a step adds nothing more:

step(seen) = seen ∪ { m | n ∈ seen and (n, m) is an edge }

grow(seen) = if step(seen) = seen then seen else grow(step(seen))

grow({ start })

The function step takes a set of nodes reached within n steps and returns a new set with every node reached within n+1 steps, without modifying the input set. The function grow repeatedly applies step until the set of seen nodes has reached a fixed point (the same before and after applying the step function). That stable set of nodes is the answer; it is obtained by evaluating an expression rather than accumulated by a loop that updates the set of seen nodes.

A set of facts and rules. A program states what is true — these edges exist; a path exists when an edge does, or when a path reaches an edge — and running it means asking what else must be true and letting the system work it out. Nothing in the program says how to search. This is the declarative, or logic, view of programming. It grew out of automated theorem proving in the early 1970s, when Robert Kowalski argued that a piece of logic could be viewed as a program and Alain Colmerauer’s group in Marseille built Prolog around that view. Bridger’s relational sublanguage takes the same idea in a smaller, always-terminating form.

Below we show how the graph reachability task is encoded as a declarative program. The program itself prescribes no search mechanism; the two clauses state what it means to be reachable from the start node, and finding the nodes that satisfy the clauses is the system’s job:

reach(start).
reach(Y) :- reach(X), edge(X, Y).

The first clause says the start node is reachable. The second says that if X is reachable and there is an edge from X to Y, then Y must also be reachable. Nothing names a node to visit first, and no set is maintained; the program stores no state and describes no procedure. When one asks which nodes are reachable, the system returns the smallest collection of facts that makes both clauses true.

A society of objects exchanging messages. A program is a collection of objects, each holding some private state and knowing how to respond to requests; computation happens as they send messages to one another. This is the object-oriented view of programming. It appeared in Simula 67, built by Ole-Johan Dahl and Kristen Nygaard to describe simulations in which each entity carries its own state, and was made central by Alan Kay and the Smalltalk group, for whom the messages between objects mattered more than the objects themselves.

Recall the graph reachability task. In the object-oriented program below, the graph becomes a collection of node objects, each holding its own list of neighbors, and the search happens as the nodes send one another a reach message:

class Node:
    neighbors                     # the nodes this one points to

    method reach(visited):
        if self ∈ visited: return
        visited.add(self)
        for each n in neighbors:
            n.reach(visited)      # send the same message onward

start.reach({ })

Each node, on receiving reach, records itself in the shared visited set and then sends the same message to each of its neighbors, which do the same. The visited set both collects the answer and keeps a node from responding twice, so a cycle does not loop forever. The traversal is the imperative one from before, redistributed: no central loop drives it, and the work is carried by objects passing a message along the edges.

What differentiates paradigms

While many imperative programs share similar syntactic forms — and similarly for functional, object-oriented, and declarative programs — the form of a program does not dictate which paradigm it belongs to. The declarative reachability rules could be written in a C-like block syntax, or the imperative worklist algorithm above in Lisp-style s-expressions, without either changing paradigm. What decides the paradigm is what a language treats as primitive and free, and therefore what it lets you leave unsaid.

The imperative program leans on a mutable store as something that is simply there: a variable is a box you can overwrite, and overwriting it costs nothing to express. The functional program has no such box — a name binds to a value and the binding does not change — so anything resembling a running change must be expressed some other way, by producing a new value rather than editing an old one. The declarative program treats search as free: it never says how the answer is found, because supplying the how is the system’s job, not the programmer’s. What one paradigm makes implicit, another makes you spell out.

A consequence is that the paradigm is not a property of a language’s grammar, and one language can host more than one. A programmer can write in a functional style inside an imperative language by refusing to mutate and building with recursion and functions that take other functions as arguments; a programmer can write imperative code inside a functional language wherever it provides a way to. The paradigm a program belongs to is the set of defaults it works with — what it treats as primitive and what it leaves implicit — and a language belongs to a paradigm by making one set of those defaults cheap and the others deliberate.

This is why paradigm fit is something a working programmer can feel. Reachability written imperatively carries a visited set and a worklist that are bookkeeping, present only to drive the search; the same problem written as rules has neither. On the other hand, for a task like a running total over a stream of inputs, or an in-place simulation that updates a grid each tick, the imperative version is succinct, while the declarative framing strains to express a process that is inherently about change over time. The awkwardness comes not from the program being wrong, but from the problem not fitting the strengths of the paradigm it is expressed in.

Multi-paradigm languages

While this chapter names four paradigms, most programming languages let programmers express programs across two or more of the paradigms. Lisp, a typical example of a functional language, had an assignment operator early and has allowed programs with mutable state ever since. In Smalltalk, each method of an object has an imperative body. Most languages a reader is likely to know support multiple paradigms: Python has objects, first-class functions, and imperative loops all at once; Rust, the language this book asks you to write the Bridger interpreter in, has all three as well, and a type discipline over them. Peter Van Roy’s survey of the field catalogues on the order of thirty paradigms once combinations are counted. This is a sign that the paradigms are overlapping views of a program rather than distinct ones: a paradigm is really about the decisions a language makes about what it supports and makes freely available to the programmer.

A paradigm, then, is a language’s center of gravity — the framing it makes cheapest and treats as primitive — and not a strict inability to write programs in a different paradigm. Floyd’s lecture already pointed this way: he treated paradigms as techniques a programmer should collect and move between as the problem demands, rather than allegiances to hold. The taxonomy is worth having for exactly the reason it is worth distrusting: it names real differences in what a language makes easy, while most real languages support multiple paradigms with varying ease.

Bridger’s philosophy

Bridger is built to be multi-paradigm, so every part of this book adds to one language rather than touring several. Keeping the comparison inside a single language is what makes it clean: with one syntax, one evaluator, and one notion of a value, a difference you see between two programs is a difference in the idea rather than an artifact of four separate syntaxes, toolchains, and libraries. One language also lets a single program cross paradigms — building a structure imperatively, querying it relationally, folding the results functionally — which is where the trade-offs stop being abstract. And with every framing within reach, you can feel which one a problem wants: you reach for the one that makes the problem short, and notice when a framing fights you.

The core is imperative and functional together: an expression-oriented language, in which even a loop or an assignment produces a value, with first-class functions and closures on one side and mutable references on the other. Onto that core the book adds a static type discipline, a Datalog-style relational sublanguage for the declarative framing, algebraic data types for modeling structured data, and objects assembled from those data types with methods. Each is introduced where the book reaches it, motivated by the problem it answers and set against the alternatives other languages chose.

Looking ahead

The branches named here are built in the order that lets each rest on the last.

• The imperative core is the subject of Parts II through IV: evaluating expressions to values, binding names in an environment, and then the state and control flow — mutation, conditionals, loops — that make a program a sequence of steps over a store.
• The functional branch arrives in Part V, with first-class functions, closures that capture the environment they were written in, and the recursion and higher-order functions that let a program be built by combining functions rather than by issuing commands.
• The type discipline follows in Part VI, as a pass over the core that analyzes programs before they run and rejects any that would use a value in a way its type forbids.
• The declarative branch is Part VII: relations defined by facts and rules, evaluated by finding the smallest set of facts closed under the rules, and queried from ordinary code.
• Algebraic data types in Part VIII give a precise way to describe structured data and take it apart by pattern matching, and they are the material the last branch is built from.
• The object-oriented branch closes the build in Part IX, as structs carrying state together with the methods that act on them.

The final part sets the branches against one another on shared problems, where choosing the framing that fits is the whole exercise. Appendix F places the languages and ideas named above in date order, each linked to the chapter that takes it up in full.

Further reading

A paradigm as a unit of thought: Robert Floyd’s Turing Award lecture “The Paradigms of Programming” (1979) is where the word, borrowed from Thomas Kuhn’s The Structure of Scientific Revolutions, entered the field. Floyd’s argument is that paradigms are techniques to be identified, taught, and expanded, and that a language should support more than one — the framing this chapter and this book take. Peter Van Roy’s “Programming Paradigms for Dummies: What Every Programmer Should Know” (2009) maps the paradigms against one another by the concepts they add, and reaches roughly thirty once combinations are counted — the concrete form of the claim that the pure cases are the exception.

The functional framing against the imperative default: John Backus’s Turing lecture “Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs” (1978) argues that the command-and-store model carried from the hardware is a limit on how programs can be built, names the “von Neumann bottleneck,” and proposes a functional alternative — a designer of Fortran arguing against the style Fortran helped establish. Part V takes up the functional lineage in full.

Logic as a programming language: Robert Kowalski’s “Algorithm = Logic + Control” (1979) makes the case that a program has a logical content, saying what is true, separable from the control that says how to search — the idea under the declarative framing. Alain Colmerauer and Philippe Roussel’s “The birth of Prolog” (HOPL II, 1993) is the account of how that idea became a language.

Objects and the messages between them: Alan Kay’s “The Early History of Smalltalk” (HOPL II, 1993) traces the object-oriented framing from Simula through Smalltalk and argues that the messaging between objects, more than the objects themselves, is the idea that matters. Part IX builds objects from the book’s own data types.

Concept checks

Syntax and Semantics

A programming language is described in two parts. Its syntax fixes what counts as a program: the rules that decide whether a string of characters is one at all. Its semantics gives each program a meaning: what it computes, and how. The two are separable: one meaning can be given more than one syntax, and one syntax more than one meaning. For example x / y in one language divides the values as integers and in another as reals. Similarly, within a single language x + y may add two numbers or concatenate two strings depending on what values x and y store.

When you have a bug in your program, it is either a syntax error — an error caused by misspelling your program: an unmatched parenthesis, a misspelled keyword, an unknown language construct — or a logical error: one that results in a program that behaves in an unexpected or inconsistent way. Syntax errors are typically trivial to detect and relatively easy to fix. Logic errors are harder: the program runs, but does the wrong thing, often in subtle ways. Much of what programmers spend their time on (i.e., testing, debugging, verification) is closing the gap between the program written and the program intended, and all of it rests on being able to say precisely what a program means. That meaning is the focus of this book.

Syntax: what counts as a program

A language’s syntax is the set of rules that decide which strings of characters are programs and what structure each one has: characters grouped into tokens, tokens assembled into a tree. Those rules are given by a grammar — a finite set of productions a mechanical procedure can check a candidate program against, and the same productions a parser follows to recover a program’s structure. Whether a string is a legal program is, once the grammar is fixed, a question with a definite answer.

Two layers hide inside the word syntax. The concrete syntax is the text as written — every parenthesis, the choice of && over and, the whitespace, the fact that multiplication binds tighter than addition. The abstract syntax is the structure that remains once those surface choices have done their one job of disambiguating: a tree commonly referred to as the abstract syntax tree (AST), which records only how the pieces of a program fit together.

The gap between the concrete and abstract syntax is easiest to see by holding the abstract structure fixed, while varying how that structure is concretely written. These three expressions are spelled by different rules:

x + y          (+ x y)          x y +

The first is infix, an operator written between its operands, the arrangement most languages inherit from arithmetic. The second is prefix, the operator first, as in Lisp, where every call takes this parenthesized form. The third is postfix, the operator last, as in the input to a reverse-Polish calculator. Three concrete syntaxes — yet a parser for any of them produces the same abstract structure, an addition with x and y beneath it, and an evaluator handed that structure cannot tell which spelling it came from. The surface can be redrawn without disturbing what is underneath, which is why this book starts at the AST: the structure is where meaning will be assigned, and the AST is the form the rest of the book works on.

In the decade preceding ALGOL 60, a programming language’s syntax was described the same way as a natural language: in prose, with examples, but ultimately determined by the programs its compiler accepted. The ALGOL 60 report gave the language’s syntax in a formal notation instead — now called Backus–Naur Form — precise enough that whether a string is a legal program became a mechanical question the report itself settled, ahead of and independent of any compiler. Backus had introduced the notation a year earlier for ALGOL 58, whose own report still described its syntax in prose; the 1960 report is where a formal grammar became the definition. Syntax has had a clean formal footing ever since.

Semantics: what a program means

Once a string counts as a program, the question becomes what that program means. Previously, we framed meaning as a mapping from a piece of syntax to a mathematical object — the value an expression evaluates to, or a coarser object such as its type. Formally, that mapping is called the semantics of the programming language. A semantics falls into one of two kinds, based on whether the meaning it assigns can be determined without ever running the program.

A semantics is static when the meaning it assigns can be determined by inspecting the program’s text alone, without ever running it. For example, determining whether every identifier a program uses is declared and in scope at each of its uses is a static question (cf. Part III) that can be answered without ever running the program on any inputs. Similarly, type checking is normally a static check (cf. Part VI): whether an operation is applied to a value of the right kind. Consider writing a program where a number is added to a function. A parser would happily parse the expression x + f, because at the time of parsing both x and f are simply names. Type checking, however, would determine that x is a name representing an integer and f is a function, and thus be able to reject the expression x + f as nonsense.

A semantics is dynamic when the meaning it assigns can only be determined by executing the program. The quintessential dynamic semantics is the concrete semantics: it traces how concrete inputs flow through the program to produce its concrete outputs. The interpreter you build throughout this book, beginning in Part II, computes exactly this, one construct at a time. When we ask what a program means, we typically mean its concrete semantics. A program can pass every static check and still not be the program we intended — i.e., the program can be well-formed, well-scoped, well-typed, and still compute the wrong answer. Static semantics is useful for confirming a program is well-behaved (as prescribed by the static check), whereas dynamic semantics describes its actual observed behavior.

A notation for meaning

ALGOL 60 gave a program’s syntax a formal notation, but its meaning was still written informally, in prose. The written description of the program’s semantics was ambiguous and allows multiple interpretations and open questions about how a program should behave. For example, should an operand short-circuit and not evaluate the right-hand operand when the left-hand one already decides the result? Does an assignment produce a value, and if so which one? Since prose can leave such questions open, two reasonable implementors can read the same description and produce two disagreeing implementations.

Over the years and decades since ALGOL 60, several notations were developed to give a program’s meaning unambiguously (cf. Program semantics). For evaluating expressions, this book uses the following notation

$$\rho ⊢e\Downarrow v$$

which can be read as in the environment $\rho$, the expression $e$ evaluates to the value $v$. The environment $\rho$ supplies the value of every name in scope, so a variable can be looked up (cf. Part III). The meaning of an expression is given by rules that tell us how to derive the meaning of an expression from the evaluation of the expression’s sub-expressions. Below we show three example rules in turn. The first rule says that the literal $0$ evaluates to itself — as does every literal — regardless of the environment.

$$\frac{}{\rho ⊢0\Downarrow 0}(\text{E-Lit})$$

The next rule states that the variable $x$ evaluates to the value $v$ assuming that in the environment $\rho$ the variable $x$ is bound to the value $v$.

$$\frac{\rho (x)=v}{\rho ⊢x\Downarrow v}(\text{E-Var})$$

The final rule states that the sum of two expressions is simply the sum of the evaluation of each of those expressions.

$$\frac{\rho ⊢e_1\Downarrow v_1\rho ⊢e_2\Downarrow v_2}{\rho ⊢e_1+e_2\Downarrow v_1+v_2}(\text{E-Add})$$

This style of writing rules has deep roots in logic and computer science: that the fact below the line is true exactly when every assumption above the line is true. This style of rules dates back to Gentzen’s work in the 1930s on logic, and it’s been used by computer scientists to define how a program executes since Plotkin in 1981 (operational semantics) and Kahn in 1987 (big-step semantics). Throughout this book, we develop these rules into a full account of Bridger’s concrete semantics.

Does the spelling matter?

How a program is spelled shapes how easily it can be read, written, and understood. Over the years, concrete forms have converged on shared expectations about meaning: a for loop is read as iterating over a collection, x := e as updating the value a variable holds, infix + as arithmetic. A reader draws on those expectations from the spelling alone, before working through what any rule says. The surface governs what a language makes easy to express and easy to grasp, and a form that cuts against a reader’s expectations misleads about as readily as a poor name.

This book starts past that point, at the abstract syntax — not because spelling is a cosmetic detail, but because this book’s subject is meaning, and meaning is assigned to a program’s structure rather than its surface syntax. How a language chooses its surface, and how that choice shapes the programs people actually write, is a real question with a study of its own; this book simply begins where meaning does.

Further reading

Giving meaning a formal footing: after BNF gave syntax a formal definition, doing the same for meaning took most of the following decade and produced several styles at once. Glynn Winskel’s The Formal Semantics of Programming Languages: An Introduction (MIT Press, 1993) is an accessible book-length review of those semantics, building each from small example languages. C. A. R. Hoare’s “An Axiomatic Basis for Computer Programming” (1969) is the primary source for one of those styles, reasoning about what a program establishes rather than tracing what it does; the operational style the rule above is written in is developed further in Program semantics.

Whether notation shapes thought: Kenneth Iverson’s Turing Award lecture “Notation as a Tool of Thought” (1980) argues the design-space question from the side that says syntax is far from cosmetic — that a well-chosen notation does part of a programmer’s reasoning for them, using the array notation of APL to make the case.

Concept checks

The Abstract Syntax Tree

Syntax and semantics separated the abstract structure of a program from the concrete syntax that disambiguates it: three spellings of an addition collapse to one tree. In this chapter, we detail the concrete implementation of the AST structure of Bridger programs that the parser provided with this book will have you use in the implementation Milestones. Specifically, this chapter details three Rust types: Expr for the expressions at the core of Bridger, Program for whole top-level declarations, and Ty for expressing types. For complete details on the concrete syntax of Bridger see Appendix B: concrete syntax.

The shape of expressions

Run down the grammar and an expression is always one of a fixed set of shapes: a literal, a variable, an operator applied to smaller expressions, a conditional, a call, and so on. A type whose values are “one of the following” is a sum type, and in Rust it is written as an enum: one variant per shape, each carrying exactly the pieces that shape is built from. The productions of a grammar and the variants of a sum type line up one for one, which is what makes the enum the natural representation of an AST.

That correspondence is old enough to have shaped which languages interpreters get written in. McCarthy’s LISP (1960) represented programs as the very lists the language processed — code as data — so a function that transformed a program was an ordinary list-processing function. The ML family later made the shapes explicit as algebraic data types and took them apart with pattern matching, a fit close enough that interpreters and compilers have been written in ML-family languages ever since. Rust inherits both halves: the enum names the shapes, and match (below) takes them apart.

A tree records structure and drops the surface detail the parser has already used up — the parentheses, the whitespace, the fact that * binds tighter than +. What survives is how the pieces fit together, and that is what the type below captures.

Bridger’s Expressions in Rust

The core of Bridger’s syntax is made up of recursively constructable expressions. This section details the components that make up such expressions and how the Book’s companion parser represents the expressions it parses. For convenience in error reporting, every parsed expression includes a span which records where in the source text the expression is located.

struct Span { src: SrcId, start: usize, end: usize }

The src says which loaded source the bytes belong to — the prelude is one source and the program another — so a span names a node uniquely even across files.

A Literal is represented by the following Lit enum. A numeric literal is represented as a 64-bit signed integer in Rust (i.e., all numeric values in Bridger are between $-2^{63}$ and $2^{63}-1$); a Boolean literal is simply a Rust bool type; a string literal is simply a Rust String, and a unit literal is the singleton value () left implicit in the Lit enum.

enum Lit { Int(i64), Bool(bool), Str(String), Unit }

Before detailing how we represent expressions, we detail several auxiliary types. The enum UnOp represents all unary operators in Bridger. Similarly, BinOp all binary operators. Finally, all names (identifiers and variables) are represented as a String.

enum UnOp { Neg, Not, Ref, Deref }

enum BinOp {
    Add, Sub, Mul, Div, Mod,      // arithmetic
    Eq, Ne, Lt, Le, Gt, Ge,       // comparison
    And, Or,                      // boolean
    Concat,                       // ++
    Cons,                         // ::  (prepend to a list)
}

type Name = String;

With each of the auxiliary data types defined, we represent Bridger expressions with the recursive enum Expr.

enum Expr {
    // a literal value: 5, true, "hi", ()
    Lit(Lit, Span),
    // a variable reference, or the receiver `self`
    Var(Name, Span),
    // a prefix operator: -e, not e, ref e, deref e
    Unary(UnOp, Box<Expr>, Span),
    // a binary operator: e + e, e == e, e and e, e ++ e, e :: e
    Binary(BinOp, Box<Expr>, Box<Expr>, Span),
    // a conditional: if e { … } else { … }, the else optional
    If(Box<Expr>, Box<Expr>, Option<Box<Expr>>, Span),
    // a block: statements and an optional trailing value
    Block(Vec<Stmt>, Option<Box<Expr>>, Span),
    // assignment through a reference: e := e
    Assign(Box<Expr>, Box<Expr>, Span),
    // a function call: e(e, …)
    Call(Box<Expr>, Vec<Expr>, Span),
    // a method call: e.m(e, …)
    Method(Box<Expr>, Name, Vec<Expr>, Span),
    // a lambda: |x, …| e, each parameter optionally annotated x: T
    Lambda(Vec<LambdaParam>, Box<Expr>, Span),
    // a pattern match: match e { arm, … }
    Match(Box<Expr>, Vec<Arm>, Span),
    // a while loop: while e { … }
    While(Box<Expr>, Box<Expr>, Span),
    // a for loop over a list: for x in e { … }
    For(Name, Box<Expr>, Box<Expr>, Span),
    // a for loop over a relation's solutions: for R(a, ?x) { … }
    ForQuery(Query, Box<Expr>, Span),
    // an early return from a function: return e
    Return(Box<Expr>, Span),
    // error propagation: e?  (sugar over match and return)
    Try(Box<Expr>, Span),
    // a tuple: (e, e, …), two or more elements
    Tuple(Vec<Expr>, Span),
    // a list: [e, …]
    List(Vec<Expr>, Span),
    // struct field access: e.f
    Field(Box<Expr>, Name, Span),
    // tuple projection by index: e.0
    Proj(Box<Expr>, u32, Span),
    // constructor application: C(e, …)
    Ctor(Name, Vec<Expr>, Span),
    // struct literal: S { f: e, … }
    Struct(Name, Vec<(Name, Expr)>, Span),
    // a relations operation: add q / clear R / solutions q / query
    Relation(Rel, Span),
}

The comment on each variant names the Bridger form it holds, and every variant matches the abstract syntax fixed in the language reference. This chapter settles the shape of each; the chapters that follow give each its meaning. Several variants hold companion types — Stmt, Arm, Pattern, Rel, and Query — which we define after two structural choices in Expr itself.

Children sit behind Box. An Expr can contain an Expr (e.g., the two operands of a Binary operator or the condition and branches of an If) so its size would depend on itself, and no fixed size would satisfy the Rust compiler. We use Box<Expr> (a pointer to an Expr). Since a pointer has a known size, a Box<Expr> can be used to hold sub-expressions recursively. A node owns its children through the Box, and dropping a tree drops everything under it. Where a node has any number of children — a Call’s arguments, a List’s elements — a Vec<Expr> owns all of them.

Four variants hold companion types, which we define now. A block (Block) is a sequence of statements followed by an optional result expression, and each statement (Stmt) is either a local let binding or an expression evaluated for its effect. A ref x = e binding is stored as an ordinary let of a ref expression, so it needs no case of its own.

enum Stmt {
    Let(Name, Option<Ty>, Expr, Span),   // let x = e   (or   let x: T = e)
    Expr(Expr),                          // an expression evaluated for effect
}

A match expression holds a list of arms. An arm (Arm) pairs a pattern with an optional guard and the expression to evaluate when the arm is chosen.

struct Arm {
    pat: Pattern,          // the pattern this arm matches
    guard: Option<Expr>,   // an optional `if` guard
    body: Expr,            // evaluated when the arm is taken
}

A pattern (Pattern) describes the shape a match tests a value against, and mirrors the expression forms it takes apart. Like an expression, every pattern carries its span.

enum Pattern {
    Wild(Span),                                 // _
    Lit(Lit, Span),                             // a literal: 5, true, "hi"
    Var(Name, Span),                            // binds the matched value to a name
    Ctor(Name, Vec<Pattern>, Span),             // a constructor: C(p, …)
    Tuple(Vec<Pattern>, Span),                  // (p, p, …), two or more
    List(Vec<Pattern>, Option<Name>, Span),     // [p, …], with an optional ...rest
    Cons(Box<Pattern>, Box<Pattern>, Span),     // head :: tail
    Struct(Name, Vec<(Name, Pattern)>, Span),   // S { f: p, … }
    Or(Box<Pattern>, Box<Pattern>, Span),       // p | p
}

The relations sublanguage folds its four expression forms into Rel. A query (Query) names a relation and supplies arguments; each argument (QArg) is either an ordinary expression or a hole to solve for, named ?x or anonymous ?.

enum Rel {
    Add(Query),        // add R(a, …)
    Clear(Name),       // clear R
    Solutions(Query),  // solutions R(a, …)
    Query(Query),      // a bare query R(a, …)
}

struct Query { name: Name, args: Vec<QArg> }   // R(a, …)

enum QArg {
    Expr(Expr),          // a ground argument
    Hole(Option<Name>),  // a hole: ?x (named) or ? (anonymous)
}

The program that holds them

An Expr builds the core of Bridger’s structure; however, at the top-level, a Bridger program is a sequence of declarations: functions, globals, types, structs, traits, relations. The order of declarations does not matter, instead every declaration is visible to every other top-level declaration (with a requirement that all global names must be unique). As such, we represent the top level Declarations simply as a map from names to declarations, and separate trait implementations and rules which are unnamed.

struct Program {
    decls: HashMap<Name, Decl>,   // fn, global, type, struct, trait, relation
    spans: HashMap<Name, Span>,   // where each declaration was written
    impls: Vec<Impl>,             // anonymous: keyed by the type they extend
    rules: Vec<Rule>,             // any number define one relation
}

enum Decl {
    Fn(Generics, Vec<Param>, Ty, Box<Expr>),   // fn f<T: C>(x: T, …) -> T = e
    Global(Option<Ty>, Box<Expr>),             // let x = e  (or  let x: T = e)
    Type(Generics, Vec<Variant>),              // type T<U> = C(U, …) | …
    Struct(Generics, Vec<Field>),              // struct S<T> { f: T, … }
    Trait(Generics, Vec<Sig>),                 // trait Tr<T> { fn m(…); … }
    Relation(Vec<Ty>),                         // relation R : (T, …)
}

The generic-bearing forms — Fn, Type, Struct, Trait, and the impl blocks — each carry a Generics: a declaration can be parameterized by types, and a type parameter may carry a trait bound its argument must satisfy:

struct Generics { params: Vec<TyParam> }   // <T, U: Show, …>; empty if absent

struct TyParam {
    name: Name,               // T
    bound: Option<TraitRef>,  // : Show — the trait bound, if any
    span: Span,               // where it is written, for diagnostics
}

The type checker in Part VI reads them — it quantifies a declaration over its parameters, then at each use instantiates them and checks the bound — while the evaluator ignores them, since running the program is type-erased. The reference’s abstract syntax folds them into a note for the same reason; the AST the parser builds keeps them for the checker.

Every Decl bottoms out in Expr — a function’s body, a global’s initializer — so the tree the last section built is what these hold. Two forms carry no single name and stay out of the map: an impl is found by the type it extends rather than a name, and a relation is defined by any number of rules at once, so each keeps its own list. We define the companion types these declarations use — Param, Field, Variant, Sig, Method, Impl, TraitRef, and the rule forms — below.

Looking a name up is then a map lookup, and that lookup is the order-free, mutually visible scope the reference specifies made concrete: where a declaration sits in the file cannot matter, because the file order is gone once the map is built, and a name declared twice collides when the map is.

A parameter (Param) and a struct field (Field) are each a name with a type, and a constructor of a type declaration is a variant (Variant) with a name and the types of its fields. Each carries the span of its own text, so a diagnostic can point at one parameter of a signature. A lambda’s parameter (LambdaParam) differs from a function’s in one respect: its annotation is optional, because the type checker can usually infer it from how the lambda is used.

struct Param       { name: Name, ty: Ty, span: Span }            // x: T
struct LambdaParam { name: Name, ty: Option<Ty>, span: Span }    // x  or  x: T
struct Field       { name: Name, ty: Ty, span: Span }            // f: T
struct Variant     { name: Name, fields: Vec<Ty>, span: Span }   // C(T, …), or C

A trait lists method signatures (Sig); an impl supplies methods (Method), which are signatures with a body. Each records whether the method takes self, its remaining parameters, and its return type.

struct Sig {
    name: Name,
    has_self: bool,       // whether the method takes `self`
    params: Vec<Param>,
    ret: Ty,              // (), when the return type is omitted
    span: Span,
}

struct Method {           // a Sig with a body
    name: Name,
    has_self: bool,
    params: Vec<Param>,
    ret: Ty,
    body: Expr,
    span: Span,
    sig: Span,            // the signature alone, `fn m(self, x: Int) -> T`
}

An impl block (Impl) records its own generics, the trait it implements if any, the type it extends, and its methods. A trait named there is a TraitRef — a trait name with any type arguments.

struct Impl {
    generics: Generics,        // impl<T> …
    trait_: Option<TraitRef>,  // the trait implemented, if any
    ty: Ty,                    // the type being extended
    methods: Vec<Method>,
    span: Span,
    head: Span,                // the header, `impl<T> Tr for T`
}

struct TraitRef { name: Name, args: Vec<Ty>, span: Span }   // Tr, or Tr<T, …>

A rule (Rule) has a head atom and a body. The head (Atom) names a relation and lists its terms (Term), each a logic variable or a literal. The body is the rule’s and-chain split into its conjuncts, and each conjunct is an ordinary expression: edge(x, y) and is_ok(x) are the same syntax, and which of them joins against a relation and which tests already-bound variables is settled by name resolution when the rules are installed, in Part VII.

struct Rule { head: Atom, body: Vec<Expr>, span: Span }   // rule H :- B1 and …

struct Atom { name: Name, terms: Vec<Term>, span: Span }  // R(t, …)

enum Term {
    Var(Name),   // a logic variable (a lowercase name)
    Lit(Lit),    // a literal
}

The type language

A type annotation on a let, the signature of a function, the fields of a struct, the columns of a relation, and the bound on a type parameter are all written in one small language of types, and it is a tree of its own:

struct Ty { kind: TyKind, span: Option<Span> }   // a shape, and where it was written

enum TyKind {
    Int, Bool, Str, Unit,    // Int, Bool, String, ()
    Tuple(Rc<[Ty]>),         // (T, U, …) — two or more
    List(Rc<Ty>),            // [T]
    Fn(Rc<[Ty]>, Rc<Ty>),    // fn(T, …) -> T
    Ref(Rc<Ty>),             // ref<T>
    SelfTy,                  // Self, in a trait or impl
    Named(Name, Rc<[Ty]>),   // N, or N<T, …> when applied
    Meta(u32),               // a type not yet known; the checker solves it (Part VI)
}

The children sit behind Rc, a reference-counted pointer, where the expression tree uses Box. Types are shared far more than expressions are: the checker records a type for every expression, nested expressions have nested types, and with plain boxes each level would hold its own copy of everything below it. With Rc the copies are pointers, and cloning a type costs nothing.

A type is used in two ways, and the split into Ty and TyKind serves both. A type the programmer wrote has a position, and a diagnostic can then say that a function was declared to return Int here and point at the annotation. A type the checker computes has none, so the span is optional. Two types are equal when their shapes are, wherever they came from, so a Ty compares and prints as its TyKind alone; Ty::int(), Ty::list(t) and their kin build the computed ones. TyKind is recursive for the same reason Expr is — a list of a list, a function returning a function. Named covers both a plain type name and a generic one applied to arguments, with an empty argument list for the plain case. This is the language the type checker in Part VI works over; here it is only the shape the parser records from a written type.

Matching over the tree

A function over an AST is a case analysis: one arm per variant, handling the pieces that variant carries. match is Rust’s tool for it, and pulling a node apart binds its fields in the same motion:

fn depth(e: &Expr) -> usize {
    match e {
        Expr::Lit(..) | Expr::Var(..) => 1,
        Expr::Unary(_, inner, _) => 1 + depth(inner),
        Expr::Binary(_, l, r, _) => {
            1 + depth(l).max(depth(r))
        }
        Expr::If(c, t, e, _) => {
            let branches = match e {
                Some(els) => depth(t).max(depth(els)),
                None => depth(t),
            };
            1 + depth(c).max(branches)
        }
        _ => 1, // remaining forms: Part II onward
    }
}

The recursion in the type becomes recursion in the function, and the shape of each arm is dictated by the shape of its variant. match is also exhaustive: drop the _ arm and the compiler names every variant still unhandled, so a new form added to Expr cannot silently fall through a pass that predates it. That guarantee — the type system enforcing that every case is considered — is why tree-walking interpreters read so cleanly in this style, and it is the single most useful piece of Rust for the chapters ahead.

The trees a compiler keeps

The AST here is shaped for a book that walks it directly. A production compiler keeps different trees, and the differences are worth knowing so the choices above read as choices.

A compiler usually holds more than one tree. This one is untyped: it is the parser’s output, and nothing in it records what an expression’s type is. Part VI’s type checker leaves the tree as it is and records each expression’s type in a side table keyed by the expression’s span — which is why a span must name a node uniquely — so a later stage can consult a type without recomputing it. Names, kept here as String, are often interned to small integers so that comparing two of them is one machine instruction rather than a character-by-character scan. And a tree stored with Box scatters its nodes across the heap; a compiler that cares about locality keeps them in an arena — one contiguous block — and replaces every Box<Expr> with an integer NodeId index into it, which also lets the side tables (types, uses) key off a small integer rather than a span. Each of these buys speed or a place to hang more information, at the cost of a tree that is heavier to build and read. A first interpreter wants neither cost, so it takes the Box, the String, and the one untyped tree.

Further reading

Building an interpreter around an AST: Robert Nystrom’s Crafting Interpreters (free online) builds two interpreters for the same language, the first a tree-walker over an AST much like this one, and it is unusually concrete about the shape of the tree and the walk over it. Its “Representing Code” and “Evaluating Expressions” chapters cover the same ground as this one and the next, in Java rather than Rust.

The trees a compiler keeps instead: Andrew Appel’s Modern Compiler Implementation in ML (Cambridge University Press, 1998) develops the typed and lowered intermediate representations named in the last section — separate trees for parsing, type checking, and code generation — and shows what each stage reads off the tree the stage before it produced.

Concept checks

Values and Runtime Errors

In the previous chapter, we covered the AST of Bridger as provided by the accompanying Rust parser. The provided code base also includes a Rust enum type Value representing the possible values a Bridger expression may evaluate to. Throughout this book, you will work through the milestones to create an interpreter that evaluates an Expr (and whole programs) to a Value. This chapter details the Value type you will be working with. It also covers what the interpreter should produce when an expression has no value at all (a runtime error). The mathematical value grammar and the semantic rules that define the meaning of Bridger programs are detailed in Appendix D: language reference.

The space of values

Evaluation produces a value, and every value a Bridger program can compute is one of a fixed set of shapes: an integer, a boolean, a string, unit; a tuple or a list built from smaller values; a constructor value or a struct value; a location into the store; a closure. The reference writes the set as a grammar:

$$\begin{array}{rlrl}v::=& n\mid b\mid s\mid ()& & \text{integer, boolean, string, unit}\\ \mid & (v,\dots ,v)& & \text{tuple}\\ \mid & []\mid v::v& & \text{empty list, list cons (non-empty list)}\\ \mid & C(v,\dots ,v)\mid S\{f=v,\dots \}& & \text{constructor value, struct value}\\ \mid & \ell & & \text{location}\\ \mid & ⟨\lambda x,\dots ,x.e,\rho ⟩& & \text{closure}\\ \mid & R\mid T& & \text{relation, type name}\end{array}$$

The last two stand for names rather than data — a declared relation, and a struct or type named as the receiver of an associated call — and nothing compares, prints, or stores them.

The above set of values represents the result of running any Bridger program or expression to completion. We describe each in detail in future chapters: integers, booleans, and strings in the tree-walking evaluation as the result of evaluating simple arithmetic, boolean, and string expressions; tuples and lists in that same chapter, as compound expressions built from smaller values; unit, the value of statements and blocks, with control flow; locations with mutable references; closures with functions; and constructor and struct values with algebraic data types and structs later still.

Bridger’s values in Rust

The set of value shapes is a sum type, the same correspondence the AST turned on: one variant per shape, each carrying what that shape is built from. The Value enum, provided with this book alongside the AST, holds them. It reuses type Name = String from the AST chapter for the names in Ctor and Struct.

enum Value {
    Int(i64),                          // 5
    Bool(bool),                        // true
    Str(Rc<str>),                      // "hi"
    Unit,                              // ()
    Tuple(Rc<[Value]>),                // (v, v, …), two or more
    List(List),                        // [] or a cons cell v :: v, see below
    Ctor(Name, Rc<[Value]>),           // a constructor value: C(v, …)
    Struct(Name, Rc<[(Name, Value)]>), // a struct value: S { f = v, … }
    Ref(Loc),                          // a location in the store (Part IV)
    Closure(Rc<Closure>),              // a function + its captured env (Part V)
    Relation(Name),                    // a declared relation, by name (Part VII)
    Type(Name),                        // a type name, receiver of `T.m()` (Part IX)
}

The comment on each variant gives an example of the kind of value it holds, and the variants line up with the grammar above one for one. The string, tuple, constructor, and struct payloads sit behind Rc, as the types in the AST chapter do: a value is copied whenever it is read from a variable or a cell, and a reference-counted pointer makes that copy a pointer bump rather than a walk of the payload. The Value enum is to a running program what Expr is to a parsed one: the type every part of the interpreter agrees on for the thing it passes around. Where Expr is what the evaluator takes apart, Value is what it builds.

One representation choice is visible in List. The reference models a list as either the empty list $[]$ or a cons $v_h::v_t$, a head joined to a tail, and the List type holds exactly that: the empty list, or a cell with a head, a tail, and the length so far, the tail shared with any other list that ends the same way. Sharing is what makes the rules’ shape a good representation and not only a good notation. Prepending with ::, taking a list apart with the pattern h :: t, and head and tail each touch one cell, whatever the list’s length, so a function that recurses down a list does work proportional to the list. An array would make ::, tail, and the tail of h :: t copy the whole list. A list literal and ++ cost the left operand’s length, since its cells are rebuilt onto the shared right operand, and len reads the count each cell stores. What the array would give back, reading the nth element in one step, Bridger has no operation for.

Expressions that do not evaluate to a value

Evaluating an expression usually produces a value; however, there are two scenarios when an expression does not evaluate to a value. Evaluation can get stuck: adding a boolean to an integer, applying a value that is not a function, projecting a field off a tuple, or dividing by zero. Each such scenario has no corresponding evaluation rule (and the expression has no well-formed meaning as a value). Instead, the interpreter immediately halts on such runtime errors. On the other hand, an evaluation can choose to return early: a return e computes e and then abandons the rest of the enclosing function’s body, carrying that value out to the function’s own result. We represent both non-local exits with one type Control in our Rust interpreter.

enum Control {
    Raise(RuntimeError),  // stuck: no rule applies; the run halts
    Return(Value),        // an early return, sent to the enclosing function
}

This chapter describes the purpose of Raise in detail. Stuckness is the absence of a result rather than a special result, a notion the operational semantics the book writes its rules in makes precise, and the reference collects the full list of cases. In the untyped evaluator of Parts II through V, these stuck states are how a nonsensical program fails; they are Bridger’s runtime errors. Return carries a value that did finish computing, only not here; a return is legal only inside a function body. We will explain how return e and the Control::Return variant are treated within the interpreter we build in the Control flow chapter and functions.

The interpreter we build must handle expressions that may contain runtime errors. Rather than having our interpreter crash or have undefined behavior on runtime errors, we have the interpreter we build make use of Rust’s Result and Error types to represent such runtime errors explicitly. That means, when the interpreter encounters such runtime errors, rather than halting it stops evaluation early and returns a RuntimeError describing why the interpreter stopped evaluation.

The variants below are the ones the arms of this part and the next raise; the driver and the prelude add theirs (no main, a cycle among global initializers, a failed read from input, a range or a call depth past the machine’s bound, printing a function), and each later part its own as its constructs arrive (a missing struct field, a method with no receiver, a query inside a filter).

enum RuntimeError {
    // x not in scope
    UnboundVariable { name: Name, span: Span },
    // 1 + true, a non-bool condition, iterating a non-list, …
    TypeError { expected: Ty, found: Ty, span: Span },
    // 5 / 0 or 5 % 0
    DivByZero { span: Span },
    // .f a value lacks
    NoSuchField { field: String, span: Span },
    // applying a non-function
    NotAFunction { found: Ty, span: Span },
    // wrong number of arguments
    ArityMismatch { expected: usize, found: usize, span: Span },
    // no arm matched the value
    NonExhaustiveMatch { span: Span },
    // == on a function or relation
    NotComparable { found: Ty, span: Span },
}

Evaluation therefore does not return a bare Value. It returns a Value or a Control, and Rust spells “one or the other” with its own sum type, Result. Its companion Option spells “a value or nothing”:

enum Result<T, E> { Ok(T), Err(E) }   // a T, or an error E
enum Option<T>    { None, Some(T) }   // a T, or nothing

Both come from Rust’s standard library, and both are how a Rust program carries the possibility of failure in a value the compiler forces every caller to look at. The evaluator puts a Value on the Ok side and a Control on the Err side — a normal value, or one of the two non-local exits:

fn eval(e: &Expr) -> Result<Value, Control> {
    match e {
        Expr::Lit(Lit::Int(n), _) => Ok(Value::Int(*n)),
        Expr::Binary(BinOp::Add, l, r, span) => {
            let a = eval(l)?;                 // a Raise or Return bubbles out here
            let b = eval(r)?;
            match (a, b) {
                (Value::Int(x), Value::Int(y)) => Ok(Value::Int(x.wrapping_add(y))),
                (a, b) => {
                    let found =
                        if matches!(a, Value::Int(_)) { type_of(&b) }
                        else { type_of(&a) };
                    Err(Control::Raise(RuntimeError::TypeError {
                        expected: Ty::int(), found, span: *span,
                    }))
                }
            }
        }
        _ => todo!("the remaining forms: the next chapter"),
    }
}

The Ok/Err split names both outcomes at the type level: a caller of eval cannot use the value without first deciding what to do when it is an Err. The ? after eval(l) is Rust’s propagation operator — when the subexpression is an Err, ? returns it from eval at once, so whichever exit it carries — a Raise with its span, or a Return with its value — travels out through every enclosing operation untouched. One mechanism threads both: every operation propagates a Control the same way, and only a function call inspects a Return, catching it at the boundary and turning it back into the call’s value. When both operands are integers the addition proceeds; when they are not, the last arm raises a RuntimeError::TypeError naming the Ty it expected and the Ty type_of read from the offending operand, and carrying the addition’s span. The addition wraps, since the reference fixes integers as 64-bit values with arithmetic modulo $2^{64}$.

Two kinds of failure

The Err(Control::Raise(…)) an addition returns and a Bridger value like Err("file not found") read alike on the page and are different in kind. The first is the interpreter stopping: no rule applied, so there is no value, and the host Result carries that fact out to the top level, where it is printed. A Bridger program cannot observe it or recover from it; the program has already stopped. The second is an ordinary Bridger value, a constructor value Err(s) that a successful evaluation produced, which the program inspects with match and carries on from. Evaluating it is a completed derivation that yields a value; nothing is stuck.

Bridger has its own Option and Result for exactly this second kind of failure, defined in the prelude as ordinary data types and handled with match — separate from Rust’s Option and Result, which are how the interpreter is written. The recoverable failures a Bridger program models with those values, the surface that makes them convenient, and the design space of failure mechanisms (values against exceptions against a halting panic) are the subject of Error handling, once algebraic data types give the language the constructors to build them. What this chapter fixes is the boundary: a runtime type error is the host stopping, and it stays outside the values a program computes with.

That boundary is why every stuck case is stated precisely. Each carries a span and names the Ty it expected against the one it found, because for Parts II through V a runtime type error is the only report a mistake gets, and the reader debugging a program has nothing else to go on. When the type checker arrives in Part VI it rules out the type-shaped stuck cases before the program runs, trading the clear failures described here for a guarantee made ahead of time. Division by zero, a failed read from input, and the interpreter’s two bounds — on call depth and on the size of a range — cannot be ruled out statically, nor, until exhaustiveness checking arrives, can a match no arm covers.

How a value is represented

A tagged union is one way to give an interpreter a single value type, and the choice reads as a choice against the alternatives a faster or a more open interpreter reaches for.

The enum stores a tag — which variant this is — beside the payload, and every value costs the tag plus room for the largest variant. match reads the tag to choose an arm, and the compiler checks that the arms cover every variant, the same exhaustiveness the AST walk relied on. A value kind cannot be added without editing the one enum and revisiting the matches the addition now leaves incomplete.

Other interpreters and compilers optimizing for speed instead often make use of smaller, packed value representations. For instance, a production virtual machine for a dynamic language often stores every value in a single 64-bit word, reading a few spare bits as the tag: small integers are represented inline with a tag bit set. This is how OCaml represents its values. It represents its native integers with 63 bits and the low bit determines whether the 64-bit word is an integer or a pointer to a structure. These packed representations achieve faster computations due to the denser representation that leads to fewer memory reads. However, the cost is that the representation is tied to a specific word size, and such packed representations are often hard to read and understand.

An interpreter written in an object-oriented language reaches instead for a class hierarchy: each value kind a subclass of a common value class, and each operation a virtual method the runtime dispatches on the object’s class. That arrangement makes the set of value kinds open — a new kind is a new subclass, added without editing a central type — and gives up the closed, checked case analysis the enum and its match provide, where the compiler can prove every kind is handled. In this book, we make the decision to use an enum type to represent the AST and Value because it makes it clear which cases are handled and which are not and is easier to read and understand for learning purposes.

Further reading

Representing values in an interpreter: Robert Nystrom’s Crafting Interpreters (free online) gives its bytecode interpreter a tagged-union value type in its “Types of Values” chapter, the same shape as the Value here, and its later “Optimization” chapter rewrites that type as a NaN-boxed word and measures what the packing buys.

Tagged data and dispatching on it: Abelson and Sussman’s Structure and Interpretation of Computer Programs (MIT Press, free online) builds data that carries a type tag and operations that read it, and works through both the central-table and the class-style organizations for dispatching on that tag — the two the last section set against the enum.

Concept checks

Tree-Walking Evaluation

The last two chapters introduced Bridger’s AST and its values. This chapter begins the evaluator: the procedure that maps an AST to a value. It covers the arithmetic, Boolean, string, list, and tuple expressions that Milestone M1 asks you to build, whose semantic rules take the form $e\Downarrow v$: the expression $e$ evaluates to the value $v$. The rest of those rules carry detail that does not bear on this fragment, and this chapter sets it aside.

Tree-walking evaluator

The rules for evaluation are compositional: the value of an expression is defined in terms of the values of its subexpressions. The E-Add rule only fixes the meaning of $e_1+e_2$ once the meanings of $e_1$ and $e_2$ are known.

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2}{e_1+e_2\Downarrow v_1+v_2}(\text{E-Add})$$

This shape of giving meaning is naturally recursive: to evaluate a node, first evaluate its children, then combine their values as the node’s rule prescribes. A leaf (a literal) is the base case: it carries its own value and does not recurse. The little arithmetic language below is fixed by four rules: E-Add above, together with a literal axiom, negation, and multiplication:

$$\frac{}{n\Downarrow n}(\text{E-Lit})\frac{e\Downarrow v}{-e\Downarrow -v}(\text{E-Neg})$$

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2}{e_1\times e_2\Downarrow v_1\times v_2}(\text{E-Mul})$$

The evaluator you develop following this book will recurse over the structure of an Expr. Below is a tree-walking evaluator for the little language above (similar to the one you will be asked to write):

enum Expr {
    Lit(i64),                       // 5
    Neg(Box<Expr>),                 // -e
    Add(Box<Expr>, Box<Expr>),      // e + e
    Mul(Box<Expr>, Box<Expr>),      // e * e
}

fn eval(e: &Expr) -> i64 {
    match e {
        Expr::Lit(n)    => *n,                       // E-Lit
        Expr::Neg(x)    => -eval(x),                 // E-Neg
        Expr::Add(l, r) => eval(l) + eval(r),        // E-Add
        Expr::Mul(l, r) => eval(l) * eval(r),        // E-Mul
    }
}

fn main() {
    // (1 + 2) * 4
    let e = Expr::Mul(
        Box::new(Expr::Add(Box::new(Expr::Lit(1)), Box::new(Expr::Lit(2)))),
        Box::new(Expr::Lit(4)),
    );
    println!("{}", eval(&e)); // 12
}

Each rule became one arm of the match; each premise became a recursive call; each conclusion became the value the arm returns. The calls eval makes on $(1+2)\ast 4$ trace the same tree as the derivation the rules build for it — eval(Mul) waits on eval(Add) and eval(Lit 4), and eval(Add) waits on its two literals — so the call tree and the proof tree have the same shape. Running the program computes the value at the root by the same steps the derivation uses to justify it.

Interpreting a program by a function that recurses over its structure is the oldest way to run one. McCarthy’s LISP defined its own evaluator this way: eval was an ordinary function, written in LISP, that took a program — itself a LISP list — and walked it, dispatching on each form and calling itself on the pieces. An interpreter for a language, written in that same language, is a metacircular evaluator, and the arithmetic walk above is the same idea with the program held as a Rust enum instead of a list.

From rules to match arms

Bridger’s evaluator has the same skeleton, over the real Expr and the real Value. Two things grow past the arithmetic sketch. Evaluation can fail — an operand can have the wrong shape, so the function returns Result<Value, Control> rather than a bare value, and a subexpression’s exit is propagated with ?. And the arithmetic fragment has no variables, so the environment carried by the reference judgment plays no part yet; eval reads only its &Expr, and the rules are read in the store-free, env-free slice $e\Downarrow v$ — the starter’s eval_expr already carries an env parameter, which nothing reads until Part III. The environment enters with let and scope there.

The correspondence is otherwise unchanged: one rule, one arm. The previous chapter wrote the Add arm in full — evaluate both operands, and on two integers return their sum, otherwise raise a TypeError. The rest of eval is built the same way, arm by arm:

fn eval(e: &Expr) -> Result<Value, Control> {
    match e {
        // E-Lit: a literal evaluates to itself
        Expr::Lit(lit, _) => Ok(match lit {
            Lit::Int(n)  => Value::Int(*n),
            Lit::Bool(b) => Value::Bool(*b),
            Lit::Str(s)  => Value::Str(s.clone()),
            Lit::Unit    => Value::Unit,
        }),

        // E-Arith: evaluate both, combine two integers (values.md)
        Expr::Binary(BinOp::Add, l, r, span) => { /* … */ }

        // the remaining forms are the work of Milestone M1
        _ => todo!("Sub, Mul, comparisons, and, or, not, tuples, lists, …"),
    }
}

Most of the remaining arms repeat Add‘s shape with a different operator, string concatenation among them. ++ joins two strings, and E-Concat names both operands’ values exactly as E-Add does:

$$\frac{e_1\Downarrow s_1{e}_2\Downarrow s_2}{e_1++e_2\Downarrow s_1{s}_2}(\text{E-Concat})$$

Its arm is the Add arm with Value::Str in place of Value::Int: evaluate both children, return their concatenation on two strings, and raise a TypeError otherwise. The same ++ also joins two lists, so the arm matches that shape as well — one operator over two value shapes, which is operator overloading; the general mechanism that lets one operator serve many types arrives with traits. Comparing strings for order arrives the same way, through cmp rather than <.

Filling in each arm is the walk applied to one rule at a time. Most arms follow a single pattern — evaluate both children, then combine their values — but two rules depart from that pattern.

When the walk departs from evaluating both

Division carries an extra premise: E-Div fires only when the divisor is nonzero. When it is zero no rule applies, so the expression is stuck, and the interpreter reports it rather than dividing. The arm reads the premise off as a guard:

// E-Div: the divisor must be nonzero, or evaluation is stuck
Expr::Binary(BinOp::Div, l, r, span) => {
    match (eval(l)?, eval(r)?) {
        (Value::Int(_), Value::Int(0)) => Err(Control::Raise(
            RuntimeError::DivByZero { span: *span },
        )),
        (Value::Int(x), Value::Int(y)) => Ok(Value::Int(x.wrapping_div(y))),
        (a, b) => Err(type_error2(Ty::int(), &a, &b, *span)),
    }
}

type_error2 builds the RuntimeError::TypeError the previous chapter wrote out by hand, blaming the first operand that is not an Int (type_error is its one-operand form); here the new case is the zero check, the guard $v_2\ne 0$ in the rule became a match arm. Modulo is the same arm with %.

The boolean connectives depart further. and and or short-circuit: the right operand is evaluated only when the left has not already settled the result. Two rules cover and — a false left operand settles it without touching the right, and a true left operand hands the result to the right — and the walk follows their shape, evaluating the left, then reaching the right on true:

// E-And-False / E-And-True: evaluate the right only when the left is true
Expr::Binary(BinOp::And, l, r, span) => {
    match eval(l)? {
        Value::Bool(false) => Ok(Value::Bool(false)),
        Value::Bool(true) => match eval(r)? {
            b @ Value::Bool(_) => Ok(b),
            other => Err(type_error(Ty::bool(), &other, *span)),
        },
        other => Err(type_error(Ty::bool(), &other, *span)),
    }
}

The arithmetic arm evaluated both children before combining them; the and arm evaluates one and may stop there. What each arm does is dictated by its rule — an axiom is a leaf, a rule with two operand premises recurses twice, a short-circuiting rule recurses once and then decides — so reading the rules off as arms also settles the questions prose semantics left open, such as whether and ever evaluates its right operand. The remaining forms of Expr — the other arithmetic and comparison operators, not, building tuples and lists, prepending to a list with ::, and projecting a tuple component with e.0 — are each one more arm of the same walk, and completing them is Milestone M1. A tuple has positional access because its arity is fixed and the index is a literal.

Beyond tree-walking evaluators

Walking the AST is one way to run a program; however, there are other alternatives when implementing an interpreter. The walk re-inspects the tree every time control reaches a node: each visit dispatches on the node’s variant and follows the Box pointers to its children. For a literal evaluated once is nothing. For the body of a loop that runs a million times — once the language has loops — it is a million repetitions of the same dispatch and the same pointer-chasing over a tree that never changed.

Interpreters that need the speed spend a compile step to remove that repetition.

• A bytecode virtual machine lowers the tree once into a flat sequence of simple instructions, then runs a tight loop that dispatches on one instruction at a time. The instructions sit in an array rather than scattered across the heap, and each is a single indexed step, so the repeated dispatch and pointer-chasing of the walk are gone. The cost is a second representation — the bytecode — to design, produce, and debug alongside the tree. CPython, the JVM, and Lua run this way, and it is the second interpreter Nystrom’s book builds for the same language as its first.
• Closure generation walks the tree once and produces, for each node, a closure that already holds its children’s closures and knows what to do; running the program calls closures and never inspects the AST again. The repeated dispatch is gone without leaving the host language or defining a bytecode, at the cost of a closure allocated per node. Feeley and Lapalme set the approach out in 1987.
• Just-in-time compilation translates the parts of a program that run hot into machine code while the program runs, reaching the speed of compiled code on those parts. It is the most involved and the most machine-specific of the three, and drives the production JavaScript and JVM engines.

A separate choice is the walk’s use of host-language recursion. eval calling itself uses the Rust call stack for the tree’s depth and for every Bridger call in progress, so a runaway recursion would exhaust it. The provided interpreter runs on a large stack and counts the calls in progress, refusing the next one past 100 000 as the stuck state StackOverflow, before the host stack runs out. An interpreter that must bound its memory more tightly keeps an explicit stack of work to do and loops over it instead of recursing, trading the directness of the recursive arms for control over memory.

This book takes the recursive AST-walk. It is the most direct realization of the semantics — one match arm per rule, the call tree the derivation tree — so the evaluator reads as the rules it implements, which is what serves a reader learning what those rules mean.

Further reading

Two interpreters for one language: Robert Nystrom’s Crafting Interpreters (free online) builds a tree-walking interpreter in its first half and a bytecode virtual machine in its second, for the same language, so the two strategies of the last section can be read against each other line for line, with the walk’s “Evaluating Expressions” the direct counterpart of this chapter.

Generating closures instead of walking: Marc Feeley and Guy Lapalme’s “Using closures for code generation” (Computer Languages 12:1, 1987, doi:10.1016/0096-0551(87)90012-9) compiles an expression into a network of closures whose application evaluates it, the middle ground that removes the walk’s repeated dispatch without a bytecode.

A register machine for a scripting language: Roberto Ierusalimschy, Luiz Henrique de Figueiredo, and Waldemar Celes’s “The Implementation of Lua 5.0” describes a production bytecode interpreter in detail, including why its virtual machine passes values through registers rather than a stack.

The evaluator written in its own language: Abelson and Sussman’s Structure and Interpretation of Computer Programs (MIT Press, free online) develops a metacircular evaluator — eval and apply for a Lisp, written in that Lisp — the modern presentation of the walk LISP first ran on.

Concept checks

Error Handling

The chapter on values and runtime errors split failure in two. A run can get stuck — no rule applies, so there is no value, and the interpreter halts with a RuntimeError the program cannot observe or recover from. Separately, a program can compute a value that stands for a failure and carry on from it. This chapter is about that second kind: the failures a program expects, how a language lets an operation signal one, and how a caller responds. The mechanism a language picks shapes how easy it is to read and understand code. This chapter looks at the history and design choices for how programs handle and recover from errors.

Failures a program expects

Some operations can fail as a normal part of doing their job. Looking up a configuration key that might be absent, parsing an integer from text a user typed, opening a file that might not exist, dividing by a number that might be zero — none of these is a bug in the program. Each is a case the program should anticipate and respond to: try another key, ask the user again, fall back to a default. The failure is part of the operation’s ordinary result, and the caller has a sensible next move.

That makes these failures different from the stuck states the values chapter described. Adding a boolean to an integer has no meaning and no recovery; the interpreter halts. A missing configuration key has a perfectly good meaning — “it is not there” — and a caller who wants to know. The question is how an operation reports such an outcome so that a caller can see it and act on it.

Mechanisms for handling errors

The earliest high-level languages signalled failure the way the hardware did: an operation set a status value, or returned a sentinel — a negative length, a null pointer, a distinguished integer — and the caller was expected to check it before using the result. This costs the language nothing to provide, and it is still how C’s standard library and most operating-system calls report failure. Its weakness is that nothing forces the check: a failed call has the same type as a successful one, so a caller can use its result as though it had succeeded and the compiler will not object, which makes the unchecked return value a classic source of bugs.

The mechanisms modern languages reach for fall into three broad categories. Two of them — exceptions and error values — repair that unchecked return by forcing the failure into the open, in different ways; the third stops the program rather than recovering. The differences show up in where the failure goes, whether the caller is forced to deal with it, and whether the possibility of failure is visible in the operation’s type.

Raising and catching exceptions

An exception moves the failure out of the return value entirely. An operation raises, and control leaves the raising code at once and travels up the call stack until it reaches a handler installed by some enclosing caller. Code between the raise and the handler is skipped. A function that does not care about a particular failure writes nothing about it; the exception passes through on its way to whoever does.

PL/I, in the mid-1960s, is among the first languages to build this into the language itself, with ON-conditions and the ON-units that handle them. The systematic treatment came a decade later: Goodenough’s 1975 paper Exception Handling: Issues and a Proposed Notation named the design questions still argued today. Chief among them is what happens after a handler runs. Under resumption, the handler can repair the situation and hand control back to the point that raised, which continues as if nothing had happened. Under termination, the raising construct is abandoned and control resumes in the handler’s context. CLU (Liskov and colleagues, later in the 1970s) made exceptions part of each procedure’s signature and committed to termination; termination became the model the mainstream languages adopted, and later designs — C++, Java, Python — followed it, while resumption largely fell out of use.

What every exception mechanism shares is that the failure is out of band. A function’s declared return type describes only the success case; whether it can also raise, and what, is either unstated or kept in a separate part of the signature. Java’s checked exceptions are the notable attempt to pull that information back into the type and force callers to account for it — an experiment whose ergonomics have been argued over ever since.

Error values

The functional tradition keeps the failure in the return value, but replaces the unchecked sentinel with a value whose type says failure is possible. ML’s option and Haskell’s Maybe carry “a value or nothing”; Haskell’s Either and Rust’s Result carry “a value or an error.” A function that might fail returns one of these, and a caller cannot reach the success value without first taking apart the wrapper and confronting the failure case.

This is the family the interpreter already uses in Rust: eval returns Result<Value, Control>, and every caller has to decide what an Err means before it can touch a Value. The possibility of failure is written in the type, the compiler checks that the caller handled it, and no separate channel or stack unwinding is involved — the failure is an ordinary value that flows through the program like any other.

Abort: panics

The third answer is to not recover at all. When a failure means the program has hit a state it was built to assume could never happen — a broken invariant, an index the code proved was in range — a language can stop the program outright: Rust’s panic!, C’s abort, a failed assertion. There is no handler and no value; the program immediately ends.

This is exactly the interpreter’s stuck errors from the values chapter, seen from a Bridger program’s side. When eval returns Err(Control::Raise(..)), the run halts and the program cannot intervene — an abort, reported at the top level. The abort family is reserved for failures where continuing would be worse than stopping, which is why it sits apart from the two recoverable mechanisms above.

Error values in Rust

Rust gives a program both Result and Option, defined in the values chapter, and one way to take them apart: match. An operation that can fail returns the wrapper, and the caller matches on it.

fn safe_div(a: i64, b: i64) -> Result<i64, String> {
    if b == 0 {
        Err("divide by zero".to_string())
    } else {
        Ok(a / b)
    }
}

match safe_div(10, 0) {
    Ok(q)  => println!("{q}"),
    Err(m) => println!("error: {m}"),
}

The Result<i64, String> in the signature is the whole point: a caller reads it and knows the call can fail, and the match will not compile unless it covers Err. The failure is in the open, and handling it is not optional.

When failures come in sequence

Handling one failure reads well. The difficulty this family is known for appears when several fallible operations run in sequence, each depending on the one before. Consider building a configuration from three lookups, each of which can fail:

fn read_config() -> Result<Config, String> {
    match lookup("host") {
        Err(e) => Err(e),
        Ok(host) => match lookup("port") {
            Err(e) => Err(e),
            Ok(port) => match lookup("user") {
                Err(e) => Err(e),
                Ok(user) => Ok(Config { host, port, user }),
            },
        },
    }
}

Each step continues inside the Ok arm of the step before, so the real work moves one level to the right for every operation, and the actual result — building the Config — ends up buried at the bottom of the staircase. This rightward drift is the shape critics of error values point to: the same three lookups written with exceptions would sit flat, one after another, because a failure would simply leave on its own. Handled naively, error values put their least flattering foot forward.

The repair is to let a failure leave early instead of nesting. An early return exits the function the moment a step fails, so the success value can continue at the outer level rather than inside an arm:

fn read_config() -> Result<Config, String> {
    let host = match lookup("host") {
        Ok(v) => v,
        Err(e) => return Err(e),
    };
    let port = match lookup("port") {
        Ok(v) => v,
        Err(e) => return Err(e),
    };
    let user = match lookup("user") {
        Ok(v) => v,
        Err(e) => return Err(e),
    };
    Ok(Config { host, port, user })
}

The staircase is gone — the steps are back in a line — but each one is still four lines of the same match-and-return. That repeated shape is exactly what Rust’s ? operator abbreviates. Writing e? on a Result unwraps an Ok to its value and, on an Err, returns it from the enclosing function at once:

fn read_config() -> Result<Config, String> {
    let host = lookup("host")?;
    let port = lookup("port")?;
    let user = lookup("user")?;
    Ok(Config { host, port, user })
}

Each ? stands for the four-line match above it. The code now reads as the three steps it is, the failure path is a single character, and the type still says the function can fail. This is the same ? the eval walk used to thread a Control outward: one operator, propagating the error channel so that ordinary code does not have to. With return and ? in hand, error values read as directly as the exception version, and keep the failure in the type.

How Bridger handles errors

Bridger makes the same choice, one level up: recoverable failure is a value. Its prelude defines Option and Result as ordinary algebraic data types, taken apart with match, and a Bridger program handles a failing operation the way the Rust above does:

fn safe_div(a: Int, b: Int) -> Result<Int, String> =
    if b == 0 { Err("divide by zero") } else { Ok(a / b) };

fn main() {
    match safe_div(10, 0) {
        Ok(q)  => println(q),
        Err(m) => println(m),
    }
}

The two flattening tools carry over as well. return is part of Bridger’s core from the start, introduced with control flow; ? arrives later as surface sugar over match and return, once ADTs give the language the constructors it works on. Bridger’s Option and Result are its own, defined in the prelude, and separate from the Rust Option and Result the interpreter is written in — the values chapter drew that boundary, and it holds here: a Bridger Err("...") is a value the program computes with, while the interpreter getting stuck is an abort the program never sees.

One detail differs from Rust when ? first arrives, and readers who know Rust will trip on it. Rust’s ? quietly inserts a From::from conversion on the error, so an Err of one error type can propagate out of a function whose error type is another. Bridger’s ? begins without that conversion: in a function returning Result<T, E>, every e? requires e to be a Result<_, E> with that same E, and a mismatch is reported as a type error naming two error types that a Rust programmer would expect to be compatible. The conversion needs trait-directed dispatch, which the language gains after ?. Once traits arrive, the prelude’s From<T> trait supplies it, and the desugaring of e? grows one call:

match e { Ok(v) => v, Err(err) => return Err(E.from(err)) }

The from resolves from the enclosing function’s error type — the expected type drives the choice, as it does for an unannotated lambda parameter — and when that type already matches the error, ? needs no conversion and inserts no from call, so code whose error types agree is unchanged. Supplying impl From<IoError> for ConfigError is what makes a Result<String, IoError> propagate out of a function returning Result<Config, ConfigError>. The conversion Rust performs silently is an ordinary trait here, with an impl a program can read and write.

Bridger has no exceptions. They are the contrast in this chapter rather than a feature: the one piece of non-local control in the core is return, and the abort family is the interpreter’s stuck errors. A program signals a recoverable failure by returning a value, and every place that might fail says so in its type.

Choosing a mechanism

No one of the three families is the plain best, and current languages divide over them. Exceptions keep the common path uncluttered — code that does not handle a failure says nothing about it — at the cost of a failure edge that is invisible at the call site and a control flow that leaves normal order. Error values make every failure visible in the type and checked by the compiler, at the cost of the drift that return and ? exist to answer. Aborting trades all recovery for the guarantee that a broken assumption stops the program instead of corrupting it.

Where languages land often reflects what they are protecting. Java, Python, and C++ center on exceptions, with Java’s checked exceptions an attempt to make the failure edge visible that programs frequently route around. Go returns an error value alongside the result and leans on convention to check it. Rust draws the line by kind of failure: Result and Option for the failures a caller should handle, panic! for the bugs it should not — recoverable failures as values, unrecoverable ones as aborts. Bridger follows that division, with the recoverable side modeled as values and the unrecoverable side its stuck errors, and leaves exceptions to the languages that build on them.

Further reading

The design questions, first stated: John Goodenough’s Exception Handling: Issues and a Proposed Notation (CACM, 1975) set out the vocabulary — including the termination-versus-resumption choice — that later designs argued within. Barbara Liskov and Alan Snyder’s Exception Handling in CLU (IEEE Transactions on Software Engineering, 1979) reports the reasoning behind putting exceptions in a procedure’s signature and choosing termination over resumption, from the experience of building the mechanism into CLU.

Error values in practice: the Rust Book’s Error Handling chapter works through panic!, Result, and the ? operator, and draws the recoverable-versus-unrecoverable line this chapter’s closing section describes. Rob Pike’s Errors are values (2015) makes the case for Go’s convention of returning an error alongside the result, and shows patterns that keep the repeated checks from piling up.

Concept checks

let a = match f()  { Ok(v) => v, Err(e) => return Err(e) };
let b = match g(a) { Ok(v) => v, Err(e) => return Err(e) };
Ok(h(b))

Program Semantics

The tree-walking chapter set out the shape of an evaluator: a function that takes an Expr apart and returns its Value, one arm of the walk per rule. Building it is Milestone M1. That evaluator, once written, is one program, and a program cannot be its own definition of the right answer — to say it is correct, we need an account of what evaluating an expression means that stands on its own, ahead of any interpreter. This chapter writes that account for the expressions of Milestone M1. It uses the inference rules the book has been reading since Part I; the notation reference covers how to read a rule and how the rules stack into a derivation. What is new here is the whole rule set at once, and what having it lets us say: which expressions have a value, which have none, and that these rules give no expression more than one.

What the rules specify

Evaluation is the judgment

$$e\Downarrow v$$

read expression $e$ evaluates to value $v$, defined by the inference rules below. Each rule is a clause of the definition: an expression evaluates to a value exactly when some rule’s conclusion says so and its premises hold. The rules are syntax-directed — the outermost form of $e$ selects which rule can apply — and compositional — a compound expression’s value is built from its subexpressions’ values, named in the premises.

The Milestone M1 fragment has no variables, so the rules here are read in the env-free slice $e\Downarrow v$. Once let and scope arrive in Part III the judgment carries an environment, $\rho ⊢e\Downarrow v$, and later features add more; the reference states the full judgment — with the store, the relation database, and the $\mathsf{Val}/\mathsf{Ret}$ outcome — of which every rule below is the value-case, effect-free projection.

The rules for the M1 fragment

Literals

A literal evaluates to the value it denotes. Written for an integer $n$:

$$\frac{}{n\Downarrow n}(\text{E-Lit})$$

The boolean literals true and false, string literals, and the unit value () each evaluate to themselves the same way; $\text{E-Lit}$ names all four. The $\text{E-Lit}$ rule is an axiom (it has no premise) and it is the base case every derivation ends at.

Arithmetic

Addition evaluates both operands and adds them, provided both are integers:

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2{v}_1,v_2\in \mathbb{Z}}{e_1+e_2\Downarrow v_1+v_2}(\text{E-Add})$$

Subtraction and multiplication have the identical shape; writing $\oplus$ for either operator:

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2{v}_1,v_2\in \mathbb{Z}}{e_1\oplus e_2\Downarrow v_1\oplus v_2}(\text{E-Arith})$$

The premise $v_1,v_2\in \mathbb{Z}$ is what confines these operators to integers: when an operand evaluates to a value that is not an integer, no arithmetic rule applies. Division carries one more premise — a nonzero divisor:

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2{v}_1,v_2\in \mathbb{Z}{v}_2\ne 0}{e_1/e_2\Downarrow v_1÷v_2}(\text{E-Div})$$

Modulo % has the same rule with the remainder in place of the quotient, and the same $v_2\ne 0$ premise, so a zero divisor matches no rule for either operator. Negation flips the sign of an integer:

$$\frac{e\Downarrow vv\in \mathbb{Z}}{-e\Downarrow -v}(\text{E-Neg})$$

Comparison and equality

Two families of operator return a boolean, and they differ in the operands they take. The ordering operators ($<$, $\le$, $>$, $\ge$) take integers, the same restriction the arithmetic rules carry. Writing $\otimes$ for one of them and $\hat{\otimes }$ for the matching order relation on integers:

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2{v}_1,v_2\in \mathbb{Z}}{e_1\otimes e_2\Downarrow (v_1\hat{\otimes }{v}_2)}(\text{E-Ord})$$

A non-integer operand matches no ordering rule and is stuck.

Equality == and inequality != instead compare structurally: two values are equal when they have the same shape and equal components, so (1, [2]) == (1, [2]) holds. They apply across the M1 value shapes — integers, booleans, strings, unit, tuples, and lists — so their rule needs no premise restricting the operands. Writing $\otimes$ for either operator and $\hat{\otimes }$ for the structural test on values:

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2}{e_1\otimes e_2\Downarrow (v_1\hat{\otimes }{v}_2)}(\text{E-Eq})$$

Later parts extend the structural test to constructor and struct values, and leave it with no result — stuck — on a function or a relation, which have no structural notion of equality. Comparisons do not chain: $a<b<c$ is not a legal expression in Bridger.

Boolean connectives

The and and or operators short-circuit, and the specification denotes that by giving each two rules. A false left operand settles and without the right operand appearing at all:

$$\frac{e_1\Downarrow \text{false}}{e_1\text{and}{e}_2\Downarrow \text{false}}(\text{E-And-False})$$

$$\frac{e_1\Downarrow \text{true}{e}_2\Downarrow vv\in \mathbb{B}}{e_1\text{and}{e}_2\Downarrow v}(\text{E-And-True})$$

and or mirrors it — a true left operand settles the result, a false one hands off to the right:

$$\frac{e_1\Downarrow \text{true}}{e_1\text{or}{e}_2\Downarrow \text{true}}(\text{E-Or-True})$$

$$\frac{e_1\Downarrow \text{false}{e}_2\Downarrow vv\in \mathbb{B}}{e_1\text{or}{e}_2\Downarrow v}(\text{E-Or-False})$$

$$\frac{e\Downarrow bb\in \mathbb{B}}{\text{not}e\Downarrow \neg b}(\text{E-Not})$$

Because $\text{E-And-False}$ has no premise about $e_2$, its conclusion holds whatever $e_2$ would do — including when $e_2$ has no value at all. Short-circuiting is a consequence of the rules, so it is a fact of the language rather than a habit of one interpreter.

Strings, tuples, and lists

The ++ operator joins two strings, and equally joins two lists; one rule covers both, requiring the operands to be the same one of those two shapes:

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2{v}_1,v_2\text{ both strings, or both lists}}{e_1++e_2\Downarrow v_1++v_2}(\text{E-Concat})$$

A tuple evaluates its components left to right and collects the values; its arity is at least two:

$$\frac{e_i\Downarrow v_i(1\le i\le n)}{(e_1,\dots ,e_n)\Downarrow (v_1,\dots ,v_n)}(\text{E-Tuple})$$

A list evaluates its elements the same way, and the result is the value the reference writes as a cons sequence:

$$\frac{e_i\Downarrow v_i(1\le i\le n)}{[e_1,\dots ,e_n]\Downarrow v_1::\cdots ::v_n::[]}(\text{E-List})$$

Neither rule constrains the values its parts produce, so the untyped evaluator builds a tuple or a list from whatever the parts are. Their difference is a typing matter evaluation does not police: a tuple’s positions may each hold a different type, whereas a list’s type [T] fixes one element type for the whole list. The type checker enforces that homogeneity in Part VI, so [1, true] builds a list here and is rejected by the type checker.

A list is also built one element at a time. :: prepends a value to a list, and its rule constrains only the right operand, which must be a list:

$$\frac{e_1\Downarrow v_1{e}_2\Downarrow v_2{v}_2\text{ a list}}{e_1::e_2\Downarrow v_1::v_2}(\text{E-Cons})$$

The value 1 :: [2, 3] is the same list as [1, 2, 3], and the same list the pattern h :: t takes apart in Part VIII: the expression that builds a list and the pattern that inspects one share their notation.

Projecting a tuple

A tuple’s component is read by position with e.i, where the index $i$ is a literal. The projection has a value when the index is in range:

$$\frac{e\Downarrow (v_0,\dots ,v_{n-1})0\le i<n}{e.i\Downarrow v_i}(\text{E-Proj})$$

An index outside $0\le i<n$, or a .i applied to a value that is not a tuple, matches no rule. Lists have no such projection: a list is taken apart by iteration and by patterns in later parts, and the absence of an indexing operator is a deliberate part of the design.

That is the whole M1 fragment. Everything the milestone evaluator computes is one of these rules applied at the root of a derivation whose sub-derivations evaluate the operands. The order in which those operands are evaluated is not observable here, because none of these expressions has an effect; once effects exist, the threaded judgment in the reference fixes the order left to right.

Derivations and stuck expressions

A derivation stacks the rules that justify one another into a tree whose leaves are axioms and whose root is the judgment it establishes. Short-circuiting shows the idea sharply. Take false and (1 / 0 == 0): its whole derivation is one rule over one axiom,

$$\frac{\frac{}{\text{false}\Downarrow \text{false}}(\text{E-Lit})}{\text{false}\text{and}(1/0==0)\Downarrow \text{false}}(\text{E-And-False})$$

The right operand 1 / 0 == 0 does not appear anywhere in the tree, so the expression evaluates to false even though 1 / 0 on its own has no value. A rule is applied only for what its premises demand, and $\text{E-And-False}$ demands nothing of $e_2$.

1 / 0 on its own is stuck: no rule concludes a value for it. The only rule for / is $\text{E-Div}$, and its premise $v_2\ne 0$ fails, so there is no derivation of 1 / 0 ⇓ v for any $v$. The same holds for 1 + true: $\text{E-Add}$ is the only rule that could conclude 1 + true ⇓ v, and its premise $v_1,v_2\in \mathbb{Z}$ fails on true, which evaluates to a boolean. A stuck expression is one for which no derivation exists — the absence of a value, rather than a special value standing for failure. The reference gathers the stuck cases of the whole language.

The interpreter of the previous chapters is what makes that absence observable. Where the semantics simply has no tree, eval returns Err(Control::Raise(..)) carrying a RuntimeError, and ? propagates it to the top level — the treatment error handling describes. The two agree: the expressions the rules leave without a derivation are exactly the ones the evaluator reports rather than assigning a value.

Determinism

Reading the rule set as a whole settles one more question: how many values can an expression have? Nothing about inference rules forces the answer to be one — a rule set can license several values for the same expression, and semantics for concurrent or randomized languages do — so it is a property to check rather than assume. Bridger’s rules give at most one. They are syntax-directed, so the form of $e$ picks out the rules that could conclude $e\Downarrow v$. For most forms that is a single rule. Where a form has two — and and or — the rules’ premises are mutually exclusive: $\text{E-And-False}$ needs $e_1\Downarrow \text{false}$ and $\text{E-And-True}$ needs $e_1\Downarrow \text{true}$, and $e_1$ cannot do both. Since each subexpression in turn has at most one value, each expression built from them does too.

So $e\Downarrow v$ is a partial function from expressions to values: every expression has one value or none, and never a choice of two. This is what lets us speak of the value of an expression, and it is why the tree-walker returning a single Value is not making an arbitrary pick among several the rules would allow — the rules allow only one. An expression has no value when it is stuck, and, once the language has recursion, when its evaluation runs forever; a big-step rule set does not distinguish those two cases, a point the next section returns to.

A family of semantic styles

The rules above are one way to give a language meaning: big-step operational semantics, which Kahn named natural semantics, relating an expression directly to its final value. Three other styles answer “what does a program mean” differently, and each is reached for a different purpose.

• Small-step (structural operational) semantics, due to Plotkin, gives meaning as a single reduction $e\to e^{\prime }$, iterated until no step remains. It exposes the intermediate states a big-step rule passes over, which is what a soundness proof by progress and preservation, and any account of concurrent or interleaved execution, is written against.
• Denotational semantics, in the Scott–Strachey tradition, maps each phrase to a mathematical object — a function from inputs to results — assembling the whole from its parts. It is the style for reasoning about when two programs mean the same thing.
• Axiomatic semantics, from Floyd and Hoare, gives meaning through what can be proved about a program, in assertions $\{P\}c\{Q\}$. It is the style for verifying that code meets a specification, rather than for computing the value it produces.

This book works in the big-step style throughout. Each rule becomes one arm of the tree-walker, a derivation tree is the evaluator’s call tree, and the judgment $e\Downarrow v$ is exactly the type of eval — an expression in, a value out — so the specification and the interpreter have the same shape and can be read against each other. It is also compact enough to be the specification you write for each new feature as it is added, which is how the rest of the book proceeds.

What the style gives up is the intermediate detail. A big-step rule set relates an expression to its final value and describes nothing between, so it cannot tell a computation that runs forever from one that is stuck: each simply lacks a finite derivation. It also fixes no order of steps beyond what the premises thread. Small-step semantics recovers both. Neither matters here — the book has no concurrent execution to describe and treats soundness informally — so big-step gives up nothing this book needs, and keeps the directness of reading as the interpreter it defines.

Further reading

The semantic styles and their sources: the founding papers for these styles — Plotkin on structural operational semantics, Kahn on natural semantics, and Hoare on the axiomatic style — and Glynn Winskel’s book-length development of all of them are collected in the further reading for Syntax and semantics, where the notation the rules above use was first introduced.

Concept checks

Milestone M1

The Expression Evaluator

Part II built the pieces of an evaluator: the values it produces, the walk that produces them, the failures it reports, and the rules that fix what each expression means. This milestone puts them together into a working evaluator for the expression fragment, and gives you a way to know it runs correctly.

The codebase

The starter is one interpreter that you grow across the milestones. Nearly all of it is provided and frozen — the parser, the value and error types, the environment and the store — so your effort goes into meaning rather than the plumbing that would have you fighting the borrow checker. The files that matter here:

src/
  ast.rs            the Expr tree and its companion types    (provided)
  interp/
    eval.rs         eval_expr — YOUR file
    value.rs        the Value type, and type_of              (provided)
    error.rs        RuntimeError and Control                 (provided)
    env.rs          the environment (used from M2)           (provided)
    store.rs        the store (used from M3)                 (provided)
  parser/           source text -> Expr                      (provided)
  types/            the type checker (M5)                    (deferred)
  relations/        the Datalog fragment (M6)                (deferred)

Most work happens in one method, which you grow a little each milestone:

pub fn eval_expr(&mut self, e: &Expr, env: &Env) -> Result<Value, Control>

Every Expr variant already has a match arm. The ones you have not reached yet are milestone-tagged holes — a todo_mN!(…) that compiles as any type but stops the run if reached — so the crate builds from the first clone with nothing written. As you fill an arm, you replace its hole with the rule’s implementation. To read the shape of any provided type — Value, Expr, RuntimeError — while you work, build the API docs and open them in your browser:

cargo doc --no-deps --open

Setting up

Install the Rust toolchain from rustup — it brings cargo, the formatter, and the linter — and confirm it runs:

cargo --version

Clone the starter repository, then build it once. A fresh clone builds green, because every hole compiles:

cd bridger-interpreter
cargo build

From there, the loop you repeat on every milestone:

cargo m1                                    # run the Milestone-1 tests
cargo fmt                                   # format your code
cargo clippy --all-targets -- -D warnings   # lint

cargo m1 is short for cargo test --features m1 — the tests you should pass in Milestone M1. The milestones are cumulative. So cargo m2 will run the tests for Milestone M2 and Milestone M1.

To-dos

Every place you write code is a macro named for its milestone, so a search lists exactly what a milestone asks for:

grep -rn 'todo_m1!' src

turns up the six arms of eval_expr — and in general, grep -rn 'todo_mN!' src is Milestone N’s checklist. The six for M1:

// src/interp/eval.rs — the six M1 arms of eval_expr
Expr::Lit(..)    => todo_m1!("E-Lit"),
Expr::Unary(..)  => todo_m1!("E-Neg / E-Not"),
Expr::Binary(..) => todo_m1!("E-Arith/Ord/Eq, E-And/Or, E-Concat, E-Cons"),
Expr::Tuple(..)  => todo_m1!("E-Tuple"),
Expr::List(..)   => todo_m1!("E-List"),
Expr::Proj(..)   => todo_m1!("E-Proj"),

Every other Expr variant is a hole tagged for a later milestone, which is why the crate compiles with none of them written.

Milestone specification

Each expression form, the rule that gives it meaning, and the case that leaves it stuck:

The full rules are in the Program Semantics chapter; this table is the checklist your evaluator is measured against, not a second statement of them.

Three contracts hold across every arm. On success an arm returns Ok(v); when the expression is stuck it returns Err(Control::Raise(…)) carrying the RuntimeError and the span of the node the rule blames — the interpreter reports rather than panics. and and or short-circuit: the right operand is evaluated only when the left has not already settled the result. And integer arithmetic wraps modulo $2^{64}$, as the values chapter fixed.

Implementing Milestone M1

Destructure each arm’s .. into the fields you need. The M1 variants and what they carry:

BinOp names the operator: Add Sub Mul Div Mod for arithmetic, Eq Ne Lt Le Gt Ge for comparison, And Or, Concat for ++, and Cons for ::.

Three tools do the work of every arm:

• Evaluate a subexpression with self.eval_expr(sub, env)?. The ? sends a stuck operand straight out, so an arm only handles the case where its operands produced values.
• Build the result — Value::Int, Value::Bool, Value::Str, Value::Tuple, Value::List. Integer arithmetic uses the wrapping operations (i64::wrapping_add, wrapping_mul, …), since the reference fixes 64-bit wraparound.
• Report a stuck expression — return RuntimeError::TypeError { expected, found, span } or RuntimeError::DivByZero { span }. The provided type_of(&v) gives the found type, Ty::int() / Ty::bool() / … name the expected one, and span is the offending node’s. A From<RuntimeError> for Control is provided, so .into() (or ?) lifts a RuntimeError into the Control::Raise the signature returns.

You have already seen this in Part II: the Add arm is worked in full, and Div and and show the divisor guard and short-circuiting. The rest of M1 is the same shape, one arm at a time.

Worked examples

An expression, and the value it evaluates to:

1 + 2 * 3          ⇓ 7
-(3 - 5)           ⇓ 2
7 / 2              ⇓ 3          (integer division)
7 % 2              ⇓ 1
2 < 3              ⇓ true
(1, 2) == (1, 2)   ⇓ true       (structural)
"ab" ++ "cd"       ⇓ "abcd"
[1, 2] ++ [3]      ⇓ [1, 2, 3]
0 :: [1, 2]        ⇓ [0, 1, 2]
(10, 20).1         ⇓ 20
false and (1 / 0)  ⇓ false      (right operand never evaluated)

And expressions with no value, which halt the run:

1 + true      ⇓ stuck   (an Int operator met a Bool)
5 / 0         ⇓ stuck   (division by zero)
"a" ++ [1]    ⇓ stuck   (++ needs both strings or both lists)
(1, 2).5      ⇓ stuck   (projection past the end of a 2-tuple)

How to know it works

cargo m1 runs the set of provided milestone M1 tests; all pass means the fragment is likely correct. Each test builds an Expr and calls eval_expr on it — one rule at a time. A value test checks the Value; a stuck test checks the error’s variant, its expected/found types, and the span it blames, but not its wording. The builders (int, binary, tuple, …) and the assertions value_of and stuck come with the repository, so a check reads close to the rule it exercises:

// 1 + 2 * 3  ⇓  7
let e = binary(Add, int(1, 0), binary(Mul, int(2, 2), int(3, 4), 3), 1);
assert_eq!(value_of(&e), Value::Int(7));

// 1 + true  is stuck: an Int operator met a Bool
let bad = binary(Add, int(1, 0), boolean(true, 2), 1);
assert!(matches!(stuck(&bad), RuntimeError::TypeError { .. }));

Fill an arm, run cargo m1, and repeat until the all M1 tests pass.

Design problems

Environments and let

Through Part II an expression meant one value wherever it stood: 2 + 2 is 4 in every context, and the evaluator needed nothing but the expression itself to find it. A variable is the first form whose value the expression does not settle on its own. x stands for 3 where a binding says so, for "hi" where another one does, and for nothing at all where none does. The structure that supplies each name’s value is the environment, and this chapter describes what an environment is and how it came to be.

Algol 60 made where does a name refer? a question with a principled answer — a name introduced in a region of a program means something inside that region and not outside it — but left open what such a region is made of once the program runs. The environment is the answer: a map from the names in scope to the values they currently denote. In Bridger, we use let x = e to extend the environment with a binding of the name x to the value e evaluates to.

A name has a value only in context

The evaluation judgment has carried an environment $\rho$ since Part I, and every rule threaded the same $\rho$ through its premises. Until now nothing read or modified the environment. The arithmetic, boolean, string, and list forms have no variable to look up, so each rule passed $\rho$ along untouched and the derivations dropped it, writing $e\Downarrow v$; the starter’s eval_expr did the same, taking an env parameter that no arm consulted. A variable changes that. Its rule reads the environment and nothing else:

$$\frac{\rho (x)=v}{\rho ⊢x\Downarrow v}(\text{E-Var})$$

$\rho$ is a finite map from variables in scope to values, $\rho :Var\rightharpoonup v$; $\rho (x)$ is the value it binds to $x$. When $\rho$ has no binding for $x$, the premise $\rho (x)=v$ cannot be met, no rule applies, and the expression is stuck — the same absence of a derivation that a type mismatch produces, reported as the runtime error UnboundVariable. An unbound name is the failure this chapter adds to the list; every other stuck case so far came from a value of the wrong shape, and this one comes from a name with no value at all.

The environment as an explicit part of an evaluator goes back to Peter Landin’s SECD machine, whose four components — stack, environment, control, dump — evaluate an expression by looking each variable up in the environment component, the E (Landin, 1964). Two years later the same author’s ISWIM gave the notation let x = e (and its mirror, the where clause) for naming a value over a region of an expression (Landin, 1966); the keyword has since landed in languages far from ISWIM, Bridger among them.

The let operator

A block is a sequence of items evaluated top to bottom, and its value is its final expression. A let is one kind of item: it evaluates its right-hand side and binds the name over the rest of the block. Writing $\{rest\}$ for the block that remains after the first item, the rule extends the environment for that remainder and for nothing else:

$$\frac{\rho ⊢e_1\Downarrow v_1\rho [x\mapsto v_1]⊢\{rest\}\Downarrow v}{\rho ⊢\{\text{let}x=e_1;rest\}\Downarrow v}(\text{E-Let})$$

The notation $\rho [x\mapsto v_1]$ is the environment $\rho$ with $x$ bound to $v_1$ added: it agrees with $\rho$ on every other name and answers $v_1$ for $x$. The right-hand side $e_1$ is evaluated in $\rho$ — the environment before the binding is added — so the name being bound is not yet in scope while its own value is computed. The rest of the block is evaluated in the extended environment, which is where the new name can be read.

An item that is a bare expression is evaluated for whatever it does and its value discarded; the block carries on in the same environment. The final expression is the block’s value, and an empty block is unit:

$$\frac{\rho ⊢e_1\Downarrow v_1\rho ⊢\{rest\}\Downarrow v}{\rho ⊢\{e_1;rest\}\Downarrow v}(\text{E-Seq})$$

$$\frac{\rho ⊢e\Downarrow v}{\rho ⊢\{e\}\Downarrow v}(\text{E-Block})\frac{}{\rho ⊢\{\}\Downarrow ()}(\text{E-Empty})$$

Because $\text{E-Let}$ extends the environment only over the block’s remainder, a binding reaches from its let to the end of the enclosing block and no further. A name bound inside a block is not in scope after the block ends, and a name bound in an outer block is in scope within an inner one unless the inner block binds the same name again.

A binding is confined to its block even when that block is nested inside another. Take a block whose first item is itself a block:

{
    { let x = 1; x + 1 };   // inner block; x is bound only within it
    x                       // UnboundVariable: x's scope ended at the }
}

The outer block evaluates its first item — the inner block — by $\text{E-Seq}$, which evaluates it in the current environment and discards the result. Inside, $\text{E-Let}$ extends the environment with $x\mapsto 1$ for the inner block’s remainder alone, yielding 2. $\text{E-Seq}$ then evaluates the rest of the outer block in the same environment it began with — the one with no x — so the final x is unbound. A block produces a value, and the binding made inside the inner block never leaves it.

Binding a name a second time is shadowing: the new binding $\rho [x\mapsto v]$ answers for $x$ from that point on, and the earlier value is unreachable through the name for the rest of that region though it is not destroyed. Since the right-hand side is evaluated before the binding is added, a let may define a name in terms of the value the same name held before it:

let x = 1;
let x = x + 1;   // the x on the right is the old 1; x is now 2
x                // 2

Building it

The environment now reaches the evaluator’s signature. The provided method is

fn eval_expr(&mut self, e: &Expr, env: &Env) -> Result<Value, Control>

and the env parameter, carried unused since Milestone M1, is what the new arms read. An Env offers two operations: lookup, which returns the value a name is bound to or None, and extend, which returns a new environment with one more binding and leaves the one it was called on untouched. $\text{E-Var}$ needs only the first: look the name up, and a miss is UnboundVariable. A block threads the second — it walks its items carrying an environment that grows as each let is met — and because every extension produces a fresh scope, that growth reaches the rest of the block and stops at its closing brace.

// M2: read a variable, and evaluate a block by threading a
// scope that each `let` extends — scope = scope.extend(x, v)
Expr::Var(..)   => todo_m2!("look up a variable"),
Expr::Block(..) => todo_m2!("evaluate a block"),

That the environment is never rewritten is the rule the whole chapter turns on. $\rho$ is read-only: a let adds a binding, and rebinding a name adds a new binding that shadows the old one, which is left as it was. Making a name’s value change over time — a counter that counts — is a separate mechanism, a mutable cell held in the store, and it arrives in Part IV. How a name’s binding is fixed by where it is written, the property that makes scope decidable before the program runs, is the next chapter; how an Env is represented, and what lookup costs as scopes nest, is the chapter after. Reading variables and evaluating blocks completes the evaluator’s work for Milestone M2.

The design space

let need not be a form of its own. Landin’s observation was that a block beginning let x = e_1; computes what applying the function $\lambda x.e$ — whose body $e$ is the rest of the block — to the argument $e_1$ computes: both evaluate $e_1$, bind the result to $x$, and evaluate that body in the extended environment. A language with functions can treat let as sugar for that application and carry one rule instead of two. Bridger keeps let a form in its own right — functions arrive in Part V, and let is available from the first block a program writes — but the two describe the same binding, and the closure rule in Part V will extend the environment the same way $\text{E-Let}$ does.

Whether a name is in scope within its own right-hand side is a genuine fork, and $\text{E-Let}$ takes a side: it evaluates $e_1$ in the environment before the binding is added, so x is bound only after its definition has been evaluated. A definition may therefore use the earlier meaning of a name it rebinds, and a let-bound function cannot call itself, since the name is not in scope while the function value is being built. Languages that want a let to bind a recursive function offer a separate recursive-binding form — let rec, or a letrec that binds the name over its own right-hand side — that closes exactly this gap. In Bridger, self-reference goes through a top-level fn, where every top-level name is in scope in every definition, so functions may call themselves and each other regardless of order.

Rebinding a name that is already in scope is a choice too. Bridger allows it — shadowing is ordinary — where some languages reject a second binding of a name in the same scope and require the programmer to choose a fresh one. Allowing it lets a block reuse a name for a series of related values; rejecting it turns an accidental reuse into an error the compiler catches. The tradeoff is between a convenience and a class of mistake, and Bridger takes the convenience.

Further reading

The environment and let: Peter Landin’s The Mechanical Evaluation of Expressions (The Computer Journal, 1964) introduces the SECD machine, whose environment component is the structure a variable is resolved against, and The Next 700 Programming Languages (Communications of the ACM, 1966) introduces ISWIM and its let and where notations for naming a value over a region of an expression, together with the reading of a local definition as a function applied to its right-hand side.

The environment model of evaluation: Abelson and Sussman’s Structure and Interpretation of Computer Programs (MIT Press, free online) develops evaluation as the extension of environments in its chapter of that name, working through how a binding form adds to the environment and how a name is looked up in it.

Concept checks

Lexical Scope

The environment is a runtime object: it is built as a program runs, growing by a binding each time evaluation meets a let and reverting to what it was when a block ends. Which value a name reads therefore depends on how far the program has run. Yet the question this chapter asks has an answer that does not wait for the program to run at all. In the following code block,

{
    let x = 1;
    let y = { let x = 2; x + 10 };
    x + y
}

the name x inside the inner block reads 2 and the x on the last line reads 1, and that interpretation is settled by determining which binding each reference to x refers to by reading the braces, without evaluating anything. Every use of a name in a program refers to one definite binding, and that binding is fixed by where the use is written. Determining a name’s binding from the shape of the program text, ahead of running it, is lexical scope (also called static scope), since the binding is settled before, and independently of, any execution.

Free and bound occurrences

For every occurrence of a name (one location where the name is written and read), we say the occurrence is bound in an enclosing block of code when that block contains a let binding for the name somewhere before the occurrence; otherwise, the occurrence is free in that block. In the following block of code,

{ let x = 2; x + 10 }

the occurrence of x in x + 10 is bound: the let x = 2 that precedes it in the same block is the binder that x is bound to. However, in the following block of code without the let binding,

x + 10        // x is free here — nothing in this fragment binds it

the occurrence of x is free, because the region under consideration no longer contains the let that bound x. Whether an occurrence is free or bound is relative to the region you are reading. A let binding reaches inward over the text it encloses, and an occurrence of a name is bound exactly when it falls inside the reach of a binder that binds its name.

The scope of a binding

The scope of a binding is the region of program text over which its name refers to it. For a let binding, the rule E-Let already fixed that region: a let extends its scope over the rest of its block, so the binding’s scope runs from just after the let binding to the closing brace of the block that holds it. This is the arrangement of Algol 60’s block structure — a name declared inside a region means something there and nowhere else — and it is what gives a block-structured program its nesting of scopes, each one the text between a binder and the brace that closes over it.

Scopes nest because blocks nest. An occurrence lies within the scope of a binding when it falls inside that binding’s region — the text from the let to the closing brace of its block, nested sub-blocks included. An occurrence can lie within the scopes of several bindings of the same name, one nested inside another; it is then bound by the innermost binding (the binding whose scope is the smallest) of the same name.

In the margin, each binding’s scope is drawn as a bar in its own colour. let x = 1 reaches over the rest of the outer block, but its bar breaks along the x + 10 line, where the inner let x = 2 binds x, its scope drawn by the orange bar. That break is a hole in the outer binding’s scope. We say that the innermost binding of x shadows the outer binding of x. The x in x + 10 lies inside both blocks and resolves to the orange binding; on the x + y line, past the inner block, the outer (blue) binding is in force again, so that x reads 1. let y reaches only the final line x + y, the one place y can be read, so its green bar covers just that row.

The rule for reading a program is uniform. An occurrence of a name refers to the binding of the nearest binder that encloses it — nearest meaning the smallest enclosing region that contains both the occurrence and a binder for the name. When no binder encloses it, the occurrence is free, and a name still free at the top of a program has no binding to resolve to: evaluating it results in an UnboundVariable error. None of this appeals to a value, an input, or how far the program has run. The binding each occurrence refers to is a function of the program text alone, which is why it can be read from the program’s text itself (without ever executing the program) — and why the word for the discipline is lexical, from the arrangement of the text itself.

Lexical scoping as a property

In Bridger, nothing new is added to the evaluator to enforce lexical scoping; instead, lexical scoping of let bindings is a property of the Milestone M2 semantic rules that were already described in the previous chapter. The E-Let rule extends the environment over the textual remainder of the block, and E-Var reads whatever environment has been threaded to the point of the occurrence: so the binding a variable finds at run time is the one the enclosing text put there.

The two views line up because the environments built at run time take the shape of the text. Each block is evaluated by extending the environment it was entered in, and a block is entered from the environment of the text that surrounds it, so at any point during the run the environments form a chain of children whose nesting matches the blocks that enclose that point in the source. Looking a name up — reading the current environment, then its parent, and outward — visits the same bindings, in the same order, as reading outward from the occurrence through the blocks that enclose it. The run-time lookup and the reading off the page cannot disagree, because they walk the same nesting. How that chain is represented, and what walking it costs as scopes deepen, is the topic of the next chapter.

Settling a name’s binding before the program runs is what later work builds on. The same chapter resolves every occurrence to a fixed position in the enclosing scopes, so that a name need not be searched for by spelling at all. And because a name’s binding is fixed by its definition, the type of what it holds can be too, which is what lets the checker in Part VI decide a program’s types without running it.

The design space

A name that is free in a fragment must ultimately resolve somewhere, and there are two disciplines for where. Under lexical scope (the scoping rules that Bridger uses), a free occurrence resolves in the environment that textually encloses it: the environment present where the code is written. Under dynamic scope, it resolves in the environment present where the code runs, the environment active at the moment control reaches the occurrence, which is decided by the execution order of the program.

In a language whose only way to enter a new environment is to enter a block, the code that runs in an environment is precisely the code written inside it, so the two disciplines choose the same binding for every occurrence, and nothing a program can do distinguishes them. They come apart only once a region of code can be carried away from where it was written and run somewhere else (i.e., via a function call from a separate part of the program). A function body mentions names it does not itself bind, and the two disciplines answer differently once its body runs under a call rather than where it was defined. That is where the choice becomes observable, and where Bridger’s commitment to lexical scope is made executable and weighed against the alternative (dynamic scoping); it is the subject of Part V.

Further reading

Block structure: the Report on the Algorithmic Language ALGOL 60 (1960) is where a name declared inside a region of a program is given a region of validity determined by the program’s own nesting — the arrangement this chapter reads scopes off of.

The environment model of scope: Abelson and Sussman’s Structure and Interpretation of Computer Programs (MIT Press, free online) develops evaluation as the extension of environments, and works through how a name is looked up by searching outward through the enclosing scopes.

Concept checks

Environment Representations and Lookup

The previous chapter settled what an environment has to provide: lookup, which reads the value a name is currently bound to, and extend, which produces a new environment binding a name to a value — the two operations Bridger’s lexical scope is built from. A running program reads a variable at nearly every step and enters or leaves a block at many of them, so lookup and extend run constantly, and the way the environment is represented sets what they cost. This chapter opens the representation the Bridger starter repository provides: what the scope chain is made of, and what a lookup costs as the chain deepens. It is the environment your interpreter uses in Milestone M2 to evaluate variables, let bindings, and blocks.

The chain of scopes

In the previous chapter, we learned how to read the value a name was bound to by following lexical scoping rules. How do we make that mechanical? The general intuition we used in lexical scoping was that the value a name was bound to was defined by the innermost let binding for that name next to the occurrence being read. We use that intuition to represent the environment as an immutable linked list of bindings whose head is the innermost binding and whose tail is the outermost binding. Consider the following block of code:

let x = 1;
{
  let y = 2;
  {
    let z = 3;
    x + z
  }
}

On line 6, when we evaluate x + z, the scope has an environment with the bindings x = 1, y = 2, and z = 3. Pictorially, the linked list of bindings would appear as a chain with the innermost binding being z = 3, then y = 2, then x = 1, and finally any environment containing the block of code (e.g., the global/root environment). If we wanted to look up the value of x in the environment, we would walk from the innermost binding (z = 3) rightward until we found a binding for x, or reached the end of the list and reported that x is unbound.

The figure traces that walk for x: a miss at z’s scope, a miss at y’s, and a hit at the third. That walk is E-Var — a name is read by starting at the innermost scope and following the links outward, taking the first binding it finds — and running off the end of the chain without a match is the UnboundVariable case. Because the walk stops at the first match, an inner binding is reached before an outer one of the same name: the walk is what makes shadowing resolve to the innermost binding.

Each extend produces one such scope — a binding and a link to the scope enclosing it — and leaves its parent untouched, because the environment is read-only. A parent is therefore shared by every scope built on top of it, and leaving a block discards only the innermost scope and exposes the chain below it unchanged: a name bound inside a block is out of scope the moment the block ends, because nothing was written that has to be undone.

In Rust, a scope is a small record — a name bound to a value, and a link to its parent:

// A scope: one binding, and a link to the scope that encloses
// it. `Rc` lets a scope be shared — several scopes can hold the
// same parent, and a value can keep a scope alive after the
// block that built it has returned.
struct Scope {
    name:   Name,
    val:    Value,
    parent: Option<Rc<Scope>>,
}

// `extend` puts a new scope in front and leaves its parent as
// it was — the read-only environment of the previous chapter.
fn extend(parent: &Rc<Scope>, x: Name, v: Value) -> Rc<Scope> {
    Rc::new(Scope { name: x, val: v, parent: Some(Rc::clone(parent)) })
}

// `lookup` walks outward: this scope, then its parent, and on
// until the name matches or the chain runs out — a run-out is
// the `UnboundVariable` of the previous chapter.
fn lookup(scope: &Rc<Scope>, x: &Name) -> Option<Value> {
    let mut cur = scope;
    loop {
        if cur.name == *x {
            return Some(cur.val.clone());
        }
        match &cur.parent {
            Some(p) => cur = p,
            None => return None,
        }
    }
}

The parent link is an Rc, a reference-counted shared pointer. A plain owned pointer — one scope owning its parent outright — would be enough while a scope lives no longer than the block that built it and is freed when that block ends. It stops being enough once a value can carry a scope away from its block: a function value keeps the scope it was defined in so it can read its free names when it later runs, and that scope has to stay alive after the block that created it has returned (the subject of Part V). Shared ownership lets the carried-away scope and the chain both hold it, and it lives as long as either does. The reason the chain is refcounted rather than owned lands with closures; the representation is chosen here so that it can.

Each scope holds a single binding because Bridger adds one scope per let, so the chain grows by a link at every binding. A common alternative gives each block one scope holding all of its bindings in a map; a lookup then walks scope to scope and probes the map at each. The distance a lookup travels is measured in bindings one way and in scopes the other, and the walk is otherwise the same.

What a lookup costs

A lookup costs its walk: the number of scopes visited before the binding is found. A name bound in the current block is a step away; a name from an enclosing block is as many steps as the scopes between the use and the binding; a prelude name read from deep inside nested blocks is the length of the whole chain. extend adds a single scope at the front, and discarding a scope drops the innermost link, so growing and shrinking the environment are each a constant-time operation and the cost of the representation sits on lookup.

A different representation moves that cost. A single map from every name currently in scope to its value answers a lookup in one probe, with no walk at all. What it does not get for nothing is the coming and going of scopes: entering a block has to record every name the block shadows, and leaving the block has to put the shadowed values back, so the map carries a stack of shadowed bindings per name, or a snapshot restored on exit. The bookkeeping the chain spends on a lookup, the flat map spends at every scope boundary instead. Which representation costs less depends on whether a program reads variables more often than it opens scopes, or the reverse.

Resolving names before the run

Lexical scope settles which binding an occurrence refers to before the program runs, so the walk’s outcome is fixed ahead of time too: for a given occurrence of a name, the number of scopes to skip before its binding is found is the same on every run, because the nesting of scopes at that point is the nesting of the enclosing blocks, and the text fixes that. Because each scope holds one binding, that count is the whole answer. A name can then be replaced, before the run, by the number of scopes the walk would have crossed, and the reference read by stepping out that many scopes — with no name compared along the way.

That single number is what Nicolaas de Bruijn introduced in 1972: drop the names entirely and write each variable as the distance to its binder — the count of enclosing binders to cross — so a term carries no variable names at all (de Bruijn, 1972). Two terms that differ only in their choice of names become the same term, and shadowing is just a larger distance, so the renaming questions that surround names do not arise. A scope that holds several bindings — the block representation, where one scope carries a whole block’s names — needs a second coordinate on top of the distance: which scope to stop at, and which binding within it. That pair is called lexical addressing, and over a single-binding chain its second coordinate is always zero, leaving de Bruijn’s lone index.

It is the same chain, with x’s spelling replaced by its distance. Because the target is fixed by the text, computing that distance is a pass over the program made before it runs, and once done the run-time lookup steps out a fixed number of scopes, with no name searched for.

Bridger keeps names. Resolving references to coordinates is a pass a tree-walker can do without, and the speed it buys is not what a tree-walker is for; against it, a name is what an error reports. UnboundVariable names the variable, and so do the type errors of Part VI, while a coordinate has no name to hand back. The chain stays keyed by name, and a lookup stays a walk.

The design space

Several choices sit behind the environment, and Bridger has taken a point in each.

Where a lookup’s cost falls. A chain of scopes puts it on the walk and keeps extension and exit cheap; a flat map spends it on save-and-restore at each scope boundary and keeps a lookup a single probe. A program that reads variables far more often than it opens scopes is served by the first; a program dominated by scope changes over shallow lookups by the second.

By name or by position. Keyed by name, a reference is searched for by spelling at run time and every name survives into the running program, where an error can report it. Resolved to a position — a de Bruijn index over the single-binding chain, or the ⟨scope, binding⟩ pair of lexical addressing once a scope holds several — a reference is found without a search, at the price of a resolution pass and of the names an error might have used. This choice is open only because scope is lexical: a language deciding bindings while running could not resolve them before it.

Owned or shared. A singly owned chain is enough while a scope dies with its block. Sharing — Bridger’s Rc — is forced once a value outlives its defining block and has to carry that block’s scope with it, which is what a closure does. Bridger shares from the start, so the chain a block builds can be captured without copying it (Part V).

The one scope not built by an extend is the root, which holds the prelude and the top-level functions. Because those functions may call one another regardless of the order they are written in, the root is assembled by the interpreter’s provided setup before any of them runs, rather than grown a binding at a time the way a block’s scopes are.

Further reading

Nameless variable representations: N. G. de Bruijn’s Lambda calculus notation with nameless dummies (Indagationes Mathematicae, 1972) represents each variable by the distance to its binder, so that terms differing only in their choice of names coincide and renaming is unnecessary — the representation an interpreter borrows when it resolves references to positions.

Lexical addressing: Abelson and Sussman’s Structure and Interpretation of Computer Programs (MIT Press, free online) works through resolving a variable reference to a coordinate — which enclosing scope, and which binding within it — in its treatment of compilation, so that a name is found by position rather than searched for by spelling.

Concept checks

Milestone M2

Environments and Binding

Part III gave the evaluator names. The environment supplies each name’s value, let binds one over the rest of a block, lexical scope fixes how far a binding reaches, and the representation makes a lookup through nested scopes work. This milestone puts them into the evaluator: two arms of eval_expr that read a variable and evaluate a block, and the run of the language grows from single expressions to programs that name their intermediate values.

The codebase, the toolchain, and the build loop are the ones Milestone M1 set up; this milestone adds two arms to the same eval_expr. If you have not built the starter yet, do that first — M1 is required to be completed and correct before this milestone can be completed.

To-dos

grep -rn 'todo_m2!' src lists exactly what this milestone asks for — the two arms left as holes after M1:

// src/interp/eval.rs — the two M2 arms of eval_expr
Expr::Var(..)   => todo_m2!("E-Var"),
Expr::Block(..) => todo_m2!("E-Block / E-Let / E-Seq"),

These are the first arms that consult the env parameter. Through M1 it was carried unused, kept quiet by a let _ = env; at the top of eval_expr; delete that line once an arm reads from env, or the lint will point out that it is now redundant.

Milestone specification

Below each row gives the form, semantic rule, and the value (or error) each new construct this milestone adds:

The full rules are in the Environments chapter; this table is the checklist your evaluator is measured against, not a second statement of them.

Two contracts hold across the block. The environment is read-only: a let never rewrites an existing binding — it adds one that shadows the old, so the nearest binding of a name wins — and extend produces a child scope while leaving its parent untouched. That is why a binding reaches exactly the rest of its block and no further: the scope a block grows is discarded when the block ends, and the caller’s environment is the one it started with. And a block aborts at a stuck item: if an item gets stuck, the ? carries the error straight out with that item’s span, and the items after it never run.

Implementing Milestone M2

Destructure each arm’s .. into the fields you need. The two M2 variants and what they carry:

A block’s items are Stmt values, of two kinds:

enum Stmt {
    Let(Name, Option<Ty>, Expr, Span),   // a binding; the Option<Ty>
    Expr(Expr),                          // is an annotation, ignored here
}

The Option<Ty> on a Let is an optional type annotation; the evaluator ignores it — it is read by the type checker we implement in Part VI.

Two tools do the work of both arms:

• Look a name up with env.lookup(name), which returns Some(v) when the name is in scope and None when it is not. A miss is the stuck case: return RuntimeError::UnboundVariable { name, span }, carrying the offending variable’s own span.
• Extend a scope with env.extend(name, value), which returns a new environment with one more binding and leaves the one it was called on unchanged.

A block threads that second tool through its items. Start from env, and walk the items in order: a Stmt::Let evaluates its right-hand side in the current scope and then extends the scope with the new binding for the items that follow; a Stmt::Expr evaluates its expression in the current scope and drops the value. The trailing expression, if there is one, is evaluated in the scope the items built and is the block’s value; a block with no trailing expression is Value::Unit. Because extend returns a child rather than mutating in place, the growing scope is local to the block — nothing you do to it reaches the environment the block was entered with.

E-Var you have already seen worked in the Environments chapter’s build section; the block arm is the same environment threading that chapter describes, carried out one item at a time.

Worked examples

An expression, the environment it needs, and the value it evaluates to:

x            (x bound to 5)          ⇓ 5
{ let x = 2; x + 3 }                 ⇓ 5
{ let x = 1; let x = x + 1; x }      ⇓ 2      (shadowing)
{ 1; 2; 3 }                          ⇓ 3      (the trailing expression)
{ let x = 5; }                       ⇓ ()     (ends in a binding)
{ }                                  ⇓ ()

And expressions with no value, which halt the run:

y            (y unbound)             ⇓ stuck  (UnboundVariable)
{ { let x = 1; x }; x }              ⇓ stuck  (x's scope ended at the inner })
{ z; 1 }                             ⇓ stuck  (z unbound; the block aborts at z)

How to know it works

cargo m2 runs the provided milestone M2 tests, and — because the milestones are cumulative — the M1 tests along with them, so a change that breaks the expression fragment shows up here too. Each test builds an Expr and checks the Value it evaluates to, or, for a stuck test, the error’s variant and the span it blames. The builders var, block, let_, and expr_stmt join the M1 ones, and env_with and eval_in evaluate an expression under a starting environment, so a check reads close to the rule it exercises:

// { let x = 2; x + 3 }  ⇓  5
let b = block(vec![let_("x", int(2, 1), 0)],
              Some(binary(Add, var("x", 2), int(3, 3), 4)), 5);
assert_eq!(value_of(&b), Value::Int(5));

// x, with x bound to 5, reads its binding
let env = env_with(&[("x", Value::Int(5))]);
assert_eq!(eval_in(&var("x", 0), &env).unwrap(), Value::Int(5));

// y is unbound: UnboundVariable at its span
assert!(matches!(stuck(&var("y", 3)),
    RuntimeError::UnboundVariable { .. }));

Fill an arm, run cargo m2, and repeat until every M2 test — and every M1 test — passes.

Design problems

Expressions, Statements, and Blocks

Part II focused on how to evaluate a literal expression to a value. Part III extended the language we consider to programs that bound values to names and used those names within expressions. A program built only from those parts returns a single value. This part introduces constructs that do something when they are evaluated: e.g., r := r + 1 changes the value a memory cell holds, a while loop repeats the actions of its body, an if takes one of two branches. Each raises a question the earlier forms never did — what is the value of a construct that does something?

Two answers are in wide use. A language can treat such a construct as a statement: a form executed for its effect, in a category apart from expressions, carrying no value and unable to be used where a value is required. Or it can treat it as an expression like any other, evaluated for a value even when the reason to write it is the effect. The choice runs through the whole language: its grammar, its evaluator, and later its type checker. In this chapter, we detail the choice we make in Bridger.

Effects

An effect is a change a construct makes when it runs that a later step can observe, over and above whatever value the construct computes. Assigning to a memory cell is one: r := e overwrites what the cell holds, and code that reads the cell afterward finds the new value where the old one had been. Printing a line to a screen is an effect; so is reading input from a keyboard or a file, writing a file, and sending or receiving bytes over a network connection. What these share is that running the construct leaves something changed — a cell, the screen, a file, a machine across the network — in a way that persists past the evaluation and sets the run apart from one in which the construct never ran.

Bridger’s built-in effect is mutation. A program changes state by writing a value to a memory cell with r := e, and that cell’s contents are what a later read observes; the cell and the assignment that writes it are the subject of the next chapter. Bridger also includes built-in functions for printing and reading primitive values; however, Bridger does not support reading or writing to files and network connections. This part focuses on creating, modifying, and reading mutable memory cells and the control flow required to compute using these primitives. This chapter examines the question of how to combine constructs for expressing value expressions and effectful computations.

Where languages draw the line

Fortran and Algol 60 drew a firm boundary between the two. An expression — a + b, f(x) — appeared inside a statement, and a statement — an assignment, a loop, a jump — was a different kind of thing: it produced no value and could not appear where a value was expected. A program was a sequence of statements, and expressions were the material they were built from. The conditional came twice over, once in each category: a conditional expression that chose between two values, and an if statement that chose between two courses of action.

Algol 68 lowered the boundary. Its report built a program out of units, each with a value and a type, and gave the value of a construct written for its effect a type of its own, void; an assignment and a loop were units like any other, and a place where a statement had stood became a place holding a void-valued expression (van Wijngaarden et al., 1976). Lisp had been built from expressions since 1960; Algol 68’s contribution was to carry that arrangement into the imperative, block-structured line Fortran and Algol 60 had established, and to name the value a construct leaves behind when its point was the effect. That value, and the decision of where to draw the line between value-expressions and statements, are the focus of the rest of this chapter.

The value of an effectful form

A construct run for its effect still has to fit into a language built from expressions: if it may stand where a value is expected, it has to produce one. The value that carries no information is the one to hand back, since there is nothing to report except that the work was done. Bridger’s unit type, whose single value is written (), plays that part. Assignment r := e yields (); a while loop yields (); an if with no else yields (). Unit arrived in Part II described as the value of a statement; a statement is the kind of form that produces it.

Unit is what lets the expression grammar absorb the effectful forms without a special case. A while loop has a value, so it may appear as a block item, as the right-hand side of a binding, or anywhere else an expression may go; its value happens to be the one that says only “done.” One category of form covers both the computations that report a result and the ones that report their completion.

Where Bridger draws the line

Almost every construct in Bridger is an expression with a value. if, match, while, for, and a block { … } all evaluate to something, so any of them may be used where a value is expected:

let n = if x > 0 { x } else { -x };

binds n to whichever branch is taken. The forms whose purpose is an effect are expressions too, and their value is (). So the statement category, which in Algol 60 held assignments and loops and conditionals, is nearly empty in Bridger — those forms have moved into the expressions.

What remains of a statement lives inside a block. Blocks arrived in Part III as the vehicle for binding; read now as the construct that sequences a program’s steps, a block is a sequence of items followed by an optional trailing expression. Each item is either a let or ref binding, or an expression closed with ;, which runs the expression and discards its value. The trailing expression, written with no ;, is the block’s value; a block with no trailing expression has the value ().

block       ::= '{' { block_item } [ expr ] '}' ;
block_item  ::= let_binding | ref_binding
              | ( if_expr | match_expr | while_expr | for_expr | block ) [ ';' ]
              | expr_stmt ;
expr_stmt   ::= expr ';' ;

The ; is the whole of what makes an expression a statement here: f() in a block is an expression whose value becomes the block’s value if it is last, and f(); is that same expression run for its effect with its value thrown away. The rules that evaluate a block — an item threaded for effect, the trailing expression as the value, an empty block as () — are the ones stated in Part III; they need no addition for this part.

The two forms that stay out of the expression grammar are the let and ref bindings. A binding is an item of a block and never an expression, so

let x = let y = 0;   // does not parse

is rejected: the right-hand side of a let must be an expression, and a let is not one. The line sits there because a binding’s work is to extend the environment over what follows it, and only a block supplies a “what follows.” A bare let x = 5 with no surrounding block would bind x over nothing and have no value to give; keeping it an item of a block is what makes its scope well defined. return stays outside the operator grammar as well — it is an expression, but one that abandons the enclosing function rather than yielding a value in place, and it travels by the same Control path the interpreter already uses for errors.

Building it

The provided evaluator has a single entry, eval_expr, returning a Value; there is no eval_stmt beside it. A block is one arm of that function, and a statement is a shape it walks rather than a thing evaluated to a value of its own:

// A block is statements then an optional trailing expression,
// which is the block's value; a statement is a binding or an
// expression run for its effect.
Expr::Block(Vec<Stmt>, Option<Box<Expr>>, Span)

enum Stmt {
    Let(Name, Option<Ty>, Expr, Span),   // a binding
    Expr(Expr),                          // run for effect
}

A Stmt::Expr(e) evaluates e and drops the value; a Stmt::Let evaluates the right-hand side and extends the environment over the rest of the block, exactly as let does. Because assignment, loops, and conditionals are ordinary expressions, they are evaluated by the same arms that handle 2 + 2, and the evaluator needs no second traversal for a category of forms that produce no value. Drawing the line low collapses two kinds of evaluation into one.

The same economy reaches the type checker in Part VI: one judgment $\Gamma ⊢e:\tau$ assigns a type to every form, with the effectful ones typed (), where a language with a statement category needs a second judgment for the forms that have no type to assign. Collecting the rules this part contributes is the work of Milestone M3.

The design space

C and Java keep the Algol 60 boundary. An if is a statement with no value, so choosing between two values calls for a separate expression-level form, the conditional operator c ? a : b; the language carries two conditionals because the statement one cannot be used where a value is wanted. Assignment goes the other way: in C a = b is an expression with a value, which is what lets if (x = 0) compile as a test — an assignment mistaken for a comparison. The split forces some forms to be duplicated across the two categories and lets others slip between them.

ML, Ruby, and Rust draw the line low, as Bridger does. In ML an if is an expression and a sequence yields its last value; Ruby lets nearly every construct return a value. Rust is the model Bridger follows most closely: it is expression-oriented, yet a let is a statement, a block’s trailing expression with no ; is the block’s value, and a ; discards. Bridger’s blocks work the same way, down to let being a block item rather than an expression. The Algol 68 arrangement of the previous section is the older member of this family; its void is the role Bridger’s () fills.

What the low line costs is a reader’s expectation that an assignment or a loop is “just a statement”: here each has a value, and a stray while where an Int was wanted is a type error against () rather than a syntax error. What it buys is a single expression grammar, a single evaluator, and a single typing judgment, with the unit type carrying the forms whose only result is that they ran. The bindings are the one place the line is drawn above the expressions, and they are drawn there because a binding means nothing except over a region that follows it.

Further reading

Expression-oriented languages: the Revised Report on the Algorithmic Language ALGOL 68 (A. van Wijngaarden and colleagues, 1976) builds a program from units carrying a value and a type and introduces the void type for a construct evaluated for its effect, the arrangement Bridger’s unit type follows. The Rust Reference describes the expression-oriented model Bridger adopts most directly — expressions and expression statements, the trailing expression of a block as its value, and let as a statement — in its chapter on expressions. The reading of a local binding as a function applied to its right-hand side, from Landin’s ISWIM, is in Part III.

Concept checks

Mutation and References

A let binds a name to a value, and the binding does not change: within its scope the name denotes that one value, and Part III built the environment so that looking the name up always finds it. A program that only binds and reads can compute a result, but it has no way to express a quantity that changes over time while the name that refers to it stays put — a counter that climbs, a running total a loop adds into, a balance that a deposit raises. Each of those is one thing, referred to by one name, holding a different value at a later moment than it held before.

The environment cannot supply that on its own. It maps a name to a value once, when the name is bound, and a later read of the name returns the same value; rebinding the name with a second let creates a new, separately scoped binding rather than altering the first. What changes over time has to live somewhere the environment points at rather than somewhere it is — a cell whose contents a program can overwrite, with the name holding the cell rather than the contents. This chapter introduces that cell. It is the mutation the previous chapter named as Bridger’s one built-in effect; here are the forms that create a cell, read it, and write it, and the addition to the evaluation judgment that lets a written value be read back later.

Origins of mutable cells

Two traditions answer the question of what a name denotes, and they place mutation differently.

In Fortran, Algol 60, and their descendants C and Java, a variable is a mutable cell, and the name and the cell are the same thing. Writing x = x + 1 reads the cell the name x denotes, adds one, and stores the result back into that same cell; the name does not acquire a new binding, the cell it has always named has the value it contains overwritten. Assignment to a variable is the primitive action, and every variable is a memory cell a program can read or write.

The functional tradition places it elsewhere. In Lisp and in Landin’s ISWIM, the reading of let the book took in Part III treats a binding as a fixed association between a name and a value; a name, once bound, denotes its value for the extent of its scope and is never modified. A language built only from that has no mutation at all. Standard ML reconciled the two by keeping the binding immutable and adding a separate kind of value — a reference cell, a box allocated on demand, whose contents a program may read and overwrite while the binding that holds the box stays fixed. Mutation moves out of the binding and into a value the binding refers to. Bridger follows that split: a let binds once and for all, and a program that needs a value to change asks for a cell and mutates the cell.

The store

A cell needs somewhere to live. The environment already maps names to values and does not change an existing entry, so the cells go in a second map, the store, written $\sigma$: a finite map from locations to values. A location, written $\ell$, is the identity of one allocated cell — a value in its own right, the thing a name holds when it refers to a cell. The environment maps a name to a value; the store maps a location to a value; and a name bound to a cell is a name the environment maps to a location that the store, in turn, maps to the cell’s current contents.

The store changes as a program runs, so evaluation has to carry it. The judgment grew in Part III from $e\Downarrow v$ to $\rho ⊢e\Downarrow v$ when names arrived; it grows again here to thread the store through the evaluation, taking one store in and handing one store out:

$$\rho ⊢⟨e,\sigma ⟩\Downarrow ⟨v,{\sigma }^{\prime }⟩$$

read as: in environment $\rho$, evaluating $e$ against the store $\sigma$ yields the value $v$ and leaves the store ${\sigma }^{\prime }$. The environment goes in but does not come back — evaluating an expression cannot change what a name is bound to — while the store goes in and comes out, because evaluating an expression can change what a cell holds. (The reference’s full judgment threads one more component, the relation database $\Delta$ of Part VII, and carries the extra outcome a return produces; this part uses the env-and-store slice.)

Every rule now threads the store, and the threading fixes the order in which subexpressions run. A form with two operands evaluates the first against the incoming store, then the second against the store the first handed out, then combines the results — left to right, each step’s output store the next step’s input:

$$\frac{\rho ⊢⟨e_1,\sigma ⟩\Downarrow ⟨v_1,{\sigma }_1⟩\rho ⊢⟨e_2,{\sigma }_1⟩\Downarrow ⟨v_2,{\sigma }_2⟩v_1,v_2\in \mathbb{Z}}{\rho ⊢⟨e_1+e_2,\sigma ⟩\Downarrow ⟨v_1+v_2,{\sigma }_2⟩}(\text{E-Add})$$

Addition takes the store in and passes it along unchanged in the sense that it writes nothing of its own, but it still threads it: if evaluating $e_1$ allocates a cell, $e_2$ evaluates against the store that already holds it. Part II left the order of +’s operands open, observing that it could be fixed once effects existed; the threaded store is what fixes it. Most forms are like +: they thread the store to pin down order and hand it back untouched. Three forms change it.

Creating, reading, and writing a cell

Bridger writes the three operations as ref e, deref e, and e1 := e2.

ref e allocates a fresh cell holding the value of e, and the cell — its location — is the value the form returns. The rule evaluates e, picks a location not already in use, and extends the store so that the new location maps to the value:

$$\frac{\rho ⊢⟨e,\sigma ⟩\Downarrow ⟨v,{\sigma }_1⟩\ell \notin \mathrm{dom}({\sigma }_1)}{\rho ⊢⟨\text{ref}e,\sigma ⟩\Downarrow ⟨\ell ,{\sigma }_1[\ell \mapsto v]⟩}(\text{E-Ref})$$

The value handed back is $\ell$, the location, not $v$; a program keeps the cell by binding the location to a name, let counter = ref 0.

deref e reads a cell. It evaluates e to a location and returns what the store maps that location to, leaving the store as it found it:

$$\frac{\rho ⊢⟨e,\sigma ⟩\Downarrow ⟨\ell ,{\sigma }_1⟩\ell \in \mathrm{dom}({\sigma }_1)}{\rho ⊢⟨\text{deref}e,\sigma ⟩\Downarrow ⟨{\sigma }_1(\ell ),{\sigma }_1⟩}(\text{E-Deref})$$

e1 := e2 overwrites a cell. It evaluates e1 to the location to write, then e2 to the value to store there, then updates the store at that location and returns () — assignment is an effect, and its value is the unit that reports only that the effect happened, exactly as the previous chapter described for the effectful forms:

$$\frac{\rho ⊢⟨e_1,\sigma ⟩\Downarrow ⟨\ell ,{\sigma }_1⟩\rho ⊢⟨e_2,{\sigma }_1⟩\Downarrow ⟨v,{\sigma }_2⟩\ell \in \mathrm{dom}({\sigma }_2)}{\rho ⊢⟨e_1:=e_2,\sigma ⟩\Downarrow ⟨(),{\sigma }_2[\ell \mapsto v]⟩}(\text{E-Assign})$$

The order is the cell first, then the value written into it. It is visible when both sides have effects of their own: in (f()) := (g()), f runs before g, because e1 is evaluated against the incoming store and e2 against the store e1 produced. A cell together with these three forms is enough to count:

let counter = ref 0;
counter := deref counter + 1;
deref counter                  // 1

ref 0 allocates a cell holding 0 and binds counter to its location. The assignment reads the cell (deref counter is 0), adds one, and writes 1 back into the same cell; the location counter holds has not changed, its contents have. The trailing deref counter reads the cell again and finds 1. This is the shape a while loop repeats to accumulate a result across its iterations, which is why the cell arrives before the loop that needs it.

A location is a value like any other, so it can be read from a cell, passed to a function, or returned — and two names can end up holding the same location:

let a = ref 0;
let b = a;                     // b holds the same location as a
a := 1;
deref b                        // 1

let b = a binds b to the value a holds, which is a location, so a and b name one cell. Writing through a changes the cell both refer to, and reading through b finds the new value. This is aliasing: two names for one mutable cell, so that a write reached by one name is observed through the other. It follows directly from a name holding the location rather than the contents, and it is what makes shared mutable state — and structures that point at each other — expressible. It is also what makes a program with mutation harder to reason about than one without, since a write here can be a change seen there; Part V returns to the style that keeps mutation scarce for that reason.

Building it

The store is a piece of interpreter state beside the environment. The provided runtime supplies it as a Store with three operations — allocate a cell and get back its location, read a location, and write a location — and a location is a small handle that a Value can carry:

Value::Ref(Loc)                // a value that is a location in the store

impl Store {
    fn alloc(&mut self, v: Value) -> Loc;   // E-Ref: fresh cell, gives its location
    fn read(&self, l: &Loc) -> Value;       // E-Deref: the cell's contents
    fn write(&mut self, l: &Loc, v: Value); // E-Assign: overwrite the cell
}

The three forms are three arms of eval_expr. ref e evaluates e and calls alloc, returning Value::Ref of the location. deref e evaluates e to a Value::Ref(l) and returns store.read(&l). e1 := e2 evaluates e1 to a Value::Ref(l), then e2 to a value, calls store.write(&l, v), and returns Value::Unit; a deref or := whose operand is not a location is a runtime type error, the store’s stuck case. The rules thread a store in and a store out; the interpreter instead keeps the one store on the interpreter and mutates it in place, so alloc and write are the step from $\sigma$ to ${\sigma }^{\prime }$ — the threading made physical. A cell, once allocated, is never reclaimed: the store only grows, matching E-Ref, which always takes a fresh location and never reuses one. When the store is read back as a space cost, that choice returns as a subject in Part X.

The surface form ref x = e is not a new binding. It reads as let x = ref e: allocate a cell for e and bind x to its location. It earns its own keyword because binding a name to a fresh cell is the common case and ref x = 0 says it more plainly than let x = ref 0, but the parser expands it to the let and the evaluator sees only the two forms it already has.

The type a reference carries, written ref<τ> for a cell holding values of type τ, and the rules that keep deref and := from being applied to a non-location before the program runs, are the subject of the type checker in Part VI. The evaluator here admits any location where one is required and reaches its stuck case at runtime when handed something else.

The design space

The three languages that keep the Algol boundary of the previous chapter also keep the variable-as-cell model. In C, Java, and Python a plain variable is mutable: x = e reassigns the name, and there is no separate word to allocate a cell or to read one, because every variable already is one. What Bridger writes as ref/deref/:= is, in those languages, the unmarked default state of every name. Aliasing is present there too, carried by pointers or object references, and it is likewise implicit — two variables may refer to one object with nothing in the syntax to say so.

ML draws the line where Bridger does: a binding is immutable, a reference cell is a separate value created by ref and reached by an explicit read and write, and a mutation site is visible in the program as one of those operations. The cost is the two extra words, ref and deref, on every use of a cell; what they buy is that a name not bound to a ref cannot be assigned into at all, so the places a program mutates are exactly the places those words appear.

Rust marks mutation on the binding but restricts the sharing. A let is immutable and let mut makes a rebindable variable, closer to the variable-as-cell model; sharing goes through borrows, & and &mut, and the compiler’s rules forbid a mutable borrow to coexist with any other borrow of the same value, so the aliasing that Bridger and ML permit freely is the case Rust’s borrow checker exists to rule out. Bridger takes ML’s first-class cell rather than Rust’s borrowing because a cell that is an ordinary value needs no second discipline layered over the language — one immutable let binds cells and non-cells alike, and a location is passed, stored, and compared like any other value. What that leaves on the table is the compiler-checked guarantee against data races and aliased writes that Rust’s rules provide; Bridger permits the aliasing and asks the programmer to manage it.

Across the three, the decision is where a program says “this can change”: on every variable by default, on a binding marked mut, or on a value obtained through ref. Bridger’s answer keeps the binding immutable and names the cell, so that the environment of Part III is left exactly as it was and everything that changes over time lives in the store.

Further reading

Reference cells and the store: The Definition of Standard ML (Robin Milner, Mads Tofte, Robert Harper, and David MacQueen, revised edition, 1997) gives the reference cell — ref, !, and := — its formal semantics over a store, the model Bridger’s cell follows. Benjamin Pierce’s Types and Programming Languages (2002) devotes its chapter “References” to building mutable cells on top of a pure calculus: the store as a map from locations to values, the evaluation relation threaded through it, and the typing of Ref T, in the same order this part and Part VI take them. The variable-as-cell model, for contrast, is described in the “References” and ownership chapters of The Rust Programming Language, where mutability is a property of a binding and a borrow rather than a value, and the borrow checker rules out the aliased writes the store model here permits.

Concept checks

Conditionals and Loops

The previous chapter gave a program a cell whose contents change: a value can be written where an earlier one stood, and a later read finds the new one. Writing one assignment changes the cell once. A program that sums the numbers in a list, or counts up to a bound, or halves a number until it drops below one, changes a cell a number of times it does not know when it is written, and decides each time whether to change it again. Two forms are missing. One chooses whether to act according to a value; the other repeats an action. This chapter adds the conditional if and the loops while and for.

Their category is already settled. The opening chapter of this part placed if, while, and for among the expressions: an if takes the value of the branch it runs, and a loop takes the value (), since a loop runs for the effect its body has on the store rather than for a result. What that chapter left open, and this one fixes, is what each evaluates to — the rules that pick a branch, and the rules that repeat one. The store threads through them as it threads through every form now, one store in and one store out, env ⊢ ⟨e, σ⟩ ⇓ ⟨v, σ'⟩. (The reference’s rules thread the relation database of Part VII and carry the outcome a return produces; this part uses the env-and-store slice mutation.md introduced.) The rules below are written with the keyword forms if e then e else e and while e e; the concrete syntax braces them, if c { … } and while c { … }, with no then.

Choosing a branch: if

The conditional is among the oldest control forms, and its shape changed as languages moved the choice into the program’s expressions. Fortran’s conditional was the arithmetic IF: IF (e) n1, n2, n3 jumped to one of three statement labels according to whether e was negative, zero, or positive — a branch to a label, decided by a sign. Algol 60 gave the if c then S else S that chooses a course of action in place, named by the condition being true or false, and set beside it a conditional expression that chooses between two values — the two-form split the first chapter of this part traced. Bridger keeps the single expression form: one if, valued by the branch it takes.

if evaluates its condition to a boolean, then evaluates the chosen branch against the store the condition produced. The other branch is not evaluated, so only the taken branch’s effects happen:

$$\frac{\rho ⊢⟨e_1,\sigma ⟩\Downarrow ⟨\text{true},{\sigma }_1⟩\rho ⊢⟨e_2,{\sigma }_1⟩\Downarrow ⟨v,{\sigma }_2⟩}{\rho ⊢⟨\text{if}{e}_1\text{then}{e}_2\text{else}{e}_3,\sigma ⟩\Downarrow ⟨v,{\sigma }_2⟩}(\text{E-If-True})$$

$$\frac{\rho ⊢⟨e_1,\sigma ⟩\Downarrow ⟨\text{false},{\sigma }_1⟩\rho ⊢⟨e_3,{\sigma }_1⟩\Downarrow ⟨v,{\sigma }_2⟩}{\rho ⊢⟨\text{if}{e}_1\text{then}{e}_2\text{else}{e}_3,\sigma ⟩\Downarrow ⟨v,{\sigma }_2⟩}(\text{E-If-False})$$

The condition threads its store into the branch, and the branch hands the store out; a write the condition makes is in place when the branch runs, and a write the branch makes is what the whole if leaves behind. The value the if yields is the branch’s value, which is what lets it stand where a value is wanted:

let n = if x > 0 { x } else { -x };

Because the whole form has one value, its two branches have to agree on a type — the result is the value of one branch or the other, and one form carries one type. That agreement is a typing rule, checked before the program runs; it is the subject of the type checker, and the evaluator here runs whichever branch the condition selects without consulting it.

An if may drop its else:

if x > 0 { print(x) };

runs its branch when the condition holds and does nothing when it does not. The form still has a value on both paths, so the missing branch has to supply one, and the only value the language can supply without a branch to evaluate is (). An else-less if reads as if e1 then e2 else () and is admitted only when its branch is itself ()-valued, so that both paths agree; a one-armed if whose branch produced an Int would have no matching value to give when the condition is false. Chained conditions are the else holding another if, if c1 { … } else if c2 { … } else { … }, which the grammar reads as an if in the else position rather than a new form.

Building it

if is one arm of eval_expr, matching the provided Expr::If node — a condition, a then-branch, and an Option for the else-branch that is absent in the one-armed form:

Expr::If(Box<Expr>, Box<Expr>, Option<Box<Expr>>, Span)

The two E-If rules say what the arm does: evaluate the condition, and on a Value::Bool evaluate the branch that boolean selects, leaving the other unevaluated; when the else-branch is absent and the condition is false, the value is Value::Unit. A condition that evaluates to anything but a boolean is a runtime type error, the conditional’s stuck case, ruled out ahead of time once the type checker of Part VI is in place.

Repeating an action: while

Repetition began as an arrangement of jumps. Early machine code and Fortran repeated work by testing a value and jumping back to a label with GO TO; the loop existed in how the jumps were placed rather than as a form the language named, and Fortran’s counting DO was the one repeat given a construct of its own. Structured programming replaced the placed jumps with constructs that control enters and leaves at a single point, so the repeat becomes a form in the grammar: the while that tests a condition and runs its body again as long as the condition holds. Dijkstra (1968) argued for retiring the GO TO in favor of such constructs, and Böhm and Jacopini (1966) had shown that sequence, selection, and iteration alone express any flowchart, so a language with if and while can describe any control a program of jumps could. Bridger’s while is that structured loop.

while needs the mutation of the previous chapter to do anything. Its condition is evaluated afresh each time around, and a re-evaluation can give a different answer only if something the condition reads has changed; without a store to change, a while whose condition starts true stays true and never stops, and one that starts false never runs. Ordering mutation before the loop is what lets the loop’s body move the condition toward false — a counter the body steps, a total it adds into, a list it shortens.

Two rules define it. When the condition is false the loop stops, yielding () and the store the condition produced:

$$\frac{\rho ⊢⟨e_1,\sigma ⟩\Downarrow ⟨\text{false},{\sigma }_1⟩}{\rho ⊢⟨\text{while}{e}_1{e}_2,\sigma ⟩\Downarrow ⟨(),{\sigma }_1⟩}(\text{E-While-False})$$

When it is true the loop runs the body, discards the body’s value, and then runs the same while again against the store the body left:

$$\frac{\begin{array}{c}\rho ⊢⟨e_1,\sigma ⟩\Downarrow ⟨\text{true},{\sigma }_1⟩\\ \rho ⊢⟨e_2,{\sigma }_1⟩\Downarrow ⟨v,{\sigma }_2⟩\\ \rho ⊢⟨\text{while}{e}_1{e}_2,{\sigma }_2⟩\Downarrow ⟨(),{\sigma }_3⟩\end{array}}{\rho ⊢⟨\text{while}{e}_1{e}_2,\sigma ,⟩\Downarrow ⟨(),{\sigma }_3⟩}(\text{E-While-True})$$

The third premise is a derivation of the very form the rule concludes. Every rule up to here broke a form into strictly smaller parts, and a derivation bottomed out when the parts were literals; this one names its own conclusion among its premises, and the store is what makes the naming finite. Each turn of the loop derives the next against a store the body has moved, and a run that reaches a false condition is a finite stack of E-While-True closed at the top by E-While-False. A loop whose condition never becomes false has no such finite stack — and so no derivation, and no value — which is the rule’s way of saying that a loop that never stops computes nothing to hand back. The store carries the difference between the two cases.

The counter the previous chapter allocated is what a while drives:

let counter = ref 0;
while deref counter < 3 {
  counter := deref counter + 1
};
deref counter                  // 3

counter holds a cell starting at 0. Each turn reads the cell, and while it is below 3 the body writes back one more; the store the body leaves is the store the next condition reads, so deref counter < 3 is true, true, true, false across four evaluations, and the loop stops with the cell at 3. The loop’s own value is (); the result the program wants is in the cell, read out afterward. A while with no cell to move — while true { } — matches only E-While-True, forever, and has no derivation.

Building it

The while arm matches the provided Expr::While node, a condition and a body:

Expr::While(Box<Expr>, Box<Expr>, Span)

The recursion the rule expresses as a repeated premise, the interpreter can express as a loop of its own: it need not call itself to run the next turn, since a host loop re-evaluates the condition and body in place, threading the one store on the interpreter exactly as the rule threads $\sigma$. The body’s value is evaluated and dropped, matching the rule’s discard of $v$, and the loop yields Value::Unit. A return reached in the body leaves the host loop at once — the interpreter carries it on the same Control channel it uses for an error, so the remaining turns do not run, the reference’s convention that a return abandons the whole while. That returning outcome is the subject of a later section.

Walking a list: for

A while repeats until a condition falls; a for repeats once for each element of a collection. Bridger’s for walks a list — the values written [1, 2, 3] and built with ::, introduced with the other compound values in Part II. A list there had no way to read its elements back out: there is no xs[i] and no xs.0, by design. for is the form that reads them, taking each element in turn and binding a name to it for the body:

let total = ref 0;
for x in [1, 2, 3] {
  total := deref total + x
};
deref total                    // 6

for evaluates the iterable to a list value, then walks it. The walk is two rules over the list’s structure — an empty list, and a cons of a head and a tail — with the evaluated list standing in the in position as the walk proceeds:

$$\frac{\rho ⊢⟨e,\sigma ⟩\Downarrow ⟨v_{list},{\sigma }_1⟩\rho ⊢⟨\text{for}x\text{in}{v}_{list}{e}_b,{\sigma }_1⟩\Downarrow ⟨(),{\sigma }^{\prime }⟩}{\rho ⊢⟨\text{for}x\text{in}e{e}_b,\sigma ⟩\Downarrow ⟨(),{\sigma }^{\prime }⟩}(\text{E-For})$$

$$\frac{}{\rho ⊢⟨\text{for}x\text{in}[]e_b,\sigma ⟩\Downarrow ⟨(),\sigma ⟩}(\text{E-For-Nil})$$

$$\frac{\rho [x\mapsto v_h]⊢⟨e_b,\sigma ⟩\Downarrow ⟨v,{\sigma }_1⟩\rho ⊢⟨\text{for}x\text{in}{v}_t{e}_b,{\sigma }_1⟩\Downarrow ⟨(),{\sigma }_2⟩}{\rho ⊢⟨\text{for}x\text{in}(v_h::v_t)e_b,\sigma ⟩\Downarrow ⟨(),{\sigma }_2⟩}(\text{E-For-Cons})$$

An empty list runs the body no times. A cons binds x to the head, runs the body against the incoming store and discards its value, then walks the tail against the store the body left. The binding of x is fresh on each turn and belongs to the body alone; it is not a cell, so writing x := … is not how a for accumulates. To carry a result across the turns, the body writes a cell that outlives the loop — total in the example — the same division of labor as while: the loop supplies the repetition, the store supplies the memory. Like while, the whole for yields (), a return in the body abandons the rest of the walk, and a for over a value that is not a list is stuck.

Because the list is finite and the walk shortens it by one each turn, a for over a list always stops — the property while gives up in exchange for looping on an arbitrary condition. The one other thing a Bridger program walks is the set of solutions to a relational query, written for q { … }; that form belongs with the relations of Part VII, where the queries it draws from are defined.

Building it

The for arm matches the provided Expr::For node — the bound name, the iterable, and the body:

Expr::For(Name, Box<Expr>, Box<Expr>, Span)

The three E-For rules describe the walk: evaluate the iterable, require a list, and for each element extend the environment with a fresh binding of the name before running the body against the current store, the body’s value discarded each turn. An iterable that is not a list is the stuck case — there are no cells to walk. The per-element binding extends the environment without disturbing the outer one, so the name is in scope for the body and gone after, and the whole for yields Value::Unit. The relational Expr::ForQuery node is the second walk, filled in with Part VII.

Leaving early: return

The forms so far hand their value to the expression around them: an if gives its branch’s value to whatever holds the if, and a block gives its trailing expression’s value to its surroundings. return e sends its value the other way. It evaluates e and carries the value out — past the rest of the block, past the turns of a loop still to come — to the boundary of the function that encloses it, which takes that value as its result. Its rule is the one place evaluation in this part produces something other than an ordinary value: a returning outcome, written $\mathsf{Ret}v$, that the surrounding forms pass along instead of continuing past.

$$\frac{\rho ⊢⟨e,\sigma ⟩\Downarrow ⟨v,{\sigma }^{\prime }⟩}{\rho ⊢⟨\text{return}e,\sigma ⟩\Downarrow ⟨\mathsf{Ret}v,{\sigma }^{\prime }⟩}(\text{E-Return})$$

Every other rule reads as it did, under one added convention: a premise that yields $\mathsf{Ret}v$ makes its own rule yield that same $\mathsf{Ret}v$, so a returning outcome travels outward on its own. This is what the loop rules meant in saying a return in the body abandons the loop — the body’s premise yields $\mathsf{Ret}v$, the loop yields it in turn, and the iterations that would have followed never run. The interpreter already carries such an outcome: the Control channel eval returns for an error is the one a return rides, which is why the ? in the loop arms above carries a return straight out of the host loop.

A return leaves the enclosing function, the subject of Part V; this chapter shows the returning outcome travelling out through the loops and blocks in its way, and that part supplies the function boundary that catches it and the calls that make an early exit worth writing. That a return stands inside a function at all is checked before the program runs — a return with none to leave is a static error rather than a value the evaluator computes.

The design space

Two decisions show through the forms of this chapter: what a conditional yields, and which loops a language provides.

Because Bridger’s if is an expression, its branches must agree on a type and a one-armed if is confined to (). A language whose if is a statement asks nothing of its branches, since the form yields nothing on either path; C and Java take that route and then add a second conditional, the operator c ? a : b, for the places a value is wanted — the split the first chapter of this part followed. The choice is whether one form serves both jobs, at the cost of the branch agreement, or two forms divide them, at the cost of carrying the conditional twice.

Loops vary more. C offers while, a do/while that tests after running the body once, and the three-part for (init; cond; step) that gathers a counter’s setup, test, and update into a header. Python and Rust make for a walk over an iterator — any value that yields elements on demand — and lean on it for counting too, over a range. Bridger provides while and a for that walks a list. while is the general loop: it repeats on any condition and can run without end, and the other shapes are while with state arranged around it — a counting loop steps a ref the body updates, a test-at-bottom loop runs its body before the first test. Bridger’s for names the one arrangement of walking a list’s elements, and it is bounded where while is not, stopping when the list runs out. What it does not do is walk an arbitrary producer the way an iterator protocol does; that generality rests on the traits and closures of later parts, while a list is the concrete sequence already in hand.

Beyond running to its end, a loop leaves only by the return of the previous section, which carries a value out past the loop and out of the enclosing function. There is no break to leave a loop early and no continue to skip to the next turn; a loop that must stop before its natural end folds that into its own condition, with a cell to signal it where the test alone will not do. The loops are kept to the two rules apiece that define them, and the state a program already has does the rest.

Structured control is one answer to the jump: name the loop and the branch as forms, and build a program from them. Another tradition answers the jump, the loop, and the branch together, by making none of them a primitive. Its programs compute by applying functions: repetition is a function that calls itself, so iteration becomes recursion; selection is an expression that evaluates one subexpression or another; and nothing jumps, since control travels where a call goes and resumes where the call returns. In the most reduced form of that tradition — the lambda calculus, whose notation Lisp borrowed — the function is the only construct, and the loop and the branch alike are things a program expresses with it rather than forms the language hands it. Bridger offers both answers: the conditionals and loops of this part, and the functions and recursion of Part V, with a program free to keep to either. return sits on the structured side of that line — a function in the recursive style has nowhere to jump out to, since its value is the expression it evaluates.

Further reading

Structured control flow: Edsger Dijkstra’s letter “Go To Statement Considered Harmful” (Communications of the ACM, 1968) makes the case for control constructs that are entered and left at one point, the shape Bridger’s if and while take, in place of the jump. Corrado Böhm and Giuseppe Jacopini’s “Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules” (Communications of the ACM, 1966) proves that sequence, selection, and iteration suffice to express any flowchart, so the loss of the general jump costs a language no control it could otherwise have.

Iteration constructs: CLU introduced the iterator, a for that draws successive values from a separate producer rather than from a stored collection, described in Barbara Liskov and colleagues’ “Abstraction Mechanisms in CLU” (Communications of the ACM, 1977); it is the arrangement Python’s and Rust’s for follow. The Rust Reference sets out the loop, while, and iterator-for that Bridger’s two loops are drawn from and pared against.

Concept checks

Milestone M3

Control Flow and Mutation

Part IV let the language do things. A cell in the store holds a value that changes, if chooses a course of action, while and for repeat one, and return carries a value out past the code around it. This milestone puts them into the evaluator, and the run of the language grows from computing a value to changing state and controlling the order in which it changes.

The codebase, the toolchain, and the build loop are the ones Milestone M1 set up. What is new here on the provided side is the store: a Store that lives on the interpreter, with three operations — allocate a cell, read one, write one — and a Value::Ref that carries a cell’s location. It is the state the mutation forms act on, described in full in the Mutation chapter’s build section.

To-dos

grep -rn 'todo_m3!' src lists five arms left as holes after M2:

// src/interp/eval.rs — the five M3 arms of eval_expr
Expr::If(..)     => todo_m3!("E-If"),
Expr::While(..)  => todo_m3!("E-While"),
Expr::For(..)    => todo_m3!("E-For"),
Expr::Assign(..) => todo_m3!("E-Assign"),
Expr::Return(..) => todo_m3!("E-Return"),

Two more cases are not on that list. ref and deref are UnOp variants, so they are two new arms of the match inside Expr::Unary — the arm you filled at M1 for -e and not e, whose stub was labelled “ref & deref join at M3”. The grep under-counts M3 by exactly those two: seven forms in all, five of them their own Expr variant and two of them cases of an existing one.

Milestone specification

Each form this milestone adds, the rule that gives it meaning, and the case that leaves it stuck:

The full rules are in Mutation and References and Conditionals and Loops; this table is the checklist your evaluator is measured against, not a second statement of them. What each form evaluates to — the branch’s value for if, a fresh reference for ref, () for the effectful forms — is the subject of the contracts below.

Three contracts hold across these arms. The effectful forms yield unit: :=, while, and for each evaluate to (), and an else-less if does too when its condition is false. A loop discards its body’s value each turn — a while body runs for its effect on the store, a for body for its effect once per element, and the loop’s own value is (). And a return leaves on a channel of its own: it is not an ordinary value the arms combine but a control transfer that travels straight out through the loops and blocks in its way, abandoning the iterations that would have followed.

Implementing Milestone M3

Destructure each arm’s .. into the fields you need:

The store is reached through the interpreter, self.store, and its three operations are the three mutation forms:

• ref e evaluates e and calls self.store.alloc(v), which makes a fresh cell and returns its Loc; the value the form returns is Value::Ref(loc).
• deref e evaluates e to a Value::Ref(loc) and returns self.store.read(loc).
• e1 := e2 evaluates e1 to a Value::Ref(loc), then e2 to a value, calls self.store.write(loc, v), and returns Value::Unit.

A deref or := whose operand is not a Value::Ref is stuck — a RuntimeError::TypeError built with Ty::reference(..) for the expected type. The rules of the Mutation chapter thread a store in and a store out; the interpreter keeps the store on itself and mutates it in place, so alloc and write are the step from one store to the next.

The control forms match the value they branch on:

• if evaluates its condition; on Value::Bool(true) it evaluates the then-branch, on Value::Bool(false) the else-branch — or Value::Unit when there is none. Only the branch taken is evaluated. A non-boolean condition is stuck.
• while is a host loop: re-evaluate the condition each turn, run the body while it is Value::Bool(true) (the body’s value taken with ? and dropped), and stop with Value::Unit when it is false. A non-boolean condition is stuck.
• for evaluates its iterable to a Value::List, then walks it, evaluating the body once per element in env.extend(x, item) — a fresh binding of x each turn, discarded after — and yields Value::Unit. An iterable that is not a list is stuck.
• return e evaluates e and leaves through the return channel: Err(Control::Return(v)). This is the second variant of Control, beside the Control::Raise an error rides (error handling). Because a loop body runs with ?, a return in the body carries straight out of the host loop, which is what abandons the remaining iterations.

At this milestone a return has no enclosing function to catch it — that boundary arrives with functions in Part V. Reaching a return where none is allowed is ruled out before the program runs, so the evaluator’s job is only to raise the channel; nothing in this milestone catches it.

Worked examples

A program, and the value it evaluates to:

if true { 1 } else { 2 }             ⇓ 1
if false { 9 }                       ⇓ ()   (else-less, condition false)
deref (ref 5)                        ⇓ 5

let r = ref 0;
r := 7;
deref r                              ⇓ 7    (write, then read it back)

let a = ref 1;
let b = a;                           // b holds the same cell as a
b := 9;
deref a                              ⇓ 9    (aliasing)

let i = ref 0;
while deref i < 3 { i := deref i + 1 };
deref i                              ⇓ 3

let acc = ref 0;
for x in [1, 2, 3] { acc := deref acc + x };
deref acc                            ⇓ 6

Programs that leave through the return channel rather than with a value:

return 5                             → returns 5
while true { return 7 }              → returns 7   (the loop is abandoned)

And programs with no value, which halt the run:

if 3 { 1 } else { 2 }                ⇓ stuck  (condition is not a Bool)
while 1 { }                          ⇓ stuck  (condition is not a Bool)
for x in 5 { }                       ⇓ stuck  (iterable is not a list)
deref 5                              ⇓ stuck  (deref of a non-reference)
5 := 6                               ⇓ stuck  (assign to a non-reference)

How to know it works

cargo m3 runs the provided milestone M3 tests and, because the milestones are cumulative, the M2 and M1 tests with them. Each test builds an Expr and checks the Value it evaluates to, the error a stuck test blames (its variant and span), or — for a return — the value it carries out. The builders if_, if_else, while_, for_, assign, and return_ join the earlier ones, ref and deref are written as unary(UnOp::Ref, …) and unary(UnOp::Deref, …), and the assertion returned unwraps the return channel where value_of and stuck unwrap a value or an error:

// if true { 1 } else { 2 }  ⇓  1
let e = if_else(boolean(true, 1), int(1, 2), int(2, 3), 0);
assert_eq!(value_of(&e), Value::Int(1));

// deref (ref 5)  ⇓  5   (ref / deref are UnOp::Ref / UnOp::Deref)
let e = unary(UnOp::Deref, unary(UnOp::Ref, int(5, 2), 1), 0);
assert_eq!(value_of(&e), Value::Int(5));

// while true { return 7 }  returns 7 through the return channel
let e = while_(boolean(true, 1), return_(int(7, 3), 2), 0);
assert_eq!(returned(&e), Value::Int(7));

Fill an arm, run cargo m3, and repeat until every M3 test — and every M2 and M1 test — passes.

Design problems

let acc = ref [];
for x in [1, 2, 3] {
  acc := x :: deref acc
};
deref acc                            // [3, 2, 1]

let i = ref 0;
let running = ref true;
while deref running {
  if deref i == 5 {
    running := false
  } else {
    i := deref i + 1
  }
};
deref i                              // 5

First-Class Functions

A program from Part IV that adds up the squares of a list and a second program that adds up the cubes are the same loop with one line changed. Writing the loop once and handing it the line that differs requires two things. The loop has to be written somewhere that both programs can reach and given a name; and the line that differs — square this, cube this — has to become something that can be passed as a value, the same way a list is passed. Passing data between parts of a program is as old as stored-program computing; however, for years the code a program calls was treated as separate from the numbers it computed with—even if early machines stored data and code the same way. This chapter covers how programs started passing around code blocks (functions) as “first-class” values the same way as any other data a program computes with.

Subroutines

Herman Goldstine and John von Neumann’s Planning and Coding of Problems for an Electronic Computing Instrument (1948) wrote:

We call the coded sequence of a problem a routine, and one which is formed with the purpose of possible substitution into other routines, a subroutine.

and envisaged “an extensive collection of such subroutines” kept as a library on wire or tape. On the EDSAC the library was real: the relocation of Initial Orders 2, described in the history chapter, existed so that a library routine could be loaded wherever the store had room for it. What relocation did not solve is how a routine gets back. A routine reached by a jump has to finish by jumping to the order after the one that called it, and that order is in a different place for every caller.

The EDSAC’s answer, the Wheeler jump, used the fact that an order is a number. The addresses below come from a small program in Campbell-Kelly’s guide to the EDSAC, and they use the θ relocation of the history chapter: an address tagged θ counts from the start of the routine it appears in, and the loader adds that routine’s origin as the tape is read. The program’s master routine, loaded at 88, calls the library print routine P6, loaded at 56, with two orders:

 θ+7    A 7 θ      add the order at θ+7 — this order — into the accumulator
 θ+8    G 56 F     jump to the subroutine at 56

and the subroutine begins with two of its own:

 θ+0    A 3 F      add a constant kept in location 3: build the return jump
 θ+1    T 25 θ     store it at θ+25, the subroutine's exit: update the return jump

A 7 θ names its own position without the programmer knowing where that will be: loaded at 88, it arrives in the store as A 95 F, and reading location 95 reads the order itself. The subroutine’s address is written absolutely, G 56 F, because the programmer drew up a table placing each routine before the tape was punched, and location 3 lies inside the initial orders, which never move. Adding the fixed constant turns the copy of the calling order into a jump back to 97, the master routine’s θ+9, and the subroutine writes that jump into its own exit order. When the subroutine finishes it runs the updated return jump and lands after the call. The return address exists only while the call is in progress, as an order the routine wrote into itself — the self-modifying technique the history chapter showed loops using for arrays, applied to control.

David Wheeler’s two-page “The use of sub-routines in programmes” (1952) describes a sub-routine as “a self-contained part of a programme, which is capable of being used in different programmes,” and locates the hard part somewhere other than the coding: once a routine is written and tested, “there still remains the considerable task of writing a description so that people not acquainted with the interior coding can nevertheless use it easily. This last task may be the most difficult.” Its closing advice for building a library is “All complexities should—if possible—be buried out of sight.” The same paper describes an integration routine that is given “access to an auxiliary sub-routine which is capable of evaluating f(x)”: a routine whose job is only defined once it is handed another routine. That is the squares-and-cubes problem again, in 1952.

Functions and procedures

Fortran made routines part of its language, in two forms. Fortran I had functions in the sense that formulas already used — a sine or a square root, supplied by the system, written inside an arithmetic expression — and, documented in the 1957 addenda to its manual, a one-line function statement that let a program define its own, of the form FIRSTF(X) = A*X+B. A function was anything that could appear inside a formula and stand for one number. FORTRAN II, distributed in the spring of 1958, added separately compiled subprograms and a second kind of routine beside the function. A FUNCTION subprogram is used by writing its name in an expression; a SUBROUTINE is run by a CALL statement and produces its results by storing into its arguments, which it receives as locations. The FORTRAN II manual states the difference in two sentences:

A FUNCTION subprogram always produces a single result. A subroutine may produce as many results as are specified as arguments in the CALL statement.

The Algol 58 report drew the same line under different names: a function declaration declares an expression “to be a function of certain of its variables,” and a procedure declaration declares “a closed unit,” with input parameters, output parameters, and possible exits, “which may be regarded as a single compound operation (in the sense of a generalized function).” The Algol 60 report folded the two into the procedure. A procedure is called by a procedure statement; a procedure whose declaration carries a type, and whose body assigns to the procedure’s own name, may also be called inside an expression, where the call is a function designator and the last value assigned is its value. “Not every procedure declaration defines the value of a function designator.”

In all three languages, “function” names a position in the program — a call inside an expression, yielding one value — and “procedure” or “subroutine” names a call that stands as a statement. Neither word says whether the routine has effects. A Fortran function could change the variables it was handed, and an Algol function designator could assign to anything in scope, so evaluating f(x) + g(x) could give different answers depending on which call ran first. Some languages took the mathematical reading of the word and made it a rule. Niklaus Wirth’s 1970 report on Pascal, which kept procedure and function as separate declarations, put it plainly: “In order to eliminate side-effects, assignments to non-local variables are not allowed to occur within the function.” The Fortran 77 standard forbade a function reference from changing any other entity in the statement in which it appears, and required that its value not depend on the order in which the processor chose to evaluate the statement. Both rules protect the same freedom that Part II left open for +: an implementation may evaluate operands in any order only if no operand can see another’s effects.

C collapsed the two kinds into one. Every C routine is a function, and a routine called for its effect is a function whose result the caller ignores. The first edition of The C Programming Language (1978) had no word for “no result”; by Dennis Ritchie’s account it “mentioned neither the void or enum types,” both of which were in use well before the language was standardized. void gave the procedure a spelling of its own as a return type, without a second kind of declaration.

Second-class citizens

Being able to call a routine, from a statement or from an expression, still leaves open what else a program can do with it. In Algol 60 a procedure’s name could be passed as an argument to another procedure, so Wheeler’s integration routine could be written with its integrand as a parameter. It could do nothing else. A procedure could not be assigned to a variable, placed in an array, or returned as a result, and the report says why a procedure could not even be passed by value: procedure identifiers “do not possess values.”

Christopher Strachey’s 1967 lecture notes, Fundamental Concepts in Programming Languages, describe the asymmetry in a section titled “First and second class objects”:

In ALGOL a real number may appear in an expression or be assigned to a variable, and either may appear as an actual parameter in a procedure call. A procedure, on the other hand, may only appear in another procedure call either as the operator (the most common case) or as one of the actual parameters. There are no other expressions involving procedures or whose results are procedures. Thus in a sense procedures in ALGOL are second class citizens—they always have to appear in person and can never be represented by a variable or expression (except in the case of a formal parameter)…

The distinction between first- and second-class values is usually traced to these lectures. The test it sets is about the language rather than about any one program: is there anything a program may do with a number that it may not do with a function?

By 1967 a language that answered “no” had been running for years, on a notation older than any computer. Alonzo Church’s λ-calculus (introduced previously) has only functions, and writes one without naming it: $\lambda x.x+1$ is the function that adds one, an expression like any other that can be an argument to another function or the result of one. John McCarthy borrowed the notation for Lisp, and in his history of the language, written for the first History of Programming Languages conference, gives the reason:

To use functions as arguments, one needs a notation for functions, and it seemed natural to use the λ-notation of Church (1941). I didn’t understand the rest of his book, so I wasn’t tempted to try to implement his more general mechanism for defining functions.

Lisp’s maplist applied a function given as an argument to each element of a list — the squares-and-cubes loop, written once. What a Lisp function value had to carry with it, and what Lisp at first got wrong about it, is the subject of a later chapter (cf. static and dynamic scope).

Functions as values in Bridger

In Bridger a function is a value. It can be bound by let, passed to another function, returned from one, and stored in a tuple, a list, or a cell, exactly as an integer can:

fn square(x: Int) -> Int = x * x;

fn twice(f: fn(Int) -> Int, x: Int) -> Int = f(f(x));

fn pick(double: Bool) -> fn(Int) -> Int {
    if double { |x: Int| x * 2 } else { |x: Int| x + 1 }
}

fn main() {
    let inc = |x: Int| x + 1;
    println(twice(inc, 5));                        // 7
    println(twice(square, 3));                     // 81
    let ops = [inc, square, pick(true)];
    println(map(ops, |g: fn(Int) -> Int| g(10)));  // [11, 100, 20]
    let cell = ref inc;
    cell := square;
    println((deref cell)(7));                      // 49
}

There are two ways to make a function value. A top-level fn declaration binds a name to one: square on its own, without an argument list, is an expression whose value is the function, and it is passed to twice in the same way inc is. A lambda, written |x: Int| x + 1, is an expression that produces a function without naming it — Church’s $\lambda x.x+1$ in Rust’s notation — and can appear anywhere an expression can: as a let’s right-hand side, as an argument, as a branch of an if. The parameter annotations and the type fn(Int) -> Int are read by the type checker of Part VI; the evaluator ignores them.

The prelude’s map, filter, and fold take a function argument, and the functions they are handed are ordinary values; so is map itself. The squares-and-cubes problem needs nothing more:

fn sum_of(f: fn(Int) -> Int, xs: [Int]) -> Int =
    fold(xs, 0, |acc: Int, x: Int| acc + f(x));

sum_of(square, range(1, 4))                        // 1 + 4 + 9 = 14

A Bridger function called for its effect is a function like any other. Bridger is expression-oriented: a form evaluated for its effect produces (), the value that reports only that the effect happened. A procedure is therefore a function whose result is (), and a declaration that omits its result type has result type ():

fn log(msg: String) {
    println("log: " ++ msg);
}

There is one kind of declaration; the Fortran II distinction survives as a type, () against everything else, and a procedure can be passed wherever a function is expected.

There are two things a program can do with an integer and cannot do with a function. Comparing two functions with == is stuck, for the reason Part II gave — no interpreter can decide in general whether two functions agree on every input — and a function has no printed form. Strachey’s test is about expressions and variables, and Bridger’s functions pass it; they are values without being data that can be inspected.

What a lambda evaluates to

Evaluating a lambda runs nothing. Its body is code to be run later, when the function is called, and until then it is not evaluated at all:

let never = |x: Int| x / 0;        // fine: nothing is divided

The division would be stuck, but no rule reaches it until never is applied to something.

What a lambda does record is the place it was evaluated. Its body may mention names that it does not bind — f in sum_of’s |acc: Int, x: Int| acc + f(x) is bound by sum_of’s parameter list, outside the lambda. These are the free occurrences of Part III, and Bridger’s lexical scope resolves each in the environment where the code is written. Until now, code always ran where it was written: a block’s body is evaluated in the environment the block extends, and nowhere else. A function body is the first code that runs somewhere else — wherever the function is called, which may be inside fold, or long after the block that built the function has finished. For the body’s free names to keep meaning what they meant where it was written, the function value has to take that environment with it. It does:

$$\frac{}{\rho ⊢⟨\lambda \vec{x}.e,\sigma ⟩\Downarrow ⟨⟨\lambda \vec{x}.e,\rho ⟩,\sigma ⟩}(\text{E-Lam})$$

The rule has no premises, since nothing is evaluated, and the store is handed back unchanged. The value $⟨\lambda \vec{x}.e,\rho ⟩$ is a closure: the parameters, the body, and the environment in force when the lambda was evaluated. A top-level fn evaluates by E-Var: the program’s environment binds its name to a closure whose environment is the program’s environment, which is how top-level functions can call one another (cf. recursion).

How a call uses the captured environment is the rule for application, in the next chapter. What the capture makes possible — a function that outlives the call that created it — is the subject of closures.

Building it

The AST node and the value it produces are both provided. A lambda is Expr::Lambda, whose parameters carry an optional type annotation; its value is the Closure variant of Value, which holds a shared pointer to one of two kinds of function:

Expr::Lambda(Vec<LambdaParam>, Box<Expr>, Span)

pub struct LambdaParam { pub name: Name, pub ty: Option<Ty>, pub span: Span }

Value::Closure(Rc<Closure>)

pub enum Closure {
    Bridger { params: Vec<Name>, body: Expr, env: Env },  // a lambda or a `fn`
    Native(BuiltinId),                                    // a prelude primitive
}

The Lambda arm of eval_expr is E-Lam: it builds a Closure::Bridger from the parameter names (the annotations are Part VI’s business and are dropped), a copy of the body, and the environment the arm was handed, and returns it as a Value::Closure. It evaluates nothing and cannot fail. Holding the environment is cheap: an Env is the shared chain of scopes chosen in Part III so that it could be captured without being copied.

Top-level functions need no arm of their own. The provided eval_program binds every fn to a Closure::Bridger whose env is the program environment before main runs, and the prelude’s built-in primitives — println, the readers — arrive as Closure::Native, so map(xs, println) passes a primitive exactly as it passes a lambda.

The design space

Whether a language has one kind of routine or two is a choice about what a call is allowed to mean. Fortran II and Pascal keep functions and procedures apart, and a reader who sees a call in an expression knows it yields one value; Pascal’s rule on non-local assignment goes further and tells the reader the call cannot disturb the expression around it. The cost is a second declaration form and, in Pascal’s case, a restriction that forbids a function from updating a counter or caching a result. C, ML, Rust, and Bridger have one kind of routine and mark a procedure by its result type — void in C, a unit type in the others — so a procedure can be passed wherever a function is expected, and map over a list with a printing function needs no special case. What they give up is the guarantee: a call in an expression may have any effect a statement could. Bridger answers the evaluation-order question by fixing the order, left to right, through the threaded store, rather than by restricting what a function may do. Languages that record effects in a function’s type, so that “this call does nothing but compute a value” is checked, are among the alternatives taken up with programming functionally.

How far a routine is a value is a second axis. Algol 60 and Pascal let a procedure be passed as an argument and nothing more. C lets a function be named by a pointer, and a pointer can be stored, passed, and returned — but C has no nested functions, so every name a function body mentions is either its own local or global to the whole program, and the pointer needs to carry nothing but the code’s address. The Lisp line, and then Scheme, ML, and Haskell, made functions values with no restrictions and a captured environment, and most languages in wide use now do the same — Python, JavaScript, C#, Rust, and Java since version 8. The restricted designs are simpler to implement for a concrete reason. A procedure passed down to a routine it calls is used while the procedure’s defining environment still exists, so a pointer to that environment on the call stack stays valid; a procedure returned up past its defining call, or stored somewhere that outlives it, carries a pointer to an environment that the stack has already discarded. Allowing that requires environments that live as long as any function refers to them, which is what Bridger’s shared Env provides and what closures examines.

Bridger takes the unrestricted end of both axes: one kind of routine, with () for procedures, and function values that are passed, returned, and stored with their environments. It stops short of treating functions as data — no equality and no printing — because neither has an answer that describes the function rather than its representation.

Further reading

Subroutines: Goldstine and von Neumann’s Planning and Coding of Problems for an Electronic Computing Instrument, Part II, Volume III (1948), sets out the subroutine and the library of them in §12 before any machine to run them had been built. Wheeler’s “The use of sub-routines in programmes” (1952) is two pages long and covers the EDSAC’s closed sub-routines, the library, interpretive routines, and the problem of describing a routine to the people who will use it. The calling sequence of the Wheeler jump is laid out order by order in Martin Campbell-Kelly’s Tutorial Guide to the EDSAC Simulator, where it can be run.

Functions and procedures in the first languages: Backus’s “The History of Fortran I, II, and III” (1978) records how function statements, and then separately compiled SUBROUTINE and FUNCTION subprograms, came into Fortran, and the FORTRAN II Reference Manual (IBM, 1958) gives the calling conventions down to where each argument’s address is found. The Algol 58 report and the Revised Report on Algol 60 (1963) show the function and the procedure as separate declarations and then as one; §4.7 and §5.4 of the latter define procedure statements, function designators, and the call-by-name rule taken up in the next chapter. Wirth’s “The Programming Language Pascal” (Acta Informatica, 1971) is the published form of the Pascal report, with procedure and function declarations in separate sections.

First-class functions: Strachey’s Fundamental Concepts in Programming Languages, lecture notes from 1967 first published in 2000, covers first- and second-class objects in §3.5.1 alongside l-values and r-values, parametric polymorphism, and the other terms it put into circulation. McCarthy’s “History of Lisp” (1979) describes borrowing Church’s notation and the first programs that passed functions as arguments. Church’s own account is The Calculi of Lambda-Conversion (Annals of Mathematics Studies 6, Princeton University Press, 1941).

Concept checks

Evaluating Function Calls

The previous chapter made functions into values. A function value is a closure: the parameter names, the body, and the environment where the function was written. This chapter is about what happens when a program calls one.

Here are two small functions. trace prints a label and then returns a number; sub subtracts:

fn trace(label: String, v: Int) -> Int {
    println(label);
    v
}

fn sub(a: Int, b: Int) -> Int = a - b;

sub(trace("a", 10), trace("b", 3))

The call’s value is 7. Getting there takes several steps, and at each one the language has to decide something:

• What is evaluated first? The interpreter evaluates sub to find its closure, and each argument to get its value. Because trace prints, the output shows the order: a then b, or b then a.
• When is an argument evaluated? Before the body starts, or only when the body uses the parameter — and so never, if the body never does.
• Where does the body run? The body looks up its parameters, and any other names it mentions, in some environment. The call has to build that environment.
• What if the body leaves early? A return in the body has to become the call’s value and go no further.

Languages in use today still answer the first two questions differently. The second divided Algol 60 and Lisp at the end of the 1950s, and the chapter begins there before giving Bridger’s answers as one inference rule, E-App.

Call by value, call by name

The Algol 60 report defined a procedure call by describing an edit to the program text. Its §4.7.3 lists the operations “on the program at the time of execution of the procedure statement”. A parameter listed in the procedure’s value part is called by value: the actual parameter is evaluated and its value assigned to a variable local to the body, as though in “an additional block embracing the procedure body”. Every other parameter is called by name:

Any formal parameter not quoted in the value list is replaced, throughout the procedure body, by the corresponding actual parameter, after enclosing this latter in parentheses wherever syntactically possible. Possible conflicts between identifiers inserted through this process and other identifiers already present within the procedure body will be avoided by suitable systematic changes of the formal or local identifiers involved.

“Finally the procedure body, modified as above, is inserted in place of the procedure statement and executed.” Under call by name an argument is an expression, pasted into the body wherever the parameter appears, and evaluated each time execution reaches one of those places — once, many times, or never. The renaming clauses keep the paste from changing what any name means: the body’s own identifiers are renamed away from those in the pasted expression, and, when the procedure is called from somewhere its nonlocal names are not in scope, the caller’s identifiers are renamed away from the body’s.

Call by name made possible a kind of procedure that call by value cannot express directly. A procedure could take an expression and a variable that appears in it, change the variable, and re-evaluate the expression:

real procedure sum(i, lo, hi, term);
    value lo, hi;
    integer i, lo, hi;  real term;
begin real s;
    s := 0;
    for i := lo step 1 until hi do s := s + term;
    sum := s
end

A call sum(k, 1, n, a[k] × b[k]) pastes a[k] × b[k] in for term and k in for i, so each turn of the loop assigns the next index to k and then evaluates the product at that index; the call computes an inner product. The technique came to be known as Jensen’s device.

A compiler cannot literally edit the program text at every call, so it has to produce the same effect another way. Peter Ingerman’s 1961 paper, titled simply “Thunks”, describes compiling each by-name argument into a small routine that computes the argument’s expression in the caller’s environment; the body runs that routine every time it uses the parameter. The paper’s title became the name for such a routine, and for any delayed computation packaged to run later.

Lisp took the other answer for every argument. McCarthy’s eval evaluates each argument of a function call first and hands the function the resulting values — call by value — so an argument is evaluated exactly once, before the body starts, whether or not the body uses it. C, ML, Java, Python, Rust, and Bridger all evaluate arguments the same way.

The rule for application

Bridger’s call is one rule. In the env-and-store judgment of Part IV:

$$\frac{\begin{array}{c}\rho ⊢⟨e_0,{\sigma }_0⟩\Downarrow ⟨⟨\lambda \vec{x}.e_b,{\rho }^{\prime }⟩,{\sigma }_0^{\prime }⟩\\ \rho ⊢⟨e_i,{\sigma }_{i-1}^{\prime }⟩\Downarrow ⟨v_i,{\sigma }_i^{\prime }⟩(1\le i\le n)\\ {\rho }^{\prime }[\vec{x}\mapsto \vec{v}]⊢⟨e_b,{\sigma }_n^{\prime }⟩\Downarrow ⟨r,{\sigma }^{\prime }⟩\end{array}}{\rho ⊢⟨e_0(e_1,\dots ,e_n),{\sigma }_0⟩\Downarrow ⟨\mathsf{Val}(\mathrm{unwrap}r),{\sigma }^{\prime }⟩}(\text{E-App})$$

Read top to bottom, the premises are the order the interpreter works in.

The first premise evaluates the operator $e_0$, in the caller’s environment $\rho$, and requires the result to be a closure $⟨\lambda \vec{x}.e_b,{\rho }^{\prime }⟩$: parameters $\vec{x}$, body $e_b$, and the environment ${\rho }^{\prime }$ that E-Lam recorded when the closure was made. The operator is an expression like any other. It is usually a name — sub, which E-Var looks up — but pick(true)(10) and (deref cell)(7) are calls too.

The second line evaluates the arguments $e_1$ through $e_n$, also in $\rho$, one after another. The store threads through them in index order — $e_1$ starts from the store the operator left, ${\sigma }_0^{\prime }$, and each later argument starts from the store the one before it left — which fixes the order at left to right, exactly as the threaded store fixed the order of +’s operands in mutation. Each $v_i$ is a value by the time the body starts. That makes the rule call by value, and the call from the start of the chapter prints a and then b before sub’s body subtracts.

The third premise runs the body. Its environment is ${\rho }^{\prime }[\vec{x}\mapsto \vec{v}]$: the closure’s captured environment, extended with each parameter $x_i$ bound to its argument $v_i$. The caller’s environment $\rho$ appears in the first two premises and not in the third. Whatever the caller has bound, the body sees only what was in scope where the function was written, plus its own parameters:

let scale = 10;

fn scaled(x: Int) -> Int = x * scale;

fn main() {
    let scale = 2;
    let x = 99;
    println(scaled(4));               // 40
}

scaled’s closure captured the program environment, where scale is 10; extending it with x ↦ 4 shadows nothing the caller holds, because the caller’s x and scale are not in it. This is the lexical scope that Part III committed Bridger to, now at work on code that runs away from where it was written. What the other choice — looking free names up in the caller’s environment — would do to programs like this one is the subject of static and dynamic scope.

The bindings the body extends are new. A call does not change the closure’s environment ${\rho }^{\prime }$; it builds a child of it for the length of the body, the same way a block builds a child scope. Two calls of the same function, or a function that calls itself, each get their own parameter bindings on top of the same captured environment.

The conclusion writes out both outcomes of evaluation, which the rules since E-Return have left implicit. The body’s result $r$ is either an ordinary $\mathsf{Val}v$ or the returning outcome $\mathsf{Ret}v$ that return produces, and

$$\mathrm{unwrap}(\mathsf{Val}v)=\mathrm{unwrap}(\mathsf{Ret}v)=v$$

turns either into the call’s value, marked $\mathsf{Val}$ again. Under the convention that a premise yielding $\mathsf{Ret}$ makes its rule yield $\mathsf{Ret}$, a return travels outward through the loops and blocks around it; E-App is where it stops. The call is the function boundary that conditionals and loops described without having one:

fn first_negative(xs: [Int]) -> Int {
    for x in xs {
        if x < 0 { return x; }
    }
    0
}

first_negative([3, -4, 5, -6]) + 100    // 96

The return x abandons the rest of the loop and the trailing 0; the call to first_negative catches it and yields -4, and the + 100 around the call proceeds as it would for any value.

When a call is stuck

Two things can prevent E-App from applying. The operator may evaluate to something other than a closure — 5(1), or a name bound to a list — and then the first premise cannot hold. Or the number of arguments may differ from the number of parameters, and then ${\rho }^{\prime }[\vec{x}\mapsto \vec{v}]$, which pairs the $i$-th parameter with the $i$-th value, has no meaning. The Algol 60 report stated the second condition in as many words: the actual parameter list “must have the same number of entries as the formal parameter list” of the declaration.

The premises also say when each is detected. A non-function operator is stuck at the first premise, before any argument has run; a wrong count is stuck only once the arguments have all been evaluated, since the rule compares the values with the parameters. In 5(trace("a", 1)) nothing is printed; in sub(trace("a", 1)) the a is printed and then evaluation is stuck.

Both are runtime errors in the interpreter built so far. With the type checker of Part VI, a call’s operator and its argument count are known before the program runs, and both become static errors.

Building it

A call is Expr::Call, holding the operator, the argument expressions, and the span of the whole call:

Expr::Call(Box<Expr>, Vec<Expr>, Span)

Everything the Call arm needs beyond eval_expr itself is provided. The closure it finds is the Closure enum from the previous chapter; the environment for the body is built with Env::extend, which returns a child scope and leaves its receiver untouched; the stuck cases have their own RuntimeError variants; and two methods on Interpreter keep count of how deep the calls are nested:

impl Env {
    pub fn extend(&self, x: Name, v: Value) -> Env;
}

RuntimeError::NotAFunction { found: Ty, span: Span }
RuntimeError::ArityMismatch { expected: usize, found: usize, span: Span }

impl Interpreter {
    fn enter_call(&mut self, span: Span) -> Result<(), RuntimeError>;
    fn leave_call(&mut self);
    fn eval_prelude(&mut self, id: BuiltinId, args: Vec<Value>, span: Span)
        -> Result<Value, RuntimeError>;
}

The arm follows E-App’s premises in order. It evaluates the operator; a value that is not a Value::Closure is NotAFunction, with found filled from the value’s runtime type, before any argument is touched. It evaluates the arguments left to right into a vector of values. What happens next depends on which kind of closure it holds. A Closure::Native is a prelude primitive, and eval_prelude runs it on the argument values. A Closure::Bridger checks the argument count against its parameters (ArityMismatch if they differ), extends its own captured env with one binding per parameter, and evaluates the body in that environment.

A Bridger body is bracketed by enter_call before it and leave_call after it, whatever the body’s outcome. The pair counts frames: a program that recurses without end is stopped at a fixed depth with a StackOverflow error, where the Rust stack running eval_expr would otherwise overflow and abort the whole interpreter.

The body’s outcome is the last thing the arm looks at. Evaluation hands it back as the Control channel: a value, a Control::Return, or a Control::Raise. The Call arm is the one place in the evaluator that inspects Control::Return instead of passing it on — it takes the returned value as the call’s value, which is $\mathrm{unwrap}$ — while a Raise continues outward as it does everywhere else.