Slashdot Mirror
Practical Statecharts in C/C++
As the title indicates, this book brings the topic of statecharts from the realm of expensive design tools to the practical realm, illustrating its points with full examples and extensive commentary.
Essentially Samek postulates that the slow adoption by developers of best practices by statechart design is due to lack of understanding of the fundamental nature of statecharts and how it is perceived as requiring expensive tools to use well. Samek insightfully discusses how statecharts as a best practice embody "behavioral inheritance" as a fundamental design concept that stands as a peer alongside the conventional pillars of object-oriented programming, namely inheritance, encapsulation, and polymorphism.
The book is very technical and written in an academic style, with ample references to original sources as well as detailed code reviews and many reader exercises. I would caution anyone from approaching this book as a quick or light read. For me, it took a seriousness and good understanding of C and C++ to follow Samek's examples and achieve the "a-ha", which was always worth it in the end. The book contains full, working code to incorporate statecharts into my own work, implemented both in C and C++.
The two basic parts of the text are (1) an explanation of statecharts and their methodological implications, and (2) a description of how to apply statecharts as a data structure in real applications, namely embedded as control strategies for "active objects." In several places in the text, Samek makes an analogy between statechart (and active object) semantics and quantum mechanics. This parallel was an interesting philosophical argument, but didn't add much for me in terms of accepting his "quantum framework" as a best practice -- I was sold by his methodological arguments he had presented already.
Speaking from experience in writing a book about using statecharts to build simulations (www.FlashSim.com), I can say Samek is a visionary who extended my perception of statecharts several steps. I know I will be quoting from it and referring to it in my work to come. This book has earned a prominent place on my bookshelf, and I would heartily recommend it to any other developer who wants to create correct, verifiable, scaleable, and solid designs (which should be ALL developers!)
You can purchase Reviewing Practical Statecharts in C/C++ from bn.com. Slashdot welcomes readers' book reviews -- to see your own review here, read the book review guidelines, then visit the submission page.
Most other programmers I meet in the workplace have a hard time understanding state machines. All of those programmers are self taught or picked up "learn programming in 21 days" type of books.
I recommend this book.
Zone Logic is a nice combination of state charts and autononmous agent design. It was used in the 80s and early 90s for industrial automation, and was particularly good at recovery from hardware failures.
Real-time systems depend on sensors to report the state of the outside world. These sensors often fail, putting the system in an illogical state. Zone Logic offered a nice structured way to deal with this.
R. Roberts. Zone Logic: A Unique Method of Practical Artificial Intelligence. Radnor, PA, Compute! Books, 1989. citeseer
I use Bruce Powel Douglass' Real-Time UML, Second Edition, Developing Efficient Objects for Embedded Systems .
It only has 1 chapter on UML statecharts, but after reading through it, I was able to describe in 1 diagram LCD behavior that used to take ~20 weakly worded requirements. (Shall do this, except when this, etc...)
If you're having trouble being explicit and clear in requirements, I would highly recommend looking at statecharts. (Picture speaks a thousand words, eh?)
Ah, well, google to the rescue: here's good example of a statechart.
State machines aren't that complicated. The UML people are just burying them under a mess of jargon. This is probably not helpful.
UML is a reasonable idea that's turning into a management fad and is being used to sell overpriced tools. Such fads come around from time to time. Anyone remember decision logic tables? "Bubtangles?" The Kepner-Tregoe method? "Business Objects?"
State Charts are one of the nine UML diagrams. There are some tutorials here.
~~ What's stopping you?
A state machine is a way of representing a computational task. The machine or program can be in precisely one of a number of possible states at a given time. Different kinds of events cause the system to move from one state to another state (called a transition). Each transition can have an associated side effect. Therefore, the model of computation is:
- read input
- decide which state to move to based on input and current state
- execute transition action
- actually move to the new state
- return to step 1
State machines are theoretically limited in the kinds of input sequences they can process. As it turns out, a state machine can only process inputs which can be described by regular expressions. However, it is possible to "augment" a state machine to extend its power. If you do this by adding a data stack, you have produced what is called a "pushdown automaton" and this gives you a great deal of power. But that is a departure from a pure "CS" FSM.The FSM is sort of the bottom rung of the computational ladder. FSMs can process regular languages (i.e. the languages describable by regular expressions). PDAs can process context-free languages (like most programming languages). Even more powerful than a PDA is a Turing machine, the theoretical "ultimate" model of a computing machine.
It might seem odd to think of the input events to the program as comprising sentences in some "language," but it makes sense when you consider it. Input events have an inherent structure to them, and this structure can often be described in the form of a regular language. In these situations, using an FSM model of the code is very natural since the code is directly, structurally related to the events it is processing.
Ok, there's your dose of CS for the day.
And it took an embedded systems developer to bring it to your attention.
It's not new. We've been doing state diagrams over here in Engineerland for decades.
...
I learned about state diagrams in college years ago. The examples that we used at the time were all the sorts of things that could be done as stand-alone projects. They typically involved parsing strings that had to match a description given by a state diagram. If you are building a lexical scanner by hand or a regular expression library, it's good stuff to know. However, I wondered how often I'd see it in the real world.
Well folks, this can be real world stuff if you apply it. It's all about retaining a state that summarizes inputs that you have seen so far. This is about communication between autonomous devices (or with a user). If nothing else, state information is useful in retaining position within a set of search results when a user is paging through them. It can be used in the session layer of a communication protocol to track handshaking. If you have to asynchronously do two things concurrently within your program, unless each of them involves completely separate transactions that are completely atomic, one or both can be modelled as state machines.
If you write GUI code where you have buttons being toggled, check boxes checked or fields filled, you have a state machine, whether you coded it or not.
If you are writing embedded systems, you don't need me to tell you that you are maintaining real time state information about the devices you are talking to.
The net will not be what we demand, but what we make it. Build it well.
I wrote about this in an internal reply but apparently people didn't seeit and are continuing to make some very ignorant statements about Statecharts.
x .c fm
Statecharts are not a fancy way to do state machines. They are an extremely sophisticated graphics based notation with a formal mathematical semantics for modelling reactive systems. The ideas behind statecharts were developed by David Harel and Amir Pnueli (a winner of the prestigious Touring award and a world expert in Temporal Logic which heavily influenced the semantics of Statecharts).
I was one of the early programmers (later manager) in the company that Harel and Pnueli founded in the early 80s. Because of its mathematical basis, we were able to build a tool that "executed" the statechart designs - not a probabilistic execution, but more akin to a mathematical proof done via a computer program.
This isn't just a nice toy. It was used by companies like Alsthom-Alcatel to build the high-speed TGF train. The reactive model of the train was designed in Statecharts and the model executed. In this way they were able to discover serious flaws in the design (e.g. situations where the doors would open while travelling at high speeds). The only alternative to doing this is to build prototypes and do real world testing. By finding flaws in the very earliest design stage, the company was able to save millions of dollars and perhaps some lives.
For more online information see:
http://ilogix.com/quick_links/white_papers/inde
There is also a paper about Statechart semantics which I am listed as an author out there, but I have only found citations online. UML adopted Harel's Statecharts with some minor modifications, as part of the standard. They never claimed to invent it.
Disclaimer: I still have some stock options in i-Logix which was founded in 1984 but never did go public.