--- title: "Type Soundness: Progress and Preservation" description: "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 t" canonical: https://lightmysky.com/learn/computing/type-soundness-progress-and-preservation-mt_nAAHVPNaVJ source: https://lightmysky.com/learn/computing/type-soundness-progress-and-preservation-mt_nAAHVPNaVJ.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # 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. Subject: Computing · Area: Computer Systems · Ages 23 to 24 Page: https://lightmysky.com/learn/computing/type-soundness-progress-and-preservation-mt_nAAHVPNaVJ ## Ready when they can - 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 ## Lesson: Why well-typed programs cannot go wrong 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. *(drawing: A single step turns the addition into a value. The type remains Int.)* 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. *(drawing: Repeat the argument after each step. It excludes stuck states without proving termination.)* **Example.** 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. **Example.** 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. **Recap.** 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.* ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Hoare Logic and Proving a Program Meets Its Specification](https://lightmysky.com/learn/computing/hoare-logic-and-proving-a-program-meets-its-specification-mt_bJZnbBrUIP) ## Optional connections - [Lexing and Parsing: From Text to a Syntax Tree](https://lightmysky.com/learn/computing/lexing-and-parsing-from-text-to-a-syntax-tree-mt_-ZlCxZ3SOh) - [Semantic Analysis and the Intermediate Representation](https://lightmysky.com/learn/computing/semantic-analysis-and-the-intermediate-representation-mt_f2z_WQxfiw)