State Machines

Commentary and Observations on State Machines

State machines are one way of implementing an iterated and complex control flow that is more maintainable than equivalent functionality using just if statements.  For  information on state machines see the wiki page.

This is just a commentary on my experience with state machines.

First of all, in many situations, using state machines is a good implementation choice.

The classic state machine can be described as a set of actions whose order of execution is controlled by an input value, a current state, and a transition table.  This type is often used in programs to implement a text parser.

For simplicity in this description, both the current state and the input value are treated as integers.  The basic sequence is as follows:

1. Set the current state to 0

2. Start the loop

3. Set the input value (read from a file or get the next character in a string variable)

4. Set the current state to the value found in the transition table by using the input value, and current state value

5. Select/jump to the block of code associated with the current state.  This code will take appropriate action and then jump to the end of the loop

6. Return to the top of the loop (Step 3 above) if some loop termination condition is not met

The main variants of this algorithm are that:

• the input value may be something other than a character
• the termination condition may not be “end of string” or “end of file”

For example, in my Adventure 3 posting, the original state machine implementation had the following changes:

• The input value was the “current state” of the device
• The next state was determined by the “input value” and the desired “state” of the device
• The termination condition was that the input value (the “current state”) matched the desired “state”

In the above type of state machine, maintenance problems become evident if the number of states is large or if the numeric range of the input value is large.  

If the number of states is large, it is difficult to understand what the code is doing because the execution sequence is encoded in the transition table and the actions are represented as numbers.  The difficulty arises because of the need to remember exactly what actions all those numbers represent, and, therefore, changes to the transition table or the code for a given state can easily have unintended side effects. 

If the numeric range of the input value is large, then there can easily be a problem with the coding of the transition table itself.  There is likely to be a lot of duplication e.g. all alphabetic characters have exactly the same transition except in certain states.  In some applications, it may not be physically possible for every value in the input to occur (e.g. even though the input value is a byte, the number of possible values is small, and the values are not numerically consecutive (See Adventure 3.) . This condition results in large logical gaps in the transition table and a very memory-consuming transition table. To overcome this problem, I have sometimes used an input translator function that accepts the input value and produces a translated value (e.g. all alphabetic characters are assigned the same translated value).  This translated value is what the state machine uses.

In my Adventure 2 posting, I describe a new (for me) type of state machine that eliminates or reduces the problems inherent in a classic state machine.  This “new” machine also makes a state machine implementation a viable option in a wide variety of situations. Its design came about (in part) when I realized that a state machine representation could be used to flatten a calling stack (when one routine calls another ). This design is summarized here.

  

In this type of state machine, there is no input value.  The execution sequence is controlled by a “current state” and a “next state.”

1. Set the next state to 0

2. Start the loop

3. Set the “current state” to “next state”

4. Select/jump to the block of code associated with the current state. This code will take appropriate action and then may set the next state before jumping to the end of the loop.

The action of at least one of the states is to exit the loop.

Note: If the next state is not changed, then state action will be repeated.  This can happen when a state machine is used to implement a polling loop.

In practice, the appropriate action was often implemented by a function call and its return value was used to determine a value for “next state”.

The benefits of having the state code decide what the next state would be are as follows:

• Transition sequences are relatively easy to follow, and, therefore, code changes are less likely to have unintended consequences
• There is no transition table to maintain
• There is no need to specially handle sparse values in an input value (even if one were used).

Miscellaneous Observations

·        I have used a state machine design to analyze a problem, and several times this analysis showed that the problem could be solved by just a few if statements.

·        When could a state machine pattern be used?

o   If the code is processing some kind of input stream and I find that I am writing a series of “if statements” to decide what to do

o   If processing decisions must be made based on the values of one or two variables and the action to be taken is determined by the values of the variable(s)

·        When should a state machine pattern NOT be used?

o   If there is no “input stream” then the problem might be too simple to justify the use of a state machine

o   If there are more than two controlling variables used to decide what action to take and the problem cannot be factored into multiple simpler problems

o   If the controlling variable(s) can be changed by external actions (e.g. other processes or threads)