MIRO SAMEK AND PAUL MONTGOMERY

f e a t u r e

State-Oriented
Programming
Implementing 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++.

T
he Unified Modeling Language (UML) pro- patterns7 built on meta-patterns of inheritance and poly-
vides a number of conceptual and graphical morphism. Following this analogy to OOP, we propose the
views for capturing and conveying designs. term state-oriented programming (SOP) to describe a pro-
Among these views, hierarchical state gramming style based on HSMs.
machines (HSMs), based on Harel state- The primary goal of this article is to present a simple
charts, are of key importance and provide the and efficient implementation of the HSM design pattern.
foundation for automatic code generation from object By providing easy-to-use C and C++ recipes for generating
models.1 Unfortunately, this creates the impression that HSMs, we hope to make the major benefits of the technol-
the methodology is only accessible through use of code ogy more accessible to the software community. The pro-
synthesizing tools. This is similar to the common belief posed implementation techniques are valuable in that they
that object-oriented programming (OOP) is only possi- raise the level of abstraction and allow for straightforward
ble with object-oriented (OO) languages. However, the mapping of UML statecharts to compact and efficient code
key OO concepts of encapsulation, inheritance, and in C or C++. We have used the technique extensively in
polymorphism may be implemented as design patterns2 deeply embedded, hard real-time RF receiver applications
in a non-OO language such as C. Similarly, hierarchical where both high speed and small memory footprint were
state machines can be viewed as another such fundamen- crucial.
tal pattern. In an effort to maximize efficiency and minimize imple-
From a more abstract perspective, one may view hierar- mentation complexity, many of the more advanced features
chical state machines as a meta-pattern, in that various of UML statecharts have been omitted. The implemented
structured uses become design patterns (behavioral pat- features form a proper subset of UML statecharts and
terns3) in their own right. This is analogous to OO design include:

22 AUGUST 2000 Embedded Systems Programming

 State-oriented programming raises the level of abstraction and
allows for straightforward mapping of UML statecharts to
compact and efficient code in C or C++.

• Nested states with proper handling the discriminator in the first level (including entry/exit, state reac-
of group transitions and group of the switch and event-type in the tions, and actions associated with
reactions second.4 This is, perhaps, the most transitions) are most commonly
• Guaranteed execution of common technique and works well represented as pointers to func-
entry/exit actions upon enter- for classical “flat” state machines tions. Representing state hierarchy
ing/exiting states and is widely employed by automat- in a flat action-state table is cum-
• Straightforward implementation of ic code synthesizing tools.5 Manual bersome. Also, this approach
conditional event responses coding of entry/exit actions and requires a large (and consequently
(guards) nested states is, however, cumber- wasteful) action/state array and
• Design that enables inheriting and some, mainly because code pertain- many fine-granularity functions
specializing state models ing to one state becomes distrib- representing actions
uted and repeated in many places, • Generic “state machine inter-
More advanced features of UML making it difficult to modify and preters” driven by typically com-
statecharts (such as history mecha- maintain when the topology of plex data structures that represent
nisms and orthogonal regions) can be state machine changes the hierarchy of states together
added as behavioral patterns built on • Action-state tables containing typi- with entry/exit actions and transi-
top of the implementation presented cally sparse arrays of actions and tions.6 This is a generalized action-
here. transitions for each state.4 Actions state table approach that attempts
We begin with a brief summary of
approaches that have been document-
ed in the relevant literature or imple- FIGURE 1 Structure of HSM design pattern
mented in commercial products. We
then describe our implementation
super
using UML class diagrams and pro-
vide a complete implementation in
both C and C++. Taking the example State Hsm
curr
of a simple digital watch, we demon-
super curr
strate how to map a UML state dia- handler top top
gram to code and how to use most fea- Msg ... ...
tures of the HSM implementation in a
evt : Event onEvent (Hsm*, Msg*) onEvent (Msg *)
concrete fashion. We briefly discuss
how the HSM pattern, when com- *
bined with RTOS facilities, can be
used to build a powerful real-time
framework. We conclude by drawing a
comparison between SOP and OOP
ConcreteHsm
and propose some modifications and 1
extensions to UML statecharts. We MsgWithData stateA
stateB
assume that the reader is familiar with dataA ...
basic concepts of state machines and dataB
...
UML notation.3,11

Standard approaches Legend:

Typical implementations of state aggregation: inheritance:

0 .. 1 0..* sub super
RUPERT ADLEY

machines in C/C++ include:

composite aggregation: association:
0 .. 1 0..* role–1 role–2
• Doubly nested switch statements
with a scalar “state variable” used as

Embedded Systems Programming AUGUST 2000 23

hsm

to represent HSMs with a more effi-

LISTING 1a hsm.h—C header file cient data structure than an array.
Techniques in this category require
typedef int Event; each action to be coded as a sepa-
typedef struct { rate function. They perform rela-
Event evt; tively poorly if the state machine is
} Msg; complex
• Object-oriented “State” design pat-
typedef struct Hsm Hsm; tern based on delegation and poly-
typedef Msg const *(*EvtHndlr)(Hsm*, Msg const*); morphism.7,3 States are represent-
ed as subclasses implementing a
typedef struct State State; common interface (each method
struct State { in this interface corresponds to an
State *super; /* pointer to superstate */ event). A context class delegates all
EvtHndlr hndlr; /* state’s handler function */ events for processing to the current
char const *name; state object. State transitions are
}; accomplished by changing the cur-
rent state object (typically re-assign-
void StateCtor(State *me, char const *name, ing one pointer). This pattern is
State *super, EvtHndlr hndlr); elegant and relatively efficient but
#define StateOnEvent(me_, ctx_, msg_)\ is not hierarchical. Accessing con-
(*(me_)->hndlr)((ctx_), (msg_)) text attributes from state methods
is indirect (cannot use an implicit
struct Hsm { /* Hierarchical State Machine base class */
this pointer) and breaks encapsu-
char const *name; /* pointer to static name */
lation. The addition of new states
State *curr; /* current state */
requires subclassing and the addi-
State *next; /* next state (non 0 if transition taken) */
tion of new events requires adding
State top; /* top-most state object */
new methods to the common inter-
};
face

void HsmCtor(Hsm *me, char const *name, EvtHndlr topHndlr);

Implementation
void HsmOnStart(Hsm *me); /* enter and start the top state */
Our implementation of the HSM pat-
void HsmOnEvent(Hsm *me, Msg const *msg); /* “HSM engine” */
tern is, to some degree, a combination
of the techniques itemized above. The
/* protected: */
structure of the pattern is shown in
unsigned char HsmToLCA_(Hsm *me, State *target);
Figure 1. This structure is greatly sim-
void HsmExit_(Hsm *me, unsigned char toLca);
plified relative to the standard full-fea-
#define STATE_CURR(me_) (((Hsm *)me_)->curr)
#define STATE_START(me_, target_) \
tured UML design.8
(assert((((Hsm *)me_)->next == 0),\
States are represented as instances
((Hsm *)me_)->next = (target_))
of the State class, but unlike the
“State” pattern as described by
#define STATE_TRAN(me_, target_) if (1) { \ Gamma et al.7, the State class is not
static unsigned char toLca_ = 0; \ intended for subclassing but rather for
assert(((Hsm *)me_)->next == 0);\ inclusion as is. Accordingly, our
if (toLca_ == 0) \ approach requires state machines to
toLca_ = HsmToLCA_((Hsm *)(me_), (target_));\ be constructed by composition rather
HsmExit_((Hsm *)(me_), toLca_);\ than by inheritance. The most impor-
((Hsm *)(me_))->next = (target_);\ tant attributes of State class are the
} else ((void)0) event handler (to describe behavior
specific to the state) and a pointer to
#define START_EVT ((Event)(-1)) superstate (to define nesting of the
#define ENTRY_EVT ((Event)(-2)) state).
#define EXIT_EVT ((Event)(-3)) Messages are represented as
instances of Msg class or its subclasses.

24 AUGUST 2000 Embedded Systems Programming

hsm

All messages carry event-type

LISTING 1b hsm.h—C++ header file (attribute evt inherited from Msg) and
possibly arbitrary data (added by sub-
typedef int Event;
classing).
struct Msg {
Events are handled uniformly by
Event evt;
event handlers, which are member func-
};
tions of Hsm class (typedef EvtHndlr).
As shown in Figure 1, a state machine
class Hsm; /* forward declaration */
typedef Msg const *(Hsm::*EvtHndlr)(Msg const *);
consists of at least one state—the top-
level state inherited from Hsm.
class State { Concrete state machines are built by
State *super; /* pointer to superstate */ inheriting from Hsm class, adding an
EvtHndlr hndlr; /* state’s handler function */ arbitrary number of states (plus other
char const *name; attributes), and defining event
public: handlers.
State(char const *name, State *super, EvtHndlr hndlr); Because event handlers are meth-
private: ods of Hsm or its subclasses, they have
Msg const *onEvent(Hsm *ctx, Msg const *msg) { direct access to attributes via the
return (ctx->*hndlr)(msg); implicit this pointer (in C++) or the
} explicit me pointer (in C). Within
friend class Hsm; event handlers, only one level of dis-
}; patching (based on event-type) is nec-
essary. Typically this is achieved using
class Hsm { /* Hierarchical State Machine base class */ a single-level switch statement. Event
char const *name; /* pointer to static name */ handlers communicate with the state
State *curr; /* current state */
machine engine (see Listing 2)
protected:
through a return value of type Msg*.
State *next; /* next state (non 0 if transition taken) */
The semantic is simple: if an event is
State top; /* top-most state object */
processed, the event handler returns 0
public:
(NULL pointer); otherwise it returns
Hsm(char const name, EvtHndlr topHndlr); /* Ctor */
(“throws”) the message for further
void onStart(); /* enter and start the top state */
void onEvent(Msg const *msg); /* “state machine engine” */
processing by higher-level states. To be
protected:
compliant with UML statecharts, the
unsigned char toLCA_(State *target); returned message is the same as the
void exit_(unsigned char toLca); received message, although return of
State *STATE_CURR() { return curr; } a different message type can be con-
void STATE_START(State *target) { sidered. As we discuss later, returning
assert(next == 0); the message provides a mechanism
next = target; similar to “throwing” exceptions.
} Entry/exit actions and default tran-
# define STATE_TRAN(target_) if (1) {\ sitions are also implemented inside
static unsigned char toLca_ = 0;\ the event handler in response to the
assert(next == 0);\ pre-defined events ENTRY_EVT,
if (toLca_ == 0)\ EXIT_EVT, and START_EVT. The state
toLca_ = toLCA_(target_);\ machine engine generates and dis-
exit_(toLca_);\ patches these events to appropriate
next = (target_);\ handlers upon state transitions. An
} else ((void)0) alternative approach would be to rep-
};
resent entry/exit and start actions as
separate methods, but this would
#define START_EVT ((Event)(-1))
require specification and mainte-
#define ENTRY_EVT ((Event)(-2))
nance of three additional (fine granu-
#define EXIT_EVT ((Event)(-3))
larity) methods and three additional
function pointers in each state.

26 AUGUST 2000 Embedded Systems Programming

hsm

The topology of a state machine is

LISTING 2a hsm.c—C implementation determined upon construction. The
constructor of the concrete HSM is
static Msg const startMsg = { START_EVT }; responsible for initialization of all par-
static Msg const entryMsg = { ENTRY_EVT }; ticipating State objects by setting the
static Msg const exitMsg = { EXIT_EVT }; super-state pointers and the event han-
#define MAX_STATE_NESTING 8 dlers. An example of a state machine
/* Hsm ctor */ and corresponding data structures is
void HsmCtor(Hsm *me, char const *name, EvtHndlr topHndlr) { shown in Figure 2. In our approach we
StateCtor(&me->top, “top”, 0, topHndlr); do not distinguish between composite-
me->name = name; states (states containing substates) and
} leaf states. All states are potentially
/* enter and start the top state */ composite.
void HsmOnStart(Hsm *me) { State transitions are implemented
State *entryPath[MAX_STATE_NESTING]; as macros: STATE_START() and
register State **trace; STATE_TRAN() (see Listing 2). The first
register State *s; macro (inline member function in
me->curr = &me->top; C++) handles start transitions (transi-
me->next = 0; tions originating from a “black dot”
StateOnEvent(me->curr, me, &entryMsg); pseudostate). The second macro
while (StateOnEvent(me->curr, me, &startMsg), me->next) { STATE_TRAN() implements a regular
for (s = me->next, trace = entryPath, *trace = 0; state transition and is slightly more
s != me->curr; s = s->super) complex.
*(++trace) = s; /* trace path to target */ Due to the UML-specified order of
while (s = *trace ) /* retrace entry from source */ invocation, all exit actions must pre-
StateOnEvent(s, me, &entryMsg); cede any actions associated with the
me->curr = me->next; transition, which must precede any
me->next = 0; entry actions associated with the newly
} entered state(s). To discover which
} exit actions to execute, it is necessary
/* state machine “engine” */ to first find the least common ancestor
void HsmOnEvent(Hsm *me, Msg const *msg) { (LCA) of the source and target states.
State *entryPath[MAX_STATE_NESTING]; For example, the LCA of the transi-
register State **trace; tion triggered by event e4 in Figure 2
register State *s; is s2 and the LCA for the transition
for (s = me->curr; s; s = s->super) { triggered by event e1 is top.
if ((msg = StateOnEvent(s, me, msg)) == 0) {; Finding the LCA can be expensive
if (me->next) { /* state transition taken? */ (see method HsmToLCA_() in Listing
for (s = me->next, trace = entryPath, *trace = 0; 2). However, for any given transition
s != me->curr; s = s->super) the LCA needs to be calculated only
*(++trace) = s; /* trace path to target */ once. Method HsmToLCA_() returns the
while (s = *trace ) /* retrace entry from LCA */ number of levels from the current
StateOnEvent(s, me, &entryMsg); state to the LCA rather than a pointer
me->curr = me->next; to the LCA state itself. The former is
me->next = 0; the same for all instances of a given
while (StateOnEvent(me->curr, me, &startMsg), HSM, that is, it is characteristic of the
me->next) { Hsm (sub)class rather than individual
for (s = me->next->super, trace = entryPath, state machine objects. For this reason
*trace = 0; s != me->curr; s = s->super) it can be stored in a static variable
*(++trace) = s; /* record path to target */ shared by all instances.
while (s = *trace ) /* retrace the entry */ The STATE_TRAN() macro ensures
StateOnEvent(s, me, &entryMsg); that all exit actions to the LCA will be
executed. The user must then explicit-
ly invoke any actions associated with

28 AUGUST 2000 Embedded Systems Programming

hsm

current time by pressing the

LISTING 2a, cont’d. hsm.c—C implementation
“mode” button

me->curr = me->next;
• Pressing the “set” button switches
the watch into setting mode. The
me->next = 0;
sequence of adjustments in this
}
mode is: hour, minute, day, month.
}
Adjustments are made by pressing
break; /* event processed */
the “mode” button, which incre-
}
ments the chosen quantity by one.
}
Pressing the “set” button while
}
adjusting month puts the watch
/* exit current states and all superstates up to LCA */
back into timekeeping mode
void HsmExit_(Hsm *me, unsigned char toLca) {
register State *s;
• While in setting mode the watch
ignores tick events
for (s = me->curr; toLca > 0; toLca, s = s->super)
StateOnEvent(s, me, &exitMsg);
• Upon return to timekeeping mode
the watch displays the most recent-
me->curr = s;
ly selected information, that is, if
}
date was selected prior to leaving
/* find # of levels to Least Common Ancestor */
timekeeping mode, the watch
unsigned char HsmToLCA_(Hsm *me, State *target) {
resumes displaying the date, other-
State *s, *t;
wise it displays the current time
unsigned char toLca = 1;
for (s = me->curr->super; s != 0; ++toLca, s = s->super)
A state diagram for the specifica-
for (t = target; t != 0; t = t->super)
tion given above is depicted in Figure
if (s == t)
3b and its partial implementation is
return toLca;
shown in Listing 3. We apply the HSM
return 0;
pattern according to the following
}
recipe:

1. Declare a new class, inheriting

from Hsm class (the Watch class)
the transition and return from the backwards” with execution of entry 2. Put into this new class all states
event handler. The framework will actions. By applying a technique sim- (State class instances) and other
then correctly execute any required ilar to that described previously for attributes (tsec, tmin, thour, and so
entry actions. LCA calculation, it is possible to on)
The state machine engine (method record an entry path only once and 3. Declare an event handler method
Hsm::onEvent() from Listing 2) is avoid repetitive calculation. This (member function) for every state.
small, due mostly to the simple data optimization trades memory and Don’t forget to declare event han-
representation employed. To mini- additional complexity for speed dlers for inherited states, like top,
mize stack use and maximize perfor- improvement. whose behavior you intend to cus-
mance we were careful to replace tomize
potential recursion (natural in hierar- Sample application 4. Define the state machine topology
chical state machines) with iteration. To illustrate the use of the HSM pat- (nesting of states) in the new class
Perhaps the weakest part of the tern, consider a simple digital watch (the Watch class) constructor
implementation lies in execution of (Figure 3). The watch has two but- 5. Define events for the state machine
entry actions during state transitions. tons—which generate external (for example, as enumeration).
Entry actions must be executed in events—and an internally generated You can use event-types starting
order from the least deeply nested to tick event. The different events are from 0, because the pre-defined
the most deeply nested state.11 This is handled differently depending upon events use the upper limit of the
opposite to the “natural” navigability the mode of operation. The basic Event type range (see Listing 1)
in our data structure (see Figure 2). watch operates as follows: 6. Define event handler methods.
This problem is solved by first Code entry/exit actions and start-
recording the entry path from the • In timekeeping mode, the user can up transitions as response to pre-
LCA to the target, then “playing it toggle between displaying date or defined events ENTRY_EVT,

30 AUGUST 2000 Embedded Systems Programming

hsm

EXIT_EVT, and START_EVT, respec- 8. Arrange to invoke Hsm::onEvent() of active objects exists in many model-
tively. Provide code for other events for each incoming event ing languages under different names:
using STATE_TRAN() macro for state active objects stereotype in UML9,
transitions. Remember to return 0 Real-time framework active instance in Schlaer-Mellor10,
(NULL pointer) if you handle the The HSM design pattern is particular- and actor in ROOM6. We use the term
event and the initial message point- ly suited for implementing behavior “actor” because it’s most compact.
er if you don’t associated with active objects (objects The typical structure of a frame-
7. Execute the initial start transition that are the roots of threads-of-control work based on active objects is shown
by invoking Hsm::onStart() in a multitasking system). The concept in Figure 4. The Actor class inherits

FIGURE 2 a) State diagram and b) corresponding data structure

a b Null

top top

super
s2
s1
e1 s21 s1 s2

super super
e3 e4
e2 s22
s21 s22

super super

FIGURE 3 a) Simple digital watch events and b) corresponding state diagram

a b

top

timekeeping
setting
H
SET_EVT
time

MODE_EVT hour minute

MODE_EVT MODE_EVT MODE_EVT

SET_EVT

SET_EVT SET_EVT
MODE_EVT

date month day

TICK_EVT MODE_EVT MODE_EVT

TICK_EVT SET_EVT

SET_EVT

32 AUGUST 2000 Embedded Systems Programming

hsm

HSM functionality from Hsm and adds

LISTING 2b hsm.cpp—C++ implementation to it a thread of execution (for exam-
ple, via taskId attribute and task’s
static Msg const startMsg = { START_EVT };
run() method) and a message queue
static Msg const entryMsg = { ENTRY_EVT };
(via msgQ attribute). Actors can only
static Msg const exitMsg = { EXIT_EVT };
communicate with each other by send-
#define MAX_STATE_NESTING 8
ing each other messages via message
/* Hsm ctor */
queues. The messages are processed
Hsm::Hsm(char const *name, EvtHndlr topHndlr)
by the HSM in run-to-completion steps.
: top(“top”, 0, topHndlr) { this->name = name; }
Run-to-completion ensures that actors
/* enter and start the top state */
don’t have to deal with concurrency
void Hsm::onStart() {
issues internally, thereby eliminating a
State *entryPath[MAX_STATE_NESTING];
whole class of difficult time-domain
register State **trace;
problems by design.
register State *s;
curr = ⊤
SOP vs. OOP
next = 0;
OOP introduces two fundamental
curr->onEvent(this, &entryMsg);
types of inheritance: implementation
while (curr->onEvent(this, &startMsg), next) {
(class) inheritance and interface
for (s = next, trace = entryPath, *trace = 0;
inheritance.7 Implementation inheri-
s != curr; s = s->super)
tance defines an object’s implementa-
*(++trace) = s; /* trace path to target */
tion in terms of another object’s
while (s = *trace ) /* retrace entry from source */
implementation. In contrast, inter-
s->onEvent(this, &entryMsg);
face inheritance enforces only object
curr = next;
interface compatibility regardless, of
next = 0;
implementation.
}
Hierarchical state machines intro-
}
duce a third type of inheritance that is
/* state machine “engine” */
equally fundamental. We call this
void Hsm::onEvent(Msg const *msg) {
behavioral inheritance. To understand
State *entryPath[MAX_STATE_NESTING];
why hierarchy introduces inheritance
register State **trace;
and how it works, consider an empty
register State *s;
(or transparent) substate nested with-
for (s = curr; s; s = s->super) {
in an arbitrary superstate. If such a
if ((msg = s->onEvent(this, msg)) == 0) { /*processed?*/
substate becomes active it behaves in
if (next) { /* state transition taken? */
exactly the same way as its superstate,
for (s = next, trace = entryPath, *trace = 0;
that is, it inherits the superstate’s entire
s != curr; s = s->super)
behavior. This is analogous to a sub-
*(++trace) = s; /* trace path to target */
class which does not introduce any
while (s = *trace ) /* retrace entry from LCA */
new attributes or methods. An
s->onEvent(this, &entryMsg);
instance of such a subclass is indistin-
curr = next;
guishable from its superclass because,
next = 0;
again, everything is inherited exactly.
while (curr->onEvent(this, &startMsg), next) {
This property of HSMs is funda-
for (s = next->super, trace = entryPath, *trace=0;
mental because it requires only the
s != curr; s = s->super)
differences from the superstate’s behav-
*(++trace) = s; /* record path to target */
ior to be defined. One observes that
while (s = *trace ) /* retrace the entry */
all OO design principles (for example,
s->onEvent(this, &entryMsg);
the Liskov Substitution Principle)
curr = next;
hold in HSM designs because one
next = 0;
deals with inheritance in yet another
}
form. The concept of behavioral
}
inheritance describes the “is-a” (“is-
in”) relationship between substates

34 AUGUST 2000 Embedded Systems Programming

hsm

and superstates and should not be and finalization is similar to entering of invocation of these methods is the
confused with inheritance of entire and exiting a state. In both cases spe- same: constructors are invoked start-
state models.3 cial methods are invoked: constructors ing from most remote ancestor classes
The analogy between SOP and and destructors for objects, entry and (destructors are invoked in reverse
OOP goes further. Class instantiation exit actions for states. Even the order order), and entry actions are invoked
starting from the topmost superstate
(exit actions are invoked in reverse
LISTING 2b, cont’d. hsm.cpp—C++ implementation order).
A final similarity between OOP
break; /* event processed */ and SOP lies in the way they are most
} efficiently implemented. Although
} polymorphism can be implemented
} in many ways, virtually all C++ com-
/* exit current states and all superstates up to LCA */ pilers implement it in the same way:
void Hsm::exit_(unsigned char toLca) { by using function pointers grouped
register State *s; into virtual tables. In view of the
for (s = curr; toLca > 0; toLca, s = s->super) deep analogy between SOP and OOP,
s->onEvent(this, &exitMsg); it is therefore not surprising that
curr = s; arguably the most efficient imple-
} mentation of HSMs is also based on
/* find # of levels to Least Common Ancestor */ function pointers grouped into
unsigned char Hsm::toLCA_(State *target) { states. These simple state objects
State *s, *t; define both behavior and hierarchy
unsigned char toLca = 1; but are not specific to any particular
for (s = curr->super; s != 0; ++toLca, s = s->super) instance of a state machine. The
for (t = target; t != 0; t = t->super) same holds for virtual functions,
if (s == t) which are characteristics of the
return toLca; whole class rather than specific to
return 0; any particular object instance. For
} this reason we observe that state
objects could (and probably should)
be placed in v-tables and be support-
ed as a native language feature.
FIGURE 4 Structure of real-time framework based on HSM
Improvments to UML?
UML state diagrams do not provide
void Actor: :run() {
onStart (); any graphical representation of state
for (;;) { reactions, which are reactions to
Msg *msg =–>mesgQ–>get();
Hsm onEvent(msg);
events not causing state transitions. In
} practice however, reactions are com-
} mon and sometimes the whole state
Actor void ActorRun(Actor *me) { hierarchy is most naturally designed to
msgQ HsmOnStart((Hsm *) me); reuse group reactions rather than
taskId for (;;) {
group transitions. In these cases a
Msg *msg = MsgQget(me–>msgQ);
run() HsmOnEvent((Hsm *)me, msg); UML state diagram cannot be proper-
} ly understood because it is simply
}
incomplete.
We propose to include reactions in
state diagrams as directed lines start-
ConcreteActorA ConcreteActorB
ing and finishing in the same state and
stateA stateA
stateB stateB
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 nota-

36 AUGUST 2000 Embedded Systems Programming

hsm

LISTING 3a Simple watch HSM: C implementation tion is different from self-transitions,

which also begin and end in the same
#include “hsm.h” state, but lie entirely outside the state.
Self-transitions are different from
typedef struct Watch Watch; reactions because they cause execu-
struct Watch { tion of entry and exit actions.
Hsm super; /* superclass */ UML statecharts distinguish com-
int tsec, tmin, thour, dday, dmonth; posite-states (states with substates)
State timekeeping, time, date; from leaf-states (states without sub-
State setting, hour, minute, day, month; states) in that they only allow leaf-
State *tkeepingHist; states to be active. This is an unneces-
}; sary limitation, which occasionally cre-
ates degenerate (empty) substates. To
enum WatchEvents { extend the analogy with OOP, this is
MODE_EVT, like saying that a class with subclasses
SET_EVT, must necessarily be abstract. Our HSM
TICK_EVT implementation does not distinguish
}; between composite and leaf states; it
/* timekeeping state handler */ allows any state to be active.
Msg const *WatchTimekeepingHndlr(Msg const *msg) { In our experience with receiver-
switch (MsgGetEvt(msg)) { applications we frequently encoun-
case START_EVT: tered the following situation: in
STATE_ENTER(me->tkeepingHist ? me->tkeepingHist : response to a given event, we wished
&me->time); to perform an action (for example,
return 0; update a digital filter) and then—
case SET_EVT: depending on the state of the fil-
STATE_TRAN(&me->setting); ter—potentially take a (conditional)
printf(“Watch::timekeeping-SET;”); state transition. We did not want to
return 0; treat the filter update as part of the
case TICK_EVT: guard condition because this would
WatchTimeTick(me); add a side effect to the guard (typi-
return 0 cally a bad idea11). The only alterna-
case EXIT_EVT: tive is to treat the filter update as an
me->tkeepingHist = STATE_CURR(me); action.
return 0; UML requires that actions associ-
} ated with transitions be executed
return msg; after all exit-actions from the source
} state but before any entry-actions to
/*... other state handlerds ... */ the target state.11 At this point how-
/* Watch constructor */ ever, it is not yet know if the transi-
void WatchCtor(Watch *me) { tion will be required at all. In gener-
HsmCtor((Hsm *)me, “Watch”, (EvtHndlr)Watch_top); al, this aspect of UML semantics
StateCtor(&me->timekeeping, “timekeeping”, makes it difficult to mix conditional
&((Hsm *)me)->top, (EvtHndlr)Watch_timekeeping); execution of reactions and transi-
StateCtor(&me->time, “time”, &me->timekeeping, tions. A UML-compliant solution
(EvtHndlr)Watch_time); would require specification of a pure
StateCtor(&me->date, “date”, &me->timekeeping, reaction (update of the digital filter
(EvtHndlr)Watch_date); in this case) and then conditional
StateCtor(&me->setting, “setting”, &((Hsm *)me)->top, propagation of another event to “self,”
(EvtHndlr)Watch_setting); specifically to trigger a pure state
StateCtor(&me->hour, “hour”, &me->setting, transition.
(EvtHndlr)Watch_hour); Because our implementation per-
forms state transitions using the

38 AUGUST 2000 Embedded Systems Programming

hsm

LISTING 3a, cont’d. Simple watch HSM: C implementation STATE_TRAN() macro, which causes
execution of all exit-actions up to least
StateCtor(&me->minute, “minute”, &me->setting, common ancestor, the order of execu-
(EvtHndlr)Watch_minute); tion is left to the designer. The UML-
StateCtor(&me->day, “day”, &me->setting, compliant implementation requires
(EvtHndlr)Watch_day); invoking the STATE_TRAN() macro
StateCtor(&me->month, “month”, &me->setting, before other actions associated with the
(EvtHndlr)Watch_month); transition. With our approach, the
me->tsec = me->tmin = me->thour = 0; designer may choose a different order
me->dday = me->dmonth = 1; (for example, reaction-guard-transi-
me->timekeepingHist = NULL; tion), if it would simplify the problem
} at hand.
A final (proposed) extension to
void main() { /* test harness */ UML statecharts is associated with
Watch watch; event handling at different levels of
WatchCtor(&watch); a hierarchical state machine. UML
HsmOnStart((Hsm *)&watch); statecharts require that the same
for (;;) { event be presented for processing to
Msg *msg = getEvt(); /* block until event arrives */ all levels of the hierarchy, starting
HsmOnEvent((Hsm *)&watch, msg); with the active state. We propose to
} allow an event to change as it propa-
} gates upward through the state hier-
archy. In our implementation this is
simple to achieve. This feature
would facilitate “throwing” an excep-
LISTING 3b Simple watch HSM: C++ implementation tion to a higher scope, which could
in turn either handle or “throw” it
#include “hsm.h” again. Because outer states of an
HSM are typically behavioral gener-
class Watch : public Hsm { alizations of inner states, this tech-
int tsec, tmin, thour, dday, dmonth; nique for handling exceptions is nat-
timeTick(); /* process tick event in the ‘time’ state */ ural and arguably, makes more sense
protected: than the traditional exception han-
State timekeeping, time, date; dling technique of unwinding the
State setting, hour, minute, day, month; call stack.
State *tkeepingHist; /* to record history */
Msg const *topHndlr(Msg const *msg); The benefits
Msg const *timekeepingHndlr(Msg const *msg); The HSM design pattern allows hier-
Msg const *settingHndlr(Msg const *msg); archical state machines to be direct-
Msg const *hourHndlr(Msg const *msg); ly and efficiently implemented in C
/*... other state handler methods */ or C++ without code synthesizing
public: tools. The event-handler methods
Watch(); /* ctor for defining state hierarchy */ provide a concise textual representa-
}; tion of the state model and allow
high-level structure and low-level
enum WatchEvents { details to be accessed easily. The sim-
MODE_EVT, plicity of the event-handlers leads to
SET_EVT, “housekeeping” code3—portions of
TICK_EVT software that can be automatically
}; generated by tools—that is trivial to
write by hand.
The HSM pattern is flexible,
allowing even fundamental changes

40 AUGUST 2000 Embedded Systems Programming

hsm

in state machine topology to be

LISTING 3b, cont’d. Simple watch HSM: C++ implementation accomplished easily, even late in the
process. Due to their hierarchical
/* timekeeping state handler */ nature, models can be developed in
Msg const *Watch::timekeepingHndlr(Msg const *msg) { incremental steps and remain exe-
switch (msg->getEvt()) { cutable throughout the develop-
case START_EVT: ment cycle. By requiring only spe-
STATE_ENTER(tkeepingHist ? tkeepingHist : &time); cialization of behavior to be coded
return 0; at nested levels of the state machine,
case SET_EVT: common policy mechanisms (for
STATE_TRAN(&setting); example, exception handling) can
printf(“Watch::timekeeping-SET;”); be handled naturally. The state
return 0; machine engine can easily be instru-
case TICK_EVT: mented (an example is available in
timeTick(); code accompanying this article at
return 0 www.embedded.com/code.html) to pro-
case EXIT_EVT: duce execution trace, message
tkeepingHist = STATE_CURR(); sequence charts, or even animated
return 0; state diagrams. In practice, however,
} we found it most useful to use a stan-
return msg; dard debugger to step through
} interesting parts of the code.
/*... other state handlerds ... */ This implementation of the HSM
/* Watch ctor */ pattern is no more complex than an
Watch::Watch() internal implementation of inheri-
: Hsm(“Watch”, (EvtHndlr)topHndlr), tance or polymorphism in C++ and,
timekeeping(“timekeeping”, &top, in fact, has many similarities (both
(EvtHndlr)timekeepingHndlr), are based on function pointers).
time(“time”, &timekeeping, (EvtHndlr)timeHndlr), Given the many parallels, it seems
date(“date”, &timekeeping, (EvtHndlr)dateHndlr), reasonable to suggest that state-ori-
ented programming should be
setting(“setting”, &top, (EvtHndlr)settingHndlr), directly supported by a (state-orient-
hour(“hour”, &setting, (EvtHndlr)hourHndlr), ed) programming language in the
minute(“minute”, &setting, (EvtHndlr)minuteHndlr), same way that OOP is supported by
day(“day”, &setting, (EvtHndlr)dayHndlr), object-oriented languages. We see
month(“month”, &setting, (EvtHndlr)monthHndlr) this as beneficial for a couple of rea-
{ sons. First, the compiler could place
tsec = tmin = thour = 0; state objects in a virtual table and
dday = dmonth = 1; perform memory and performance
tkeepingHist = NULL; optimizations at compile time (for
} example, computation of LCAs for
/* test harness */ state transitions). Second, the com-
void main() { piler could check consistency and
Watch watch; well-formedness of the state
watch.onStart(); machine, thereby eliminating many
for (;;) { errors at compile time. In our view
Msg *msg = getEvt(); /* block until event arrives */ this is one direction in which C/C++
watch.onEvent(msg); could evolve to better support future
} real-time applications. esp
}

Miro Samek is lead software architect at

IntegriNautics Corp. He holds a PhD in

42 AUGUST 2000 Embedded Systems Programming

 hsm
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
miro@integrinautics.com.

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
paulm@integrinautics.com.

Resources
1. Bell, Rodney, “Code Generation form
Object Models,” Embedded Systems
Programming, March 1998, p. 74.
2. Samek, Miro, “Portable Inheritance and
Polymorphism in C,” Embedded Systems
Programming, December 1997, p. 54.
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.
5. www.i-logix.com
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.
8. www.omg.org/docs/97-96-02.pdf, UML
1.1 Alpha—Behavioral Elements: State
Machines.
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.

Embedded Systems Programming AUGUST 2000 43