Tony Hoare and His 'Billion-Dollar Mistake': How Null References Still Haunt Us Today

Among the legends of computer science, Tony Hoare occupies a uniquely paradoxical position. He both created algorithms that transformed programming history and personally introduced a bug that has plagued developers for over half a century — the null reference. In his own words, it was a "billion-dollar mistake."

One Person, Two Legacies

Tony Hoare's career is a study in contradictions. On one hand, he invented Quicksort, QuickSelect, and other highly efficient algorithms still in widespread use today. He laid theoretical foundations for languages like Pascal and Go, earned over 21 honors throughout his life — including the Turing Award, widely regarded as the Nobel Prize of computer science — and was knighted for his contributions to education and computing.

On the other hand, as one YouTube creator half-jokingly noted, roughly 70% of documented bugs in enterprise Java can be traced back to a single decision Hoare made in 1965: introducing the null reference. One of the most severe outages in recent memory was triggered by a null pointer exception.

Born on January 11, 1934, in what is now Sri Lanka, Hoare received a top-tier British education, attending Dragon School in Oxford and King's School in Canterbury before entering Merton College, Oxford in 1952. After graduating, as part of his Royal Navy national service, he spent 18 months learning Russian and studied for a time at Moscow State University.

Quicksort: Born Without a Computer

Perhaps most remarkably, Hoare invented Quicksort without access to a computer or a programming language that supported recursion. He worked it all out with pen and paper — as the video creator put it, "like he had a ChatGPT running inside his head."

The idea behind Quicksort is elegantly simple: pick a pivot element at random, place everything smaller on one side and everything larger on the other, then recursively apply the same process to both halves. Each pass locks in the final position of one element, until the entire array is sorted.

Quicksort's greatness comes down to two things. First, its runtime: average complexity of O(n log n), which scales gracefully as arrays grow. Second, its minimal memory footprint — critically important in the 1960s, when a kilobyte of core memory cost $5,000 (in period dollars), equivalent to roughly $50,000 per KB today. In that context, a memory-efficient algorithm was invaluable.

Interestingly, Hoare had no opportunity to implement it for quite some time. When he joined Elliott Brothers in 1960, his first assignment was to implement Shellsort. He confidently told his manager Pat that he could do better, and the two bet sixpence on it. Hoare sketched boxes and arrows on a whiteboard; Pat implemented it and conceded defeat — probably the highest-ROI sixpence in history.

Shellsort, proposed by Donald Shell in 1959, is an improved version of insertion sort that works by comparing elements a certain distance apart, gradually reducing that gap to 1. Its average complexity is roughly O(n^1.5) — better than simple O(n²) sorts, but still no match for Quicksort's O(n log n). When Hoare took on the Shellsort task, he immediately saw room for improvement. It's worth noting that Quicksort degrades to O(n²) in the worst case — such as when the array is already sorted and the pivot is always the largest or smallest element. This is why engineering practice later introduced randomized pivot selection, using randomness to avoid edge cases and make the average-case performance guarantee more reliable in practice.

The "Billion-Dollar Mistake"

During his time at Elliott Brothers, Hoare also convinced the company to adopt ALGOL 60 instead of a proprietary language — a commercially successful move. He later collaborated with Niklaus Wirth on ALGOL W, and it was this language that introduced null references into our lives.

In a 2009 QCon talk, Hoare made a public confession:

"I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object-oriented language, ALGOL W. My goal was to ensure that all use of references should be absolutely safe… But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years."

The cost of that "temptation" is still being paid today. As the video notes, a major Google Cloud outage in June 2025 was rooted in a missing null pointer check — a simple if statement was skipped, causing APIs and authentication services to fail globally. Services worldwide were affected for roughly seven and a half hours; platforms like Spotify were among those hit, with losses running into the millions.

The irony is almost unbearable: Hoare set out to build an "absolutely safe" type system, and instead introduced one of the most persistent vulnerabilities still being patched today. As the creator points out, even if Hoare hadn't invented it, someone else would have — much like today's AI race, some technologies feel almost historically inevitable.

At its core, a null reference is a special pointer value meaning "no object here." The problem is that when a program tries to access a property or method through a null reference, the runtime throws a NullPointerException — a check developers routinely forget. Modern languages have begun addressing this at the type-system level: Kotlin, Swift, and Rust introduce a distinction between nullable and non-nullable types, forcing developers to handle null cases at compile time rather than at runtime. Rust goes further, replacing the null reference concept entirely with the Option<T> enum. Hoare himself later reflected that had the type system required every reference to be checked before use, the mistake could have been avoided — at the cost of only slightly more awkward syntax.

CSP: The Intellectual Root of Concurrent Programming

Hoare's other major contribution to computer science is Communicating Sequential Processes (CSP). The video uses a Go code example to illustrate the concept clearly:

Process one creates a channel and blocks, waiting. Process two does its work and sends a message through the channel (say, "Hello World"). Only once process two completes the communication does process one receive the message and continue.

The core idea of CSP is that communication is a synchronous handshake. Process one must wait for process two to initiate communication — they wait for each other — unless a buffer is introduced, allowing the sender to proceed without immediately blocking. Processes are independent units of behavior that share no variables.

If you've written Elixir, this model will feel familiar, because CSP is the intellectual origin of the actor pattern. Go's goroutines and channel mechanism are, at their core, a modern embodiment of CSP principles.

CSP (Communicating Sequential Processes) was formally introduced by Hoare in a 1978 paper. Its central claim: the complexity of concurrent systems should be managed through communication, not shared memory. Traditional multithreaded programming relies on shared variables with locks (mutexes/semaphores) to coordinate concurrency — a recipe for deadlocks and race conditions that are notoriously hard to debug. CSP keeps each process's state independent, with interaction only through message passing, transforming concurrent logic into more easily reasoned-about communication sequences. The actor model is related to CSP but distinct: in the actor model, each entity has its own mailbox and sending is asynchronous; pure CSP channel communication defaults to synchronous, blocking handshakes. Go's channels support both buffered and unbuffered modes, covering both semantics — making it one of the most widely adopted industrial implementations of CSP thinking.

A Thinker Who Could "See Around Corners"

Hoare's contributions extend even further — QuickSelect, statistical algorithms, practical work on ALGOL compilers, a unified theory of programming, the Dining Philosophers Problem — his fingerprints are everywhere.

He also left behind several widely quoted lines. On ALGOL 60, he said: "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."

And perhaps his most thought-provoking observation, on software design:

"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. The first method is far more difficult."

Hoare passed away this past March. The video creator wondered what this man who could "see around corners" would have made of the vast quantities of AI-generated code being written today. Regardless, from Quicksort to CSP, from the lessons of the null reference to a philosophy of simplicity, Tony Hoare's influence will endure for a very long time.