Graphs and State Machines for Agents, Part 3: Building the Machine

Part 2, “Every Graph Is a State Machine,” ended on a promise and a diagram. It showed that the agent graph you drew in Part 1 is a finite state machine, feature for feature, and it said the drawing is what makes a system checkable instead of hopeful. This part collects the promise. We are going to build the machine, and the first thing to notice is how little there is to build.

Here is the shift this whole part turns on, stated plainly: the transition function is data. Not a subroutine, not a class hierarchy, not a framework. A plain value you can print, store, diff, send over a wire, and render into a picture. Once you treat it that way, something strange happens to the bugs you spend your life fighting. Impossible states, duplicate submits, leaked timers, forgotten cleanup: they stop being things you test for and start being things you cannot express. You do not defend against them. You build a machine in which they have no name.

The interpreter is one line

Start with the smallest thing that works, because it is almost embarrassingly small. A state machine is two pieces: a table that says which event moves you where, and an interpreter that reads the table. Write the table as a plain object.

const machine = {
  idle:    { SUBMIT:  'loading' },
  loading: { RESOLVE: 'success', REJECT: 'failure' },
  success: {},
  failure: { RETRY:   'loading' },
};

Now the interpreter. Given a state and an event, look up what the table says. If the table has no entry for that event in that state, stay where you are.

function transition(state, event) {
  return machine[state]?.[event] ?? state;
}

That is the whole engine. One expression. It reads machine[state][event], and if that move is undefined it falls through to state and the event is ignored. This is the double-click bug from Part 2 disappearing in a single ??: SUBMIT has no entry under loading, so a second submit while the first is in flight returns loading unchanged. Nothing to debounce, nothing to disable.

Look at what you get for that one line, because it is more than tidiness.

• The whole feature fits on a screen. Every state, every event, every move is in one object you can read top to bottom. There is no hunting through six files to reconstruct what the system does. The behavior is not described by the code; it is the code, sitting in front of you as a shape.
• A diff shows behavior, not plumbing. When someone changes what the feature does, the change lands as a line added or removed from the table. A reviewer sees “CANCEL now returns to idle from loading” as a one-line diff, not as a subtle reordering of conditionals three functions deep. The intent is legible in the patch.
• The machine is just a value, so it travels. You can JSON.stringify it, store it in a database, send it to a client, load a different table for a different customer, or feed it to a renderer that draws the diagram automatically. Logic that lives in control flow can do none of this. Logic that lives in data can do all of it for free.
• Testing changes character. States times events is a finite grid. Instead of sampling a few happy paths and hoping, a test can walk the entire table: for every state, fire every event, assert the result. You are not testing a sample of behavior. You are checking the whole specification, because the specification is small and finite by construction.

The switch version, and letting the compiler hold the line

The object table is the most flexible form. There is a second form that trades a little flexibility for a guarantee the object cannot give you: the switch. It is more verbose, and in a typed language that verbosity buys something real.

type State = 'idle' | 'loading' | 'success' | 'failure';
type Event = 'SUBMIT' | 'RESOLVE' | 'REJECT' | 'RETRY';

function transition(state: State, event: Event): State {
  switch (state) {
    case 'idle':    return event === 'SUBMIT'  ? 'loading' : state;
    case 'loading': return event === 'RESOLVE' ? 'success'
                  :  event === 'REJECT'  ? 'failure' : state;
    case 'success': return state;
    case 'failure': return event === 'RETRY'   ? 'loading' : state;
    default: {
      const _exhaustive: never = state;
      return _exhaustive;
    }
  }
}

The interesting line is the one that looks like ceremony. In the default branch, state should be impossible, because every case is handled, so TypeScript narrows its type to never. Assign it to a never variable and nothing happens. But add a fifth state to the union, disconnected, and forget to add its case, and now state in the default is 'disconnected', which is not assignable to never. The build fails. The state you forgot to handle is caught by the compiler, at your desk, not by a user in production three weeks later.

Rust takes this further with the typestate pattern, where the state is not a value you check at runtime but a type the compiler tracks. Each state is a distinct type, and a transition consumes one and returns another.

struct Idle;
struct Loading;

impl Idle {
    fn submit(self) -> Loading { Loading }
}

A Loading value has no submit method, so calling submit on something already loading is not a runtime guard that returns early. It is a program that does not compile. The illegal transition is not caught. It cannot be written. This is the same idea as Part 2’s “make illegal states unrepresentable,” pushed all the way into the type system, where the check happens before the program has ever run.

You already wrote this, and called it a reducer

If you have written a Redux reducer or a useReducer hook, you have already written transition. The signature is identical: (state, action) => nextState, which is transition(state, event) -> nextState in different clothes. The reducer pattern took over React state management precisely because this shape is the right one. So why do most reducers still ship the bugs a state machine kills?

Because of one habit. Look at how almost every reducer is written:

function reducer(state, action) {
  switch (action.type) {   // switching on the EVENT
    case 'SUBMIT':  return { ...state, status: 'loading' };
    case 'RESOLVE': return { ...state, status: 'success' };
    // ...
  }
}

It switches on the action. Any action can change anything from anywhere, because the current state is never consulted before the move. That is the four-boolean mess from Part 2 with nicer syntax: RESOLVE will happily set success even when you were idle and never sent a request. A reducer becomes a real state machine the moment it checks the current state first.

function reducer(state, action) {
  const next = machine[state.status]?.[action.type];
  if (!next) return state;              // event illegal here: ignore it
  return { ...state, status: next };
}

One extra lookup. Now RESOLVE from idle finds no entry and is ignored, exactly as it should be. The reducer you already know how to write was one line away from being a machine that cannot enter a nonsense state. Most teams get this backwards: they add more action handlers to cover the new edge cases, when the fix is to stop letting an event fire without asking where you are.

Finite state is not all your state

Now the objection every working engineer has been holding. Real components have form inputs, retry counts, timestamps, fetched payloads. You cannot enumerate a text field. So how can the state be finite?

It is not, and it was never supposed to be. The trick is a split that the textbooks call an extended state machine, and once you see it you cannot unsee it.

• The finite mode is small, qualitative, and enumerable. idle, loading, editing, disconnected. There are four of them. They are the named situations the system can be in, and they are the thing the machine governs.
• The context, sometimes called extended state, is everything unbounded that rides alongside: the form values, the retry count, the data you fetched, the timestamp of the last attempt. It is never enumerated and never part of the finite set. It is just a bag of data the machine carries.

The mode answers “where are we.” The context answers “with what.” The machine is the law over the mode; the context is cargo. Formally the transition function grows two arguments and two results:

transition(state, context, event) -> [nextState, nextContext, actions]

Same idea as before, now honest about the data. It still takes where you are and what happened. It now also takes the cargo, and returns the next mode, the next cargo, and (we will get to this) a list of things to do.

Guards decide, actions describe

Two constructs turn the table into something that runs real software.

A guard is a condition on a transition. The move only fires if the condition holds. The canonical case is a bounded retry: in loading, a REJECT should go back to loading and try again while there are attempts left, and to a terminal gaveUp once they run out. The guard reads the context to decide.

function transition(state, context, event) {
  switch (state) {
    case 'loading':
      if (event.type === 'RESOLVE') {
        return ['success', { ...context, data: event.data }, []];
      }
      if (event.type === 'REJECT') {
        return context.retries < 3
          ? ['loading', { ...context, retries: context.retries + 1 }, ['scheduleRetry']]
          : ['gaveUp', context, ['reportFailure']];
      }
      return [state, context, []];
    default:
      return [state, context, []];
  }
}

Look at the return values. ['loading', {...}, ['scheduleRetry']]. The third element is a list of actions, and here is the design choice that matters: the transition does not perform the side effect. It returns it. scheduleRetry is a string, a piece of data naming a thing to do, not a call to a timer API. Something outside the function, an interpreter, receives that list and executes it.

This one move keeps transition pure. It takes values and returns values, touching nothing in the outside world. That means you can test it with no mocks at all: call it with a state, a context, and an event, and assert on the tuple it returns. No fake timers, no stubbed fetch, no spy on a spinner. The hard-to-test part, the effects, is isolated in the interpreter, and the logic, the part with all the branches, is a pure function you can hammer with a table of inputs. Redux middleware and Elm’s command pattern are built on exactly this separation: the reducer returns a description of what should happen, and a runtime layer makes it happen.

const states = {
  loading: {
    onEntry: ['startSpinner', 'startTimeout'],
    onExit:  ['stopSpinner', 'cancelTimeout'],
  },
};

That distinction, effect-on-the-state versus effect-on-the-edge, has a name older than any of these frameworks.

Mealy and Moore, and the question they force

Classical automata theory split machines by where their output comes from.

A Moore machine produces output based on the state alone. A traffic light is Moore: while it is in green, it stays lit green, and the output is a function of the state, nothing else. A Mealy machine produces output based on the state and the event that arrived. A vending machine is Mealy: it dispenses a can when a COIN event lands while in idle, so the output depends on both where you were and what happened.

Map that onto what we just built and it lines up exactly. Entry and exit actions are Moore-flavored: they fire because you are entering or leaving a state, tied to the state itself. Transition actions like scheduleRetry are Mealy-flavored: they fire because of a specific edge, a specific event arriving in a specific state.

The reason to know the distinction is that it turns a vague question into a sharp one. For any effect, ask: should this happen because of the state I am in, or because of how I got here? Starting a spinner is a property of being in loading, however you arrived, so it is entry action, Moore. Firing an analytics event for “user clicked retry” is a property of that specific edge, so it is transition action, Mealy. Conflate the two and you get subtle bugs: a spinner that flickers because it was tied to an event instead of the state, or a retry-count increment that runs on the wrong edge. Naming which kind of effect you have is how you put it in the right place.

This is not new, it is the substrate

None of this is a pattern someone invented for React. It is the model serious systems have always been specified in, precisely because it is the one you can verify.

• TCP is a state diagram. Every connection walks a fixed set of states: LISTEN, SYN-SENT, ESTABLISHED, FIN-WAIT-1, TIME-WAIT, and the rest. RFC 793 specified it as a diagram back in 1981 because prose was too ambiguous to make two machines that had never met agree on what every packet means. The diagram was the specification, not a picture of it.
• Regex engines run on state machines. A regular expression compiles to a deterministic finite automaton that consumes one character and moves to one next state, constant time per character, no backtracking. That is why grep scans enormous files at the speed of the disk. The finiteness is the performance.
• The Pac-Man ghosts are four state machines. Each ghost is a small machine cycling through chase, scatter, and frightened, and their famous different personalities come entirely from four different transition tables, not four different engines. Same interpreter, four tables, four behaviors. That is the “machine as data” claim made playable.
• A CPU is a clocked state machine. The control unit steps through states in hardware on every clock edge, and hardware description languages like Verilog and VHDL treat the finite state machine as a primary idiom, because the thing being described genuinely is one.
• UI forms are state machines whether you admit it or not. A form moves through pristine, editing, validating, submitting, and then succeeded or failed. The classic bug where a modal closes but its dark overlay stays on the screen is an unintended combination of two independent flags, and an explicit machine makes that combination unrepresentable, the same way the four-boolean mess was made unrepresentable in Part 2.

Statecharts, for when flat machines explode

There is one honest limit to the flat machine, and it shows up fast. Imagine a text editor with bold, italic, and underline, each independently on or off. As a flat machine you need a state for every combination: bold, bold_italic, bold_underline, bold_italic_underline, and so on. Three toggles is eight states. Add a fourth and it is sixteen. The states multiply because the concerns are independent but the flat machine forces them into one list.

David Harel solved this in 1987, in a paper titled “Statecharts: A Visual Formalism for Complex Systems.” It adds three constructs to the plain finite state machine, and together they are what let state machines scale to real software.

If this sounds familiar, it should: UML state diagrams are statecharts under another name, and this is the model that libraries in the XState family implement directly. Harel’s three constructs are not exotic extensions. They are the difference between a formalism that works on a toy and one that survives a real application without exploding into thousands of states.

You can build one now

Go back to the handle the series turns on: a prompter asks a question; an architect draws a graph. Part 1 drew the shape. Part 2 named it. This part built it, and the build turned out to be smaller than the bugs it removes. A table of states to events, a one-line interpreter that reads it, a split between the finite mode and the context riding alongside, guards that decide, actions returned as data, entry and exit effects tied to states, and Harel’s three constructs for when the flat machine gets too big. The whole discipline still compresses to one instruction you can carry into any framework: name the states, the events, and the transitions.

You now have every piece to build a working machine for any feature in front of you. The reason we built it in this order is what comes next. Part 4, “Agents as State Machines,” points this exact construction at an LLM agent, and the same guarantees that killed the double-submit and the leaked timer become something heavier: reliability by construction, and then safety, for a system whose steps you do not fully control.