Type Soundness

Every time you run a program, something could go wrong: you might add a number to a string, call a method on null, or read a field that does not exist. Type checking is a static analysis that flags exactly those mistakes — before the program ever runs.

But a type checker is only useful if it means something. The question is: if the type checker is happy, does that really guarantee the program won't crash? The answer is captured in a theorem called type soundness, first stated cleanly by Wright and Felleisen in 1994.

It rests on two lemmas that together say: "a well-typed program never gets stuck." Progress says every well-typed program can always take a step (or is already finished). Preservation says that step doesn't break the typing. Together, they turn type annotations from documentation into a runtime guarantee.

Below is a tiny expression evaluator with a built-in type checker. Each expression is either a number, a boolean, an addition of two numbers, or an if-then-else. The type checker assigns types before evaluation and rejects ill-typed programs.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="editor-row">
  <div class="expr-group">
    <label for="expr-input">{{label_expr}}</label>
    <input id="expr-input" type="text" placeholder="{{placeholder_expr}}" spellcheck="false" autocomplete="off" />
  </div>
  <div class="btn-row">
    <button id="btn-check" type="button">{{btn_check}}</button>
    <button id="btn-run" type="button">{{btn_run}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>
<div class="result-area">
  <div class="result-box" id="type-box">
    <span class="box-label">{{label_type}}</span>
    <span class="box-value" id="type-out">—</span>
  </div>
  <div class="result-box" id="eval-box">
    <span class="box-label">{{label_value}}</span>
    <span class="box-value" id="eval-out">—</span>
  </div>
</div>
<div class="status" id="status"></div>
<div class="examples-section">
  <p class="examples-label">{{label_examples}}</p>
  <div class="examples-row" id="examples-row"></div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .9rem; line-height: 1.5; }
.editor-row { display: flex; flex-direction: column; gap: .5rem; margin-bottom: .7rem; }
.expr-group { display: flex; flex-direction: column; gap: .3rem; }
label { font-size: .82rem; font-weight: 600; color: #555; }
input { font: 15px ui-monospace, monospace; padding: .45rem .7rem; border: 1.5px solid #b0bec5; border-radius: 8px; width: 100%; outline: none; transition: border-color .15s; }
input:focus { border-color: #1d3557; }
.btn-row { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .85rem; border: 1.5px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; transition: opacity .15s; }
button:hover { opacity: .85; }
button.ghost { background: #fff; color: #1d3557; }
.result-area { display: flex; gap: .6rem; margin-bottom: .5rem; }
.result-box { flex: 1; border: 1.5px solid #cdd9e3; border-radius: 10px; padding: .5rem .7rem; background: #f4f8fb; min-height: 52px; }
.result-box.ok { border-color: #0a7d33; background: #e8f7ee; }
.result-box.bad { border-color: #c92f3c; background: #fdecea; }
.box-label { display: block; font-size: .74rem; font-weight: 700; color: #6b7a8d; text-transform: uppercase; letter-spacing: .04em; margin-bottom: .2rem; }
.box-value { font: 14px ui-monospace, monospace; word-break: break-all; }
.status { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin-bottom: .4rem; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.examples-label { font-size: .8rem; font-weight: 600; color: #555; margin: .3rem 0 .4rem; }
.examples-row { display: flex; flex-wrap: wrap; gap: .4rem; }
.ex-btn { font: 13px ui-monospace, monospace; padding: .25rem .6rem; border: 1px solid #adb1b8; background: #e8eef3; color: #1d3557; border-radius: 6px; cursor: pointer; }
.ex-btn:hover { background: #cdd9e3; }

// Code not found

Notice what happens when you mix types: true + 1 fails the type check instantly, even though the evaluator would happily try to compute something nonsensical. That rejection is progress and preservation in action — the type checker guarantees that evaluation can always proceed safely, or it refuses to start.

Type soundness is proved by two lemmas about the operational semantics of a language — the rules that say how expressions reduce to values.

Progress. If $e$ is a well-typed expression (written $\vdash e : T$) and $e$ is not yet a value, then there exists an expression $e'$ such that $e \to e'$. In plain English: a well-typed program is never stuck mid-computation.

Preservation (Subject Reduction). If $\vdash e : T$ and $e \to e'$, then $\vdash e' : T$. A reduction step cannot change the type of the result. The guarantee survives every step of evaluation.

Together they imply: if a program type-checks, evaluation either terminates normally or diverges — it never crashes with an undefined operation. Wright and Felleisen proved this for Mini-ML in 1994 using structural induction on the typing derivation, not by testing programs. The proof is finite, yet it covers infinitely many possible inputs and execution paths.

The connection to the halting problem is subtle: type checking itself is decidable (in most common languages), but it only rules out a specific class of errors. Checking full correctness — does this program compute what I intended? — is still undecidable in general.

The progress-and-preservation argument is not an academic curiosity — it is the engine behind the safety guarantees of every major typed language:

• Rust: the borrow checker is an extended type system. Type soundness is what makes "if it compiles, it won't use-after-free" true, not just a slogan.
• Java and Kotlin: the type system rules out most ClassCastException and null-pointer crashes; Kotlin's nullable types push the guarantee further.
• Haskell: purity and the IO monad are enforced by the type system — a function typed Int -> Int cannot perform side effects, and soundness ensures that holds throughout execution.
• TypeScript: adds soundness approximately. TypeScript intentionally trades full soundness for expressiveness (any, type assertions) — a useful reminder that soundness is a spectrum.
• Proof assistants (Coq, Lean, Agda): type soundness is the foundation of the propositions-as-types correspondence — a proof of a theorem literally is a well-typed program.

Wherever you see a "type-safe" language promise, you are seeing the Wright–Felleisen theorem deployed at scale. Related ideas appear in circuit complexity (where gate types must match) and in formal verification of hardware.

Type soundness is deceptively simple: two lemmas about one step of evaluation, proved by induction, covering all programs forever. Yet the consequence is enormous — the type checker becomes a verifiable promise, not a style suggestion.

Progress says your program is never stranded without a next move. Preservation says each move respects the type contract. Together they mean: write code that passes the type checker, and an entire class of runtime disasters is mathematically impossible.

The next time a compiler tells you "type error," it is not being pedantic. It is invoking a proof — and saving you from a crash that might only appear at 3 a.m. in production. That is the quiet power of the halting problem's decidable cousin.