Proving Semantic Properties
What you'll learn: How to use operational semantics as a mathematical foundation to prove important properties about programs, such as determinism and type safety.
Once you've defined the operational semantics of a language—the precise rules for how programs execute—you can use these rules to prove theorems about your language's behavior. This moves programming language design from art to science.
Why Prove Properties?
Operational semantics gives you formal rules (judgments and transitions) that describe every step of program evaluation. With these rules written down mathematically, you can prove guarantees about your language. Two crucial properties are:
Determinism: A program's execution has exactly one possible outcome. You prove this by showing that if a program can take two different evaluation steps from the same state, those steps must actually lead to the same result. This uses structural induction over your semantic rules.
Type Safety (Soundness): "Well-typed programs don't go wrong." You prove this through two lemmas:
- Progress: A well-typed expression either is already a value, or it can take an evaluation step (no "stuck" states)
- Preservation: If an expression has type T and takes an evaluation step, the result still has type T
How It Works
You prove these properties by induction on the structure of your semantic derivations. For each semantic rule, you show the property holds. Since all program executions are built from these rules, the property holds universally.
Think of it like proving a recipe always produces edible food: verify each individual step is safe, then conclude the entire process is safe.
Key Takeaway: Operational semantics transforms informal language descriptions into rigorous mathematical systems where you can prove fundamental properties like determinism and type safety hold for all programs.