Implementation techniques for FSM states
-
28-09-2019 - |
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?
Solution
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:
OTHER TIPS
There’s always what I call the Flying Spaghetti Monster’s style of implementing FSMs (FSM-style FSMs): using lotsa goto
s. For example:
state1:
do_something();
goto state2;
state2:
if (condition) goto state1;
else goto state3;
state3:
accept;
Very nice spaghetti code :-)
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)
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).
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.