Basic Finite State Machines
The main challenge in programming event-driven systems, such as Active Objects, is to identify the appropriate actions to execute in response to a given event. In general, the actions are determined by two factors: by the nature of the event and by the current context (i.e., by the sequence of past events in which the system was involved).
The traditional techniques, such as the event-action paradigm, handle the context manually by storing the history of past events in a multitude of variables and flags. But this results in code riddled with a disproportionate amount of convoluted conditional logic that programmers call “spaghetti” code.
Techniques based on state machines are capable of achieving a dramatic reduction of the different paths through the code and simplification of the conditions tested at each branching point. A state machine makes the event handling explicitly dependent on both the nature of the event and on the context (state) of the system.
States are equivalence classes of past histories of a system, all of which are equivalent in the sense that the future behavior of the system given any of these past histories will be identical. Thus the concept of “State” is the most efficient representation of the relevant history of the system. It is the minimum information that captures only the relevant aspects for the future behavior and abstracts away all irrelevant aspects.
The concept of “State” naturally leads to the concept of State Machine, which is the set of all states, that is equivalence classes of relevant histories, plus the rules for changing from one state to another. These rules are called transitions and capture the fact that some events contribute to the relevant history while others do not. Those events influencing the future behavior trigger the state transitions.
Hierarchical State Machines
Hierarchical state machines (a.k.a. statecharts) are an advanced formalism for specifying state machines, which extends the traditional automata theory in several ways.
The most important innovation of UML state machines over classical FSMs is the introduction of hierarchically nested states. The value of state nesting lies in avoiding repetitions, which are inevitable in the traditional “flat” FSM formalism. The semantics of state nesting allow substates to define only the differences in behavior from the superstates, thus promoting sharing and reuse of behavior.
Hierarchical state machines support state entry and exit actions for states, which provide the means for guaranteed initialization and cleanup, very much as constructors and destructors do for classes. Entry actions are always executed starting with the outermost state, which is analogous to class constructors executed from the most general class. The exit actions, similar to destructors, are always executed in exact reverse order. Entry and exit actions combined with state nesting complicate transition sequence.
The Importance of an Event-Driven Framework
State machines can be an incredibly powerful technique, but they require an infrastructure (framework) that at a minimum provides: a run-to-completion (RTC) execution context for each state machine, queuing of events, and event-based timing services. This is really the pivotal point: Without an event-driven infrastructure, such as a Real-Time Embedded Framework, state machines are like cars without an infrastructure of roads and gas stations.
The relationship between an event-driven framework and state machines is mutually synergistic. On one hand, the framework provides the thread context and event queuing that the state machines need to process the events in a run-to-completion fashion. On the other hand, state machines provide the structure and clear design for the event-driven behavior running inside the framework. State machines are also the most constructive part of the design amenable to modeling and automatic code generation.
Hierarchical State Machines are a deep subject and this post is only an introduction. State hierarchy is very much like inheritance and therefore it comes with its own design patterns and idioms. Hierarchical State Machines offer similarly rich semantics and just as many various aspects that are worth learning. Here are some recommended resoures: