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