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

Operational Semantics of Conditionals

Small-step and big-step rules for if-then-else statements based on boolean guard evaluation.

Operational Semantics of Conditionals

What you'll learn: How if-then-else statements are formally evaluated step-by-step through semantic rules based on boolean guard conditions.

The Core Idea

Now that we understand how to formalize arithmetic and boolean expressions, we can define precisely how conditional statements work. An if-then-else statement has a guard (the boolean condition), a then-branch, and an else-branch. The semantics must specify: first evaluate the guard, then execute exactly one branch based on the result.

Small-Step Semantics

Small-step rules break evaluation into tiny transitions:

  1. If the guard isn't a value yet: if e then s₁ else s₂ → if e' then s₁ else s₂ (where e steps to e')
  2. If guard is true: if true then s₁ else s₂ → s₁
  3. If guard is false: if false then s₁ else s₂ → s₂

Think of it like a railroad switch: first the switch mechanism (guard) must settle into position, then the train (execution) follows exactly one track.

Big-Step Semantics

Big-step rules describe the complete evaluation in one judgment:

  • True case: If e ⇓ true and s₁ ⇓ v, then if e then s₁ else s₂ ⇓ v
  • False case: If e ⇓ false and s₂ ⇓ v, then if e then s₁ else s₂ ⇓ v

This says "evaluate the guard completely, then evaluate the appropriate branch completely."

Why This Matters

These formal rules ensure conditionals behave deterministically. The guard must evaluate to a boolean value before branching occurs, and exactly one branch executes—never both, never neither.

Key Takeaway: Operational semantics of conditionals formalize if-then-else as: evaluate the boolean guard first, then transition to (or evaluate) exactly the then-branch if true, or the else-branch if false.