State Machines, Redux
Whenever I mention state machines, an e-mail blizzard arrives from folks who have been using them for years and wonder why the rest of you haven't gotten with the program. One such reader, Peter Wolstenholme, is a coauthor of Modeling Software with Finite State Machines and sent a copy along for my perusal.
They note three "trivial truths" about software development:
- Programs are complex.
- Code is impenetrable.
- Unless you're producing executable code or an analytic model, you're not doing anything useful.
In particular, they note that UML Use Cases tend to be "sunny-day scenarios" describing how the program should work when everything goes right. That approach has the unfortunate side effect of requiring explicit definitions for all possible misbehaviors, truly a thankless and basically impossible task.
Although a finite state machine must cope with the same situations, it moves from one known state to another under the direction of clear rules describing the allowable input values and conditions. Unknown situations either trigger an entry to a specific error state or perform no action at all. The machine simply cannot branch into the bushes or digress into "this can't happen" code.
Their guiding principle is this: "A behavior specification should solve the problem and must be comprehensible for outside persons..." They advocate using collections of small, special-purpose state machines linked together with a straightforward protocol, so that each machine does exactly what's needed and the higher level machines control lower levels without meddling in their innards. The specs for those machines are both human-readable documentation and runtime control, with the added benefit that anything not specified simply can't happen.
This may sound a lot like the usual hierarchical decomposition, but it has the advantage of using components that actually perform predictable functions. The interface handles command-and-control logic, not the usual data-passing-and-tinkering we've all fallen into.
Chapter 7, "Misunderstandings About Finite State Machines", refutes many of the reasons you use for not employing state machines. In particular, control-system state machines have several key differences from the usual string-parsing machines (usually) taught in comp-sci courses and, as a result, can handle input conditions without triggering the dreaded combinatorial explosion.
Of course, nobody ever knows the specifications for a program before it's written, but state machines let you define what the program will actually do (and not do!) and change those definitions to match the mutating specs, without having code that does weird things you've never considered.
When a state machine does something unexpected, it's generally a case of an input not doing what it should. At that point, you know the machine's exact state and can match up the input with the spec to see what should be happening. I predict you'll often find the spec didn't define that situation, so the program is actually doing what it should: Nothing!
One particularly useful difference from usual practice is that input values indicate whether they're valid. For example, a digital input bit can be High, Low, or Unknown; it's not just a simple Boolean value. Although you can't always detect an error condition, having to decide what to do may direct your attention in the right direction.
The book also describes their proprietary StateWORKS virtual machine, which collects all the tedious and generic state-machine control logic into a solid lump. The book carries a license for the entry-level version, although you need not buy anything to use the principles.
The StateWORKS virtual machine is a Posix-conformant C++ program that runs under a variety of operating systems, so the state machines don't run on bare-metal microcontrollers. Wolstenholme mentioned in an e-mail that one user wrote a Java program that ate the state-machine descriptions and spat out "intricate and unreadable C code" that he then compiled for the target system. In effect, StateWORKS became the system definition and verification model, with the C code implementing the machines "as designed."
Bottom line: This one is worth reading even if you think your current methods are working fine, because it'll shake your confidence.