关于WHILE小步解释器中State类型与upd函数的技术问询

Great question—this is a common point of confusion when shifting from imperative-style interpreters to functional implementations, especially with small-step semantics. Let’s break this down clearly:

State as a Function: What It Means #

You’re exactly right: in many functional WHILE interpreters, State is defined as type State = Var -> Val—a function that maps variable names to their current values.

This isn’t a requirement to manually write a custom function every time you need a state, though. Instead, it’s a clever use of functional programming’s immutability principle:

• A function naturally represents a lookup mapping: to get the value of variable x, you just call state x.
• Since functions are immutable in most pure functional languages, we avoid accidental side effects—critical for small-step semantics, where we need to track every discrete state change precisely.

How the upd Function Works (No Mutation Needed!) #

The trick here is that we never "modify" the original state. Instead, upd (short for update) returns a new state function that reflects the desired change. Let’s use a concrete example to make this tangible:

First, an initial state that returns a default value (like 0) for any variable:

initState :: State
initState _ = 0  -- All variables start at 0

Now, here’s what a typical upd function might look like:

upd :: State -> Var -> Val -> State
upd currentState var newValue = \queryVar -> 
  if queryVar == var 
    then newValue 
    else currentState queryVar

When you call upd initState "x" 5, you don’t change initState at all. Instead, you get a brand new function:

• If you pass "x" to this new function, it returns 5.
• For any other variable, it delegates to the original initState (returning 0).

This pattern perfectly aligns with small-step semantics: each evaluation step takes the current state and produces a new state, without ever mutating existing data.

Key Takeaway #

Think of state functions as snapshots of the program’s variable values at a specific step. initState is the starting snapshot, and upd lets you create new snapshots with one variable changed. This approach keeps your interpreter logic clean, predictable, and free of the bugs that can come from mutable state.

内容的提问来源于stack exchange，提问作者Peter Braun