Course contentsShow
← Computer Science
Lesson 2018 of 2,87245. Type Systems and SemanticsFree lesson

Small-Step vs Big-Step Semantics

Two approaches to operational semantics: small-step (transition by transition) and big-step (to final result).

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 becomes 3 + 8. Then it becomes 11." Every intermediate form is explicit.
  • Big-step: "The expression 3 + 4 × 2 evaluates to 11." 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.