Chapter 51. State Machine

Model a system as a set of explicit states with transitions between them.

Many systems react to stimuli differently, depending on some internal property. Sometimes it’s useful to classify these different internal states and describe both the differences in response and what causes the system to move between these states. A State Machine can be used to describe and perhaps to control this behavior.

51.1 How It Works

State Machines are a common thing to find both in software and in discussions about software—which is why I used a State Machine in the opening example for this book. The degree to which a State Machine is used varies with the situation, as does the form of State Machine in use.

To explore this, I’ll use a different example, one that is less clear-cut than the one in the Introduction. Let’s consider an order processing system. Once I’ve created an order, I can freely add or remove items in that order, or cancel it. At some point, I have to provide payment for the order. Once I’ve paid for it, the order is eligible to be shipped, but before that I can still add or remove items or cancel the order. Once it’s shipped, I can’t do any of that.

I can describe this order using the state transition diagram of Figure 51.1.

Figure 51.1 UML state machine diagram for an order

At this point, I need to address the meaning of “state.” In general use, we often refer to the state of an object as the combination of the values of its properties. In this reading, removing an item from an order changes its state. However, the state machine diagram doesn’t reflect all these possible states; instead, it only shows a few states. These are the states that are interesting in terms of the model, in that they affect the behavior of the system. I’ll refer to this smaller set of states as machine states. So, while removing an item changes the state of the order, it doesn’t change its machine state.

This state model is a useful way of thinking about the behavior of the order, but this doesn’t mean that we want a state machine model in our software. The model can help us understand that we need a check on the cancel method to verify that we are in the appropriate state. But this can simply be a guard clause in the cancel method.

Similarly, tracking what machine state the order is in could be a status field on the order, but it could also be completely derived. You could determine if you are in the paid state by checking if the payment authorization amount is greater than or equal to the overall cost of the order. The diagram may still be a useful way to visualize how the order works, but you don’t need the model to be manifest in the software.

State Machines, like other alternative computational models, come in several varieties which share many common elements but with notable differences. I’ll start with the common elements. The essence of a State Machine is that it has a notion of multiple states that the machine can be in. We can then define multiple transitions on each state, where each transition is triggered by an event and causes the machine to move to a target state. This target state is often, but not necessarily, a different state. The resulting behavior of the machine is the definition of the states and the events that trigger the movement between states.

Figure 51.1 shows a diagrammatic representation of such a network. The collecting state has four transitions defined on it. These say that if the machine, when in that state, receives a cancel event, it moves to the cancelled state. A paid event leads to the paid state, the add item and remove item events both lead back to the collecting state. The add item and remove item events are separate transitions, even though they go to the same target.

A general question with state machines is how they react to an event that isn’t defined on the state that the machine is currently in. Depending on the application, such an event may be an error, or it may be safely ignored.

Figure 51.1 also introduces another notion, that of a guarded transition. When in the paid state, if the machine gets an add item event, it takes a different transition depending on whether there’s enough money or not. The Boolean conditions on the transitions should not overlap, otherwise the state machine won’t know where to go. Guarded transitions don’t have to appear on all State Machines; indeed the introductory example doesn’t have them.

Figure 51.1 describes several machine states and the events that cause the machine to move between them, but it is still a passive model as it does not invoke any actions that cause changes to the system. To have an Adaptive Model with a State Machine, we need a way to bind actions into the machine. Over the years, several schemes have come up to do this. There are two places you can sensibly bind actions to: the transitions or the states. Binding an action to a transition means that the action is executed whenever the transition is taken. Binding an action to a state most commonly means that the action is invoked when you enter the state. But you can also see actions bound to exits from a state too. Some machines allow internal actions that are invoked when an event is received in that state—like a transition back to itself, but perhaps without triggering any entry actions again.

Different action-binding approaches suit different problems and different personalities. I don’t have any strong guidelines to offer, other than to keep it as simple as it can reasonably be to model your behavior. Many implementations of state machine techniques have gone for the maximum expressiveness of the machine—such as the very expressive state machine models used by the UML. But small state machines suitable for DSLs can often work well with much simpler models.

51.2 When to Use It

I have that horrible feeling when I know that almost the only thing I can say is that you should use a State Machine when the behavior you’re specifying feels like a State Machine—that is, when you have a sense of movement, triggered by events, from state to state. In many ways, the best way to see if a State Machine is appropriate is to try sketching one on paper and, if it fits well, to try it in action.

There is one danger area where the smidgeon of language theory I gave earlier (“Regular, Context-Free, and Context-Sensitive Grammars,” p. 96) can be helpful. Remember that State Machines are limited to parsing regular grammars, meaning they can’t handle matching arbitrarily nested parentheses. If your behavior has anything like that, you may run into the same problem.

51.3 Secret Panel Controller (Java)

In many places in this book, starting with the Introduction, I’ve used a simple state machine as an example. For all the cases where I’ve mentioned it, I’ve used a single Semantic Model, which I describe in the Introduction. The state behavior doesn’t do guarded transitions and binds very simple actions to state entry. The actions are simple, in that they don’t involve executing an arbitrary code block but only sending a numeric code message. This simplifies the state machine model and the DSLs to control it (which is very important for an example like this).