Pattern Matching

A huge share of bugs are data in a state that “should not happen”: a null where a value was expected, two fields that quietly contradict each other, a case nobody remembered to handle. The durable idea here is to make those states impossible to express in the first place, and to have the compiler force you to handle every case that remains.

The person who saw it first

Robin Milner was in Edinburgh around 1973 building LCF, a machine that checks mathematical proofs. He needed a language to write the tactics that manipulate those proofs, and he was clear-eyed about the danger: one type slip in a tactic could quietly wave through a false theorem. He did not trust himself, or anyone, to avoid that by care alone.

So the language he wrote for it — ML, the meta language — had a type checker that made the mistake impossible to even express, and inferred the types so the safety cost you almost no typing. Out of that fell three ideas that reshaped how we model data: algebraic data types (a value is this or that, and the compiler knows which), exhaustive pattern matching (take a term apart and handle every shape, or it will not compile), and type inference. His summary has outlived the theorem prover: “well-typed programs cannot go wrong.” (Turing Award, 1991.)

Side by side

C — a struct can hold nonsense; you check for it at runtime and hope you covered every path.
Prolog — unification is pattern matching too, and gorgeous, but dynamic: mistakes surface as failed goals at run time.
ML and its family — the type checker does the matching. Add a new variant to a type and every match that forgot it stops compiling. Illegal states become unrepresentable.

Why it endures

This is “data modeling” at its sharpest, and it went mainstream: Rust enums, Swift enums, Haskell, F#, TypeScript’s discriminated unions, and the “parse, don’t validate” school all descend from Milner’s ML. You feel it every time a compiler says “switch must be exhaustive.”

The shape of it

(* Standard ML — an algebraic data type and an exhaustive match. *)
datatype shape = Circle of real | Rect of real * real

fun area (Circle r)    = 3.14159 * r * r
  | area (Rect (w, h)) = w * h
(* Delete a branch above and the compiler warns: match not exhaustive. *)

(No ML toolchain is wired into the playground yet, so this one is for reading. Ask and I will add one.)

[!recall] “Make illegal states unrepresentable” — what does that buy you, and when? It moves a whole class of “that should never happen” bugs from run time to compile time. By modeling data as sums and products you stop illegal combinations from being constructed at all, and exhaustive matching means adding a new case breaks every site that forgot to handle it — so the compiler, not a production incident, tells you what you missed.

Sources

Milner, “A Theory of Type Polymorphism in Programming” (1978) — where type inference and “well-typed programs cannot go wrong” come from.