State Machines in Go

23 March 2021

This could be a very long post, as I go off on tangents about Chomsky and other language paradigms. But it’s Go, so it’s only fitting the post should be practical, if verbose ;)

Formal Languages and State Machines

If you studied Computer Science, you might remember the classes of automata - broadly, levels of computational power that a machine has (lots of this work was done by Turing, RIP):

Combinatorial Logic
Finite-State Automata
Pushdown Automata
Turing Machines

And the types of language that can express configurations of them (programme them), after Chomsky:

Type 3 aka Regular - Finite State Automata
Type 2 aka Context-free - (non-deterministic) Pushdown Automata
Type 1 aka Context-sensitive - bounded Turing Machines
Type 0 aka Recursively Enumerable - Turing Machines

The programming languages we use are Turing Complete (except when they’re not, like Terraform - why I hate the term infrastructure as code). This is a term that oft-bandied around, and I feel often misunderstood (eg, your computer does not have infinite memory, it can’t even address infinite memory). Anyway, I said no tangents.

Turing Complete languages are hard to reason about (if not impossible - the halting problem). Coding is hard. Often the algorithm we’re writing can be expressed in one of the more simple types of language. Have you ever written a numerical expression in your code? x = ((2 * y) + z)/12)? That’s a context-free language for a pushdown automaton.

Often times, just a Regular Language and its FSA will do. Regexs are this: a specialised DSL for writing programmes that match strings. They’re super-useful; way more concise than spelling that matcher out in Go code, and often much faster, as their “virtual machine” is optimised for running them and just them.

But to see the limit of their expressiveness, try to write a regex that matches a*bba*, where the numbers of as on each side must match.

Often though, we want more general FSAs. Think of them as “parsing” not text, but sequences of arbitrary input / events.

Finite State Automata

aka FSM - Finite State Machines, DFSA - Deterministic Finite State Automata (there are technical differences with the deterministic bit; I list these for SEO).

FSA are often drawn like this (we love graphviz, and Wikipedia):

So, we want to embed an FSA in our Turing-Complete language. Some provide special syntax to make this easy:

In Scala using Akka


class Buncher extends FSM[State, Data] {

startWith(Idle, Uninitialized)

when(Idle) {
    case Event(SetTarget(ref), Uninitialized) =>
      stay().using(Todo(ref, Vector.empty))
}

onTransition {
    case Active -> Idle =>
      stateData match {
        case Todo(ref, queue) => ref ! Batch(queue)
        case _                => // nothing to do
      }
}

when(Active, stateTimeout = 1 second) {
    case Event(Flush | StateTimeout, t: Todo) =>
      goto(Idle).using(t.copy(queue = Vector.empty))
}

whenUnhandled {
    // common code for both states
    case Event(Queue(obj), t @ Todo(_, v)) =>
      goto(Active).using(t.copy(queue = v :+ obj))
    case Event(e, s) =>
      log.warning("received unhandled request {} in state {}/{}", e, stateName, s)
      stay()
}

initialize()
}

And in Elixir using OTP

defmodule Conversation do

use GenFSM

def start_link() do
    GenFSM.start_link(__MODULE__, :na)
end

def hello(pid) do
    GenFSM.send_event(pid, :hello)
end

def init(:na), do: {:ok, :martin, nil}

def martin(:hello, nil) do
    IO.puts "Hello, Paul"
    {:next_state, :paul, nil}
end

def paul(:hello, nil) do
    IO.puts "Hello, Martin"
    {:next_state, :martin, nil}
end
end

FSA in Go

For languages without first-calls (or close) support, we want to make it easy and simple to:

Express the FSA logic without getting lost in other details of the language
Eyeball the FSA and reason about its behaviour, especially its side-effects (or lack thereof)
Spot from 1000ft away that it’s an FSA we’re looking at, and that’s the mental model we should apply.

Here are a few patterns that have been around in imperative languages for ages, adapted to Go:

Spell-It-Out

If your code looks like this, it’s an FSA. More likely, it’ll look like a mess, because the author didn’t realise what they were writing, but it can be refactored to this pattern, and then taken on from there.

1-D Slice of func Pointers

With Data

We might wanna track a bag of data. This could be passed round as arguments or whatever, but it’s easiest to stick it in a struct and have that be reciever for the transition functions - you can take an address to a bound method (ie method and its receiver), which is the closest you can get to partial application in Go.

Different Data Schemata

Sometimes you’ll want different data fields depending on which state you’re in. Say the turnstyle has a “broken” state, where it refuses coins and is waiting to be fixed. In that state (or group of states) it might want to count coins - how many uses were attempted and thus money lost - and daysBroken. But in the “working” group of states it wants takings like we’ve seen, and maybe timesActuated. With some programming tricks, we can have the “state object” presented to different states be of different types.

I haven’t shown it here, but eg Akka supports it. When you transition from a state in one group to another, you have to derive the new data object from the old one. Redux etc aren’t all that dissimilar either.

2-D Matrix of func Pointers

https://levelup.gitconnected.com/implement-a-finite-state-machine-in-golang-f0438b6bc0a8 shows how you can have a 1-D array, indexed on a 2-tuple, which might be slightly more ergonomic. I guess tuples are Equatable and Hashable in Go.

Implementation Notes

Random thoughts on productionising this

dispatch should put the event on a queue and another goroutine should read it off. This means transition functions can call it to synthesise more events into the FSA without risking infinite recursion. This will also serialise events that come in on multiple threads, allow a bounded queue length, etc. That dispatch loop should also call transition functions with an expiring context.
The side-effects should probably be decoupled from the main FSA thread by another queue (they’ll currently block it). This will also serialise them, etc. Call the function emit maybe. Though you should think about your semantics - maybe you want them to be blocking so that the machine can’t race ahead while previous transitions are still be effected.
“Clocking” a FSA on a timer is very common, but there’s some caveats. You probably want the period to be x, not x + processing time. What do you do if one timer event isn’t off the queue, or done processing (long-running side-effects, synchronous or not) when the next timer goes off?

Libraries

There are a couple out there.