Semantics of Variable Assignment and State
You'll learn: How to formally model memory and assignment so a program can remember and update values.
The Problem: Programs Need Memory
Until now, our operational semantics have dealt with expressions that evaluate to values—but real programs remember things. When you write x = 5, the program needs to store that information somewhere and retrieve it later when you use x.
Environments as Program State
We model program state (memory) as an environment: a mapping from variable names to their current values. Think of it like a dictionary or table:
{ x ↦ 5, y ↦ 10, z ↦ 7 }
This says variable x holds 5, y holds 10, and so on.
Assignment Updates the Environment
An assignment statement like x := 8 doesn't evaluate to a number—it changes the environment. We write semantic rules that show the before and after states:
⟨x := 8, { x ↦ 5, y ↦ 10 }⟩ → { x ↦ 8, y ↦ 10 }
The assignment replaced x's old binding (5) with the new one (8), leaving y untouched.
Variable Lookup
When evaluating x + 3, we look up x in the current environment, retrieve its value, then proceed with arithmetic.
Why This Matters
By formalizing state as environments and assignment as environment updates, we can reason precisely about:
- Which variables are in scope
- When values change
- Whether two program fragments behave identically
Key Takeaway: State is modeled as an environment mapping variables to values; assignment semantics define how operations update these bindings, enabling programs to remember and modify data over time.