Before tackling a seemingly complex code problem with lots of functions and complex logic, Jeff Cogswell recommends trying a finite state machine – a set of states and appropriate rules and actions that go with those states – to greatly simplify your coding. Service oriented architectures sound complicated and daunting, but they’re not so hard to implement. The concepts involved are actually fairly simple, and this article describes them by using examples drawn from the networking domain. Software consultant Stephen B. Morris describes some of the principles of service orientation in the down-to-earth contexts of C++ and networking.
Finite State Machines in C++; Generic C++ for Networks
About The Author
Eugenia Loli
Ex-programmer, ex-editor in chief at OSNews.com, now a visual artist/filmmaker.
Follow me on Twitter @EugeniaLoli
The article itself is quite nice. The following things are missing for me: deterministic vs nondeterministic FSMs, FSM types (cyclic, acyclic) and FSM minimization algorithms (at least overview).
I use Flex+Bison to code parsers most of the time, because they can unfold even complex expressions.
The ideal FSM class set for me would be 🙂
[code]
FSM * fsm = new FSM();
Rule * rule1 = fsm->addRule(“foo”);
Rule * rule2 = fsm->addRule(“bar”);
Rule * rule3 = fsm->addRule(rule1,AND,rule2);
fsm->optimize();
[/code]
WARNING – OSNew’s parser doesn’t allow me to write angle brackets, not even with entities. I used a pair of {} instead.
If you only wat to write parsers, there’s a C++ framework named Spirit which lets you write straight C++ code which mimics EBNF expressions.
Spirit is here: http://spirit.sourceforge.net/
The code you wrote might be expressed the following way, with Spirit:
rule{} rule1 = str_p(“foo”);
rule{} rule2 = str_p(“bar”);
rule{} rule3 = rule1 & rule2;
Although I’m not sure you really wanted to say ‘AND’ over there, as in that case the grammar vould be a void set (“foo” and “bar” yelds NIL).
If you inteded to match “foo” followed by “bar”, then you could write
rule{} rule3 = rule1 >> rule2;
Edited 2006-04-24 07:58
Boost::Spirit is a very nice recursive-descent parser framework, but unfortunately recursive-descent parsers are not suitable for large grammars. They are slow, because they have to backtrack all the time (unless they are predictive), and the stack can easily be exhausted, especially in recursive definitions.
What would be nice is a Spirit-like framework that automatically builds a state machine from the expression tree. I am working on this, but it is extremely difficult.
State machines are of great interest to me these days.
I’m going to be involved in a project implementing some Event-Driven Architecture concepts in addition to SOA.
Some reading has led to some interesting discussion threads on the web, notably:
http://www.javalobby.org/java/forums/m91987260.html
“Effectively I’m designing my client application to be an event driven state machine with respect to processing in-coming messages and user interface interactions. A completely event driven application tends to be consistent in the manner of its design and implementation. Consistency assist comprehension. ”
“Event handling is thus the fundamental atomicity of the app design.”
“[W]e’ve just turned the application into this generic message processing engine. Functional test that puppy to your heart’s delight.”
Excellent stuff when you are trying to piece together a complex enterprise application. As the last quote indicates, this fits in really well with test-driven design too.
Other interesting software to look at is the Enlightenment window manager, which also relies heavily on events, and the Pawn language, which supports states and automatons (http://www.compuphase.com/pawn/pawn.htm)
Software for CMS detector at CERN (high level event trigger) is based on finite state machine structure. IMO, producing software in that form pays back later, because it is much easier to read and mantain such code (code blocks are more logically arranged), not to mention that controlling and monitoring the software is easier.
Maybe linux init system should be FSM based, i.e. it could be clearly defined how something starts and how system can know when it has reached functional state, or if it doesn’t work.
More info about the framework used for CMS software:
http://xdaqwiki.cern.ch