Tony Hoare: null, quicksort and CSP

I’ve thrown more NullReferenceExceptions than any other exception in my career, by a distance, and I’ve caught more of them in other people’s code in review. For most of my years as an MVP, if someone sent me a C# stack trace, I’d have bet on that one before reading it, and I’d have won most of the time. So the first thing I thought of when I read that Tony Hoare had died, on the 5th of March at 92, was that he apologized for it. Not many people get to apologize for something that big.

Hoare did a remarkable amount, over a very long working life, and I’m not qualified to write about all of it. But three of his ideas have been part of my working life since I was a student, and I think each one is worth understanding properly, so this is a tribute in the form of a short lesson on each.

Quicksort

In 1959 Hoare was a visiting student at Moscow State University, working on machine translation, and he needed a way to sort the words of a sentence before looking them up in a dictionary on tape. The method he came up with was quicksort, which he published in 1961, and which in one form or another is still the default sort in a lot of the software you use.

The idea is to pick one element, the pivot, and rearrange the array so that everything smaller is on its left and everything larger is on its right. Then you do the same thing to each side, and keep going until the pieces have one element each. All the cleverness is in the rearranging, which is called partitioning, and Hoare’s original way of doing it is still the one I like best. Two indexes start at opposite ends and walk toward each other. The left one stops at something that belongs on the right, the right one stops at something that belongs on the left, they swap, and they carry on until they cross.

Here it is in C#, which is what I’d have written it in for most of the last twenty years:

static void Quicksort(int[] a, int lo, int hi)
{
    if (lo >= hi) return;
    int p = Partition(a, lo, hi);
    Quicksort(a, lo, p);
    Quicksort(a, p + 1, hi);
}

static int Partition(int[] a, int lo, int hi)
{
    int pivot = a[lo + (hi - lo) / 2];
    int i = lo - 1, j = hi + 1;
    while (true)
    {
        do i++; while (a[i] < pivot);
        do j--; while (a[j] > pivot);
        if (i >= j) return j;
        (a[i], a[j]) = (a[j], a[i]);
    }
}

It’s short, and it’s easy to get wrong. Notice that the recursion is on lo..p and p+1..hi, not p-1 and p+1 as in the other common version, because Hoare’s scheme doesn’t put the pivot in its final place. Mix the two up and you get a sort that’s quietly wrong on a lot of inputs. Use this version with the last element as the pivot and it can recurse forever on an array as small as two elements. I’ve done the first one in an interview, on a whiteboard, in front of someone who knew.

On average it does about n log n comparisons, and it’s fast in practice because those two indexes walk through memory in order, which caches love. Its worst case is n², when the pivot keeps landing at one end, which is why the middle element, or a random one, is a better pivot than the first. Hoare’s longer paper on it, in 1962, already discusses choosing the pivot at random for exactly that reason.

The null reference

In 1965 Hoare was designing the type system for ALGOL W, and he wanted references to be safe: the compiler would check that a reference to a record of one type was never used as another. And then he added a null reference, because it was easy to implement. Speaking at a conference in London in 2009, he said: “I call it my billion-dollar mistake. It was the invention of the null reference in 1965.”

The mistake is subtle enough that it took the rest of us about forty years to start fixing it. A type like Customer is supposed to be a promise: anything of this type is a customer, and you can ask it for its name. Null breaks the promise. A Customer variable can also hold nothing at all, and the type system doesn’t know which, so every use is a bet. When you lose the bet, you get a crash, at run time, often far from where the null came from. In C, with Turbo C on DOS, losing the bet meant writing through address zero and taking down the whole machine, which at least made the lesson memorable.

The fix is to make “maybe nothing” a different type from “definitely something”, so the compiler can tell you when you haven’t checked. ML and Haskell had that long ago. Swift and Kotlin built it in. C# got nullable reference types in version 8, in 2019, where Customer means not null and Customer? means might be null, and the compiler warns you when you treat one as the other. Turning that on in a big, old codebase is a slog, and we’ve done it in two of our services and not the rest. Each service we did it in surfaced a handful of real bugs, which is about the best argument for his apology I can make.

Communicating sequential processes

The third one is the one I understood last. In 1978 Hoare published a paper called Communicating Sequential Processes, later a book, describing a way to write concurrent programs. Instead of threads sharing memory and protecting it with locks, you have independent processes that share nothing and communicate only by sending each other messages over channels. A send and its matching receive happen together, so the communication is also the synchronization.

The reason that matters is that the hard bugs in concurrent code are about shared state: two threads reading and writing the same thing in an order nobody intended. If nothing is shared, those bugs can’t happen, and what’s left, mostly deadlock, can be reasoned about, and in CSP even proved about, because Hoare gave it a mathematical model.

Most of the programmers who use his idea today use it through Go, whose goroutines and channels come pretty directly from CSP, and whose designers say so. The Go proverb is “don’t communicate by sharing memory; share memory by communicating”, and that’s Hoare’s paper in a sentence. In .NET, which is where I’ve spent most of my time, the closest thing is System.Threading.Channels, and I’ve used it more in the last few years than I ever used locks deliberately.

The thread through all three

Behind all of it was the idea Hoare is best known for among people who study this: that a program is a mathematical object and you can prove things about it. His 1969 paper, An Axiomatic Basis for Computer Programming, introduced what’s now called Hoare logic, usually written today as {P} C {Q}, meaning that if P is true before command C runs, Q is true after. I liked proofs as a student, and I spent a career writing programs I never proved anything about, and I’ve always felt slightly guilty about the gap.

His Turing Award lecture in 1980, The Emperor’s Old Clothes, has the line I’ve quoted to more engineers than any other: “There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies.” He goes on to say the first method is far more difficult.

I’ve been thinking about that sentence a lot this year, while reviewing code I didn’t write and that an agent produced in a few minutes. A lot of it is the second kind. It works, the tests pass, and there are no obvious deficiencies. Hoare spent nearly seventy years arguing for the first kind, and I think he’d have had some sharp things to say about where we’re heading.