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:
- If the guard isn't a value yet:
if e then s₁ else s₂ → if e' then s₁ else s₂(whereesteps toe') - If guard is true:
if true then s₁ else s₂ → s₁ - 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 ⇓ trueands₁ ⇓ v, thenif e then s₁ else s₂ ⇓ v - False case: If
e ⇓ falseands₂ ⇓ v, thenif 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.