On State of State Machines
State Machines are things that all programmers should recall from their basic Computer Science courses, along with other basics like binary trees and merge sort. But until fairly recently I thought that they are mostly useful as low-level constructs, built by generator code like compiler compilers and regular expression packages. This contempt was fueled by having seen multiple cases of gratuitous usage: for example, state machines were used to complicate simple task of parsing paragraphs of line-oriented configuration files when I worked at Sun. So my thinking was that state machines are only fit for compilers to produce, something non-kosher for enlightened developers.
But about two years ago I started realizing that state machines are actually nifty little devices, not only to be created by software but also by wetware. And that their main benefit can actually be simplicity of the resulting solution -- when used in right places.
1. Block Me Not
The first place where I realized usefulness of state machines was within bowels of an XML parser. Specifically, when trying to write a non-blocking (asynchronous) parsing core of Aalto XML processor (more on this nice piece of software engineering in future, I promise)
Challenge with writing a non-blocking parser is simple: whereas blocking parser -- one that explicitly reads input from a stream and can block until input is available -- has full control of control flow, including ability to only stop when it wants to (at a token boundary; after fully parsing an element, or comment), a non-blocking parser is at mercy of whoever feeds it with data. If there is no more data for non-blocking parser to read, it has to store whatever state it has and return control to caller, ready or not. Which basically means it may have to stop parsing at any given character; or even better, within half-way THROUGH a character, which can happen with multi-byte UTF-8 characters And do it in such way that whenever more data does become available, it is ready to resume parsing based on newly available data.
So what is needed to do that? Ability to fully store and restore the state. And this is where state machine made its entrance: gee, wouldn't it make sense to explicitly separate out state, and create a state machine to handle execution. Or, in this case, set of small state machines.
Indeed it does; and once you go that route implementation is not nearly as complicated as it would be if one tried to do it all using regular procedural code (which might just be infeasibe altogether)
2. All Your Base64 Are Belong To Us
Ok, complex state keeping should be an obvious place for state machines
to rule. But much smaller tasks can benefit as well.
Base64 decoding
is a good example: given that decoding needs to be flexible with respect
to things like white space (linefeeds at arbitrary locations), possible
limitations on amount that can be decoded with one pass (with
incremental parsing, as is the case with Woodstox),
and the need to handle possible padding at the end, writing a method
that does base64 decoding is a non-trivial task. I tried doing that, and
resulting code was anything but elegant. I would even go as far as call
it fugly.
That is, until I realized I should apply earlier lessons and see what comes of simple state keeping and looping. Lo and behold, tight loop of base64 decoding is tight both by amount of code (rather small) and processing time (pretty damn fast). Resulting state machine has just 8 states (4 characters per 24-bit unit to decode, few more to handle padding), and code is surprisingly simple and easy to follow (but still long enough not to be included here -- check out Woodstox/Stax2 API class "org.codehaus.stax2.ri.typed.CharArrayBase64Decoder" if you are interested in details).
3. Case of "I really should have..."
One more case where state machine approach would probably have worked
well is that of "decoding framed XML stream".
At work, there is an analysis system that has to read gigabytes of data. Data consists of a sequence of short XML documents, separated by marker byte sequences that act as simple framing mechanism. Task itself is simple: take a stream, split it into segments (by markers), feed to parser. But to make it both reliable and efficient is not quite as easy: marker sequence consists of multiple bytes, and theoretically bytes in question could belong to a document: it's the full sequence that can not be contained within document. Plus for extra credit one should try to avoid having to re-read data multiple times.
So, foolishly I went ahead and managed to write piece of code that does such de-framing (demultiplexing) efficiently (which is needed for scale of processing we do). But code looks butt ugly; and took a bit of testing to make work correctly. Unfortunately I only had the light bulb moment after writing (... and fixing) the code: Would this not be a PERFECT case for writing a little state machine, where one state is used for each byte of the marker sequence?
Maybe next time I actually consider techniques I recently re-discovered, and apply them appropriately. :-)
