Boost logo

Boost :

Subject: Re: [boost] [MSM] Comparison with ad-hoc FSM implementation
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2009-12-09 16:27:24

Hi Christophe,

Thanks for your detailed reply. I think it's important that you
add some sort of basic rationale of this sort to the documentation -
you need to evangelise what you believe are the advantages of the
library from first principles to its potential users.

I'm just going to pick up on a couple of points, mainly because I
don't know enough about UML to comment on the rest.

Christophe Henry wrote:
> - events containing data. In your case, you are more or less forced to
> choose between the O(1) (which you did) and forgo event data or the
> O(n) (chosen by Rhapsody) at a speed cost. Metaprogramming techniques
> allow us a O(1) with event data.

I'm not sure how true that is.

To make this concrete, let me discuss the terminal emulator FSM
that I described in the Boost.FSM review. This has one main event,
"character received", that carries the character as data. There
are a few other events such as "SIGWICH" (GUI terminal size changed
by user). For most "character received" events in most states, the
action is to insert the recieved character at the current cursor
position and advance the cursor. When the "escape" character is
received the FSM changes to another state in which the subsequent
characters are processed differently.

I would implement this something like:

struct terminal_fsm {

  enum state_t { normal, seen_escape, ... };
  state_t state;
  Screen screen;
  Position cursor_pos;

  void character_received(char c) {
    switch (state) {
      case normal:
        switch (c) {
          case escape: state = seen_escape; break;
          .... more special characters like tab, newline etc ....
          default: screen[cursor_pos] = c; ++cursor_pos; break;
      case seen_escape:
        switch (c) {
          case 'H': // say esc H = 'home'
                     cursor_pos = 0; break;
          .... lots more escape sequences ....
        state = normal;

  void sigwinch(int rows, int cols) {
    // it would be a better example if this did something depending on
    // the state; use your imagination...


This is O(1). Of course a difference is that it has different
entry points for the different events. This doesn't seem unreasonable
to me, but if you wanted a single entry point you could do something

struct character_received_event {
  char c;
struct sigwinch_event {
  int rows, cols;

void process_event(const character_received_event& e) { ....
void process_event(const sigwinch_event& e) { ....

Now you can call process_event() with events of either type.

How would you do this with MSM? Something like this presumably:

row < normal, character_received_event, seen_escape, none, &is_escape_char >,
row < normal, character_received_event, normal, &insert_at_cursor_and_advance >,
row < seen_escape, character_received_event, normal, &cursor_home, &is_H >,
row < seen_escape, character_received_event, normal, none >,
row < any, sigwinch_event, unchanged, &resize_screen >

(I'm guessing that the un-guarded row applies when none of the guards
match for a particular state-event pair, and presumably there is some
way of matching any state as in the last row.)

When this is extended to include all the other special characters and
escape sequences, you'll have lots of rows that have the same state-event
pair but different guards, each testing the character in the
character_received_event for a particular value. It looks to me as if
it will do this in O(N), not O(1). Or is there some other way of doing

> And if you want to implement all these features in a switch/case, your
> code will quickly become terrible. You'll have to issue guidelines on
> how to implement them, each developper will have to redo the same
> again and again with the corresponding flow of bugs (what if I forget
> a "break"? Uh oh) and low productivity (not even talking about
> documentation).

C++ provides many ways to shoot yourself in the foot, as we all know.

I am reminded of the section in the C++ FAQ that says, paraphrasing:

Q: Java has the "final" keyword that makes it impossible for a subclass
to override a method. How do I do that in C++?

A: Write a comment that says "Do not override this method in subclasses".
If that doesn't work, write a comment that says "If you override this in
a subclass you will be fired."

That's not to say that anti-foot-shooting is a bad thing. I use
boost::noncopyable a lot, for example. In my experience of implementing
state machines, I have not encountered the "terrible" code that you
imagine (or "spaghetti" and Andrey described it in the FSM review). This
may be a matter of taste: one person's spaghetti is another's... err...

> Do we agree that this proves the need of a library?

I can see that some believe they need a library to do this; personally
I might choose not to use it, but that shouldn't bother you (and doesn't
suggest that it should not be in Boost). You are welcome to try to
convince me that it has benefits that I have not yet seen....

Regards, Phil.

Boost list run by bdawes at, gregod at, cpdaniel at, john at