Today I wanted to play around with building a small thread-safe finite state machine. I’m mostly interested in the thread safety angle, so the machine is kept extremely simple. Clojure’s protocol feature turned out to be just what the doctor ordered.
The fsm consists of three things: the current state, the input alphabet, and a transition function which maps the current state and an input symbol to the next state. The fsm has two ‘methods’: state, which returns the current state, and act which acts on the input symbol and current state to compute the next state. Here is how act and state are implemented.
Let’s make things more concrete by building a machine. Our input alphabet will contain only a single symbol, 1. The machine will count the parity mod 4 of the number of times it has seen the symbol 1. It ignores input other than the symbol 1. We’ll call the machine blue, in honor of the Sweetwater Blue Ale I had while building it.
Playing with it at the repl we see that at first glance everything appears to work.
But is it thread safe? Let’s beat on it with some threads.
Well, 100000 mod 4 is 0, so it got the right answer. And blue passed various similar tests, which I’ll spare you. But the thought occurs that maybe my test is not a very good test. So let’s test the test. Yes, I’m kind of goofing on you, but not entirely. The way to test the test is to build a flawed version of the act function, one with a deliberate concurrency bug, and see whether the test catches it.
Using the new, flawed definition, we build another machine and test again. Notice the final state is ::1, which is incorrect. The red machine started in state ::0, so after seeing the symbol 1 exactly 100000 times it should have been in state ::0. This suggests the beat-on-it-with-threads test has some merit, and that having passed it repeatedly gives the thread safety of the blue machine some plausibility.