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.
That's the sound of a topic that went zooming over the heads of most /.'ers (me included). It would have been quite nice of the author to include some links that describe what a statechart is and why a C++ programmer should care. It might be one of those things where the book is geared towards those who already know, but it would still be good so those who don't could get some background.
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.
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?"
"While I can see that author Miro Samek has a directed target for his audience, I strongly feel that this book is a 'must read' for technical developers that wish to eliminate their chances at successfully mating within the next three to four days. In most cases, the knowledge gleaned from this book will also allow the reader to avoid sexual intercourse indefinately (excluding mating rituals that involve the transfer of monetary units first)."
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.
...
For those readers who haven't before encountered state machines:
Los Alamos National Lab has some good info (overview mostly)
Lecture notes from MIT
An interesting research project from The Beast
Some info on how FSMs are used for AI in computer games
Arr! The laws of physics be a harsh mistress!
I once had to use an authoring tool (Rapid CBT), priced in the thousands of dollars, which was completely driven by statecharts. In my opinion, the statecharts offered no advantage at in the development as most of the logic needed wasn't suitable for statecharts. My guess is that statecharts are an easy way to make a visual representation of what is happening in the code, but is restrictive to the coding itself.
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.
If you've ever used one of the source ports that allow more triggerable actions and used a 'zombie doll' you've designed a state machine.
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.
I'd go on a Vegan diet but the delivery time from Vega is too long. --brownkitty
... 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
Ed Nisley had reviewed this in Dr. Dobb's Journal. The review is available here. I had just read the article this morning and was pleasently surprised to see the review here.
First and absolutely foremost: an FSM is an adstract concept born of graph theory. A statechart is a diagram of an FSM, which complies to a rigorous specification for what each notation means.
The statechart spec adds a few semantically trivial notations (i.e. they can be easily translated into standard digraph style FSM), which are nonetheless extremely useful for presenting clear, easy to understand diagrams.
Most of those additions have been mentioned already (e.g. nesting) but there are also guard conditions (i.e. transition if X except if y), and indications of entrance, presence, and exit behavior. Very handy for describing behavior.
IP is just rude.
Is there any torture so subl
As one of the original developers of Statemate, a tool for modelling with Statecharts, I have to step in here. Statecharts are not flow charts nor are they state diagrams. They are an extension of the latter, but they are actually a mathematical language based on temporal logic. As such, Statecharts can be processed to prove or disprove assertions about your design.
x .c fm
:)
Alsthom Alcatel, for example, used our tool to discover flaws in the high-speed TGF before they started actually building it. They thereby saved millions of dollars in construction retooling costs and probably some lives as well.
You can find a whole bunch of whitepapers here:
http://ilogix.com/quick_links/white_papers/inde
Full disclosure: I still have in a drawer somewhere some stock options in i_logix, which was founded in 1984 but never did go public
Statecharts are not just buzzword ... I think that the comments should treat this topic as effectively as possible. Statecharts are perhaps one of the most useful ways of representing and specifiying system behavior.
... but what one can then do is then run a verifier on the statechart, to sort out these niggly bits.
S tateflow - http://www.ilogix.com/products/magnum/index.cfm
U ppaal - http://www.uppaal.com/ ... and quite powerful
e d_Articles/EmbeddedSystemsArticle.html
t ternAlmanac/review.htm
# example
p ositional.ppt
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
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.
That's funny. On my machine, Intel C++ 7.x compiles a simple std::string/std::vector test into code that executes slight faster than the equivilent const char */const char ** test. Unless you have the time to hand optimize every little data structure, the STL will be faster in the long run. I always find it silly when I read C books, and see something like "a linked list isn't the most efficient data structure for this, but this operation isn't *that* critical, and using a list saves implementation complexity." If we were using the STL, you could just use whatever data structure was best suited to the task at hand, without worrying about implementation complexity!
A deep unwavering belief is a sure sign you're missing something...
Karnaugh maps were traditionaly used by hardware logic designers to minimize the number of gates required to implement a logical function at the bit level.
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.