State Machines

Almost any program can be modelled as a state machine.

I say "almost any" because it is, just, possible to think of a program which cannot easily be resolved into anything more than a one-state state machine. Consider a command interpreter with no support for loops or function definitions (like the old DOS command.com) and with no internal commands, only the ability to execute external commands. It loops forever and does only one thing for every line it reads.    If it does no error handling, the execution is a single line, a call to execve or one of its relatives. There are internal stages inside the C library call, but they are effectively invisible to the program.  However, it's not a very useful program. Neither is any version of HelloWorld. The echo application does have its uses.

Once one gets beyond this, even simple programs have at least two states: setup and execute. A simple version of cp has to open two files for input and output before beginning to copy data.  It needs to handle error reporting and cleanup. That's arguably five states. (The real cp is more complex, handling multiple options and treating directories and files as different types of targets.)

We don't think of it as five states because we don't tend to explicitly model states which are sequential and where there is no condition involved in the state transition. A sequence of unique operations is implicitly a transition between a set of sequential states; but we're more likely to model the opening of two files in setup as two actions during a single stage than we are two states distinct from each other. Likewise, if your error handling is "print a message to console and exit the program" we may not think it worthwhile to have an explicit error state.

In a few cases, we model an entire program as an explicit state machine. If you write a text transduction program using lex/flex the whole program is written as a set of actions tied to a set of states, with the main loop just calling yylex(). Parsers of any sort tend, after some basic setup, to be entirely modelled as state machines.

In many other cases, we want only a part of a program - perhaps reading a configuration file, perhaps an entire thread of control where the inputs to the state machine come as queued messages - to be an explicit state machine.

In many cases we delegate the management of the state machines to third-party tools like flex/bison or Boost Spirit. Xerces hides the states involved in parsing XML, especially if you use it with a DOM model. In other cases we use the State pattern to model a set of states within a class. (The State pattern has other uses. If we process a sequence of events but the transition between states comes from an external call (e.g. user input, or a change between daytime and nighttime processing), the State pattern is useful without being reasonably described as a state machine.) Many frameworks can be thought of as state machine managers where the application developer principally defines handlers for certain state transitions.

All of this is, on reflection, moderately obvious. After all, the fundamental Turing Machine reading an infinite tape of 1s and 0s is an explicit state machine. Why bother belabouring the obvious?

The simplest answer is: once you have a decent feel for explicit state machines, they become an important tool in improving clarity and maintainability in general code. Most obviously, they are a key tool in getting rid of long functions with if/else tests where what is being tested is internal data of the class or where parsing input data breaks down naturally into two steps.

To take the latter point first, because it is less obvious: normally handing variant input maps to a Command pattern.  But consider where, for example, you are parsing a wide set of string tokens.  Instead of doing a brute-force set of string comparisons, it makes a lot of sense from an efficiency standpoint to group the strings by (for example) the value or character class of the first character of a token.  In naive code, this leads to nested switch statements as the price of performance. But once one has determined that first condition, you are effectively in a state of an implicit state machine, even if the state can be described as "parsing tokens beginning with 'c'". A fully decomposed version would be a set of Command pattern implementations mediated by a state machine.  In this particular instance, the state itself adds little clarity -- the individual action functions remain the same -- but in some cases the category can be more meaningful depending on the nature of the up-front determination of the state (e.g. "parsing numeric token"). The case with purely arbitrary states is probably better modelled as nested commands if needed for the sake of efficiency: explicit states will just add a layer of arbitrariness to the process.

One design advantage of the more general decomposition of general if/else functions into a set of states is that the resources needed by some states may not be needed by any other state. In that case the ownership of the resource can be passed to that state on construction, simplifying the data model of the calling class.

But state machines can also be used to clarify logic which is less obviously a set of if/else tests. A succession of calls which hide, internally, calls to common error-handling procedures, or where the return value from one call determines the choice of the next (not necessarily via if/else: it can be via indexing, or by chaining functions along the lines of monadic operations, or by passing a result *into* a wrapper function which branches on it) might[1] be clarified by extracting the implicit state transitions and making them explicit.

[1]Or might not: state machines are not a panacaea. Chunking of other sorts can, in many cases, be clearer and simpler than modelling with explicit states. The thing that determines whether an explicit state machine assists in clarification is whether the states compose a coherent set of concepts at the same level.