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

Subject: Re: [boost] [MSM] Comparison with ad-hoc FSM implementation
From: Christophe Henry (christophe.j.henry_at_[hidden])
Date: 2009-12-10 18:58:20

Hi Phil,

>> I fully agree with Michael's point that more complicated constructs
>> are really messy to implement with ad-hoc techniques.

>Do we have any concrete examples of larger problems anywhere?  I would
>be interested to see them so that I can consider how I would implement them.

Sure. Please have a look in the MSM doc at the MsmSession_Handout.pdf.
At the last page, you'll see the description of an iPod nano. This
example was presented in the BoostCon hands-on session. We managed to
write a fsm representing a full mock-up in 90mn (of course we cheated
a bit as I had prepared something). And we immediately generated the
code.
Do you think it would be possible with an ad-hoc solution in such a
short time (or even double more)?

>> But on the construct presented by Phil I personally find a lot to criticize.
>> First of all, it is a mess.
>
>I would be much happier if you could please avoid using language like this.

Please excuse me but I fail to understand what you mean. Being not a
native speaker, I'd greatly appreciate some help as I wasn't under the
impression to use a rude language.

>> what really bugs me is the mix of fsm structure with
>> character processing.
>
>But in this application, the FSM is driven by the characters that are
>received - that is what it is all about.  Why do you want to separate
>it out into two things?

Because I consider that the purely fsm part of the application should
be separated from the character analysis. A close look at the functor
will show you that it handles character analysis and then generates an
event. The fsm then decides what to do with the event. A different fsm
can choose to reuse the code in another context. I find this pretty
natural. Character analysis on one side,  handling on the other.

>>>void process_event(const character_received_event& e) { ....
>>>void process_event(const sigwinch_event& e) { ....
>>
>> Having to write overloads in a template word??? No, thanks!
>
>Can you please explain why ?

I find it pretty clear that
template <class Event> void process_event(Event const&);

constitutes a better interface than (adding more events):
void process_event(const character_received_event& e) { ....
void process_event(const sigwinch_event& e) { ....
void process_event(const some_other_event& e) { ....
void process_event(const yet_another_other_event& e) { ....
etc.

>Consider the transition from the seen_escape state to the normal state,
>which occurs at the end of an escape sequence.  For this you would need
>a last_char_of_escape_sequence event.  You would need to consider this
>in your case statement above (e.g. letters normally do terminate the
>escape sequence but digits normally don't).  But this categorisation
>happens for received characters whatever state the machine is currently
>in.  So in the transition table you would need rules like this:
>
>row < normal,      escape_char,                      seen_escape >,
>row < normal,      last_char_of_escape_sequence,     normal >,
>row < normal,      not_last_char_of_escape_sequence, normal >,
>row < seen_escape, escape_char,                      seen_escape >,
>row < seen_escape, last_char_of_escape_sequence,     normal >,
>row < seen_escape, not_last_char_of_escape_sequence, seen_escape >,

The example seems to grow at will, but the issue stays the same. I
operated a seemingly small change, concretely:
case escape: state = seen_escape; break;

was replaced by a functor containing:
case escape: fsm.process_event(escape_char()); break;

Which I can repeat any time you set the state variable inside a case
statement. The only difference is that now, the code analysing the
character has no idea of the fsm structure, which means it can be
reused in another fsm. This is made possible by the use of a functor.
Otherwise, it's your algorithm, only organized in such a way that you
have a better chance of reuse in another fsm context.

Whatever, I just wanted to show another way of implementing the same
algorithm using MSM, with the same performance and a better chance of
reuse.
A bigger application will probably illustrate better the strength of MSM.
If you look at the iPod example, you'll see how the library will do
things which are very hard with an ad-hoc solution.
I'd be interested to see how an such implementation would solve this
problem. I think it might constitute a more interesting discussion
base.

Regards,

Christophe