Mutable data and simulators

Lesson 10 gave us an operational model in which a name denotes a binding in a frame, and assignment overwrites that binding. There the changing state lived in variables. This lesson moves it where real systems keep it — inside data structures. We add two mutators to the pairs of Lesson 04, set_head and set_tail, and from that single capability we build mutable queues (whose rear-pointer trick is the whole reason to allow mutation), mutable tables, an event-driven digital-circuit simulator, and bidirectional constraint propagation. Along the way we meet the new hazard mutation brings: sharing — when two structures point at the same cell, a change to one is silently a change to the other.

1 · Mutators, sharing, and identity

A pair (Lesson 04) was a constructor pair(a, b) with selectors head/tail. Make it mutable by adding two mutators that overwrite a field in place:

set_head(p, v);   // change the head field of pair p to v
set_tail(p, v);   // change the tail field of pair p to v

This is the environment model's assignment, aimed at a data object's field instead of a frame binding. It immediately raises a question that immutable data never did: what if two names refer to the same pair? Then mutating through one is visible through the other — they are shared, or aliased.

const a = list(1, 2, 3);     // a -> [1] -> [2] -> [3]
const b = a;                 // b is the SAME list (alias), not a copy
const c = list(4, 5);
set_tail(c, tail(tail(a)));  // c now shares a's last cell: c -> [4] -> [5] -> [3]

set_head(tail(a), 99);       // intend to edit "a" only...
// a is now (1, 99, 3)
// b is now (1, 99, 3)   <-- b changed too: b IS a
display(b);   // (1, 99, 3)  -- surprise if you thought b was a snapshot

 a ─┐
    ├─> [1|·]──>[99|·]──>[3|/]
 b ─┘                      ^
                           |   c and a SHARE this last cell
 c ────> [4|·]──>[5|·]─────┘

The discipline that tames this is the same as always: keep mutation behind a small interface. Expose constructors, selectors, and a few named mutators; never let clients hold raw cells and splice them by hand. The abstraction barrier now guards who is allowed to change what.

2 · A mutable queue — the rear-pointer is the point

A queue is FIFO: insert at the rear, remove from the front. You could implement it on an immutable list, but inserting at the rear of an n-element list means rebuilding all n cells — Θ(n) per insert. Mutation buys the whole reason a queue exists: keep an explicit rear pointer to the last cell so insertion is Θ(1).

function make_queue() { return pair(null, null); }   // [front_ptr | rear_ptr]
const front_ptr = q => head(q),  rear_ptr = q => tail(q);
const set_front = (q,p) => set_head(q,p),  set_rear = (q,p) => set_tail(q,p);
const is_empty = q => front_ptr(q) === null;

function insert_queue(q, item) {
  const cell = pair(item, null);
  if (is_empty(q)) { set_front(q, cell); set_rear(q, cell); }
  else { set_tail(rear_ptr(q), cell);    // splice onto the OLD rear  -- O(1)
         set_rear(q, cell); }            // advance the rear pointer  -- O(1)
  return q;
}
function delete_queue(q) {
  set_front(q, tail(front_ptr(q)));      // drop the front cell        -- O(1)
  if (is_empty(q)) set_rear(q, null);
  return q;
}

insert a, then b, then c:

  front_ptr ─┐                        ┌─ rear_ptr
             v                        v
            [a|·]───>[b|·]───>[c|/]

delete_queue: just advance front_ptr to the next cell — no shifting, no copy.

3 · Mutable tables

A table maps keys to values with in-place update. Represent it as a headed list of [key, value] records; lookup walks the chain, insert mutates an existing record or splices a new one after the head.

function make_table() { return list("*table*"); }   // a dummy head cell
function lookup(key, table) {
  const rec = assoc(key, tail(table));               // find [key,val] or false
  return rec ? tail(rec) : undefined;
}
function insert(key, value, table) {
  const rec = assoc(key, tail(table));
  if (rec) set_tail(rec, value);                      // UPDATE in place
  else set_tail(table, pair(pair(key, value), tail(table)));  // SPLICE new record
}

A two-dimensional table is a table whose values are themselves tables (a subtable per first key) — exactly the operation/type table that drove apply_generic in Lessons 07–08, now seen as the mutable structure it always was. Building generic dispatch required a mutable table so that installing a new representation could add an entry without rebuilding the whole structure.

4 · The digital-circuit simulator — event-driven mutation

Now mutation earns its keep as simulation. Model a digital circuit as wires carrying a signal (0 or 1) and function boxes (and/or/inverter gates) that watch their input wires and, after a propagation delay, set their output wire. The engine is an agenda: a priority queue (built from §2's mutable structure) of actions scheduled at future times.

function inverter(input, output) {
  function invert_input() {
    const new_val = input_signal(input) === 0 ? 1 : 0;
    after_delay(INVERTER_DELAY, () => set_signal(output, new_val)); // SCHEDULE
  }
  add_action(input, invert_input);   // watch the input wire
}
// driver loop:
function propagate() {
  while (!agenda_empty(the_agenda)) {
    const action = first_agenda_item(the_agenda);
    action();                        // may mutate wires and schedule more events
    remove_first_agenda_item(the_agenda);
  }
}

5 · Constraint propagation — relations, not procedures

The simulator still has a direction: inputs flow to outputs. Constraint propagation drops even that. A constraint like a + b = c is a relation: a network of connectors (cells holding a value or "no value") wired to constraint boxes (adder, multiplier, constant). Set any two of a, b, c and the box computes the third — it has no preferred direction. The same adder that finds c from a,b finds a from c,b. When a connector gets a value it notifies its constraints; each constraint checks whether it now has enough known values to fix an unknown, and if so sets it (recording who set it, so retracting a value can propagate backward). This is a foretaste of Lesson 18's logic programming, where "run forwards or backwards" becomes the whole paradigm — and it is only possible because connectors are mutable, shared, observed objects.

Common mistakes / failure modes

Checkpoint exercise

const q = make_queue();
insert_queue(q, "a"); insert_queue(q, "b");
delete_queue(q); insert_queue(q, "c");

Where this points next

Mutation behind a clean interface gave us queues, tables, and faithful simulations of changing worlds. But notice what the agenda quietly guaranteed: the circuit simulator only computed the right answer because events were processed in a single, definite time order. The instant mutable state is shared among processes that run concurrently — that interleave rather than run in one fixed sequence — that guarantee evaporates, and the order in which operations touch the shared cell becomes a correctness problem. Two withdrawals from one account, interleaved the wrong way, can lose an update. Lesson 12 confronts this directly: concurrency turns the implicit time that mutation introduced into an explicit hazard, and asks what it means for a concurrent program to be correct.

Interview prompts

• What hazard does mutating data introduce that mutating a variable did not make obvious? (§1 — sharing/aliasing: two structures pointing at the same cell, so a change through one is silently a change through the other; identity now matters, not just contents.)
• Why is mutation the whole point of a mutable queue? (§2 — an explicit rear pointer plus set_tail gives Θ(1) rear insertion; without mutation each insert would rebuild the list in Θ(n).)
• How does insert on a mutable table avoid rebuilding it, and where have you seen this table before? (§3 — it mutates an existing record with set_tail or splices one new record after the head; it is the operation/type table behind apply_generic in Lessons 07–08.)
• Explain the digital-circuit simulator's architecture. (§4 — wires are stateful objects with watcher actions; gates schedule set_signal on outputs after a delay; an agenda (mutable time-ordered queue) drives events, each of which may schedule more — event-driven mutation.)
• What makes constraint propagation bidirectional? (§5 — a constraint is a relation among connectors with no preferred direction; given enough known connectors a box computes any unknown, so the same adder runs "forwards" or "backwards" — a preview of logic programming.)
• Why does b = a followed by set_head(a, ...) change b? (§1 — b = a aliases the same object rather than copying; the mutation is visible through every name that reaches the cell.)
• What did the agenda silently rely on, and why does that point to concurrency? (§4, Where next — a single definite time order for events; once shared mutable state is touched by interleaving processes, that order is gone and ordering becomes a correctness problem.)