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

Introduction to Operational Semantics

What operational semantics is and why it formally defines program execution behavior step-by-step.

Introduction to Operational Semantics

You'll learn: How operational semantics provides a precise, step-by-step specification of what happens when a program runs.

What Is Operational Semantics?

Operational semantics is a formal method for defining exactly how programs execute. Think of it as writing an extremely detailed instruction manual for how an abstract machine evaluates each part of your code—one tiny step at a time.

While type systems tell you what valid programs look like, operational semantics tells you how those programs behave when they run. It's the difference between knowing the grammar rules of a language versus understanding what sentences actually mean in practice.

Why Do We Need It?

When you write code, you have an intuition about what should happen: "this variable gets assigned," "this function gets called," "this expression evaluates to 42." But intuition isn't precise enough for:

  • Compiler correctness: How do we prove a compiler translates code correctly?
  • Language design: What should happen when unusual cases arise?
  • Formal verification: Can we mathematically prove our program does what we claim?

Operational semantics answers these by defining evaluation rules in mathematical notation, showing exactly how program states transition from one configuration to the next.

The Core Idea

Imagine describing how a calculator works. You wouldn't just say "it computes answers"—you'd specify: "To evaluate 3 + 4 * 2, first evaluate 4 * 2 to get 8, then evaluate 3 + 8 to get 11." Operational semantics does exactly this for entire programming languages, creating a reference implementation in logic rather than code.

Key Takeaway: Operational semantics formally defines program execution as a sequence of small-step state transitions, providing a mathematical foundation for understanding what programs actually do when they run.