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

Semantics of Variable Assignment and State

Modeling program state as environments and defining how assignments update variable bindings.

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.