11.1. Finite State Machines

Every software engineer should be familiar with finite state machines (FSMs). The concept is so useful that you could expect to find it almost anywhere, from hardware device controllers to pattern-matching and parsing engines such as the one used by YACC. Developers of such diverse applications have embraced the use of FSMs because they make it possible to transform a tangled web of complex program logic into a comprehensible expression of well-understood formalism. We can credit this power to two things: the fundamental simplicity of the FSM abstraction and its declarative form.

Few general-purpose languages have built-in support for constructing FSMs, and C++ is no exception. If they aren't a regular part of every C++ programmer's vocabulary, maybe it's just for want of a tool that makes them as easy and fun to build as they should be. In this chapter we aim to design and build just such a tool: a finite state machine construction framework.

11.1.1. The Domain Abstraction

The domain abstraction of finite state machines consists of three simple elements.

States

An FSM must always be in one of several well-defined states. For example, the states of a simple CD player might be called Open, Empty, Stopped (with a CD in the drawer), Paused, and Playing. The only persistent data associated with a pure FSM is encoded in its state, though FSMs are seldom used alone in any system. For example, the parsers generated by YACC are built around a stack of state machines; the state of the whole system includes that of the stack and of each FSM in the stack.

Events

State changes are triggered by events. In our CD player example, most events would correspond to button presses on its front panel: play, stop, pause, and open/close (the button that opens and closes the drawer). Events aren't necessarily "pushed" into a state machine from the outside, though. For example, in YACC parsers, each event represents a different token, and is "pulled" from the input stream by the parsing process. In some systems, events contain associated data. For instance, an identifier token in a C++ parser might carry the text of the identifier, while an integer-literal token might carry the value of the integer.

Transitions

Each state can have any number of transitions to other states. Each transition is labeled with an event. To process an event, the FSM follows the transition that starts from the current state and is marked with that event. For example, a CD player has a transition from Playing to Stopped labeled with the stop event. Usually, transitions also have some associated action, such as stop playback in the case of our CD player. In the case of YACC, following transitions means manipulating the stack of FMSs and/or executing the user's semantic actions.

11.1.2. Notations

There are several common ways to describe a state machine on paper, but perhaps the most user-friendly notation is a graphical one. Figure 11.1 represents the CD player we've been using as an example. In the picture, states are shown as circles and transitions are shown as arrows, labeled with the events that trigger them.

Note the transition from Empty to Stopped. Remember that we said not all events need to be "pushed" on the system from the outside? To model real CD players, the FSM will begin a CD detection process when the drawer is closed; when it detects a CD in the drawer, the system sends itself a cd-detected event. To make this work, the transition from Open to Empty must have an associated action that begins the CD detection process. When a new disc is detected, most CD players collect information about the number of tracks and the total playing time of each one; our cd-detected event should contain that information so that the transition's action can store it somewhere and show the number of tracks on the player's front panel.

The graphical representation shows everything that can happen in an FSM at a glance, with no wasted syntactic elements. One popular strategy for FSM construction, in fact, is to draw the state machine using a graphical user interface with a code-generating back end. If only C++ allowed pictures in its input syntaxthey could be a perfect DSEL notation!

Since C++ can't parse pictures, we're going to use a different notation called a State Transition Table (STT), which is essentially just a vertical list of the FSM's transitions. Table 11.1 shows the STT for the CD player.

Table 11.1. CD Player State Transition Table

Current State	Event	Next State	Transition Action
Stopped	play	Playing	start playback
Stopped	open/close	Open	open drawer
Open	open/close	Empty	close drawer; collect CD information
Empty	open/close	Open	open drawer
Empty	cd-detected	Stopped	store CD information
Playing	stop	Stopped	stop playback
Playing	pause	Paused	pause playback
Playing	open/close	Open	stop playback; open drawer
Paused	play	Playing	resume playback
Paused	stop	Stopped	stop playback
Paused	open/close	Open	stop playback; open drawer

Although the structure of the FSM is less apparent than it was in the graphical form, it's still fairly easy to follow. To process an event, the state machine finds a row that contains its current state in the first column and the event in the second column; the third and fourth columns of that row indicate the new state and the action to take upon making the transition. Note that while we left transition actions out of the FSM's graphical representation to minimize clutter, in the STT they cause little or no interference.