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.
It is easy enough to use a standard library that helps you maintain such buffers/stacks/queues. No need to mess around with standard c arrays.
I miss my rubber keyboard.(Homepage)
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.
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 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.
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!
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