Finite State Machine : Bad design?

Question

Are Finite State Machines generally considered as bad design in OOP ?

I hear that a lot. And, after I had to work on a really old, undocumented piece of C++ making use of it, I tend to agree. It was a pain to debug.

what about readability/maintainability concerns?

Answer 1

State machines are good at some things (syntactic and lexical analysis). How exactly is your piece of C++ code using an FSM and what for?

Answer 2

I think if the code is well documented there is no problem to implement it using a OOP approach. Most of the C/C++ use to implemente FSM using switch statements which sometimes can compromise the readability if the machine is large.

Recently I needed to parse a Regular Language, and implemented an FSM using the OOP approach, the code readability and maintainability were good. I mean, much better than using large switch statements.

A tip, at a first moment, I've implemented the FSM containg states and the states containing the transitions. However, in my case it proved to be a better approach to have a class to represent the FSM containing one collection of states and another of transitions. It made easier to me to clone the machines (it was a requirement to me) and to have a smaller transition function.

I hope it helps, Carlos.

Answer 3

I would say that finite state machines are much easier to debug than other ways of solving the same problems (problems such as matching regular languages). What's nice about FSMs is all in the name... you might have a state machine with 15 states, so you can draw a diagram on a piece of paper showing all the transitions. You can use the diagram to figure out useful properties of the system, such as which strings it accepts and how it gets into error states. With more complicated systems, diagramming is often difficult or impossible.

Even the people who say "gotos are evil" think they're the right way to implement state machines. (Of course, some people think gotos are always evil... but you can't please everybody).

Answer 4

Couldn't tell you what They say.

But OO and FSM sorta attack different problem domains. In a domain where objects are interacting -- that calls for an object-oriented approach. In a domain where the world is in one state or another -- that calls for a FSM design.

Realistically, you can mix these designs with/at different levels of abstraction, which will come out cleaner than using only one or the other.

Answer 5

FSMs should never be considered bad. They are far too useful, but people whom aren't accustomed to them will often consider them burdensome.

There are numerous ways to implement one with OOP. Some are uglier than others. Your low-level guys will use switch statements, jump tables or even "goto."

If you're looking for a cleaner way to do it, I'd recommend Boost's State Chart library, which is built just for implementing UML state diagrams in C++. It makes use of modern template techniques, to make things more readable. It also performs very well.

Answer 6

Finite state machines are a tool to achieve certain end. As any tool, they can be abused too.

They are not the most gracious of tools, but the work they are good at is about impossible to achieve by other means (and usually any other approach is then doomed to be a horrible mess thousand times worse than the machine).

The job is operating in conditions where classic wait states are forbidden.

I have to read touchscreen. To read the position, I have to exchange about 15 commands over SPI. I need good 100 readouts a second. I have to wait about 1 microsecond after each command, for respective busy flag to vanish before I can continue. There is also a number of other operations that must be attainable over the same interface, like setting contrast, changing modes, turning backlight on or off, reading temperature. If I performed while(BUSY_BIT); for each wait, I would eat up all the CPU in matter of moments. If I did sched_yield() or usleep(1), I would never attain the number of readouts I want. The only way is a finite state machine.

But there are ways to make the finite state machine play nice too. Hide the machine behind the scenes and give the developers functions to work with.

My job experience so far was dominated by 2 systems based on 3 different finite state machines.

1. a big web portal, where in each step you retrieve some data from the database, and basing on it prepare more queries. In the last step you use the data to generate HTML. Each task - a webpage module - was implemented as a PHP class inheriting from the engine. State was preserved in class variables. Each step was a separate function. At end of a step, stored queries were optimized and sent out to the engine, through caches, and the answers were provided back to the original.
2. an embedded device with many subsystems. Task Pump is used. Each module registers a handler that is called many times a second from the main loop. The handler may preserve state in static or class variables, with states. This cooperative multitasking allows for much smaller memory footprint than running all in separate threads, allows for manual prioritizing of tasks by registering them twice, and has the thread run at high priority, overshadowing the rest of the system.
3. semi-interpreter. That touchscreen. Function calls and their wait states are registered, but each is called only once, then removed from the program queue. The interpreter is called as a task of taskpump, executing a limited number of functions until encountering a function marked as a wait state (or exceeding the number of functions to be called). Then it continues until the wait state vanishes. Other tasks enqueue jobs as (sometimes long) sequences of functions to be executed, then wait for result. This way I can limit the number of states I need to create to about 4 where I need results. If the command is of "send away, never check result" like "set contrast", they don't need discrete states at all. So the actual states are "wait for event and register requested data", "wait for measurement" and "read results and assign them properly".

The code would be twice as simple and three times clearer if written structurally or sequentially. Except it would't work, or would work with abysmal performance.