To read original PDF of the print article, click here.
Miro Samek and Paul MontgomeryImplementing hierarchical state machines doesn't mean you have to use code-synthesizing tools. Here are some techniques for simple, efficient, and direct mapping of state machines to C or C++.
The Unified Modeling Language (UML) provides a number of conceptual and graphical views for capturing and conveying designs. Among these views, hierarchical state machines (HSMs), based on Harel statecharts, are of key importance and provide the foundation for automatic code generation from object models. 1 Unfortunately, this creates the impression that the methodology is only accessible through use of code synthesizing tools. This is similar to the common belief that object-oriented programming (OOP) is only possible with object-oriented (OO) languages. However, the key OO concepts of encapsulation, inheritance, and polymorphism may be implemented as design patterns 2 in a non-OO language such as C. Similarly, hierarchical state machines can be viewed as another such fundamental pattern.
From a more abstract perspective, one may view hierarchical state machines as a meta-pattern, in that various structured uses become design patterns (behavioral patterns 3 ) in their own right. This is analogous to OO design patterns 7 built on meta-patterns of inheritance and polymorphism. Following this analogy to OOP, we propose the term state-oriented programming (SOP) to describe a programming style based on HSMs.
The primary goal of this article is to present a simple and efficient implementation of the HSM design pattern. By providing easy-to-use C and C++ recipes for generating HSMs, we hope to make the major benefits of the technology more accessible to the software community. The proposed implementation techniques are valuable in that they raise the level of abstraction and allow for straightforward mapping of UML statecharts to compact and efficient code in C or C++. We have used the technique extensively in deeply embedded, hard real-time RF receiver applications where both high speed and small memory footprint were crucial.
In an effort to maximize efficiency and minimize implementation complexity, many of the more advanced features of UML statecharts have been omitted. The implemented features form a proper subset of UML statecharts and include:
More advanced features of UML statecharts (such as history mechanisms and orthogonal regions) can be added as behavioral patterns built on top of the implementation presented here.
We begin with a brief summary of approaches that have been documented in the relevant literature or implemented in commercial products. We then describe our implementation using UML class diagrams and provide a complete implementation in both C and C++. Taking the example of a simple digital watch, we demonstrate how to map a UML state diagram to code and how to use most features of the HSM implementation in a concrete fashion. We briefly discuss how the HSM pattern, when combined with RTOS facilities, can be used to build a powerful real-time framework. We conclude by drawing a comparison between SOP and OOP and propose some modifications and extensions to UML statecharts. We assume that the reader is familiar with basic concepts of state machines and UML notation.3,11
States are represented as instances of the State class, but unlike the "State" pattern as described by Gamma et al.7, the State class is not intended for subclassing but rather for inclusion as is. Accordingly, our approach requires state machines to be constructed by composition rather than by inheritance. The most important attributes of State class are the event handler (to describe behavior specific to the state) and a pointer to superstate (to define nesting of the state).
Messages are represented as instances of Msg class or its subclasses. All messages carry event-type (attribute evt inherited from Msg ) and possibly arbitrary data (added by subclassing).
Events are handled uniformly by event handlers , which are member functions of Hsm class ( typedef EvtHndlr ). As shown in Figure 1 , a state machine consists of at least one state-the top-level state inherited from Hsm . Concrete state machines are built by inheriting from Hsm class, adding an arbitrary number of states (plus other attributes), and defining event handlers.
Because event handlers are methods of Hsm or its subclasses, they have direct access to attributes via the implicit this pointer (in C++) or the explicit me pointer (in C). Within event handlers, only one level of dispatching (based on event-type) is necessary. Typically this is achieved using a single-level switch statement. Event handlers communicate with the state machine engine (see Listing 2 ) through a return value of type Msg* . The semantic is simple: if an event is processed, the event handler returns 0 (NULL pointer); otherwise it returns ("throws") the message for further processing by higher-level states. To be compliant with UML statecharts, the returned message is the same as the received message, although return of a different message type can be considered. As we discuss later, returning the message provides a mechanism similar to "throwing" exceptions.
Entry/exit actions and default transitions are also implemented inside the event handler in response to the pre-defined events ENTRY_EVT , EXIT_EVT , and START_EVT . The state machine engine generates and dispatches these events to appropriate handlers upon state transitions. An alternative approach would be to represent entry/exit and start actions as separate methods, but this would require specification and maintenance of three additional (fine granularity) methods and three additional function pointers in each state.
The topology of a state machine is determined upon construction. The constructor of the concrete HSM is responsible for initialization of all participating State objects by setting the super-state pointers and the event handlers. An example of a state machine and corresponding data structures is shown in Figure 2 . In our approach we do not distinguish between composite-states (states containing substates) and leaf states. All states are potentially composite. State transitions are implemented as macros: STATE_START() and STATE_TRAN() (see Listing 2 ). The first macro (inline member function in C++) handles start transitions (transitions originating from a "black dot" pseudostate). The second macro STATE_TRAN() implements a regular state transition and is slightly more complex.
Due to the UML-specified order of invocation, all exit actions must precede any actions associated with the transition, which must precede any entry actions associated with the newly entered state(s). To discover which exit actions to execute, it is necessary to first find the least common ancestor (LCA) of the source and target states. For example, the LCA of the transition triggered by event e4 in Figure 2 is s2 and the LCA for the transition triggered by event e1 is top .
Finding the LCA can be expensive (see method HsmToLCA_() in Listing 2 ). However, for any given transition the LCA needs to be calculated only once. Method HsmToLCA_() returns the number of levels from the current state to the LCA rather than a pointer to the LCA state itself. The former is the same for all instances of a given HSM, that is, it is characteristic of the Hsm (sub)class rather than individual state machine objects. For this reason it can be stored in a static variable shared by all instances.
The STATE_TRAN() macro ensures that all exit actions to the LCA will be executed. The user must then explicitly invoke any actions associated with the transition and return from the event handler. The framework will then correctly execute any required entry actions.
The state machine engine (method Hsm::onEvent() from Listing 2 ) is small, due mostly to the simple data representation employed. To minimize stack use and maximize performance we were careful to replace potential recursion (natural in hierarchical state machines) with iteration.
Perhaps the weakest part of the implementation lies in execution of entry actions during state transitions. Entry actions must be executed in order from the least deeply nested to the most deeply nested state. 11 This is opposite to the "natural" navigability in our data structure (see Figure 2 ). This problem is solved by first recording the entry path from the LCA to the target, then "playing it backwards" with execution of entry actions. By applying a technique similar to that described previously for LCA calculation, it is possible to record an entry path only once and avoid repetitive calculation. This optimization trades memory and additional complexity for speed improvement.
The typical structure of a framework based on active objects is shown in Figure 4 . The Actor class inherits HSM functionality from Hsm and adds to it a thread of execution (for example, via taskId attribute and task's run() method) and a message queue (via msgQ attribute). Actors can only communicate with each other by sending each other messages via message queues. The messages are processed by the HSM in run-to-completion steps. Run-to-completion ensures that actors don't have to deal with concurrency issues internally, thereby eliminating a whole class of difficult time-domain problems by design.
SOP vs. OOP
Hierarchical state machines introduce a third type of inheritance that is equally fundamental. We call this behavioral inheritance . To understand why hierarchy introduces inheritance and how it works, consider an empty (or transparent) substate nested within an arbitrary superstate. If such a substate becomes active it behaves in exactly the same way as its superstate, that is, it inherits the superstate's entire behavior. This is analogous to a subclass which does not introduce any new attributes or methods. An instance of such a subclass is indistinguishable from its superclass because, again, everything is inherited exactly.
This property of HSMs is fundamental because it requires only the differences from the superstate's behavior to be defined. One observes that all OO design principles (for example, the Liskov Substitution Principle) hold in HSM designs because one deals with inheritance in yet another form. The concept of behavioral inheritance describes the "is-a" ("is-in") relationship between substates and superstates and should not be confused with inheritance of entire state models. 3
The analogy between SOP and OOP goes further. Class instantiation and finalization is similar to entering and exiting a state. In both cases special methods are invoked: constructors and destructors for objects, entry and exit actions for states. Even the order of invocation of these methods is the same: constructors are invoked starting from most remote ancestor classes (destructors are invoked in reverse order), and entry actions are invoked starting from the topmost superstate (exit actions are invoked in reverse order).
A final similarity between OOP and SOP lies in the way they are most efficiently implemented. Although polymorphism can be implemented in many ways, virtually all C++ compilers implement it in the same way: by using function pointers grouped into virtual tables. In view of the deep analogy between SOP and OOP, it is therefore not surprising that arguably the most efficient implementation of HSMs is also based on function pointers grouped into states. These simple state objects define both behavior and hierarchy but are not specific to any particular instance of a state machine. The same holds for virtual functions, which are characteristics of the whole class rather than specific to any particular object instance. For this reason we observe that state objects could (and probably should) be placed in v-tables and be supported as a native language feature.
Improvements to UML?
We propose to include reactions in state diagrams as directed lines starting and finishing in the same state and lying entirely within that state. (An example of this notation is shown in Figure 3 for reactions to TICK_EVT and MODE_EVT .) Please note that this notation is different from self-transitions, which also begin and end in the same state, but lie entirely outside the state. Self-transitions are different from reactions because they cause execution of entry and exit actions.
UML statecharts distinguish composite-states (states with substates) from leaf-states (states without substates) in that they only allow leaf-states to be active. This is an unnecessary limitation, which occasionally creates degenerate (empty) substates. To extend the analogy with OOP, this is like saying that a class with subclasses must necessarily be abstract. Our HSM implementation does not distinguish between composite and leaf states; it allows any state to be active.
In our experience with receiver-applications we frequently encountered the following situation: in response to a given event, we wished to perform an action (for example, update a digital filter) and then-depending on the state of the filter-potentially take a (conditional) state transition. We did not want to treat the filter update as part of the guard condition because this would add a side effect to the guard (typically a bad idea 11 ). The only alternative is to treat the filter update as an action.
UML requires that actions associated with transitions be executed after all exit-actions from the source state but before any entry-actions to the target state. 11 At this point however, it is not yet know if the transition will be required at all. In general, this aspect of UML semantics makes it difficult to mix conditional execution of reactions and transitions. A UML-compliant solution would require specification of a pure reaction (update of the digital filter in this case) and then conditional propagation of another event to "self," specifically to trigger a pure state transition.
Because our implementation performs state transitions using the STATE_TRAN() macro, which causes execution of all exit-actions up to least common ancestor, the order of execution is left to the designer. The UML-compliant implementation requires invoking the STATE_TRAN() macro before other actions associated with the transition. With our approach, the designer may choose a different order (for example, reaction-guard-transition), if it would simplify the problem at hand.
A final (proposed) extension to UML statecharts is associated with event handling at different levels of a hierarchical state machine. UML statecharts require that the same event be presented for processing to all levels of the hierarchy, starting with the active state. We propose to allow an event to change as it propagates upward through the state hierarchy. In our implementation this is simple to achieve. This feature would facilitate "throwing" an exception to a higher scope, which could in turn either handle or "throw" it again. Because outer states of an HSM are typically behavioral generalizations of inner states, this technique for handling exceptions is natural and arguably, makes more sense than the traditional exception handling technique of unwinding the call stack.
The HSM pattern is flexible, allowing even fundamental changes in state machine topology to be accomplished easily, even late in the process. Due to their hierarchical nature, models can be developed in incremental steps and remain executable throughout the development cycle. By requiring only specialization of behavior to be coded at nested levels of the state machine, common policy mechanisms (for example, exception handling) can be handled naturally. The state machine engine can easily be instrumented (an example is available in code accompanying this article at http://www.embedded.com/code/2000code.htm) to produce execution trace, message sequence charts, or even animated state diagrams. In practice, however, we found it most useful to use a standard debugger to step through interesting parts of the code.
This implementation of the HSM pattern is no more complex than an internal implementation of inheritance or polymorphism in C++ and, in fact, has many similarities (both are based on function pointers). Given the many parallels, it seems reasonable to suggest that state-oriented programming should be directly supported by a (state-oriented) programming language in the same way that OOP is supported by object-oriented languages. We see this as beneficial for a couple of reasons. First, the compiler could place state objects in a virtual table and perform memory and performance optimizations at compile time (for example, computation of LCAs for state transitions). Second, the compiler could check consistency and well-formedness of the state machine, thereby eliminating many errors at compile time. In our view this is one direction in which C/C++ could evolve to better support future real-time applications.
Miro Samek is lead software architect at IntegriNautics Corp. He holds a PhD in physics from Jagiellonian University in Cracow, Poland. Miro previously worked at GE Medical Systems where he developed real-time software for diagnostics X-ray equipment. He may be reached at firstname.lastname@example.org .Paul Y. Montgomery is software group leader at IntegriNautics Corp. He holds a PhD in Aero/Astro engineering from Stanford University, specializing in control systems applications based on the Global Positioning System. He may be reached at email@example.com.
3 . Douglass, Bruce Powell. Doing Hard Time. Reading MA: Addison-Wesley Longman, 1999.
4 . Douglass, Bruce Powell. Real-Time UML: Developing Efficient Objects for Embedded Systems. Reading, MA: Addison-Wesley, 1998.
6 . Selic, Bran, Garth Gullekson, and Paul T. Ward. Real-Time Object-Oriented Modeling. New York City: John Wiley & Sons Inc., 1994.
7 . Gamma, Erich, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Reading, MA: Addison-Wesley, 1995.
9. Douglass, Bruce Powell and Srini Vason, "Temporal Models in UML," Dr. Dobbs Journal, December 1999.
10. Levkoff, Bruce, "A Schlaer-Mellor Architecture for Embedded Systems," Embedded Systems Programming, November 1999, p. 88.11. Douglass, Bruce Powell, " UML Statecharts " Embedded Systems Programming, January 1999, p. 22.