Friday, June 04, 2004
One of the most fundamental concepts in all of computer engineering is the state machine. Whether implemented in hardware or software, state machines are core to the whole field of digital information processing. State machines are the foundation for every CPU design in existence, network protocols, regular expressions, most GUI architectures, and just about everything else you can imagine. Yet, I often find that software engineers haven't been trained to think strongly in terms of state machines, but rather sequential code. Sure, when pressed everybody knows what a state machine is, but they implement them infrequently, prefering sequential code instead. Why is that? Maybe it's my combination of both a hardware and software background, but I find state machines a quite natural expression of many problem solutions.
A secondary question is, why do all popular programming languages have such poor support for representing such a foundational abstraction? The Gang of Four devote eight pages to documenting the State pattern in Design Patterns. While this is helpful, it seems to me that it would be easier to simply add some syntax to the language to help out with something this basic. Why force everybody to reimplement the same idea of states and a driver machine every time we solve a problem?
In pondering these questions, I decided to do something about that. The cool thing is that Lisp, of course, makes this easy with macros. I'm now starting to implement a state machine mini-language as a macro library. I'll publish some code snippets as I get them better fleshed out.
Links to this post: