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

Operational Semantics of While Loops

Recursive semantic rules that define iterative loop execution and termination conditions.

Operational Semantics of While Loops

What you'll learn: How formal semantic rules recursively define the execution and termination of iterative while loops.

The Core Idea

A while loop repeats a block of code as long as a condition remains true. In operational semantics, we describe this behavior using recursive rules that mirror the loop's iterative nature: check the condition, execute the body if true, then repeat the entire while statement with the updated state.

The Semantic Rules

Think of a while loop like a tollbooth inspector who repeatedly asks: "Does the condition still hold?" If yes, they process the body and circle back to ask again. If no, they let you pass.

Formally, we write two rules:

Rule 1 (Condition False): If the boolean expression evaluates to false in the current state, the loop terminates immediately without changing the state.

⟨b, σ⟩ ⇒ false
─────────────────────
⟨while b do S, σ⟩ ⇒ σ

Rule 2 (Condition True): If the boolean expression evaluates to true, execute the body statement S to get a new state σ', then recursively evaluate the entire while loop again in that new state.

⟨b, σ⟩ ⇒ true    ⟨S, σ⟩ ⇒ σ'    ⟨while b do S, σ'⟩ ⇒ σ''
──────────────────────────────────────────────────────────
⟨while b do S, σ⟩ ⇒ σ''

Why Recursion?

The recursion in Rule 2 elegantly captures iteration. Each loop iteration is a recursive call with an updated state. The base case (Rule 1) ensures termination when the condition becomes false.

Key Takeaway: While loop semantics use recursive rules to formalize iteration: one rule for termination when the condition is false, another that executes the body and recursively re-evaluates the loop with the updated state.