Ed is an EE, PE, and author in Poughkeepsie, New York. You can contact him at [email protected].
"Heat builds up from spinning-friction, which expands the brass, which nicks the cog-teeth. Damp weather curdles the gear-oil—and in dry weather, a spinning Engine can even create a small Leyden-charge, which attracts all manner of dirt. Gears jam and gum, punch-cards adhere in the loaders..."
The Difference Engine
William Gibson and Bruce Sterling
Even the names conjure up moving parts and glowing bulbs. Embedded programs, barely visible through deep inspection ports, hum quietly with a whiff of ozone. Cast-iron device drivers sport gleaming, well-oiled shafts and whirling governors. Interrupt handlers race along polished rails, invisible while they move and twitching nervously when they pause.
State machines, on the other hand, seem to tick and creak while puffing clouds of steam.
A copy of Miro Samek's Practical Statecharts in C/C++ (CMP Books, 2002; ISBN 1-57820-110-1, published by the same company that publishes Dr. Dobb's Journal) landed on my in-heap a few weeks ago, prompting serious déjà vu. My heap yielded, after the usual concerted rummaging, Christopher Clare's 1973 book Designing Logic Systems Using State Machines.
To cut directly to the chase, you should buy the former and envy my possession of the latter. Here's why.
Back in Time
The cover of Clare's book presents a state-of-the-art 1972 HP35 calculator, which featured a four-level stack for RPN calculations, one memory, and no programming. Those magnified LED digits simply weren't visible from the camera's angle, so inept photo retouching predates Photoshop.
When you recall that Intel introduced its 4004 Ur-microprocessor in 1971, it's not surprising that the HP35 CPU required several custom chips. Program memory resided in three ROMs, each holding 256 10-bit words.
Pop Quiz: Implement any six transcendental functions of your choice using no more than 7.5 Kb (bits!) of program memory and a one-level subroutine stack. Show your work on seven-segment LEDs. Extra credit: Allow keyboard entry and validate the arguments using no additional ROM chips.
Clare described "Algorithmic State Machines" as part of the logic design process, with examples that involved actual logic gates and transistors. According to the book's foreword, Hewlett-Packard used these techniques in the HP35 calculator with good results.
In this context, the word "machine" agrees reasonably well with common usage. A machine is a gizmo that performs a specific function—toast bread, mix concrete, compute a sine function, add two numbers. The words "machine," "mechanism," and "mechanics" date back to a time long before threaded bolts were the Next New Thing.
Similarly, a state represents a machine's current condition: heating, churning, shifting, adding. A given state may last for nanoseconds in machines with electrons as their moving parts or days in your grandfather's clock. The duration of any state far exceeds the time required to move from one to another and, in fact, the transition time is usually taken to be zero.
A state machine, therefore, is a mechanism that sits around in one of several distinct conditions. When an external event occurs, the machine responds by selecting a new state based on its inputs and perhaps producing some output signals along the way. A whole taxonomy enumerates the subtleties of how and when the machine recognizes events, precisely which part of the transition produces the outputs, and what transitions may occur.
You can think of a state machine as living in the midst of a polling loop. Each time around the loop, the machine examines its inputs and decides what to do. If nothing's happening, it remains in the same state. When something happens, it takes the action called for by its current state and enters the appropriate next state. When the polling loop calls it again, the process repeats.
Those 1973 state machines looked a lot like flowcharts, and their version of a polling loop was an oscillator feeding discrete gates configured into flip-flops. If you'd never heard of Karnaugh maps, you'd be in for a rough ride, but manual logic synthesis was the order of the day and the projects were generally small enough that you could, with typical engineering persistence, smelt a state machine into a circuit board with a finite amount of effort.
The fact that we can barely imagine implementing anything in hardware nowadays tells you a lot about how the world has changed.
The Big Bang
You may have had, at one time or another, the dismal duty of converting raw key pressure into characters. The usual code degenerates quickly into overlapping shift flags, special "pending" flags for multiple-keystroke combinations, and, if you were conscientious, synching the keyboard's status LEDs with the flags. It's hard to avoid spaghettioid code while testing each flag at each spot, it might have any possible effect, let alone figuring out the effects of multiple flags.
The canonical example of state-machine operation depicts a keyboard handler that replaces those nasty flags with a series of states: normal, shifted, and so forth. Just looking at that clean diagram makes you feel foolish, which, in my case, generally means I've just learned something really important.
The keyboard state machine produces lowercase keys until it sees a Shift key, whereupon it enters the shifted state. It remains there, emitting uppercase characters, until the Shift key goes away. That input returns it to the original lowercase state. By encapsulating the notion of "shifted" as a distinct condition—a state—you can localize all its effects and conditions.
However, shortly after you get that working, somebody reminds you about the Ctrl keys. And they want to distinguish between Left-Shift and Right-Shift. And what about those Alt keys? And the infamous Windows keys? And so forth and so on.
Shortly after it's working again, you're informed of a business need to switch between whatever the normal keyboard layout might be and, say, Esperanto. On the fly, of course.
At that point, you find yourself staring at the debris of the dreaded combinatorial explosion, where states labeled "Left-Shift-Ctrl-Alt-Esperanto" flourish weed-like on the page. The number of states equals (at least) the number of distinct conditions you must handle and the number of possible next-state transitions is the square of that, a number that can get very large very rapidly.
This doesn't bother some folks. I recall reading a paper in the Proceedings of the IEEE (probably V88N7, July 2000, but it's lost in the aforementioned heap) describing an intelligent-vehicle/smart-highway system implemented using a state machine sporting upward of a quarter-million states. It was all automatically generated and they seemed quite proud of it. I confess to a trifling concern about validating such a monster: All together now, "But it never did that before!"
Because state machines work so well with smaller problems, there's been extensive effort applying them to larger problems while avoiding combinatorial explosions. That effort involves, as you might expect, buzzword compliancy.
Enter encapsulation, hierarchy, UML, and design patterns.
Getting Practical
Miro Samek accomplishes three mighty feats in Practical Statecharts in C/C++: He explains how hierarchical state machines work, converts those machines into C/C++, then provides a framework to run those machines in real-time environments or your favorite GUI. Along the way, he demolishes the opposition (how you used to do it), shows you the right way (with code to prove the point), and doesn't bore you to tears (even when explicating quantum mechanics). Quite a feat by any stretch of the imagination.
Hierarchical state machines defuse the combinatorial explosion by allowing state machines to share behaviors, which means the total number of states adds rather than multiplies. For example, the machine that handles Ctrl keys is quite similar to the one that handles Shift keys, so perhaps one (large) chunk of code can describe their common attributes, while a few (smaller) chunks handle the differences.
David Harel introduced the notation of statecharts while exploring HSM terrain in the late '90s and it's now incorporated in the Unified Modeling Language (UML). While that might seem to be the end of the discussion, UML reminds me a lot of the old OSI seven-level network model: Everybody learned it, everybody referred to it, and everybody knew why it didn't quite apply to their particular situation.
Pop Quiz: Name the seven OSI networking levels in order. Explain why most systems imploded at least three levels into one. Show your work in 1492-byte chunks.
In under 200 pages, the first half of Practical Statecharts in C/C++ covers state machines, statecharts, the usual implementations, behavioral inheritance, the five key state-machine design patterns, and how to actually pull off inheritance in both C and C++, all with highlighted code samples. Whew!
At that point, you have enough motivation to reform your current methods and enough knowledge to get it right. That's worth the price of admission and, frankly, you should read this part of the book just to open your eyes to a different way of doing things. Even if you never use the code directly, it'll be a win.
The second half of the book describes Samek's Quantum Framework and the techniques used to bolt it onto the operating system of your choice. He gives examples for DOS(!), Windows, and On-Time's RT-Kernel32, showing that, while you don't need an inherently multitasking OS to get the job done, it certainly makes the job a lot less tedious.
State machines are a nearly perfect fit for real-time and highly reactive systems because they easily distribute the workload among many distinct states that inherently avoid compute-bound lumps of indivisible code. At the risk of oversimplifying, the Quantum Framework handles the hocus-pocus required to transfer control between the OS and the current state within your design.
Even if you're not doing embedded programming (thanks for following along, though), you should read pages 215 through 248 of Chapter 8, where Samek provides a clear and concise discussion of the most common program design pitfalls—handling errors and exceptions, memory management problems, threads and blocking, and event passing. Expect to smack your forehead and go rummaging for an old source file when you realize that you've made a mistake he describes.
The remainder of the book covers the implementation of the Quantum Framework in sufficient detail that you'll know not only how it works but why he did it that way. While not exactly a can't-put-it-down thriller, it's certainly well done and worth perusing, which I can't say about a lot of technical books these days.
The Big Picture
Flowcharts were a big thing in 1973 and, judging from the wall of books at my local big-box outlet, UML is at least that big three decades later. The various graphical program generators for UML attempt to present the structure of a program in a more readily visible format so you can see what's going on, while automagically generating source code to present the same structure to the compiler.
As with flowcharts, though, beyond a screenful or two, you simply cannot keep all the pieces in your head at once. Samek notes this problem and offers behavioral inheritance as a partial solution, allowing outer states to describe the common behavior of their descendants. By eliminating gratuitous repetition of information, you can condense the problem down to its irreducible level of complexity.
The devil, as always, remains in the details. At the highest level, you can say that a program works thus-and-so and behaves wonderfully well as it does. At the lowest level, you get Yet Another Microsoft Security Bulletin:
All versions of Windows ship with an ActiveX control known as the Certificate Enrollment Control...The control contains a flaw that could enable a web page, through an extremely complex process, to invoke the control in a way that would delete certificates on a user's system.
Statecharts seem a definite step toward building software with well-understood properties. At least we can avoid some of the weird failure modes plaguing the rickety edifice we now inhabit by actually enumerating the states the software can occupy and specifying what happens next.
We still lack a way to view entire problems, from grand overview to grittiest details, without having one level obscure the others. I fear that after abstracting all the underlying behavior in a system into a grand overview, all we can see is a mighty case of overconfidence.
We've long since passed the point where any nontrivial project could be understood by any one person. Our failures come from marginally understood pieces interacting in hard-to-predict ways, with error conditions providing particularly nasty surprises. Perhaps if we do a better job of keeping the small pieces under control, we can make higher level systems behave more predictably.
It's certainly worth a try.
Reentry Checklist
CMP Books publishes Practical Statecharts in C/C++, which means, as nearly as I can tell, that I've been discussing a book put out by a relative of this very magazine. Other than sending me a (free) review copy, nobody's done any arm-twisting.
In The Difference Engine (Bantam,1991; ISBN 0-553-29461-X), William Gibson and Bruce Sterling explored what might have been had Babbage's machinery actually worked as designed. Neal Stephenson described how our world might mutate under the relentless impact of nanotechnology's invisibly small mechanical rod logic in The Diamond Age (Bantam, 1996; ISBN 0-533-57331-4).
You can get Clare's book from one of Amazon's used-book sellers, but at eighty bucks, it's almost certainly not worth it. I'm keeping mine just in case the value goes up. Envy me, okay?
E. M. Forster's The Machine Stops (http://www.plexus.org/forster.html) describes the Final State as seen from 1909, shortly after the Wright guys cracked the code on airplane travel. It's eerily prescient along several axes.
The Certificate Enrollment problem was discussed in Microsoft Security Bulletin MS02-048 (http://www.microsoft.com/ technet/security/notify.asp). You must be ready to produce your Microsoft Passport on command. Let's not get into the whole two-digit year thing again.
The HP Calculator Museum (http://www.hpmuseum.org/) has a picture of that original HP-35 calculator (http://www.hpmuseum.org/35first.jpg). Alas, my late-1970s-vintage HP-33E no longer lights up, even with new NiCad cells.
DDJ
