↓ Skip to main content
Thinking Above the Code: Leslie Lamport on Writing Specs Before Programs
  1. Archive/

Thinking Above the Code: Leslie Lamport on Writing Specs Before Programs

Author
AI Assistant
Curated for Pradithya Aria Pura · AI-written summary of the source material

Leslie Lamport gave this plenary at the 2014 Microsoft Research Faculty Summit, a few months after his Turing Award was announced. The talk is an hour long and has one argument: before you write code you should write down what the code is supposed to do, and the right way to think about that is mathematically, in terms of states and behaviors. It’s this week’s classic partly because the same argument now has a new audience. When an agent writes the code, the spec is often the only thing a person writes at all. (This week’s digest also includes Hillel Wayne’s QCon talk on finding distributed-systems bugs at design time, which works well as a follow-up.)

To think, you have to write
#

Slide: How to Think. Writing is nature’s way of letting you know how sloppy your thinking is.

Lamport opens with a sequence: think before hunting the saber-toothed tiger, before building the house, before writing the program. You think by writing. He quotes the cartoonist Guindon:

Writing is nature’s way of letting you know how sloppy your thinking is.

If you’re thinking without writing, you only think you’re thinking.

Builders write blueprints before construction. For programs, he says, the blueprint is a specification. He notices that the word makes people panic, so he moves quickly to say that specs come in a range.

A spectrum of specifications
#

Slide: A spectrum of specifications. Prose: most code is really simple.

Blueprints run from a rough sketch for a weekend project to detailed drawings for a large building. Specs are the same. Most code is simple, and a few sentences of prose are enough. Subtler code needs what Lamport calls mathematical prose: still informal, but precise. Code that is complex, subtle or critical, and concurrent or distributed code usually is all three, should get a formal spec. The reason is practical: you need tools to check it, and tools can’t read prose.

Two models: functions and behaviors
#

Slide: How to describe a set of behaviors. Any set of behaviors is the intersection of a safety property and a liveness property.

Computer scientists, he says, should think like scientists, and science works by building mathematical models. Astronomy got a long way by treating a planet as a point mass. For programs, two models do most of the work:

  • A function, which in math is just a set of ordered pairs from inputs to outputs. It’s useful, but it can’t tell quicksort from bubble sort, and it can’t describe programs like operating systems that run forever.
  • A behavior, which is a sequence of states, where a state assigns values to variables. A program is modeled as the set of all its possible behaviors.

Any set of behaviors is the intersection of a safety property (violated at some finite point, like partial correctness) and a liveness property (only judged on the whole infinite behavior, like termination). Lamport says safety is where most bugs are, and sets liveness aside for the rest of the talk.

Euclid’s algorithm as two formulas
#

Slide: The language TLA+. MODULE Euclid with CONSTANTS M, N, VARIABLES x, y, Init and Next formulas.

A safety spec has two parts: an initial-state predicate and a next-state relation. Unprimed variables refer to the current state and primed variables to the next. For Euclid’s GCD algorithm:

Init == (x = M) /\ (y = N)

Next == \/ (x > y) /\ (x' = x - y) /\ (y' = y)
        \/ (y > x) /\ (y' = y - x) /\ (x' = x)

He works through M = 12 and N = 18 by substitution: (12, 18), then (12, 6), then (6, 6). At (6, 6) neither disjunct can be satisfied, so there is no next state and the program stops. The algorithm is deterministic because every state has at most one successor. To model nondeterminism, you let the relation allow several. Add declarations and an EXTENDS Integers line and you have a TLA+ module that a model checker can run.

“Math only works for toy examples”
#

Slide: quote from Chris Newcombe of Amazon. We have used TLA+ on 10 large complex real-world systems.

He answers the usual objection with two stories. The first is Chris Newcombe’s 2013 report that Amazon had used TLA+ on 10 large systems, and that in every case it either kept serious bugs out of production or gave engineers enough confidence to make aggressive performance optimizations. Managers there were budgeting engineering time for it. The second is the Xbox 360 memory system. Chuck Thacker had an intern write a TLA+ spec of it, and the intern found a bug before the spec ever reached the model checker. IBM’s designers confirmed it, said their testing wouldn’t have caught it, and it would have crashed every Xbox after about four hours of use.

A spec when “correct” can’t be defined
#

The middle of the talk is about an informal spec he wrote for TLATeX, the TLA+ pretty-printer. Aligning /\ conjunctions and = signs in the output depends on what the user meant, and that can’t be specified formally. He says that makes the spec more necessary, because you still have to decide what the program does. His spec was six rules written as mathematical prose in comments. Debugging six rules was much easier than debugging 850 lines of code, and he thinks the code would have been longer and the output worse without them. He didn’t write it in TLA+ because perfect alignment didn’t matter and no tool could have helped.

Quicksort without recursion
#

Slide: recursive quicksort in pseudocode, with Partition and QS procedures

The best-known part of the talk is a challenge he says almost nobody solves in ten minutes: write quicksort without recursion. People try to mechanically convert the recursive version and get stuck. Lamport’s point is that recursion is just one way to implement divide and conquer, and it isn’t part of the algorithm.

Slide: Next-state relation for quicksort over a set U of index ranges still to be partitioned

His version keeps a set U of index ranges that still need partitioning, starting with {⟨0, n−1⟩}. The next-state relation is: if U is not empty, pick any ⟨b, t⟩ in U. If b ≠ t, pick a pivot p, let A' be any valid partition of that range, and replace ⟨b, t⟩ with ⟨b, p⟩ and ⟨p+1, t⟩. Otherwise just remove it. This is more general than the recursive version, since every behavior of recursive quicksort is also a behavior of this one, and it suggests a parallel version directly.

Why can almost no one find this version of quicksort? Because people’s minds are stuck in code.

He also mentions PlusCal, a pseudocode-like language whose expressions can be any TLA+ (any mathematics). It compiles to TLA+ and is meant for people who prefer to think in algorithm notation.

What to specify, and why people don’t
#

Lamport’s practical advice is short. Specify any piece of code that someone else might use or change, and that includes you a month from now. Say what it does, meaning everything a user needs to know, and, if it’s subtle, how it does it. Keep the spec in the comments and record how mathematical concepts map to implementation structures, for example a graph stored as arrays of node and link objects. Learn to write formal specs, run them through a model checker, and fix them, even if you never write a formal spec at work. That practice is how you learn to think mathematically, and it improves the informal specs you will write.

His answer to “the spec will go out of date” is that every patch makes code a little uglier, and code written without a spec is a patch from its first line. People who tell you not to write a spec are telling you not to think.

Thinking doesn’t guarantee that you won’t make mistakes. But not thinking guarantees that you will.

In Q&A he dismisses specification by example (“examples… keep you from thinking”, because they show the easy cases and not the hard ones). On temporal logic, which TLA is built on, he says: “temporal logic is evil”, but it’s necessary for liveness. In a thousand-line TLA+ spec, 999 lines are ordinary math and the last one is a temporal formula.

Key takeaways
#

  1. Writing is how you find out whether your thinking holds up. If a design exists only in your head, Lamport would say you haven’t thought it through yet.
  2. Specs range from a few sentences of prose to formal TLA+. Pick the level by how subtle and critical the code is, and use formal, tool-checked specs for concurrent and distributed systems.
  3. Model a program as a function when only input and output matter, and as a set of behaviors (sequences of states) when you care how it runs or when it never terminates.
  4. A safety spec is two formulas, an initial predicate and a next-state relation over primed and unprimed variables. Nondeterminism just means the relation allows more than one next state.
  5. Working above the level of code reveals designs that code-level thinking hides, as non-recursive quicksort over a set of pending ranges shows.
  6. The Amazon and Xbox 360 examples show formal specs paying off on industrial systems. In the Xbox case the bug turned up while the spec was being written.
  7. Learning formal specification is worth it even if you never ship one, because it trains the mathematical thinking that informal specs need.

Source
#

  • Talk: “Thinking Above the Code”
  • Speaker: Leslie Lamport (Microsoft Research), 2013 ACM Turing Award recipient
  • Event: Microsoft Research Faculty Summit 2014 (plenary)
  • Duration: 59:50
  • Video: https://www.youtube.com/watch?v=-4Yp3j_jk8Q

Related