Practical Statecharts in C/C++ 121
Practical Statecharts in C/C++: Quantum Programming for Embedded Systems | |
author | Miro Samek |
pages | 389 |
publisher | CMP Books |
rating | 10/10 |
reviewer | Jonathan Kaye |
ISBN | 1578201101 |
summary | Practical and methodologically sound approach to improving software design using statecharts |
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.
Zing .... (Score:3, Interesting)
I know, I know, you can just google it yourself. But why have hundreds of people searching for exactly the same thing when one person could save a lot of people some time.
what ever happened to Zone Logic? (Score:4, Interesting)
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 [nec.com]
Real world examples. (Score:4, Interesting)
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.
Doom using the zombie trick....Re:Zing .... (Score:2, Interesting)
For instance. When the player crosses a line I want the following to happen. I don't really know state semantics so it's in english which for a programmer is very poor. This can be as complex as you want, this is just a simple one:
Set up some moving floors that will carry an object (zombie doll).
Player crosses line.
Open a door and release zombie doll.
Zombie doll 1 moves, crosses a line and turns up the lighting.
Zombie doll 1 moves crosses a line and opens trap door releasing monsters at player.
Zombie doll 1 moves crosses a line and opens another door releasing Zombie doll 2
Zombie doll 2 moves crosses line opens exit for player.
Zombie doll 1 stops.
Zombie doll 2 moves crosses a line drops floor player may be on.
Zombie doll 2 moves crosses line which turns pit floor into lava.
Zombie doll 2 moves.
Zombie doll 2 moves.
Zombie doll 2 crosses line and opens an exit for the player.
Zombie doll 2 stops.
A friend rendered a bloated complex microprocessor design into a state machine he placed on an eprom.
The eprom was clocked and some other chips added to step it through a rather complex routine. It could take input, it could 'make decisions' based on that input, all of it was encoded on the eeprom.
It required no microprocessor, minimal support hardware ect etc. Just a clock, an eprom, some logic chips and someone who knew state machines.
It was 1000 times less expensive than the buggy, non-working microprocessor design.
All he had to do was see what the customer wanted to do and purpose program it for that task. If it needed reporgramming, burn another eprom.
bumsword of the month - certifiably (Score:2, Interesting)
... methinks SlashDot may be spammed by m$monkeys. Many of my Google searches on this topic ended me up at the msdev site.I resist temptation to drop US$15000 to be m$certified.
State machines, statecharts, all seems a tad modal to me. State, to me, is simply a piece of information and calling it "state" and giving it this whole modal metaphor simply confuses. I hear a FUDding sound
progging by example, examples, lots of examples oh, and we're "modelling" here we don't actually need to do any coding
(aka a class) with various interface methods (messages/questions you can command/ask of this object) that I choose to dangle off of it:Buried underneath/within/externally/remotely of this object somewhere, that no one needs to know about, is some storage that somehow indicates whether the button is currently "up" or "down." I guess some might call this the "state" of the button.
clear as mud
Some good readings ... (Score:2, Interesting)
It is very interesting to see Statecharts mentioned on Slashdot. Statecharts are very useful for many reasons. I know that at NASA, in Europe and in the embedded world, generating code from directly from statecharts is very useful in having a very effective way of producing good code such that all the STATES of the system are known.
Note however that this DOES NOT mean that the code is verified. Things such as deadlocks, livelocks, and unreached states may exist
Another problem that some Statechart autocoders create is that they use a lot of GOTO statements. If you hate GOTOs then you may encounter them a lot with some tools.
Some good references:
Statemate - http://www.ilogix.com/products/magnum/index.cfm
FREE and looks very good, it is a real time model checker for timed automata.
Spin - http://www.spinroot.com/spin/whatispin.html
Also very good
Good reads are some of
1. The work by Eric Klavins of Caltech
http://www.cs.caltech.edu/~klavins/pubs.html
http://www.eecs.umich.edu/gasm/ (Abstract State Machines @ Umich)
Particularly Eric Klavins work on "Object Oriented State Machines"
- http://ai.eecs.umich.edu/CNM/Publications/Publish
- http://www.embedded.com/story/OEG20020429S0053
2. Miro Samek's website
- http://www.quantum-leaps.com/
3. "The Curiously Recurring Template Pattern"
- http://www.langer.camelot.de/Articles/Fawcette/Pa
4. The Boost C++ Metapramming Library (how can one forget Boost?)
- http://www.mywikinet.com/mpl/paper/mpl_paper.html
5. Gerrard Holzmann's Spin Tool
http://www.spinroot.com/spin/whatispin.html
But you should also read Eric Klavin's Propositional Logic Tutorial
- http://www.cs.caltech.edu/~klavins/lpe/slides/pro
6. The work of Nancy Day at the University of British Columbia
ftp://ftp.cs.ubc.ca/pub/local/statecharts/README
And many many more
Re:Karnaugh maps. not granularity (Score:3, Interesting)
If the system uses a single byte that means you have 256 possible states. If you have two bytes it's 65,536 states and so on. I don't think you want to draw a Karnaugh map for something like Emacs, you won't live long enough.
That's what I mean by fine-grained state, a single state of the system is defined by the state of all the bits in the system.
A course-grained state implies a higher level of abstraction. Like in a communications protocol when they say waiting for an Ack is a state.
So this is what I mean by granularity.