Wednesday, August 16, 2006

The Problems with the State Pattern

Design Patterns

I cannot rave enough about the Gang of Four (GoF) Design Patterns book. Ever since it came out over ten years ago I plug this book to all the software engineers that I meet. I’ve even had two personal copies stolen from me. I treat this like the Gideon’s and their distribution of the bible. I’m happy for people to steal my copies because if they think it is worth stealing it means they appreciate the value of the book.

Alas Design Patterns is getting a little dated. The code examples are in languages that aren’t so commonly used these days. The notation for presenting design and interaction diagrams is pre-UML. All in all the book needs to be revised and released in a new 2nd edition. There are a couple of other books that attempt to present the patterns in more modern languages, Java and C#, but somehow these aren’t very good.

I Have a Hammer and Everything Is a Nail

Engineers who encounter Design Patterns for the first time often go through an ‘ah ha’ moment where they recognise and find names to patterns that they have been using all along. The pattern names are more common as they have crept into the design and implementation of class libraries, such as Observable (based on the Observer pattern) in Java.

The ‘ah ha’ moment is usually followed by an ‘oh wow’ moment as new patterns are discovered in the book solving problems that the engineer has encountered previously but hadn’t found a satisfactory solution. From that moment on there is often a desire for the engineer to use all of the patterns in the book. I often call this pattern mania. It’s the hammer syndrome, when you have a hammer everything is a nail. I can use the hammer (patterns) for all of my problems.
With a bit of experience and guidance, pattern mania passes and a more informed usage of Design Patterns then ensues.

Not All Patterns Are Equal

Of the twenty one design patterns two of them need to be used with caution and in fact I recommend them with a health warning. These are State and Singleton. In this blog entry we’ll cover State and Singleton subsequently. Singleton for future reference causes problems similar to the use of global variables, a universally bad idea.

Why I Dislike the State Pattern

Each of the Design Patterns includes a consequences section outlining the issues relating to the use and implementation of each particular pattern. I encourage you to read the State pattern as there is little value to be gained from reproducing it here. A summary of the pattern can be found here http://exciton.cs.rice.edu/JavaResources/DesignPatterns/StatePat.htm, but reading the chapter in the book is best.

There are several consequences in using the State pattern, which to me are fundamental and make it to all intents and purposes impractical to use. These are:

Class Explosion!

It has taken the OO concept and applied it to the extreme as a class has to be implemented for each state. Even for simple state machines a large number of classes need to be implemented resulting in:
  • More code to write
  • Difficulty in reviewing the structure of the state machine as its implementation is smeared across multiple classes

Brittle Interface

The state interface as defined in the pattern is expensive to maintain when a new event is introduced. The valid events are defined in the interface of the ‘context’ class where there is a method for dealing with each event. These also need to be added to each state class.


Alternative State Pattern Implementations Strategies

There are other approaches to implementing state machines instead of using the State Pattern. These strategies vary depending upon the complexity of the state machine to be implemented.

Introduce an Event class

As the GoF Design Patterns book states, ‘design to interfaces not implementation’. One of the shortcomings of the State pattern is that the interface is brittle as previously described. When we want to add a new event we have to add a new method to the state ‘context’ interface and to all of its subclasses. This is expensive and a fiddle to do especially if there are many states implemented as classes.

The State Pattern only really goes half-way in providing an object-oriented implementation. What is missing is a representation for events. We can introduce a class for the event or better still an enumerate type, where the values of the enumeration represent the different possible events. We can then introduce an onEvent( Event anEvent ) method to the ‘context’ class and the State class.

Once we have a standard onEvent() interface we have a couple of alternative implementation strategies.

Table Driven

This is actually covered in the original design patterns book. We can make the implementation table driven. This essentially involves adding a two dimensional array with states as one dimension and events as the other. Each element of the array contains the next state. Additional arrays can be implemented to support other aspects onEvent() of transitioning from one state to another for instance an action to be performed (based on the Command pattern perhaps). The array can either be populated through initialization as code in the class, or alternatively, be data driven and read from a file (including an XML document).

The table driven approach has the advantage that the whole state machine can be viewed in a single place making it easier to review and maintain.

Flags and Conditional Logic

The state of the class can also be represented by flags, or variables for holding the state, within the class (using the good old enumated value again). Conditional logic within the method be used to determine the next state based upon the current state and the event that has just occurred. If you know the state == x then do this else if the state == y do the following.
This approach can be surprisingly simple to implement. Often the state machine to be implemented isn’t that complicated and so this is a very practical solution. Like the table driven approach the whole state machine can be viewed in a single place within the method and changes are easy to make as a result.

Guidelines

Most business objects do not have a sufficiently complex state to warrant a full implementation of the State pattern. Usually they follow a typical CRUD (Create, Read, Update and Delete) cycle. Therefore I recommend the following guidelines:

  1. In 9 out of 10 cases you should stick to the Flags and Conditional Logic Approach described above as most state implementations are not that complicated. This is usually sufficient for managing implementations requiring the support of up to five states.
  2. If the state machine is more complex, say with ~6 states and events, then consider introducing Events and combine this with a State Pattern implementation.
  3. Finally consider the Table Driven Approach, for the most complex State machines. Often I would still use in this preference to a class based State Pattern implementation.

5 comments:

Anonymous said...

I agree that conditional logic is up to the task of defining business process (most of the time).
In a recent consulting engagement, we had to recommend against a workflow engine (ROI just wasn't there) and subsequently suggest an alternative. We suggested that project teams use a blend of embedded frameworks, known programming language constructs and table-driven logic. FWIW, we did give a pass to the State pattern as well.

Architect Venice said...

The modern trend in design is toward integration of previously separated specialties, especially among large firms. In the past, architects, interior designers, engineers, developers, construction managers, and general contractors were more likely to be entirely separate companies, even in the larger firms.

Mark said...

Like any pattern the State pattern can be used incorrectly or in a place it doesn't fit well. I'm not sure if this is what you have experienced or not but my experience is that, when it fits, the State pattern is a lifesaver.

In our projects we have had engineers manage 'state'-based activities by scattering the 'state' management code over several methods (and even several classes). They did this without realizing they were modelling state behavior.

When it was pointed out what they had done we reimplemented using simple state machines and state classes. This greatly simplified the code and made the design intent much clearer.

In fact, for our current project we are considering creating a, possibly template-based, common state machine to handle the kinds of cases we have run into so it can be used wherever it makes sense.

Of course, in these cases the state transition diagrams are well defined and don't change much over time. But if they do it still manages to keep the changes localized to a small set of classes that are much more easily maintained than if this were spread out among classes that have other responsibilities as well.

Alex Theodoridis said...

State design pattern fits very well when you need to implement the state machine. I don't understand why your developers had some problems with that. Probably they didn't really use OOP.
I did some experiment and moved the state design pattern in a template library. Please take a look here:
https://code.google.com/p/dpsmlib/

The only problem with this pattern is the relation between the states so states cannot be reused in some other state machines. This was solved in my implementation by introduction of event system.

Mark said...

Hi Alex,

OOP wasn't the problem. It was a realization of the use of states without actually implementing states that was the problem. The states and state behavior was considered a part of other classes' responsibilities. When I pointed out the state-based aspect of the behavior it became obvious to them. It was simply a case of being too close to the problem and having too many things to do to take that step back and realize what was going on in the code.