Small-Step vs Big-Step Semantics
What you'll learn: You'll discover the two main approaches to defining how programs execute step-by-step—one that shows every tiny transition, and one that jumps straight to the final answer.
The Core Idea
When we define operational semantics (how programs run), we have two philosophical choices:
Small-step semantics (also called structural operational semantics or transition semantics) models computation as a sequence of individual reduction steps. Think of it like watching a movie frame-by-frame—each step shows one tiny transformation of your program's state.
Big-step semantics (also called natural semantics or evaluation semantics) models computation by relating an initial expression directly to its final result. It's like fast-forwarding to the ending—you specify how an expression evaluates to its value without explicitly showing intermediate states.
Analogy
Imagine explaining how to solve 3 + 4 × 2:
- Small-step: "First, we see
3 + 4 × 2. Then it becomes3 + 8. Then it becomes11." Every intermediate form is explicit. - Big-step: "The expression
3 + 4 × 2evaluates to11." We skip the middle and describe the complete evaluation relationship.
When to Use Each
Small-step is better for:
- Reasoning about non-terminating programs
- Modeling concurrency and interleaving
- Proving properties about every execution state
Big-step is better for:
- Simpler definitions for terminating programs
- Interpreter implementations
- Compositional reasoning about total functions
Key Takeaway: Small-step semantics shows every transition in a computation sequence, while big-step semantics relates starting expressions directly to final values—two complementary ways to define precisely what programs mean.