Semantics of Boolean Expressions
You'll learn: How formal semantic rules define the evaluation of boolean expressions, including the special behavior of short-circuit operators.
What Are Boolean Expressions?
Boolean expressions evaluate to either true or false. Just as we saw operational semantics define how arithmetic expressions reduce to numeric values, we now need formal rules for boolean expressions. These include comparisons (x < 5), logical operators (and, or, not), and importantly, how these operators can skip evaluation of parts of the expression.
Core Semantic Rules
In operational semantics, we write judgments that describe evaluation:
- Literal values:
true ⇓ trueandfalse ⇓ false(base cases) - Negation: If
e ⇓ truethennot e ⇓ false, and vice versa - Comparisons: If
e₁ ⇓ n₁ande₂ ⇓ n₂, thene₁ < e₂ ⇓ (n₁ < n₂)
Short-Circuit Evaluation
This is the crucial part! Boolean operators often don't evaluate both operands:
AND (conjunction):
- If
e₁ ⇓ false, thene₁ and e₂ ⇓ falsewithout evaluating e₂ - If
e₁ ⇓ trueande₂ ⇓ v, thene₁ and e₂ ⇓ v
OR (disjunction):
- If
e₁ ⇓ true, thene₁ or e₂ ⇓ truewithout evaluating e₂ - If
e₁ ⇓ falseande₂ ⇓ v, thene₁ or e₂ ⇓ v
Think of it like a guard checking doors: if the first door reveals the answer, why check the second?
This matters for correctness (avoiding errors in x != 0 and 10/x > 2) and performance.
Key Takeaway: Operational semantics for boolean expressions define precise evaluation order and short-circuit rules, where logical operators may skip evaluating their second operand based on the first operand's value.