Type Soundness: Progress and Preservation
A language is defined by a small-step semantics saying how a program takes one step. Soundness is two lemmas over that definition: a well-typed program is never stuck, and taking a step preserves its type. Together they say the errors the type system rules out cannot occur at run time.
What a learner can do afterwards
- Read a small-step rule and say what it asserts about one step of evaluation
- State progress and preservation and say what each rules out on its own
- Give a language feature that breaks soundness and say which lemma it breaks
1 · Read
A language is defined by small-step rules, where each rule says how one program takes one step. When you read a rule, you learn exactly what a single step of running looks like.
Soundness is two promises. Progress says a well-typed program is never stuck: it can always take another step or it is already a value. Preservation says taking a step keeps the type: the new program has the same type as before.
A null reference can be well-typed yet have nowhere to go when the program uses it. The program stops without being a value, so it is stuck. That breaks progress, the promise that typed programs never get stuck.
Each promise rules out its own failure alone: progress rules out getting stuck, preservation rules out changing type mid-run. Together they say the errors the type system forbids cannot happen while your program runs.
Progress keeps typed programs moving, preservation keeps their type steady, and together they keep forbidden errors away.
2 · Watch
Take it off screen
Where it sits
Learn first
This opens up
Nothing builds on it yet.
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.