Implementation techniques for FSM states

Question

How do you go about implementing FSM(EDIT:Finite State Machine) states? I usually think about an FSM like a set of functions, a dispatcher, and a thread as to indicate the current running state. Meaning, I do blocking calls to functions/functors representing states.

Just now I have implemented one in a different style, where I still represent states with function(object)s, but the thread just calls a state->step() method, which tries to return as quickly as possible. In case the state has finished and a transition should take place, it indicates that accordingly. I would call this the 'polling' style since the functions mostly look like:

void step()
{
  if(!HaveReachedGoal)
  {
    doWhateverNecessary();
    return; // get out as fast as possible
  }
  // ... test perhaps some more subgoals
  indicateTransition();
}

I am aware that it is an FSM within an FSM.

It feels rather simplistic, but it has certain advantages. While a thread being blocked, or held in some kind of while (!CanGoForward)checkGoForward(); loop can be cumbersome and unwieldy, the polling felt much easier to debug. That's because the FSM object regains control after every step, and putting out some debug info is a breeze.

Well I am deviating from my question: How do you implement states of FSMs?

Answer 1

There’s always what I call the Flying Spaghetti Monster’s style of implementing FSMs (FSM-style FSMs): using lotsa gotos. For example:

state1:
  do_something();
  goto state2;

state2:
  if (condition) goto state1;
  else           goto state3;

state3:
  accept;

Very nice spaghetti code :-)

Answer 2

I did it as a table, a flat array in the memory, each cell is a state. Please have a look at the cvs source of the abandoned DFA project. For example:

class DFA {
    DFA();
    DFA(int mychar_groups,int mycharmap[256],int myi_state);
    ~DFA();
    void add_trans(unsigned int from,char sym,unsigned int to);
    void add_trans(unsigned int from,unsigned int symn,unsigned int to);
    /*adds a transition between state from to state to*/
    int add_state(bool accepting=false);
    int to(int state, int symn);
    int to(int state, char sym);
    void set_char(char used_chars[],int);
    void set_char(set<char> char_set);
    vector<int > table; /*contains the table of the dfa itself*/
    void normalize();

    vector<unsigned int> char_map;
    unsigned int char_groups; /*number of characters the DFA uses,
                    char_groups=0 means 1 character group is used*/
    unsigned int i_state; /*initial state of the DFA*/
    void switch_table_state(int first,int sec);
    unsigned int num_states;
    set<int > accepting_states;
};

But this was for a very specific need (matching regular expressions)

Answer 3

The state Design Pattern is an interesting way of implementing a FSM:

http://en.wikipedia.org/wiki/State_pattern

It's a very clean way of implementing the FSM but it can be messy depending on the complexity of your FSM (but not the amount of states). However, the advantages are that:

• you eliminate code duplication (especially if/else statements)
• It is easier to extend with new states
• Your classes have better cohesion so all related logic is in one place - this should also make your code easier to writ tests for.

There is a Java and C++ implementation at this site:

http://www.vincehuston.org/dp/state.html

Answer 4

If you are creating a complex state machine then you may want to check out SMC - the State Machine Compiler. This takes a textual representation of a state machine and compiles it into the language of your choice - it supports Java, C, C++, C#, Python, Ruby, Scala and many others.

Answer 5

I remember my first FSM program. I wrote it in C with a very simple switch statement. Switching from one state to another or following through to the next state seemed natural.

Then I progressed to use a table lookup approach. I was able to write some very generic coding style using this approach. However, I was caught out a couple of times when the requirements changed and I have to support some extra events.

I have not written any FSMs lately. The last one I wrote was for a comms module in C++ where I used a "state design pattern" in conjunction with a "command pattern" (action).