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)
