The other day I was looking at the statistics for this site and I noticed that one of the most popular post with readers was the one I wrote on the producer/consumer design pattern. Given that level of interest, it seemed appropriate to write a bit about another very common and very popular design pattern: the state machine. There’s a good reason for the state-machine’s popularity. It is an excellent, often ideal, way to deal with logic that is repetitive, or branches through many different paths. Although, it certainly isn’t the right design pattern for every application, it is a really good technique for translating a stateful process into LabVIEW code.
However, some of the functionality that state machines offer also means they can present development challenges. For example, they are far more demanding in terms of the design process, and consequently far less forgiving of errors in that process. As we have seen before with other topics, even the most basic discussion of how to properly design and use state machines is too big for a single post. Therefore, I will present one post to discuss the concepts and principles involved, and in a second post present a typical implementation.
State Machine Worst Practices
For some reason it seems like there has been a lot of discussions lately about state machine “best practices”. Unfortunately, some of the recommendations are simply not sound from the engineering standpoint. Meanwhile others fail to take advantage of all that LabVIEW offers because they attempt to mimic the implementation of state machines in primitive (i.e. text-based) languages. Therefore, rather than spinning out yet another “best practices” article, I think it might interesting to spend a bit of time discussing things to never do.
In describing bad habits to avoid, I think it’s often a good idea to start at the most general level and work our way down to the details. So let’s start with the most important mistake you can make.
1. Use the state machine as the underlying structure of your entire application
State machines are best suited for situations where you need to create a complex, cohesive, and tightly-coupled process. While an application might have processes within it that need to be tightly-coupled, you want the application as a whole to exhibit very low levels of coupling. In fact, much of the newest computer science research deprecates the usage of state machines by asserting that they are inherently brittle and non-maintainable.
While I won’t go that far, I do recognize that state machines are typically best suited for lower-level processes that rarely, if ever, appear to the user. For example, communications protocols are often described in terms of state machines and are excellent places to apply them. One big exception to this “no user-interface” rule is the “wizard” dialog box. Wizards will often be built around state machines precisely because they have complex interface functionality requirements.
2. Don’t start with a State Diagram
Ok, so you have a process that you feel will benefit from a state machine implementation. You can’t just jump in and start slinging code right and left. Before you start developing a state machine you need to create a State Diagram
(also sometimes called a State Transition Diagram
), to serve as a road-map of sorts for you during the development process. If you don’t take the time for this vital step, you are pretty much in the position of a builder that starts work on a large building with no blueprint. To be fair, design patterns exist that are less dependent upon having a completed, through design. However, those patterns tend to be very linear in structure, and so are easy to visualize in good dataflow code. By contrast, state machines are very non-linear in their structure so can be very difficult to develop and maintain. To keep straight what you are trying to accomplish, state machines need to be laid out carefully and very clearly. The unfortunate truth, however, is that state machines are often used for the exact opposite reason. There is a common myth that state machines require a minimum of design because if you get into trouble, you can always just, “add another state”. In fact, I believe that much of the bad advice you will get on state machines finds its basis in this myth.
But even if we buy the idea that state machines require a more through design, why insisted on State Diagrams? One of the things that design patterns do is foster their own particular way of visualizing solutions to programming problems. For example, I have been very candid about how a producer/consumer design pattern lends itself to thinking about applications as a collection of interacting processes. In the same way, state machines foster a viewpoint where the process being developed is seen as a virtual machine constructed from discrete states and the transitions between those states. Given that approach to problem solving, the state diagram is an ideal design tool because it allows you to visually represent the structure that the states and transitions create.
So what does it take to do a good state-machine design? First you need to understand the process — a huge topic on its own. There are many good books available on the topic, as well as several dedicated web sites. Second, having a suitable drawing program to create State Diagrams can be helpful, and one that I have used for some time is a free program called yEd. However fancy graphics aren’t absolutely necessary. You can create perfectly acceptable State Diagrams with nothing more than a paper, a pencil and a reasonably functional brain. I have even drawn them on a white board during a meeting with a client and saved them by taking a picture of them with my cell phone.
Moreover, drawing programs aren’t much help if you don’t know what to draw. The most important knowledge you can have is a firm understanding of what a state machine is. This is how Wikipedia defines a state machine:
A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical model of computation used to design both computer programs and sequential logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states. The machine is in only one state at a time; the state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition; this is called a transition.
An important point to highlight in this description is that a state machine is at its core is a mathematical model — which itself implies a certain level of needed rigor in their design and implementation. The other point is that it is a model that consists of a “finite number of steps” that the machine moves between on the basis of well-defined events or conditions.
3. Ignore what a “state” is
Other common problems can arise when there is confusion over what constitutes a state. So let’s go back to Wikipedia for one more definition:
A state is a description of the status of a system that is waiting to execute a transition.
A state is, in short, a place where the code does something and then pauses while it waits for something else to happen. Now this “something” can be anything from the expiration of a timer to a response from a piece of equipment that a command had been completed successfully (or not). Too often people get this definition confused with that for a subVI. In fact one very common error is for a developer to treat states as though they were subroutines that they can simply “call” as needed.
4. Use strings for the state variable
The basic structure behind any state machine is that you have a loop that executes one state each time it iterates. To define execution order there is a State Variable
that identifies the next state the machine will execute in response to an event or condition change. Although I once saw an interesting object-oriented implementation that used class objects to both identify the next state (via dynamic dispatch) and pass the state machine operational data (in the class data), in most cases there is a much simpler choice of datatype for the State Variable: string or enumeration.
Supposedly there is an ongoing discussion over which of these two datatypes make better state variables. The truth is that while I have heard many reasons for using strings as state variables, I have yet to hear a good one. I see two huge problems with string state variables. First, in the name of “flexibility” they foster the no-design ethic we discussed earlier. Think about it this way, if you know so little about the process you are implementing that you can’t even list the states involved, what in the world are you doing starting development? The second problem with state strings is that using them requires the developer to remember the names of all the states, and how to spell them, and how to capitalize them — or in a code maintenance situation, remember how somebody else spelled and capitalized them. Besides trying to remember that the guy two cubicles down can never seem to remember that “flexible” is spelled with an “i” and not an “a”, don’t forget that there is a large chunk of the planet that thinks words like “behavior” has a “u” in them…
By the way, not only should the state variable be an enumeration, it should be a typedef enumeration.
5. Turn checking the UI for events into a state
In the beginning, there were no events in LabVIEW and so state machines had to be built using what was available — a while loop, a shift register to carry the state variable, and a case structure to implement the various states. When events made their debut in Version 6 of LabVIEW, people began to consider how to integrate the two disparate approaches. Unfortunately, the idea that came to the front was to create a new state (typically called something like, Check UI
) that would hold the event structure that handles all the events.
The correct approach is to basically turn that approach inside out and build the state machine inside the event structure — inside the timeout event to be precise. This technique as a number of advantages. To begin with, it allows the state machine to leverage the event structure as a mechanism for controlling the state machine. Secondly, it provides a very efficient mechanism for building state machines that require user interaction to operate.
Say you have a state machine that is basically a wizard that assists the user in setting up some part of your application. To create this interactivity, states in the timeout event would put a prompt on the front panel and sets the timeout for the next iteration to -1. When the user makes the required selection or enters the needed data, they click a “Next” button. The value change event handler for the button knows what state the state machine was last in, and so can send the state machine on to its next state by setting the timeout back to 0. Very neat and, thanks to the event-driven programming, very efficient.
On the other hand, if you are looking for a way to allow your program to lock-up and irritate your users, putting an event structure inside a state is a dandy technique. The problem is that all you need to stop your application in its tracks is one series of state transitions where the “Check UI” state doesn’t get called often enough, or at all. If someone clicks a button or changes something on the UI while those states are executing, LabVIEW will dutifully lock the front panel until the associated event is serviced — which of course can’t happen because the code can’t get to the event structure that would service it. Depending on how bad the overall code design is and the exact circumstances that caused the problem, this sort of lock-up can last several seconds, or be permanent requiring a restart.
6. Allow default state transitions
A default state transition is when State A always immediately transitions to State B. This sort of design practice is the logical equivalent of a sequence structure, and suffers from all the same problems. If you have two or more “states” with default transitions between them, you in reality have a single state that has been arbitrarily split into multiple pieces — pieces that hide the true structure of what the code is doing, complicates code maintenance and increases the potential for error. Plus, what happens if an error occurs, there’s a shutdown request, or anything else to which the code needs to respond? As with an actual sequence structure, you’re stuck going through the entire process.
7. Use a queue to communicate state transitions
Question: If default transitions are bad, why would anyone want to queue up several of them in a row?
Answer: They are too lazy to figure out exactly what they want to do so they create a bunch of pieces that they can assemble at runtime — and then call this kind of mess, “flexibility”. And even if you do come up with some sort of edge case where you might want to enqueue states, there are better ways of accomplishing it than having a queue drive the entire state machine.
Implementation Preview
So this is about all we have room for in this post. Next Monday I’ll demonstrate what I have been writing about by replacing the random number acquisition process in our testbed application with an updated bit of LabVIEW memorabilia. Many years ago the very first LabVIEW demo I saw was a simple “process control” demo. Basically it had a chart with a line on it that trended upwards until it reached a limit. At that point, an onscreen (black and white!) LED would come on indicating a virtual fan had been turned on and the line would start trending back down. When it hit a lower limit, the LED and the virtual fan would go off and the line would start trending back up again. With that early demonstration in mind, I came up with this State Diagram:
When we next get together, we’ll look at how I turn this diagram into a state-machine version of the original demo — but with color LEDs!
Until next time…
Mike…