A Novel C++ Implementation of State Machines

R. J. Brown -- Elijah Laboratories Inc.

Finite state machines, or just "state machines" for brevity, are an important concept in the design of systems. Together with dataflow diagrams and entity relationship diagrams, state machines, represented by a state transition graph, sometimes called a state transition diagram, or just a state graph, describe how a given node in a dataflow diagram is to behave. The arrival of events on incoming dataflows causes a deterministic behaviour of that node. This behaviour can be described by a state machine.

In this implementation, an active instance of a state machine is a session traversing a state graph. A state machine is created by injecting a session into a state of a state graph. A state machine proceeds by responding to events. Events are messages passed by function call. Every session object has a virtual member function corresponding to every possible event in the state graph's domain.

Each session coresponds to a thread of execution. Since all local state is kept in the session object, there can be multiple sessions all traversing the same state transition graph concurrently. Each event happens in the context of a given session, and is signalled by a function call that is the equivalent of a message being passed to the session telling it to change state. Since these functions are member functions, or methods, of the session object, then the name of the event is the name of the member function, and the session it happened in is the name of the session object.

Each such method of a session has a set of 3 corresponding methods of the state object in the state transition graph which that session is presently traversing. These methods are the guard, the exit action, and the next state. If any special handling of the event at the session level is required, this must be done in the session's code, after the guard, and before the exit action.

The guard is used to determine whether the sesion should change state at all or not as a result of this event (see the comments in session.H). The session is responsible for any session-unique processing that might be required, the exit action is the common processing required of all sessions whenever they exit this present state in the state graph, and the next state determines what state that session must now transit to, and causes that transition to occur.

Since each event is a function call to a method of the session, all possible events must have corresponding methods in the session object. Since the session hands off most of the work to the current state object in the state graph that it is traversing, the all states must have methods for all events. This acts as a safety net by forcing the code to be able to handle every possible event in any given state. It is a common programming error to not provide an event handler for some event in a particular state because it is not expected for that event to occur in that state. If that event does occur in that state, then the program behaves incorrectly, and may even crash.

Furthermore, since event notification is in the form of a function call, full type checking of function signatures is performed by the C++ compiler, and the overhead to process an event is minimal, requiring no potentially lengthy table lookup operations, and permitting the optimization capabilities of the compiler to be fully utilized, even to the extent that some events could potentially be compiled as inline code and avoid the function call altogether, provided the compiler is smart enough.

This code, using the main() in the file rs_ff.C, implements a state machine that emulates an RS flip-flop. This is intended to serve as a demonstration and example of how to implement your own custom state machines using the same approach. To the extent that it is a concrete instance from which the general abstract concept is to be elucidated, it truly constitutes a paradigm for this style of implementation of state machines.

Source FilesInclude files
mytypes.Cmytypes.H
rs_ff.C 
rs_ff_session.Crs_ff_session.H
rs_ff_state.Crs_ff_state.H
 session.H
  state.H

Elijah Laboratories Inc. logo Elijah Laboratories Inc. logo

© 2002 Elijah Laboratories Inc.
ALL RIGHTS RESERVED WORLDWIDE.

Web page design by Robert J. Brown.
Last modified: Sat May 3 00:55:19 CDT 2003

Signature