As I’ve mentioned a few times, I love programming state machines. I spent many years writing software for communications software using odd protocols. The easiest way of implementing those protocols was almost always to use a state machine. Once you get used to working with them, you discover that all sorts of problems fit the paradigm.
A couple of weeks ago, Chris Wellons published an instructive post on state machines that I really liked. Most articles you see on state machines illustrate the idea with a simple problem and don’t worry about efficient implementations Wellons, of course, is having none of that. His problems are nontrivial and he spends time deriving efficient implementations.
For example, his first problem is a Morse code decoder. It’s a problem crying out for a state machine and if you spend a couple minutes thinking about it, a natural implementation for the state diagram is a binary tree. Naturally, Wellons noticed this and came up with a beautiful solution. He implemented the state table as a binary heap so that there was no need to store a representation of the edges. See his post for the details. The result is an implementation that compiles to under 200 bytes.
Wellons also discusses a UTF-8 decoder, a word counter, and a couple of other problems. Along the way, he looks at using co-routines and generators as an implementation strategy.
The post is dense so you’ll have to read it carefully and spend a bit of time understanding everything but the rewards are worth it. State machines are a powerful tool and it’s worth spending some time getting comfortable with them.