The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

State pattern or table driven FSM?

I know the "theory" behind them and their implementation. Just wanted to know from JoS readers what their experience was, and which pattern did they find better to implement.

my own experience is while state patterns bring in the advantages of what GoF talks of, they are a definite bit of overhead when the number of transitions aren't large, and the  amount of processing per state is not much. Table driven approaches can be quite nice - so one idea could be to mix them both. Sort of put control logic in the main controller, code each state as a class, but define transitions using a table lookup instead of doing it within the state classes.

Thoughts?
v
Thursday, September 01, 2005
 
 
Christopher Wells Send private email
Thursday, September 01, 2005
 
 
Peter
Thursday, September 01, 2005
 
 
Perhaps the 'optimal' implementation depends on what you're trying to optimize: for example, if the thing I'm implementing is the protocol driver for some standard communications protocol then the definitions of the state-machine transitions may be well-documented *and* cast in stone ... and so I *don't* need an implementation strategy which optimizes for maintenance (i.e. which facilitates changes to the specification).

BTW, apart from 'table driven FSM' another possibility is like nested switch statements:

void handle_event(Event e)
{
  switch(m_state)
  {
    case STATE_DISCONNECTED:
      switch(e.code)
      {
        case EVENT_CONNECT_REQUEST:
          ... etc...
      }
  }
}

Anyway I find this one of the harder coding tasks ... harder for me to conceptualise than multi-threading, for example. The ROOM book I referenced above made me wish for better tool support (i.e. a CASE tool) ... the book introduces a product named ObjectTime that was bought by Rational ... I don't know what happened to it after that.
Christopher Wells Send private email
Thursday, September 01, 2005
 
 
I like the hybrid approach.

A truly table driven approach never works. There will always be some sort of scenario/condition that can't be expressed easily in the table. This will cause you to have to go to code and add the special conditional logic there. What a mess. You end up with a situation where the table doesn't tell the whole story. Something like: "Oh yeah, unless the state is named ProcessOrder and it is the last day of the month. Then we ignore the table entries and go to the DelayPosting state."

A truly state object approach gives you great flexibiliy in conditioning special cases but can be less flexible for configuring for mulitple clients. You end up needing to make code changes to alter the state machine for different requirements.

I prefer a hybrid approach which basically uses a table of object names that correspond to the MAJOR states. Each major state then instantiates and builds its internal sub-states in code. This allows you to configure which major state implementation a given client uses but control everything else in code. For example, I can have two clients using identical state machines except that one uses the ProcessOrderA state and the other one uses the ProcessOrderB state. This gives me a hook into the code to do whatever I need to do to satisfy each clients requirements. This also means that my state table layout never changes because the concept of a "major state" is set in stone.
matt
Thursday, September 01, 2005
 
 
The state pattern is not just a FSM implementation. It allows you to change object implementation (and behavior) at runtime and it localizes state dependent behavior and data.

Based on this pattern, an object can dynamically change its class at runtime (via state change).

Table driven FSM cannot do this.

class DynObject implements MyInterface {
    private MyInterface implementation;
   
    public DynObject(MyInterface implementation) {
        this.implementation = implementation;
    }
   
    public void changeClass(MyInterface implementation) {
        this.implementation = implementation;
    }

    public Class getClass() {
        return this.implementation.getClass();
    }
}
Dino Send private email
Thursday, September 01, 2005
 
 
The nested switch and case is a real horror to look at, but can't be beaten for flexibility, ease of programming, and the (double-edged) lack of infrastructure.

Anybody maintaining the code will, of course, really hate you. (Keep at it yourself for long enough, and you'll really hate you too.) But that's just how it is with state machine type code; the least you can do is keep the state management bits simple and clear, for which the switch statement is perfect.

Of course, table-driven approaches are preferred. But how often do you see something suitable for that? It almost *never* happens!
Tom_
Thursday, September 01, 2005
 
 
Thumbs down on the nested switch approach. It's just too brittle. Every time you want to add any new states you end up modifying the same huge piece of code. With the objects as states approach I can safely add sub-states to a given process without the possibility of breaking unrelated processes. I'm also not fighting with other developers for the same piece of code all of the time.
matt
Thursday, September 01, 2005
 
 
One more thought...

I admit that the nested switch and table driven approaches are easier to implement in web based systems. These systems typically keep the state as a string or token either in the page or in a database. It is more natural to translate the mechanism for storing state into one of these two approaches. The objects as states approach is much harder to implement for a web app because you end up persisting objects for the session or rebuilding the entire object tree with each page post.
matt
Thursday, September 01, 2005
 
 
> Every time you want to add any new states ...

I mentioned it with some hesitation ... it is one of the canonical solutions though, and worth mentioning. Of course, you can refactor the switch-statement solution so that the event-handling for every state is contained within its own subroutine:

void handle_event(Event e)
{
  switch(m_state)
  {
    case STATE_DISCONNECTED:
      handle_state_disconnected_event(e);
      break;
    ... etc ...
  }
}

void handle_state_disconnected_event(Event e)
{
  switch(e.code)
  {
    case EVENT_CONNECT_REQUEST:
      ... etc...
  }
}

You can then put each subroutine in a different module, e.g. to minimize inter-programmer contention for exclusive write-access to modules.

Anyway, I reckon that's an example of what I was saying: that different solutions are each optimal in different ways.
Christopher Wells Send private email
Thursday, September 01, 2005
 
 
I prefer the table approach, if it can be used.

Attributes of a table implementation can be verified automatically - e.g., "There is no sequence of inputs that makes us reach state 'x'" or alternatively "here's a sequence that reaches state 'x'" if it's reachable.

When it's a table, the table generation itself can often be delegated to run-time and/or another tool. The classical example are lexical analysers - e.g., if you want a syntax highlighting editor, the switch()/case: solution to determine lexical classes and font attributes is significantly less convenient in almost every aspect. But there are many other cases that benefit from it -- e.g., when I wrote a testing program for some hardware gadget, I moved the test logic to a table being read from a file, which allowed other people to modify the tests when the hardware evolved, without having to delve into the real code.

In general, data driven execution (FSM or otherwise) is more flexible and rarely less efficient.
Ori Berger
Thursday, September 01, 2005
 
 
I doubt it is more efficient. The state pattern does not require any lookup. The object contains the state.
Dino Send private email
Thursday, September 01, 2005
 
 
... and the state "knows" its transitions.
Dino Send private email
Thursday, September 01, 2005
 
 
For real projects, I've had good experiences with the nested switch statements. However, I've found them much more maintenance-friendly if you switch on the event first, and on the state second. (This is non-intuitive, but seems to help.)

Generally, I have a switch statement for the event, and each branch of the switch statement calls a separate method. Each of these methods has switch statements for the states.

This works because I find it much more common to add new events after the fact than to add new states. When events carry responsibilities with them ("so-and-so wants to know what happened to the framistat" implies that you eventually have to tell him about it), this style makes it easy to verify that the responsibility has been met.

I also find that a sets of cooperating small state machines are easier to cope with than a single large one. Don't be afraid to build state machines that fire events into each other.
Jim Lyon Send private email
Thursday, September 01, 2005
 
 
Lot of interesting replies! I've personally used both approaches. My take is the state pattern is probably a bit of an overhead if the following is true

1. Your state transitions are pretty rigidly fixed,
2. Number of states is small.
3. You're not necessarily going to fiddle around with the transitions too much

And it's probably my implementation - but I don't like the idea of using reflections to terminate my main control (or context) loop as it steps through the states.

The table driven approach is nice as long as there are a small number of branches off a single state, based on conditions on an event. Otherwise, you end up with sphagetti code when you should ideally be stepping thru the states using the table look-up.

The reality of my situation is that I have a couple of SM's that actually quite clean and implemented using state pattern techniques, it's just that when I look at it now - I wonder if it really needed that pattern at all.
v
Thursday, September 01, 2005
 
 
Thou shalt have but one status field; unless thou hast a state of "On Hold" therein goest upon to two state fields.
John Griffiths Send private email
Thursday, September 08, 2005
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz