Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Introduction Why Bother? Designing a Statechart The Next Step Coding a Statechart in C It's All About Me Declaring State Machine Objects Initializing State Machine Objects Deploying the Application on the Toolstick

Why Bother?

The legitimate question is "Why even bother using advanced UML statecharts in low-end 8-bitters?" After all, these parts are so small that no big programs can fit into them anyway, let alone designs requiring UML statecharts.

Well, a lot can go wrong in 8KB, or even 4KB of code. All these small microcontrollers are archetypal event-driven systems with the main job of constantly reacting to events. In general, the reaction to an event depends both on the event type and, more importantly, on the current execution context. For example, if you press a button of an electronic watch, the watch probably reacts differently when it is in the timekeeping mode, compared to the same button pressed in the setting mode.

From the programming point of view, the dependency on the context often leads to convoluted, deeply nested if-else spaghetti code. The "spaghetti" results from capturing the various bits and pieces of the relevant event history (the context) in multitude of variables and flags, then setting, clearing, and testing these variables in complex expressions scattered throughout the code until it's really hard to tell which path through the code will be taken in response to a given event.

Finite State Machines (FSMs) offer a better alternative because they make the reactions to events explicitly dependent on the execution context, represented as "state". By recognizing the importance of the context upfront, FSMs become powerful spaghetti reducers that drastically cut the number of execution paths through the code, simplify the conditions tested at each branching point, and simplify transitions between different modes of operation; see my article "Back to Basics" for more information. In doing this, state machines eliminate many variables and flags used to store the context, and replace most of them with a single "state variable". Therefore the resulting application typically requires less RAM than the original spaghetti, which is a big deal for a small 8-bitter.

But I'm probably not saying anything new. The classical automata theory has been around since dirt. Nonetheless, it is also widely known that the traditional FSMs have a nasty tendency called "state and transition explosion". The number of states and transitions necessary to represent a system tends to grow faster than the complexity of the system itself because the traditional FSM formalism imposes repetitions; see my article "Deja Vu". For example, a FSM model of a simple 4-operation calculator might have some 15 states. Every one of these states needs to handle the "C" (CANCEL) event, because users must be able to cancel computations and start over at any stage. In traditional FSMs, you have to repeat the essentially identical CANCEL transition some 15 times. Similarly, you have to repeat at least a few times the "CE" (CANCEL_ENTRY) transition, the "=" (EQUALS) transition, and many others. Needless to say, the resulting code is not just bloated, but is also full of impossible to maintain repetitions, all of which renders the whole formalism barely usable. The complexity level at which FSMs start to "explode" is quite low. Apparently, traditional state machines are already in trouble to handle the complexity of a 4-operation calculator, a small home appliance, or even a more advanced digital watch--all application areas for low-end microcontrollers.

To become truly usable, the classical automata theory needs a mechanism for sharing and reusing transitions across many states. The formalism of statecharts, invented originally by David Harel and adapted subsequently into virtually all modern methodologies, including the UML, adds exactly such a mechanism. By allowing hierarchical nesting of states, statecharts provide an efficient way of sharing behavior, so that the complexity of a statechart no longer explodes but grows linearly with the complexity of the modeled system. Obviously, formalism like this is a blessing to embedded developers because it makes the state machine approach truly applicable to real-life problems; see "Deja Vu".

Reuse of Behavior in UML Statecharts Statecharts achieve reuse of actions and transitions through a combination of hierarchy and "programming-by-difference" semantics. States may have substates that inherit the actions and transitions of their superstates, just as classes have subclasses that inherit the attributes and operations of their superclasses. For example, a state diagram of a pocket calculator can be vastly simplified by introducing an abstract superstate "on" that contains most of the calculator states inside (see Figure 4). [Click image to view at full size] Figure 4: UML state diagram of a pocket calculator where all substates of "on" superstate share the common transitions CANCEL and OFF. To understand how the high-level transitions apply, assume that the user presses the CANCEL button while the calculator state machine is in the result state. The state result does not pre-scribe how to handle the CANCEL event. However, the CANCEL event is not silently discarded, as it would be the case in the traditional FSM. Rather, because result is now nested inside the on superstate, the state machine attempts to handle the event at the higher level of state hierarchy of the on state. Because UML statecharts support entry and exit actions on states, the self-transition CANCEL in the on state requires in this case exiting the result state, exiting the on state, en-tering the on state again, taking the initial transition within the on state, and finally entering the begin state. In summary, the transition CANCEL took the state machine from state result to state begin, properly exiting and entering all the states on the way. Identical argumentation can be made for every substate of the on superstate, so the single CANCEL transition in the on superstate replaces all low-level transitions that would be necessary in the traditional "flat" FSM without hierarchy. As you can see, the semantics of hierarchical state nesting is based on the "programming-by-difference" principle. All substates of the on superstate need only define the differences from the superstate, and otherwise can reuse the behavior by simply ignoring the commonly handled events, such as CANCEL or OFF. —M.S.

Previous Page | 1 Introduction | 2 Why Bother? | 3 Designing a Statechart | 4 The Next Step | 5 Coding a Statechart in C | 6 It's All About Me | 7 Declaring State Machine Objects | 8 Initializing State Machine Objects | 9 Deploying the Application on the Toolstick Next Page

RELATED ARTICLES Logging In C++ : Part 2 OutSystems Updates Agile Platform SDK, .NET Controls Released for Communications Enabling Web Pages Welcome To the World of Cryptographic Voting recls 100% .NET		TOP 5 ARTICLES No Top Articles.