After we have discovered the implementation of state machines by means of switch statement and table, let's take a look at an object-oriented implementation variant: the State pattern. We will then compare the three variants.
The State software design pattern is implemented by Spring Statemachine, Boost Meta State Machine (MSM) or the Qt State Machine Framework. The State pattern belongs to the group of behavioural design patterns, and encapsulates the state-dependent behavior of an object as seen from the outside. Each state is implemented as a separate class that defines the behaviour of the machine in that state. All state classes are derived from a common interface, so that all states can be treated uniformly.
The class diagram of the blind control system is as follows:
The interface State defines the methods whose behavior is state-dependent. In addition to the methods starting with raise… to trigger an event, there is the method getName, which returns the name of the state.
The StateMachine class represents the state machine. In the attribute activeState it manages the class corresponding to the active state, and thus the state-specific behaviour. The State pattern is similar to the Strategy pattern: a state corresponds to a strategy, i.e. the implementation of a concrete behaviour. However, while the strategy in the Strategy pattern is set from the outside, the states in the State pattern take care of this themselves. In the state pattern, if you like, a "strategy" replaces itself with another – or in the correct nomenclature: a state activates its subsequent state on its own.
Let's take a closer look at the example. The client application sends messages to the state machine by calling StateMachine methods. Let's say the user presses the [↓] key. The client informs the state machine about this action by calling the raiseUserDown method. The response of the machine depends on the active state:
- In the Moving up state, the machine changes to the Idle state.
- In the Idle state, the machine switches to the Moving down state.
- In the Moving down state, the automaton ignores the event.
StateMachine therefore delegates the call to the corresponding method of the active state object. The StateMachine method raiseUserDown calls the same-named method of activeState:
public void raiseUserDown() {
activeState.raiseUserDown();
}
What happens next is at the discretion of the state object. If it is an object of class Idle, a transition to Moving down occurs. This is what raiseUserDown looks like in Idle:
public void raiseUserDown() {
stateMachine.activateState(new MovingDown(stateMachine));
}
The method activates the new state by passing a corresponding state object to the StateMachine method activateState, which assigns it to the activeState field.
If, on the other hand, the machine is in the Moving down state, nothing should be done when raiseUserDown is called. The MovingDown class therefore does not implement this method at all. Instead, the raiseUserDown implementation of superclass AbstractState is called:
public void raiseUserDown() {
}
This method does nothing and thus ignores the event – in our case, a meaningful default behaviour for all events for which the particular concrete state class does not implement any behaviour.
Source code of the example application
Let's look at the source code of the blind control system in an implementation based on the State pattern. The state machine consists of six classes, as well as a client class that uses the machine.
The interface State specifies what is a state in the example application:
package de.itemis.state_machine.example.state_pattern;
public interface State {
public void raiseUserUp();
public void raiseUserDown();
public void raisePosSensorUpperPosition();
public void raisePosSensorLowerPosition();
public String getName();
}
The AbstractState abstract class implements the reference to the StateMachine and the default behaviour for events, ignoring it:
package de.itemis.state_machine.example.state_pattern;
abstract public class AbstractState implements State {
protected StateMachine stateMachine;
public AbstractState(StateMachine stateMachine) {
this.stateMachine = stateMachine;
}
public void raiseUserUp() {
}
public void raiseUserDown() {
}
public void raisePosSensorUpperPosition() {
}
public void raisePosSensorLowerPosition() {
}
abstract public String getName();
}
The classes Idle, MovingUp and MovingDown represent the three concrete states:
package de.itemis.state_machine.example.state_pattern;
public class Idle extends AbstractState {
public Idle(StateMachine stateMachine) {
super(stateMachine);
}
@Override
public void raiseUserUp() {
stateMachine.activateState(new MovingUp(stateMachine));
}
@Override
public void raiseUserDown() {
stateMachine.activateState(new MovingDown(stateMachine));
}
@Override
public String getName() {
return "Idle";
}
}
package de.itemis.state_machine.example.state_pattern;
public class MovingUp extends AbstractState {
public MovingUp(StateMachine stateMachine) {
super(stateMachine);
}
@Override
public void raiseUserDown() {
stateMachine.activateState(new Idle(stateMachine));
}
@Override
public void raisePosSensorUpperPosition() {
stateMachine.activateState(new Idle(stateMachine));
}
@Override
public String getName() {
return "Moving up";
}
}
package de.itemis.state_machine.example.state_pattern;
public class MovingDown extends AbstractState {
public MovingDown(StateMachine stateMachine) {
super(stateMachine);
}
@Override
public void raiseUserUp() {
stateMachine.activateState(new Idle(stateMachine));
}
@Override
public void raisePosSensorLowerPosition() {
stateMachine.activateState(new Idle(stateMachine));
}
@Override
public String getName() {
return "Moving down";
}
}
The StateMachine class is the "face" of the state machine that is shown to the outside:
package de.itemis.state_machine.example.state_pattern;
public class StateMachine {
public StateMachine() {
activateState(new Idle(this));
}
State activeState = null;
public void activateState(State state) {
activeState = state;
}
public State getActiveState() {
return activeState;
}
public void raiseUserUp() {
activeState.raiseUserUp();
}
public void raiseUserDown() {
activeState.raiseUserDown();
}
public void raisePosSensorUpperPosition() {
activeState.raisePosSensorUpperPosition();
}
public void raisePosSensorLowerPosition() {
activeState.raisePosSensorLowerPosition();
}
}
The state machine is used by the application code like this:
package de.itemis.state_machine.example.state_pattern;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Example {
public static void main(String[] args) throws IOException {
StateMachine stateMachine = new StateMachine();
stateMachine.activateState(new Idle(stateMachine));
BufferedReader console = new BufferedReader(new InputStreamReader(System.in));
while (true) {
System.out.println("Active state: " + stateMachine.getActiveState().getName());
System.out.print("Please enter event number! ");
System.out.print("1: User.up, 2: User.down, 3: PosSensor.upperPosition, ");
System.out.println("4: PosSensor.lowerPosition");
String line = console.readLine();
int eventNr = -1;
try {
eventNr = Integer.parseInt(line);
} catch (NumberFormatException ex) {
eventNr = -1;
}
switch (eventNr) {
case 1:
stateMachine.raiseUserUp();
break;
case 2:
stateMachine.raiseUserDown();
break;
case 3:
stateMachine.raisePosSensorUpperPosition();
break;
case 4:
stateMachine.raisePosSensorLowerPosition();
break;
default:
System.out.println("Unknown event number: " + eventNr + ".");
break;
}
}
}
}
By the way, an object-oriented programming language is not necessarily required for the State pattern. It can also be implemented with an imperative language such as C as long as the language supports function pointers. The core of the State pattern is that the active state reacts to events and activates another state, if needed.
In a C implementation each state is associated with a function (the "state function") that implements the relevant actions. The state machine memorizes the active state by a pointer to its state function. This returns a pointer to the next state or more precisely: to the latter’s state function.
Which implementation approach is best?
For "real" computers such as notebooks, desktops or servers, the differences between implementations do not really matter. The situation is different for embedded devices, which are typically very limited in memory or CPU performance. The clear answer of which implementation is best is – it depends.
State machines are very fast. In a state machine with few states and few events, optimization considerations are hardly worthwhile. The situation is different with a large number of states or events. At this point, however, we won’t ponder what exactly a ”large“ number is – 500?, 50,000?, 5 million? –, but look at a few basic considerations only.
A large number of states means that:
- The switch statement contains many cases.
- The (one-dimensional) state transition table becomes very tall.
- The state pattern requires many state classes.
If the number of events is large, this means that:
- Within the individual case clauses in the switch statement there is a lot to do, depending on the respective state.
- The state transition table becomes very wide.
- In the State pattern the individual state classes are quite extensive, depending on the respective state.
In all implementation scenarios, the execution time is composed of the following elements:
- Searching for the active state
- Searching for a transition based on the event(s)
- Activating the subsequent state
In addition, guard conditions and actions have their respective execution times. Since these are highly application-specific, however, we will not consider them further here. The activation of the subsequent state consists in each case of a simple assignment: we can ignore its time and memory requirements.
Execution time requirements
To find the active state, the switch statement performs at least one comparison, the situation in which the first case clause of the switch statement is the active state. At worst, the switch statement requires as many comparisons as there are states, i.e. if the last case clause corresponds to the active state. If all states are active equally frequently, the switch statement performs on average z/2 comparisons, where z is the number of states. The execution time is thus of the order of magnitude O(z). This is followed by the analysis of whether specific events are present. This would trigger the corresponding transitions. The execution time for this is – with a similar consideration as for the states – of the order of magnitude O(e), where e is the number of event types.
The execution time requirement for the lookup operation in a one-dimensional state transition table is also O(z) + O(e). The first term describes the row-by-row searching for the active state, the second term represents the search for a given event within the row. If there are several transitions from the active state to different subsequent states, then several rows usually have to be searched. However, this does not change the order of magnitude.
The object-oriented approach wins out here, with a time requirement that is independent of the number of states. Since the active state is already present as an object, the time requirement for "searching" the active state is of the order of magnitude O(1). Then there’s the method call corresponding to the event. At first glance this may also look like O(1), but the effort is likely to be conservatively estimated at O(e), depending on the programming language and its runtime environment.
Memory requirements
Switch statement as well as state transition table must include all combinations of state and event, either in the program code of the switch statement or in the table data. The memory requirement is therefore of the order of magnitude O(z · e) in both cases. However, the table always occupies this memory space to its full extent, even if it is sparsely populated. The switch statement, on the other hand, only needs to encode those state/event combinations for which an event leads to a transition. On the other hand, a function pointer in the table occupies only the memory size of an address, which in general should be less than the code that a single state/event combination occupies on average.
In the State pattern each state class contains a method for each event that the respective state must take into account. Thus we also have an order of magnitude is also O(z · e). As with the switch statement, however, only those event methods have to be coded that should affect something other than the general behaviour implemented in the abstract upper class. Only these methods require space for their program code.
ROM or RAM memory
It is important to consider the devices on which a state machine is to run. Object-oriented languages typically require a large runtime environment and more RAM. This can limit or prevent their use on embedded devices. The more program parts can be fitted into immutable ROM, the better. Executable code, as in the switch statement, falls into this category, as well as hard-coded state transition tables. In an object-oriented implementation of the State pattern you should reuse static state objects, rather than always dynamically creating new objects in RAM.
Debugging capability
It is also important to know how easily a statechart application can be debugged during development. A developer needs to be able to set breakpoints at specific points in the application to halt execution there and continue it step by step, to analyze why the application does not behave as expected. In a state class this is quite simple. Switch statements are also suitable. For tables, the developer can only set breakpoints in the functions to which the function pointers in the table refer. If these pointers are in the wrong cells, however, the analysis is tricky.
Clarity and maintainability
Generally the code of state machines is neither intuitive nor comprehensible. In this respect the State pattern is best, because it avoids a confusing and difficult-to-read switch statement. As long as a state does not have to handle too many different events, it remains manageable. New states require only new state classes; a change in the behaviour is limited to a change in the affected states. This reduces maintenance effort.
In the case of automata with few states, on the other hand, the effort of an object-oriented implementation is not necessarily worthwhile, because a switch statement in this case would not be so confusing.
If a state machine framework is available and is suitable for the target platform from a resource requirements viewpoint, it should be used: comprehensibility and maintainability can only benefit.
Outlook – Generating source code automatically
All the implementation variants we have discussed suffer from a number of disadvantages in principle:
- No form of implementation can come close to the state diagram in terms of clarity and intelligibility. The more extensive a state machine is, the more unreadable and unmanageable is its representation as program code or state transition table.
- The transformation of a state diagram into an implementation is complex and error-prone.
- Changes to the statechart mean changes to the implementation. This is again complicated, error-prone and in no way easy to maintain.
Implementation effort and complexity require tool support, so that a developer ideally only needs to take care of the graphical statechart. In the next part of this series, we will learn how YAKINDU Statechart Tools is supporting this.
To read the whole “How to use state machines for your modelling” series, download our whitepaper for free.
Comments