Re: [boost] [MSM] Comparison with ad-hoc FSM implementation

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;
        }
        break;
      case seen_escape:
        switch (c) {
          case 'H':  // say esc H = 'home'
                     cursor_pos = 0; break;
          .... lots more escape sequences ....
        }
        state = normal;
        break;
    }
  }

  void sigwinch(int rows, int cols) {
    screen.resize(rows,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 
like:

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 
this?

> 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...
noodles?

> 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.