Nested Modal Transducers

This is a summary of the original Nested Modal Transducers article from 2019 that might help make sense of how the implementation of Cosmos Boulders is laid out. Nested Modal Transducers is:

• A methodology for building hierarchical state machines in a purely functional setting (no in-place changes are made to data structures)
• At any given time, each state machine has a configuration, which is a data structure consisting of:
  • its mode (the traditional "state indicator": one of a finite, fixed set of labels)
  • its data (the "extended state", including any counters, flags, timers, etc.)
  • a collection of configurations, one for each of the sub-machines nested within this one
• When a state machine receives an input, it may transition to a new configuration, and produce zero or more outputs
• This is realized with a pure function called a transducer with the signature:
  • (Config × Input) → (Config' × [Output])
• The transducer for a state machine is responsible for transitioning all of its sub-machines by calling their transducers on the nested configurations
• In doing so it can intercept the input sent to the sub-machine, and the outputs returned from the sub-machine, and manage them as it sees fit

Some History

Reducers, popularized in the context of UI construction by Redux, are very useful as a purely functional model of state machines. However, they do not capture very well the idea that when the state machine enters or leaves a given state, something should happen. Nested Modal Transducers thus tries to extend the model, influenced by The Elm Architecture (which has been implemented in React as the [use-elmish][] hook) in which the functions return effects as well as a new state. They are thus "transducers" rather than reducers.

Use in Cosmos Boulders

While the Nested Modal Transducers exposition calls them "inputs" and "outputs" to keep the terminology generic, in practice "inputs" are often called "actions", and "outputs" are often called "effects", and this is the case in the Cosmos Boulders codebase as well.

Multiple return values are annoying to construct and deconstruct. Often, a transducer has no effects that it needs to communicate out. In that case, we can model it as a reducer, and we have two options: an adapter that takes a reducer and converts it to a transducer (by having it return also an empty list of effects); or an adapter that takes a transducer and throws away the effects it produces, on the knowledge that it will always be returning an empty list, so that it looks like a reducer to client code. Both allow for simpler usage at calling sites that expect a single return value from a function, but beyond that, the latter is probably preferable, as it keeps the types consistent (we can write all our transducer functions as functions which return a pair) and fo allows for a future where the (sub-)state machine in question does start producing effects.

Returning effects allows the sub state machines to be constructed with more locality of reference, which can support more modular construction and better encapsulation. For example, pressing the fire button causes the player to shoot a missile. Perhaps the player's ship is unable to fire (or something else); the player should be what decides whether a missile gets shot (or something else, when the fire button is pressed). But missiles are part of the game state, not the player state. The responsibility is spread out across multiple state machines. A solution is to pass the "fire button pressed" action down from the game, to the player, and have the player return a "shoot missile" effect, which the game intercepts and, in so doing, adds a new missile to the missiles list. Each state machine is therefore responsible for its own part. The Cosmos Boulders source code does not do this nearly as much as it could, largely because its design is descended from the original implementation (based on reducers rather than transducers), but there are vague plans to improve that design to capture a sharper presentation of this idea.

Notes

Transducers should probably be thought of as returning a multiset of effects, rather than a list, because order should not matter. On the other hand, if effects really are effects, order does matter; the issue is more of one where we must avoid designing state machines that can produce ambiguous outcomes due to producing multiple interdependent effects.