Writing A Finite State Machine in Go

Image by Author

I am back with a new blog post after a really loooong time. Sorry for this radio silence. I had too many things going on in my life and although I did some pretty cool things in the meantime (such as beating the so called state of the art Deep Learning algo in a particular domain by a large margin using some traditional ML and Image Processing techniques) I did not get any time to write anything.

I have recently been working on a very interesting project at my work which involves Machine Learning, Code Translation, and some other cool things. A part of the project is being developed in Go and a part in Python. Thanks to that I got a chance to get back to write some Go code after a couple of years.

One of the things I was looking to have is a Finite State Machine.

Image by Author

Intuitively speaking a Finite State Machine (FSM from now on) is just a directed graph where each node represents a state and from a state (node) you can visit another node (state) based on mainly two things

• The two nodes must have an edge (arrow if you want) between them (This one is actually obvious, but still better to say explicitly)
• Each edge represents some kind of action / rule and when you are at a state you can go to any other connected state provided the input you receive (events we call it) match with the rule linking these two states.

To make it simple, please have a look at the state machine I have used as the top image of the article. To make things easy, I am again putting it here.

Image by Author

Here, you start at the locked state. Which is often called the Initial State. And from there you have two actions available. One is coin and another is push. Now, as you can see in the image if the action is coin then you change your state to un-locked. But if the action is push then you circle back to the same state, i.e., locked.

FSM is a mathematical model of computation. Which means you can express a vast range of computational tasks using a FSM. It is less powerful than a Turing Machine (Another computational model) or a Push Down Automata, but nonetheless pretty powerful already.

Image by Author

Yes, OK! :) I am going to show the code.

Before I begin, I just wanted to state that, my code has one external dependency, gonum/graph You can see the entire documentation here.

And also, I must mention that there are some good, already existing, implementation of FSM out there. Such as the one from looplab. But I wanted to roll out my own for the flexibility and the learning.

Let’s start with the imports.

This one is fairly straight forward. So let’s move on to the first block. We define the backbone of our FSM here. This means we are going to define a simple Node (State) and Edge (Link) structure.

In gonum you can virtually make any struct a Node, as long as it implements the ID function. Also, we are going to use a directed multi-graph. And gonum calls Edge as Line for this type of Graphs. So we have also defined our Line.

Our Node struct has a Value field, which is an interface that means it can contain many different types of values.

Our Link struct has a Rules field, which is a map from an Operator to an Event These two are custom data types. I will show them soon. But so that you are not confused, I am going to tell you now that they are just string types.

Now let’s define the StateMachine

This is simple.

We will go ahead and define some important functions now. First one is the one to create new StateMachine.

With that done, we need couple of more. Let’s define a function to initialize the FSM, one to add more state to it, and one to Link two states with a Link (which also holds the rule that needs to be satisfied so that one can traverse through it.)

Simple enough. We will also create a function to create a new rule.

These all are important, however, they can be called boiler-plate in a sense. Now we are going to define the heart of our FSM. We will define a function called FireEvent Which will fire an event and based on the event fired, the present state where the FSM is, and the outgoing Links from that state, it will take a call to whether it should change the state to a new one or not.

So at the start of this function we are getting the present state where the FSM is at the moment. Once we obtain that we get an Iterator for all the States connected to it in an outgoing sense (Hence the From Function call). Once we get the iterator, we iterate over all of those nodes.

For each state that is there, connected to PresentNode in an outgoing sense, we obtain the Link connecting both of them.

We obtain the rule for that Link and we compare the rule’s value with the event’s value.

To give an example, let’s say a Link l has this rule eq:coin and the present event is coin.That means the event that is received by the state is equivalent to the rule. Which means we can take this link and move to the state where this link ends.

Here, I want to spend a little bit of time trying to explain why I introduced something called Operator. My idea here is simple. We will have a predefined set of Operators, such as eq , neq, gt, lt, gte, lte, etc. They may seem familiar to many people. They are =, !=, >, <. ≥, ≤ respectively. By introducing this concept in our StateMachine, the rules it can express, become very big. So we can model a large number of processes using this. (My secret ambition is to introduce probabilistic operators and turn the FSM to non-deterministic FSM :) ). Of course for the purpose of demo and this article I am showing only one Operator: eq

At this stage we are mostly done. However, I am going to define a pretty little function called Compute which takes a slice of events, and computes where the FSM will be at the end of the chain of events.

We are done! 😅

Although it may look like a lot, actually the code that we had written so far is very straight forward and easy to understand. It is also pretty concise.

Now is thetime to take the StateMachine for a spin.

when we run this code, this is the result

$ go run main.go                                                                                                                                                                                     ✔ 
Initial state is ------- locked
unlocked
locked
------------ Final state is locked

This is exactly how we expected it to behave!

Some advantages of this implementation are following

• The state values can be anything.
• A rule can be anything as long as it involves a supported operator
• We can actually read a series of events from anywhere, user prompt, network traffic, csv file… you name it.
• Highly extendable and customizable (without the main, the code is less than 150 lines long)
• It depends on a very robust library gonum which brings a lot of power and reliability.

That is all folks. If you like this article, please clap and share. It gives me inspiration for other articles in the future. You can connect with me in Linkedin also.

The code is, as usual, open sourced and can be used in any way you may want. The full code can be found at this github link — https://gist.github.com/rcshubhadeep/1606c7f3ee4606edb194a30c04811bb2

Hope you enjoyed this article and hope to see you soon again.