Concurrent state evolution

You can call this my origin story as a developer. I will tell it in chronological order.

And no—the story did not turn me into a villain. That remains true even though I am a Doctor (a PhD).

The bug that started it

This section explains why unclear ownership let overlapping work move the vehicle marker out of order.

My first assignment at a new job was a replay engine. A replay engine repeats saved movement from an earlier trip.

The engine read recorded coordinates, which are saved location points. It moved a vehicle marker along the recorded route.

The engine also supported pausing and resuming. Between each pair of points, it moved the marker smoothly.

A Clojure go-loop read the coordinates. A go-loop is an asynchronous loop.

An asynchronous loop can wait without stopping other work. Other tasks can run during that wait.

The loop read from a channel. A channel is a queue shared by tasks that may run at the same time.

Such tasks are concurrent because their work can overlap. They do not necessarily run in a fixed order.

On each turn, the loop calculated a step. It then moved the marker and chose what should happen next.

Those jobs could overlap because nothing made their order explicit. Ownership meant sole responsibility for choosing the next step.

Two steps both believed they had that responsibility. Each chose “what happens next,” so the marker jumped.

A vehicle is a state machine

This section explains how named modes and ordered changes described the replay engine.

At the same time, I was reading Guy Steele’s Lambda: The Ultimate GOTO.

The paper makes a useful, simple claim. A loop can be a function that names itself at the end.

Several such functions already form a state machine. A state machine uses named conditions and rules for changing them.

A state records the machine’s current condition. A mode is the name for one such condition.

A transition is one change from the current mode. Its successor is the mode that comes next.

You do not need a special “state machine framework.” You need a current mode and a rule for its successor.

The replay engine was plainly such a machine. Its mode was :stopped, :running, :paused, or :resumed.

Each transition chose one successor. This explicit choice fixed the order of the machine’s next step.

Within :running, the diagram also shows [:running :frames]. This is a nested state, meaning a more specific condition inside another.

The nested condition handles frame interpolation. Frame interpolation moves the marker in small steps between two recorded points.

I stored the state in an atom. An atom is Clojure’s small, shared box for a value that can change.

The outside world could interrupt the atom’s work. A pause click was one such interruption.

A multimethod advanced the machine. A multimethod is one function that selects another function from a value.

The selected function is called a handler. Here, the current :status selected the handler.

Clojure — the decider

(defmulti resolve-state (fn [state-atom] (:status @state-atom)))

;; running: which recorded point do we head for next?
(defmethod resolve-state :running [state-atom]
  (let [next-position (next-position-index state-atom)]
    (if (= next-position :end)
      (swap! state-atom assoc :command :pause)
      (swap! state-atom merge {:command :advance :position-index next-position}))
    (execute-async #(execute-action state-atom))))

;; running between two points: take one step of the slide toward the target
(defmethod resolve-state [:running :frames] [state-atom]
  (let [{:keys [distance-elapsed start end]} @state-atom
        step (get speeds @(rf/subscribe [:replay/playback-speed]) :1x)]
    (if (zero? distance-elapsed)
      (let [line (line-string [start end])]                ; the segment to slide along
        (swap! state-atom assoc :line line :distance (length line) :distance-elapsed step))
      (swap! state-atom update :distance-elapsed + step))
    (swap! state-atom assoc :command [:advance :frames])
    (execute-async #(execute-action state-atom))))

(defmethod resolve-state :stopped [state-atom]
  (swap! state-atom assoc :command :stop)
  (execute-async #(execute-action state-atom)))

(defmethod resolve-state :paused [state-atom]              ; stash what we were doing
  (swap! state-atom rename-keys {:command :prev-command})
  (swap! state-atom assoc :command :pause)
  (execute-async #(execute-action state-atom)))

(defmethod resolve-state :resumed [state-atom]             ; and pick it back up
  (swap! state-atom rename-keys {:prev-command :command})
  (execute-async #(execute-action state-atom)))

Running has a smaller phase inside it

This section explains why frame-by-frame movement belongs inside the broader :running mode.

Most of the time, the vehicle is simply :running. Between two GPS points, it has a more specific job.

A GPS point is a location measured by the Global Positioning System. An animation frame is one displayed step of movement.

Between the points, the vehicle moves one frame at a time. That temporary job belongs inside :running.

It is not a sibling of :paused. Here, a sibling would be another mode at the same level.

Therefore, the state is [:running :frames]. It is not a new top-level label such as :running-between-frames.

Read the state as “running, specifically in the frame-moving phase.” A vector is an ordered collection written inside square brackets.

The vector’s first value answers the broad question. Its second value adds the specific detail.

The multimethod can dispatch on the whole vector. Dispatch means selecting a handler from the supplied value.

Other code may care only about the broad mode. That code can ignore the remaining detail.

The temporary phase stays local to :running. It does not leak into the rest of the system.

Decide, then do

This section explains the exact order between choosing a command and performing its work.

First, resolve-state decides. Then, execute-action performs.

This order gives each step one owner. The decider alone chooses what should happen next.

A command is the stored name of that next work. resolve-state records the command without moving the marker on the displayed map.

Next, execute-action performs the real work. For example, it may move the marker.

After that work, it hands control back to the decider. The same order then begins again.

Clojure — the effects

(defmulti execute-action (fn [state-atom & _] (:command @state-atom)))

;; advance: grab the next pair of route coordinates, drop into frame mode
(defmethod execute-action :advance [state-atom]
  (let [[start end] @(rf/subscribe [:replay/route-coordinates])]
    (rf/dispatch-sync [:replay/vehicle-position start])
    (swap! state-atom assoc
           :start start
           :end end
           :distance-elapsed 0
           :position start
           :status [:running :frames]))
  (resolve-state state-atom))                ; bounce back to deciding

;; advance one frame: slide the marker a step along the current segment
(defmethod execute-action [:advance :frames] [state-atom]
  (let [{:keys [line distance distance-elapsed]} @state-atom]
    (if (< distance-elapsed distance)
      (let [position (along line distance-elapsed)]
        (rf/dispatch-sync [:replay/vehicle-position position])
        (swap! state-atom assoc :position position :status [:running :frames]))
      (swap! state-atom assoc :status :running)))   ; segment finished, back to running
  (resolve-state state-atom))

(defmethod execute-action :pause [state-atom]
  (swap! state-atom assoc :status :paused))

The two roles, in plain pseudocode

# Two roles bouncing off each other — no language required.

decide(state):                 # pure: choose the next command, touch nothing
    state.command = transition_for(state.status)
    trampoline(do, state)      # hop — schedule the effect, don't call it directly

do(state):                     # effectful: perform the command, then loop back
    perform(state.command)     # move the marker, persist, call an API…
    trampoline(decide, state)  # name the next, let the trampoline bounce

A trampoline is a scheduling technique. It schedules the next call instead of making that call directly.

The two multimethods use this technique in turn: decide, perform, decide. The program keeps returning to the event loop.

The event loop is the system that runs ready work one piece at a time. Returning there prevents recursive calls from piling up forever.

A recursive call is a function call that eventually leads back to the same function. Each direct call would otherwise remain unfinished.

A state names its successor rather than calling it. Here, it writes :status or :command into the atom.

Then execute-async schedules the next step. The atom serves only as a place to leave the successor’s name.

The later channel version moves that name and its data together. Both become one explicit value describing the transition.

The channel replaces the setTimeout

This section explains how a Redux-style loop supplied the missing transition order.

Then I saw the same shape in Redux in ClojureScript with Rum.

The Redux pattern keeps state in one place. It also provides one place that may change that state.

An event is a value that describes something that happened. A reducer is a function that calculates the next state.

The reducer receives the current state and one event. It returns the next state.

That machinery was exactly what I needed. A go-loop took events from a channel.

A multimethod served as the reducer. The loop therefore handled one event before taking the next.

(go-loop []
  (when-let [[type data] (<! actions)]
    (swap! state transform data type)
    (recur)))

That was the missing piece. The replay engine already named successors instead of calling them.

setTimeout is a timer that schedules later work. I replaced that timer with a channel.

One go-loop then became the trampoline. It received each named successor in an explicit order.

I call the resulting pattern concurrent state evolution. It evolves state while tasks may otherwise overlap.

The payload rides with the name

This section explains how each transition carries both its next action and the required data.

The channel now serves as the trampoline. It receives each successor and schedules the corresponding handler.

A state never calls its successor. It puts the successor’s name and payload on the channel.

The payload is the data that the next step needs. Data that once hid in an atom now travels with the transition.

A transition value is the complete message placed on the channel. Each message has the form [action data].

The action says what happens next. The data says what that action should use.

Each [action data] value is therefore self-contained. It keeps the next step with the data for that step.

Later, I used this pattern in an email-extraction pipeline. A pipeline is an ordered series of processing steps.

There, the “states” were pipeline steps rather than vehicle modes. The loop itself stayed the same.

Clojure — the email pipeline

(defmulti evolve-flow (fn [action _data _config _ch] action))

;; persist the raw email, then hand the saved id on to the next step
(defmethod evolve-flow ::persist-email
  [_ email config ch]
  (let [saved (p/create-email! (:db config) email)]
    (dispatch-action ch ::extract-order-data {:email-id (:id saved)})))   ; next state + payload

;; pull structured order fields out of the email body with the assistant
(defmethod evolve-flow ::extract-order-data
  [_ {:keys [email-id]} config ch]
  (let [order (.processMessage assistant (load-body email-id))]
    (dispatch-action ch ::persist-order-details {:email-id email-id :order order})))

(go-loop []
  (when-let [[action data] (<! ch)]
    (try
      (evolve-flow action data config ch)
      (catch Throwable t
        (dispatch-error! ch action t data)))
    (recur)))

The same loop, beyond Clojure

# Any language with a queue/channel can run this loop.

loop forever:
    action, payload = take(channel)          # blocks until a message arrives
    try:
        handlers[action](payload, channel)   # may push the next (action, payload)
    except err:
        push(channel, (ERROR, { action, payload, err }))

# A handler names its successor and ships the data that successor needs:
handler EXTRACT_ORDER (payload, channel):
    order = ai.extract(payload.email)
    push(channel, (PERSIST_ORDER, { order }))   # next state + payload

What this buys you

This section explains the three practical properties that come from one ordered transition loop.

Putting every transition through one loop gives you a few useful properties:

• One vantage point. Every transition passes through the same place. One log line can describe the entire walk. The loop also processes one transition at a time.
• Failure is an action. A handler may fail before it returns. The loop then turns that error into an error action. That action carries the failing step and its payload. An error policy is the rule for responding to failures. This policy lives in the loop instead of every handler.
• Earlier work can be undone. An error can route the process to a rollback. A rollback reverses work that already finished. A later failure can therefore undo an earlier database write. This is the basic saga idea. A saga compensates for completed work when the full process cannot finish.

One thing the loop can't catch

This section explains why work that outlives its handler must report its own errors.

A try/catch is code that handles errors thrown while it runs. Here, it only sees errors thrown before the handler returns.

A handler may start work that continues separately. One example is another thread, which is an independent path of execution.

Another example is a fire-and-forget request. Such a request starts work without waiting for its result.

That separate work must catch its own errors. It must then re-dispatch them by sending a new error action.

The trampoline sequences transitions. It does not supervise the separate work beneath them.

Here, supervise means watching that work through completion. The loop stops watching when the handler returns.

That is the whole pattern I still use. Before stopping, I should say that I did not invent it.

This is not exacly new

This section explains which parts predated my implementation and what I actually observed.

None of the parts are new. Loops expressed through recursion predate this implementation.

Recursion means that a function eventually invokes itself. The state-machine idea also came earlier.

The Redux loop predates my implementation too. My useful observation was that these parts share the same shape.

Aligning them changes a fragile concurrent loop. It becomes an explicit series of state transitions that I can reason about.

Name the next state instead of calling it. Carry its payload with it. Let a channel perform the recursion.