◄ WORLD V · SONNY 5DART 259 · a helldive at the net

PROGRESS & PRESERVATION well-typed programs do not go wrong — the two lemmas that prove it

What does a type system actually guarantee? Type soundness: “well-typed programs do not go wrong” (Milner). Wright & Felleisen made proving it a recipe of two lemmas. Progress: a well-typed term is either a value or can take a step — it never gets stuck (no 1 + true with nowhere to go). Preservation (subject reduction): if a well-typed term steps, the result is well-typed at the same type. Together, by induction: a well-typed program steps and steps, always typed, never stuck — it runs to a value or forever, but never to nonsense. This is the theorem a type system exists to earn.

THE TECHNIQUE progress (never stuck) + preservation (type kept per step)

A well-typed arithmetic term reduced step by step. The demo shows the type is preserved at every step and the term makes progress to a value: live demo







  
HISTORY & CREDIT Milner 1978 · Wright-Felleisen 1994

  
“A type checker just catches typos.” — it earns a theorem: every program it accepts is guaranteed never to reach a meaningless state. Progress and preservation are the proof that “well-typed” means “won't go wrong,” not just “looks tidy.” cited

  
1978 · Robin Milner — “A Theory of Type Polymorphism”: well-typed programs cannot go wrong.
1994 · Andrew Wright & Matthias Felleisen — “A Syntactic Approach to Type Soundness”: the progress + preservation proof method, now the textbook standard.
now · every new type system is validated by proving these two lemmas.

  
Progress says it can move; preservation says it stays typed while moving. Chain them by induction and “well-typed” becomes a promise about the entire run, not a single moment. Wright-Felleisen 1994






  
RECOMMEND FOR I-13 type preserved across reduction, computed

  
On the canonical compiler, the well-typed term (1+2)+3 reduces to 6, staying type Int at every step (preservation) and never stuck (progress):

  
$ i13 run t_soundness.i13   # (1+2)+3, typed Int throughout
e0 = 6
type_tag_Int = 1       -- preserved at every step
steps_taken = 2        -- progress: value reached, never stuck

  
Recommend: this dart names what i13's ledger is. i13's check prints COVERED: stack balance, control-structure pairing, call arity and NOT COVERED: types — that ledger is a soundness statement for the properties it does prove. i13 earns progress-and-preservation-style guarantees for its stack discipline (it proves the stack stays balanced, never underflows) but explicitly declines the type half (1 + true is not something i13 rules out, because to it everything is f64). The whole batch is a tour of the guarantee i13's ledger, with one honest line, says it does not make.