I often use Event-driven Finite State Machines to capture stateful behaviour. Doing so in combination with a compiler with a strong type system helps me to think about all possible combinations of the effects of commands on a given state, and what the events produced (if any) are. In particular, I find many programs required for embedded applications can often be safely expressed by using Event-driven Finite State Machines, leading to very high-quality outcomes. They're also great for managing those stateful scenarios where network communication takes place.
My intention here is to capture a pattern that I've found myself using a great deal. I didn't come up with this pattern, and in fact for me, this pattern evolved out of using Akka persistence for event sourcing (1). These are also known as Event-driven finite state machines, which are described as the "transition from one state to another is triggered by an event or a message" (2).
Here are the two function signatures that I use:
fn for_input(s: State, c: Command) -> Vec<Event>
fn transition(s: State, e: Event) -> State
The first function yields zero or more events to be caused, given a state and a command. The second function applies an event given a state to yield a new state.
Commands are an enumeration of actions that can be performed on the state machine and defined exclusively within the confines of it. Events can come from many places outside of the state machine and cause commands to manifest themselves for the for_inputs function. For example, the state machine might not be aware of a network, yet network events such as the receipt of data can manifest in one or more commands to submit to the for_inputs function.
The for_input function yields zero or more events having carried out the command, which may be side-effecting.
For each event returned from the for_input function, the transition function is then called, yielding a new state. The transition function avoids performing side-effects and is therefore pure. We should be able to replay events to produce a state without causing side-effects. More on that later.
These functions are able to be combined to perform commands and transition state e.g.:
fn run(s: State, c: Command) -> (Vec<Event>, State)
However, I find it useful to keep both of the functions distinct even when composed, as it helps think through:
- what commands upon state produce what events; and
- what events cause a transition from one state to another.
These considerations map nicely to FSM diagrams e.g.
Writing the code for these two separate concerns also maps quite nicely. Keeping the diagram up to date with the code, and treating it as the source-of-truth, pays dividends in communicating design and driving modifications to the code.
Another aspect of having the two functions is that the second function permits the restoration of the state from replaying a series of events. This is known as event-sourcing (3). In a nutshell, event sourcing permits us to reconstruct the state by replaying the events historically. We can therefore avoid replaying commands and their effects and call just the transition function. By leveraging event sourcing, we can also persist our events having called the for_input function, and subsequently restore our state on the state machine even when the host program is restarted.
States, Commands, and Events are often expressed in a language using enumerations. By leveraging pattern matching in languages such as Rust, Scala, and Kotlin, the compiler can help us ensure that we are thinking of all combinations of applying commands to state and events to the state. Resist the temptation to "catch-all" commands or events by using matching expressions (match arms) as it is inevitable that they'll be a state combination that you've not considered, and we want the compiler to help us exhaust them all. That said, there some commands that apply to all states. In our example, the Stop command may be universally applied no matter what the state. There are always exceptions.
The state objects will contain, well, state! This internal state can be shared between state objects leveraging the fact that there will only ever be one state at a time. Reference counting this internal state is common where value-copying may be expensive. In Rust, I've successfully used Rc<RefCell<T>> to share mutable internal states between each State enumeration.
Happy stateful programming!
(1) https://doc.akka.io/docs/akka/current/typed/persistence.html
(2) https://en.wikipedia.org/wiki/Event-driven_finite-state_machine
(3) https://martinfowler.com/eaaDev/EventSourcing.html
