Build and visualize finite state machines in Go

Wikipedia describes Finite State Machines (or FSMs) as a mathematical model of computation of an abstract machine that can be in exactly one of a finite number of states at any given time. It can move between states as a response to some stimulus (an event); such a change is known as a transition.

So, how exactly does this concept in computing translate over to the software development realm?

Often, we model software around the objects from the real world, and the behavior of these objects can seem quite complex when the environment interacts with them asynchronously. FSMs help us understand & model reactive systems, and simplify some rather complex scenarios. We begin by taking a example of a traffic signal.

Traffic signals & FSMs

Usually traffic signals across the world alternatingly light up with one of the 3 colors: green for go, amber for warning & red for stop. There’s a certain fixed amount of time between each color change which occurs in a sequence, green ⇒ amber ⇒ red. At times, a pedestrian can push a button at crossings to reset the color to amber, which then proceeds to go to red as the timer expires. Following is the state transition diagram for the situation:

/postimages/trafficlights_state_diagram.svg

And following is the procedural implementation of the above situation:

const (
	ColorRed   string = "ColorRed"
	ColorAmber string = "ColorAmber"
	ColorGreen string = "ColorGreen"
)

var currentColor string = ColorGreen

// invoked when the timer for a color expires
func handleTimerExpired() {
	if currentColor == ColorRed {
		currentColor = ColorGreen
	} else if state == ColorGreen {
		currentColor = ColorAmber
	} else if state == ColorAmber {
		currentColor = ColorRed
	}
}

// invoked when a pedestrian pushes the halt traffic button
func handleReset() {
	if currentColor == ColorGreen {
		currentColor = ColorAmber
	} else if currentColor == ColorRed {
		currentColor = ColorAmber
	}
}

The problem with this implementation is:

The code conveys the how, but not the what of what it’s describing
There are high chances of bugs creeping in, due to some case not being considered

So, what’s next?

Our traffic signal has three states:

Red, Amber & Green

And two events:

TimerExpire - triggered when the fixed time between states expire

Reset = triggered when a pedestrian pushes the halt traffic button

Next, we build our FSM library to model the diagram into code.

Building the FSM library

We begin by defining the types and structures of our library. Most of our code is self-documented using comments.

// EventType represents all events that exist in the state machine.
type EventType string

// StateType represents all states that exist in the state machine.
type StateType string

// state represents the configuration of a state in the machine, one of which is the transitions.
type state struct {
	// transitions map an event with a destination state.
	transitions map[EventType]StateType
}

// Machine represents a finite state machine.
type Machine struct {
	name    string              // Name of the machine
	current StateType           // Current state of the machine
	initial StateType           // Initial state of the machine
	states  map[StateType]state // states maps the name of a state with the state configuration
}

Here, the Machine struct encapsulates all properties of our state machine, such as the initial state, current state and all possible states & transitions of our state machine.

Next we define the types that help use construct our machine.

// Transition maps an event with a destination state.
type Transition struct {
	Event EventType // Name of the event that triggers the transition
	Dst   StateType // Destination state of the transition
}

// Transitions is a slice of related transitions.
type Transitions []Transition

// StateDesc is the description of a state.
type StateDesc struct {
	Name        StateType   // Name holds the name of state
	Transitions Transitions // Transitions holds all valid transitions originating from the state
}

// States is an slice of related state descriptions (StateDesc).
type States []StateDesc

Now we define the NewMachine function that constructs and returns an instance of Machine.

// NewMachine returns an instance of the state machine (Machine) after it accepts
// the details of the machine, such as initial state & state descriptions.
// It returns an error if the parameters are invalid.
func NewMachine(name string, initial StateType, states States) (*Machine, error) {
	mStates := make(map[StateType]state)

	for _, s := range states {
		state := state{
			transitions: make(map[EventType]StateType),
		}

		for _, t := range s.Transitions {
			state.transitions[t.Event] = t.Dst
		}

		mStates[s.Name] = state
	}

	if _, ok := mStates[initial]; !ok {
		return nil, ErrMachineCreationFailed
	}

	machine := &Machine{
		name:    name,
		states:  mStates,
		initial: initial,
	}

	return machine, nil
}

Right now, we have only defined structures, types and the constructor. We still need to code the behavior of our Machine, such as a method that helps us transition to the next state and another to return the current state of the machine.

// Returns the current state that the machine is in.
func (m *Machine) Current() StateType {
	if m.current == "" {
		return m.initial
	}
	return m.current
}

// getNextState returns the next state for a given event after considering
// the current state and it's transitions. If a valid transition doesn't exist
// it returns an error.
func (m *Machine) getNextState(event EventType) (StateType, error) {
	current := m.Current()
	next, ok := m.states[current].transitions[event]

	if !ok {
		return "", ErrEventDeclined
	}

	return next, nil
}

// Transition returns the final state after accepting a valid event, and transitioning
// to the next state after considering the current state and it's transitions.
// If a valid transition doesn't exist it returns an error.
func (m *Machine) Transition(event EventType) (StateType, error) {
	next, err := m.getNextState(event)
	if err != nil {
		return m.current, ErrTransitionFailed
	}

	m.current = next
	return next, nil
}

// States returns a slice of all state descriptions (StateDesc) of the state machine.
func (m *Machine) States() States {
	states := make(States, 0)

	for name, state := range m.states {
		s := StateDesc{
			Name:        name,
			Transitions: make(Transitions, 0),
		}

		for tname, dst := range state.transitions {
			s.Transitions = append(s.Transitions, Transition{
				Event: tname,
				Dst:   dst,
			})
		}

		states = append(states, s)
	}

	return states
}

I’ve added a third method States() that returns all state descriptions of a Machine. We’ll use this later to implement the drawing module.

Next, we define the errors we’ve mentioned above.

import "errors"

// ErrMachineCreationFailed is the error returned when creation fails.
var ErrMachineCreationFailed = errors.New("machine creation failed")

// ErrTransitionFailed is the error returned when a transition fails.
// This can be due to an invalid event.
var ErrTransitionFailed = errors.New("transition failed")

// ErrEventDeclined is the error returned when an event cannot be
// processed by the state machine, due to it's current state.
var ErrEventDeclined = errors.New("event declined")

The error interface in Golang is simple and it just exposes an Error method, which returns a string.

Modelling the traffic signal using our FSM library

Since we have our Machine ready, we can use it to describe our traffic signals.

const (
	Green StateType = "Green"
	Amber StateType = "Amber"
	Red   StateType = "Red"
)

const (
	TimerExpire EventType = "TimerExpire"
	Reset       EventType = "Reset"
)

machine, err := NewMachine(
	"trafficlight",
	Green,
	States{
		{
			Name: Green,
			Transitions: Transitions{
				{Event: TimerExpire, Dst: Amber},
				{Event: Reset, Dst: Amber},
			},
		},
		{
			Name: Amber,
			Transitions: Transitions{
				{Event: TimerExpire, Dst: Red},
				{Event: Reset, Dst: Amber},
			},
		},
		{
			Name: Red,
			Transitions: Transitions{
				{Event: TimerExpire, Dst: Green},
				{Event: Reset, Dst: Amber},
			},
		},
	},
)

Next, we can transition between states using:

machine.Transition(TimerExpire)

The TimerExpire event will cause the our traffic lights state machine to react to this event and switch from Green to Amber state.

If a reset event is triggered using: machine.Transition(Reset), the machine will transition to the Amber state again. This is by virtue of our machine description.

You can instantly notice that it has become quite simpler to describe how a traffic signal behaves, in code.

Bonus: Visualizing & drawing a state machine

FSMs can be drawn using a state diagram. There are a variety of tools that’ll help you code a diagram using a domain specific language (or DSL) meant for it. One such tool is graphviz.

Graphviz can convert text files written in the DOT language into image files. For example, the following DOT code will render into the figure of state diagram above.

digraph trafficlight {
    "Green" -> "Amber" [ label = "Reset" ];
    "Green" -> "Amber" [ label = "TimerExpire" ];
    "Amber" -> "Amber" [ label = "Reset" ];
    "Amber" -> "Red" [ label = "TimerExpire" ];
    "Red" -> "Amber" [ label = "Reset" ];
    "Red" -> "Green" [ label = "TimerExpire" ];

    "Amber";
    "Green";
    "Red";
    node [width=0.3 shape=point style=filled];
    "" -> "Green";
}

For sake of brevity, we won’t get into the specifics of the DOT language.

In order to get DOT output for our Machine we define the DrawMachine function.

// DrawMachine accepts a Machine, "draws" it and returns a string
// in the Graphviz DOT format. This string can be parsed by Graphviz
// to be converted into a diagram.
func DrawMachine(machine *Machine) string {
	var buf bytes.Buffer
	states := machine.States()

	sortStates(states)

	writeHeader(&buf, machine.name)
	writeTransitions(&buf, machine.initial, states)
	writeStates(&buf, states)
	writeStartPoint(&buf, machine.initial)
	writeFooter(&buf)

	return buf.String()
}

// Writes the header to buffer in DOT format.
func writeHeader(buf *bytes.Buffer, name string) {
	buf.WriteString(fmt.Sprintf(`digraph %s {`, name))
	buf.WriteString("\n")
}

// Writes all state transitions to the buffer in DOT format.
func writeTransitions(buf *bytes.Buffer, current StateType, states States) {
	for _, k := range states {
		if k.Name == current {
			for _, t := range k.Transitions {
				buf.WriteString(fmt.Sprintf(`    "%s" -> "%s" [ label = "%s" ];`, k.Name, t.Dst, t.Event))
				buf.WriteString("\n")
			}
		}
	}

	for _, k := range states {
		if k.Name != current {
			for _, t := range k.Transitions {
				buf.WriteString(fmt.Sprintf(`    "%s" -> "%s" [ label = "%s" ];`, k.Name, t.Dst, t.Event))
				buf.WriteString("\n")
			}
		}
	}

	buf.WriteString("\n")
}

// Writes all states to buffer in DOT format.
func writeStates(buf *bytes.Buffer, states States) {
	for _, k := range states {
		buf.WriteString(fmt.Sprintf(`    "%s";`, k.Name))
		buf.WriteString("\n")
	}
}

// Writes the pointer to the starting node to the buffer in DOT format.
func writeStartPoint(buf *bytes.Buffer, initial StateType) {
	buf.WriteString(fmt.Sprintln("    node [width=0.3 shape=point style=filled];"))
	buf.WriteString(fmt.Sprintf(`    "" -> "%s";`, initial))
	buf.WriteString("\n")
}

// Writes the footer to buffer in DOT format.
func writeFooter(buf *bytes.Buffer) {
	buf.WriteString(fmt.Sprintln("}"))
}

// Sorts the state descriptions and transitions in ascending order
// so that the diagram doesn't change after each run.
func sortStates(states States) {
	sort.Slice(states, func(i, j int) bool {
		return states[i].Name < states[j].Name
	})

	for _, state := range states {
		sort.Slice(state.Transitions, func(i, j int) bool {
			return state.Transitions[i].Event < state.Transitions[j].Event
		})
	}
}

Once we have this ready, we can use it to get the DOT output string for our traffic signal machine, using: dot := DrawMachine(machine)

We can convert the DOT code into an image using the Grapviz tool installed on your system or by pasting it into one of the countless Graphviz editor playgrounds available online.

Conclusion

State machines, albeit unfamiliar, are extremely useful to model reactive situations. It lets you describe logic in terms of its behavior, due to the declarative nature. Since, only defined transitions are valid, the chances of moving to an invalid state should be virtually impossible.

The final code for FSMs in Golang, along with examples is available on my github profile, https://github.com/sebinbabu/zostate and the state description of our traffic signal is available here.

References

xstate: State machines and statecharts for the modern web
looplab/fsm: Finite State Machine for Go