Type Soundness: Progress and Preservation
Small-step rules define one evaluation step. For a basic expression language, progress says a closed well-typed expression is a value or can step; preservation says a step retains its type. Together they exclude reachable stuck expressions under the stated semantics. They do not promise termination or freedom from every runtime failure.
What a learner can do afterwards
- Read an evaluation rule and explain the single step it permits
- State progress and preservation for closed expressions and explain why both are needed across a run
- Analyze a specified language extension and identify a failed progress or preservation obligation
1 · Read
You have used assertions to reason about code. Now examine a language's typing and evaluation rules. Integer literals have type Int, boolean literals have type Bool, and addition requires two Int expressions. Write t -> t' for one evaluation step. For integer literals a and b, a + b steps to their sum. For example, 1 + 2 -> 3.
An expression is closed when it has no free variables. Values here are integer and boolean literals. Progress says a closed well-typed expression is a value or has an allowed evaluation step. A stuck expression is neither a value nor able to step. Progress checks the current typed expression; alone it does not keep later expressions well-typed.
Preservation says: if t has type T and t -> t', then t' also has type T. The expression 1 + 2 has type Int and reduces to 3, also Int. Preservation constrains steps that occur; it does not itself require a non-value to have a step. Progress supplies that other obligation for closed well-typed expressions.
Together, the lemmas exclude reachable stuck expressions. Start closed and well-typed. Progress gives a value or a step. Preservation keeps the result typed, so progress applies again; evaluation also retains closedness here. This argument does not prove termination, correct answers to every task, or freedom from physical resource failures.
Consider an extension where null is a reference value and deref(null) is assigned type Int. Suppose deref(null) is not a value and has no evaluation or exception rule. It is closed, typed and stuck, so progress fails. Null is not inherently unsound: a language could reject this dereference or define exception semantics with an appropriate soundness theorem.
Consider a faulty extension: bad(0) has type Int, but bad(0) -> 1 + true. Addition requires two integers, so the result is ill-typed and stuck. The initial expression can step and meets progress's conclusion. Preservation fails because the result lacks type Int. A step that changes Int to Bool would also violate preservation, even if its result were a value.
Progress gives a value or a step for closed typed expressions. Preservation keeps results typed. Together they exclude stuck states under the stated rules, not every failure.
Original lesson, questions and flashcards about type soundness, written for this dataset.
2 · Watch
Take it off screen
Where it sits
Optional connections
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.