Design for deriving one state-machine / double-dispatch classfrom another

Hello Group!

I am experimenting with a design for implementing a state machine in a
single class in such a way that a new state machine can be derived
from an existing state machine.

One part of this design has a cost that grows linearly with the depth
of the inheritance hierarchy. My specific question: Is there some way
to avoid this linear cost (while still respecting the basic design
philosophy)?

I give a complete and compilable example program at the end of this
post that illustrates the design and the question. I will ask my
question in more detail by quoting from the example program.

The basic design:

The state of the state machine is encoded as a pointer to a member-
function "state handler:"

int (mod_state_two::*state) (int event); // the state handlers are
the state

The first level of dispatch (discriminating on the state) in the
double dispatch occurs by calling the state-handler function pointed
to by the state variable:

int processEvent (int event) { return (this->*state) (event); }

(The int return type of the function-pointer signature and of
processEvent is just a non-essential convenience in my example.)

The second level of dispatch (discriminating on the event) occurs
because the state-handler functions contain switch statements that
switch on the event:

virtual int stateStart (int event) {
switch (event) {
case eZero:
state = &mod_state_two::stateZero;
return 0;
case eOne: // events can be ignored by certain states
// ignore
return 0;
default: // events can be rejected as erroneous by certain
states
throw ("invalid event");
}
}

This code is concise, efficient, reasonably readable, and manages to
implement the entire state machine in a single class. This last helps
make the code for a single state machine concise, and makes concise
the process of deriving one state machine from another.

(Miro Samek in his book "Practical Statecharts in C/C++" discusses the
trade-offs made by a number of state-machine implementations, and
advocates this pointer-to-member-function scheme for certain
purposes.)

When we derive one state machine class from another, we can re-use the
first level of dispatch (discriminating on the state) by making the
state-handler member functions virtual. In a good C++ implementation
there is no hierarchy-depth-dependent cost to having a state handler
called deep in the inheritance hierarchy resolve (because it is a
virtual function in the base class that has not been overridden) to
that of the root of the hierarchy. So far, so good.

However, in my design, in order for a derived state machine to re-use
the second level of dispatch (the switch statement that discriminates
on the event), it has to explicitly delegate that call to its
immediate base class. But that class may need to re-delegate the call
up the hierarchy, and so on. This is illustrated by the three-level
hierarchy in the example program: The root class is mod_state_two,
from which mod-state-three is derived, and then mod_state_four.

In mod_state_four (derived from mod_state_three):

virtual int stateZero (int event) {
switch (event) {
case eThree:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_four::stateThree);
return 3;
default: // delegate to base class
return mod_state_three::stateZero (event);
}
}

but further, in mod_state_three (which derives from mod_state_two):

virtual int stateZero (int event) {
switch (event) {
case eTwo:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_three::stateTwo);
return 2;
default: // delegate to base class
return mod_state_two::stateZero (event);
}
}

That is, when in state stateZero, mod_state_four delegates dispatching
on events (other than eThree) to mod_state_three's stateZero state
handler:

default: // delegate to base class
return mod_state_three::stateZero (event);

but mod_state_three then turns around and delegates this dispatch
(for events other than eTwo) to mod_state_two:

default: // delegate to base class
return mod_state_two::stateZero (event);

which, in this example, is the root of the inheritance hierarchy.

This is the cost grows linearly in the inheritance depth.

Is there a way to inherit both levels of the double dispatch without
incurring such a cost?

Here is the full, compilable example that uses this state-machine
design scheme and illustrates the questions asked above.

The example is contrived: the state machines implement modular
addition. For a state machine that adds numbers mod n, both the
states and the events correspond to the integers 0, 1, ..., n - 1. An
event x when processed by state y triggers a transition to state (x +
y) mod n.

Three levels are implemented in the example. mod_state_two is the
root of the hierarchy, and performs addition mod 2. mod_state_three
derives from mod-state_two, and mod_state_four derives from
mod_state_three, and they perform addition mod 3 and 4, respectively.

This example shows how the design works and what it accomplishes: You
can derive one state machine from another, reusing most of the logic
of what might be a very complicated base state machine, you can add
new states and events to it, and in the derived state machine you only
have to write code for the parts of the topology you actually modify.

The example is given as a single translation unit, and main() is a
simple test harness that instantiates and exercises a modular-addition
state machine.

Thanks for any corrections, design strategies, or general thoughts.

And... Happy State-Machine Hacking!


K. Frank


Example code:

==========

class mod_state_two { // addition-mod-2 state machine
public:
enum { // events
eZero = 0,
eOne = 1
};
mod_state_two() : state(&mod_state_two::stateStart) {}
int processEvent (int event) {
return (this->*state) (event);
}
protected:
int (mod_state_two::*state) (int event); // the state handlers
are the state
// the state handlers
// stateStart is just an example state that will be
// inherited unchanged by all the derived state machines
virtual int stateStart (int event) {
switch (event) {
case eZero:
state = &mod_state_two::stateZero;
return 0;
case eOne: // events can be ignored by certain states
// ignore
return 0;
default: // events can be rejected as erroneous by certain
states
throw ("invalid event");
}
}
// stateZero, etc., are the logically meaningful states
// for modular arithmetic
virtual int stateZero (int event) {
switch (event) {
case eZero:
state = &mod_state_two::stateZero;
return 0;
case eOne:
state = &mod_state_two::stateOne;
return 1;
default:
throw ("invalid event");
}
}
virtual int stateOne (int event) {
switch (event) {
case eZero:
state = &mod_state_two::stateOne;
return 1;
case eOne:
state = &mod_state_two::stateZero;
return 0;
default:
throw ("invalid event");
}
}
};

class mod_state_three : public mod_state_two { // addition-mod-3
state machine
public:
enum {
eTwo = 2 // the only new event
};
protected:
// the only new state
virtual int stateTwo (int event) {
switch (event) {
case eZero:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_three::stateTwo);
return 2;
case eOne:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_three::stateZero);
return 0;
case eTwo:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_three::stateOne);
return 1;
default:
throw ("invalid event");
}
}
// modify existing states to change topology
virtual int stateZero (int event) {
switch (event) {
case eTwo:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_three::stateTwo);
return 2;
default: // delegate to base class
return mod_state_two::stateZero (event);
}
}
virtual int stateOne (int event) {
switch (event) {
case eOne:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_three::stateTwo);
return 2;
case eTwo:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_three::stateZero);
return 0;
default: // delegate to base class
return mod_state_two::stateOne (event);
}
}
};

class mod_state_four : public mod_state_three { // addition-mod-4
state machine
public:
enum {
eThree = 3 // the only new event
};
protected:
// the only new state
virtual int stateThree (int event) {
switch (event) {
case eZero:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_four::stateThree);
return 3;
case eOne:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_four::stateZero);
return 0;
case eTwo:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_four::stateOne);
return 1;
case eThree:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_four::stateTwo);
return 2;
default:
throw ("invalid event");
}
}
// modify existing states to change topology
virtual int stateZero (int event) {
switch (event) {
case eThree:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_four::stateThree);
return 3;
default: // delegate to base class
return mod_state_three::stateZero (event);
}
}
virtual int stateOne (int event) {
switch (event) {
case eTwo:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_four::stateThree);
return 3;
case eThree:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_four::stateZero);
return 0;
default: // delegate to base class
return mod_state_three::stateOne (event);
}
}
virtual int stateTwo (int event) {
switch (event) {
case eOne:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_four::stateThree);
return 3;
case eTwo:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_four::stateZero);
return 0;
case eThree:
state = static_cast<int (mod_state_two::*)
(int)>(&mod_state_four::stateOne);
return 1;
default: // delegate to base class
return mod_state_three::stateTwo (event);
}
}
};

int main() {
mod_state_four sm4;
mod_state_two &sm(sm4);
int v;
v = sm.processEvent (mod_state_two::eOne); // ignored, v = 0
v = sm.processEvent (mod_state_two::eZero); // move to stateZero,
v = 0
v = sm.processEvent (mod_state_four::eThree); // v = 3 (0 + 3 mod
4)
v = sm.processEvent (mod_state_four::eTwo); // v = 1 (3 + 2 mod
4)
return v;
}

==========


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

on Tue Apr 03 2012, "K. Frank" <kfrank29.c-AT-gmail.com> wrote:

> This code is concise, efficient, reasonably readable, and manages to
> implement the entire state machine in a single class. This last helps
> make the code for a single state machine concise, and makes concise
> the process of deriving one state machine from another.

IMO what you end up with here is not particularly readable. Have you
had a look at http://boost.org/libs/msm? I think you'll find it more
readable, concise, and efficient to build state machines that way.

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Hi Dave!

On Apr 3, 2:37 pm, Dave Abrahams <d...@boost...com> wrote:
> on Tue Apr 03 2012, "K. Frank" <kfrank29.c-AT-gmail.com> wrote:
>
> > This code is concise, efficient, reasonably readable, and manages to
> > implement the entire state machine in a single class. This last helps
> > make the code for a single state machine concise, and makes concise
> > the process of deriving one state machine from another.
>
> IMO what you end up with here is not particularly readable. Have you
> had a look at http://boost.org/libs/msm? I think you'll find it more
> readable, concise, and efficient to build state machines that way.

Thank you for the reference to boost/msm. I was not aware of that
library. (I have looked at boost/statechart (boost/fsm) several
times.)

What I am trying to do is both much simpler -- I am implementing
a simple "flat" state machine, rather than a hierarchical state
machine (i.e., a UML statechart-style state machine) -- but also
somewhat different.

One of my key design goals is to be able to "derive" one state
machine from another, and have the derived state machine be able
to "inherit" as much of the base state machine's behavior as it
chooses.

Is the ability to derive one state machine from another naturally
supported by boost/msm? I have browsed the boost/msm documentation,
and nothing along these lines has caught my eye. (I have also
looked through the boost/statechart documentation and other
statecharts materials including Harel's statecharts paper, and
I haven't seen the concept of deriving one state machine from
another.)

Any pointers to reference materials or thoughts on how to derive
one state machine from another would be appreciated.

(As a side note, part of my focus is to explore how to implement
state machines from scratch, rather than how to implement state
machines on top of some state-machine infrastructure.)

> Dave Abrahams
> BoostPro Computinghttp://www.boostpro.com
> ...

Thanks again for your comments.


K. Frank


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

on Tue Apr 03 2012, "K. Frank" <kfrank29.c-AT-gmail.com> wrote:

> Is the ability to derive one state machine from another naturally
> supported by boost/msm?

You know, I'm not sure. I've pointed the Boost.MSM author at your post
and am hoping he'll answer.

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Hello Dave!

Thank you for your reply.

On Apr 6, 4:03 pm, Dave Abrahams <d...@boostpro.com> wrote:
> on Tue Apr 03 2012, "K. Frank" <kfrank29.c-AT-gmail.com> wrote:
>
> > Is the ability to derive one state machine from another naturally
> > supported by boost/msm?
>
> You know, I'm not sure. I've pointed the Boost.MSM author at your post
> and am hoping he'll answer.

I would love to hear from the Boost.MSM expert. I hope he has the time
to wander by and join the discussion.

> --
> Dave Abrahams
> BoostPro Computinghttp://www.boostpro.com

Following up on the original post, I do think I have a scheme that solves
my original problem, but it looks quite unattractive (at least to me).

The issue is how to have a multi-level inheritance hierarchy of classes
that implement a double dispatch without introducing a cost that scales
linearly in the depth of the hierarchy.

The best I can come up with -- which I don't like -- is to introduce a
virtual state-plus-event-handler function for each combination of state
and event.

Thus in the example, the base class, mod_state_two, handles states
stateStart, stateZero, and stateOne and events eZero and eOne.
Therefore, mod-state_two would have to define six virtual functions:

handle_stateStart_eZero
handle_stateStart_eOne
...
handle_stateOne_eOne

mod_state_three adds the state stateTwo and event eTwo, and would
therefore have to define six more virtual functions, specifically:

handle_stateStart_eTwo
handle_stateZero_eTwo
handle_stateOne_eTwo
handle_stateTwo_eZero
handle_stateTwo_eOne
handle_stateTwo_eTwo

(mod_state_three would also override one of the state-plus-event
handlers defined in the base class, handle_stateOne_eOne, because
it needs to change the topology of the corresponding transition.)

(In essence, the virtual-function table becomes the two-dimensional
transition table of the classic table-driven state-machine design.)

As in the original design, a derived state-machine class has
complete freedom to reuse or modify the topology of its base
state-machine class: it can add new states and events, and
override any of the base class's existing state-plus-event
handlers.

In this scheme, a derived state machine never _explicitly_ delegates
a call to its base class, instead relying on the c++ virtual-function
mechanism to do so, and thus avoids the inheritance-depth-dependent
cost (because the virtual-function mechanism doesn't have this cost).

But the code becomes much more verbose, cluttered up with all of these
state-plus-event handlers, of which many are vacuous no-ops.

I think, in a technical sense, this solves the original problem, but
it doesn't look like a good idea to me. I like the original design
better.

Maybe this is the best one can do with c++, but I'm still looking
for improvements.

Again, any thoughts would be appreciated.


K. Frank


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On 6 Apr., 22:03, Dave Abrahams <d...@boostpro.com> wrote:
> on Tue Apr 03 2012, "K. Frank" <kfrank29.c-AT-gmail.com> wrote:
>
> > Is the ability to derive onestate machinefrom another naturally
> > supported by boost/msm?
>
> You know, I'm not sure. I've pointed the Boost.MSM author at your post
> and am hoping he'll answer.

Sorry for the delay, Easter time...
The documentation is not talking about this subject because it has
never been requested, but MSM does allow quite a bit.
As a reminder, MSM is based on a transition table. States are
independent classes and are only logically part of a fsm if referenced
in the table. To try to draw it as UML, it would be States <-- fsm,
with <-- being a dependency.
For ex, see http://svn.boost.org/svn/boost/trunk...02.html#d0e334.

The only 2 things a state machine needs is an initial_state and a
transition_table typedefs.

The easiest way, which most people do, is to inherit a front-end state
machine class and provide a new table and initial state. States being
not part of the fsm, rewriting the table is sufficient and only means
a few lines of copying.

The second way, provided as example inside libs\msm\doc\HTML\examples
is in the directory distributed_table. In this case, the table is
distributed in the different states, and the fsm itself has none. A
state then looks like:
struct Empty : public msm::front::state<>
{
template <class Event,class FSM>
void on_entry(Event const&,FSM& ) {std::cout << "entering: Empty"
<< std::endl;}
template <class Event,class FSM>
void on_exit(Event const&,FSM& ) {std::cout << "leaving: Empty" <<
std::endl;}
void open_drawer(open_close const&);

struct internal_transition_table : mpl::vector<
// Start Event Next
Action Guard
//+-------------+---------+-------------+---------
+---------------------------+----------------------+
msm::front::a_row2 < Empty , open_close , Open ,
Empty,&Empty:pen_drawer >
//+-------------+---------+-------------+---------
+---------------------------+----------------------+
> {};
};

See here the distributed table. The drawback of this method is that it
forces strong coupling between states (like in your example) as they
need to know each other. MSM can do it, but it goes against its
philosophy of reuse and I think very few have really been interested
in this capability. But it allows a very good reuse while inheriting.

The third way requires a bit of metaprogramming: inherit a fsm, and
add/delete/change the transitions you need. Adding is easy, the other
2 harder. If we take as basis the example provided in the functor
front-end (http://svn.boost.org/svn/boost/trunk/libs/msm/doc/HTML/
examples/SimpleWithFunctors.cpp), let's say we want to add a
transition Stopped => Playing on an event called new_event. We can use
boost::mpl:ush_back:

// inherit from player_ fsm
struct derived_player : public player_
{
// new transition Stopped => Playing with event new_event
typedef Row<Stopped, new_event, Playing> added_row;
// new transition table based on player_ with an added transition
typedef
boost::mpl:ush_back<player_::transition_table,ad ded_row>::type
transition_table;
};


HTH,
Christophe


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Hi Christophe!

Thank you very much for your reply and comments.

On Apr 10, 12:19 am, Christophe Henry
<christophe.j.he...@googlemail.com> wrote:
> On 6 Apr., 22:03, Dave Abrahams <d...@boostpro.com> wrote:
>
> > on Tue Apr 03 2012, "K. Frank" <kfrank29.c-AT-gmail.com> wrote:
>
> > > Is the ability to derive onestate machinefrom another naturally
> > > supported by boost/msm?
>
> > You know, I'm not sure. I've pointed the Boost.MSM author at your post
> > and am hoping he'll answer.
>
> Sorry for the delay, Easter time...

And to you a belated Happy Easter!

> The documentation is not talking about this subject because it has
> never been requested, but MSM does allow quite a bit.
> ...
>
> The easiest way, which most people do, is to inherit a front-end state
> machine class and provide a new table and initial state. States being
> not part of the fsm, rewriting the table is sufficient and only means
> a few lines of copying.

If I understand you correctly in this approach one
completely rewrites the transition table.

If I take the perspective that the guts of the state
machine, i.e., its core "business logic" is its
topology (i.e., the transition table), then this
approach doesn't achieve my goal of letting a
derived state machine reuse the bulk of its base
state machine.

> The second way, provided as example inside libs\msm\doc\HTML\examples
> is in the directory distributed_table. In this case, the table is
> distributed in the different states, and the fsm itself has none. A
> state then looks like:
> struct Empty : public msm::front::state<>
> {
> template <class Event,class FSM>
> void on_entry(Event const&,FSM& ) {std::cout << "entering: Empty"
> << std::endl;}
> template <class Event,class FSM>
> void on_exit(Event const&,FSM& ) {std::cout << "leaving: Empty" <<
> std::endl;}
> void open_drawer(open_close const&);
>
> struct internal_transition_table : mpl::vector<
> // Start Event Next
> Action Guard
> //+-------------+---------+-------------+---------
> +---------------------------+----------------------+
> msm::front::a_row2 < Empty , open_close , Open ,
> Empty,&Empty:pen_drawer >
> //+-------------+---------+-------------+---------
> +---------------------------+----------------------+
> > {};
>
> };
>
> See here the distributed table. The drawback of this method is that it
> forces strong coupling between states (like in your example) as they
> need to know each other. MSM can do it, but it goes against its
> philosophy of reuse and I think very few have really been interested
> in this capability. But it allows a very good reuse while inheriting.

Okay, if I use the terminology that that rows of a
transition table are labelled by states and the
columns by events, am I right that in this scheme
each state contains its corresponding row in the
transition table? (To avoid any confusion, I am
using "row" here to denote a row in a two-dimensional
table. I believe what you are calling a "row" is what
I would call a "cell" or a "single entry" in the
transition table.)

In this case I have two questions:

First, in order to change the topology of my "derived"
state machine by changing one entry in the transition
table, would I then take the state that corresponds
to the row containing that entry and derive a new state
from it (or perhaps just replace the state with a new
state?), and rewrite the entire row of the transition
table in the derived state?

This would correspond in my example to overriding a
state-handler function in the derived state machine
and rewriting the entire switch statement that performs
the second level (discriminating on the event) of the
double dispatch. (This I can already do without incurring
the hierarchy-depth dependent run-time cost.)

So am I right that that in this scheme one can reuse
unchanged rows of the transition table, but not individual
unchanged cells?

Second, if an unchanged state references a modified (i.e.,
derived) state, does the msm framework know somehow to
use the modified state?

By way of explicit example, in my mod-2 modular-arithmetic
example when in state stateZero, event eOne triggers a
transition to state stateOne. In the mod-2 state machine,
eOne sends stateOne back to stateZero, but in the derived
mod-3 state machine, eOne sends stateOne to the new
stateTwo. So I have to modify the stateOne row of the
transition table. So in your scheme I would have a derived
(or new) version of the stateOne state class that contains
its modified row of the transition table. But now I go
back to the original stateZero class. Presumably it has
the following entry in its row of the transition table:

_row< stateZero, eOne, stateOne >

Do I now have to modify this part of the code for the
stateZero class to something like this:

_row< stateZero, eOne, derivedStateOne > // ?

If this is necessary, it looks like I still have to
rewrite the entire transition table, even though it
is distributed across the state classes.

Am I looking at this correctly?

> The third way requires a bit of metaprogramming: inherit a fsm, and
> add/delete/change the transitions you need. Adding is easy, the other
> 2 harder. If we take as basis the example provided in the functor
> front-end (http://svn.boost.org/svn/boost/trunk/libs/msm/doc/HTML/
> examples/SimpleWithFunctors.cpp), let's say we want to add a
> transition Stopped => Playing on an event called new_event. We can use
> boost::mpl:ush_back:
>
> // inherit from player_ fsm
> struct derived_player : public player_
> {
> // new transition Stopped => Playing with event new_event
> typedef Row<Stopped, new_event, Playing> added_row;
> // new transition table based on player_ with an added transition
> typedef
> boost::mpl:ush_back<player_::transition_table,ad ded_row>::type
> transition_table;
>
> };

Okay, I think I see what is going on here. (I confess
to not being familiar with boost::mpl, but the intent
seems pretty clear.)

Can you clarify how I would rewire an existing transition
(i.e., entry in the transition table)?

For example, in my modular-arithmetic example, how would
I rewire something in my mod-2 state machine like

_row< stateOne, eOne, stateZero >

to become

_row< stateOne, eOne, stateTwo >

in my mod-3 state machine?

If this scheme does let me modify individual cells of
the transition table (as well as add to the transition
table), then it looks like it would accomplish my design
goal. (And would do so without me needing to pre-define
all of the "no-op" virtual functions for each state-event
combination.)

> HTH,
> Christophe

Thank you. I appreciate your insights.


K. Frank


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Hello Christophe!

Again, thanks for sharing your wisdom.

I have a question about the low-level implementation of a
boost/msm state machine.

On Apr 10, 12:19 am, Christophe Henry
<christophe.j.he...@googlemail.com> wrote:
> On 6 Apr., 22:03, Dave Abrahams <d...@boostpro.com> wrote:
>
> > on Tue Apr 03 2012, "K. Frank" <kfrank29.c-AT-gmail.com> wrote:
>
> > > Is the ability to derive onestate machinefrom another naturally
> > > supported by boost/msm?
>
> > You know, I'm not sure. I've pointed the Boost.MSM author at your post
> > and am hoping he'll answer.
>
> Sorry for the delay, Easter time...
> The documentation is not talking about this subject because it has
> never been requested, but MSM does allow quite a bit.
> As a reminder, MSM is based on a transition table. States are
> independent classes and are only logically part of a fsm if referenced
> in the table. To try to draw it as UML, it would be States <-- fsm,
> with <-- being a dependency.
> For ex,
seehttp://svn.boost.org/svn/boost/trunk/libs/msm/doc/HTML/ch03s02.html#d....

Just as one can use template meta-programming, for example,
to unroll loops, I assume that msm gains efficiency
by using template meta-programming to "elide" various
levels of indirection and function calls that would
show up in a non-template implementation.

But after the template meta-programming has done its
work, how is the state machine then implemented? What
actually happens at run time?

The state machine is in some state. How is the state
encoded? (Integral value, function pointer, type of
a polymorphic variable, etc?) The state machine then
processes some event. How is the event encoded?

A double dispatch (state / event) still has to occur.
What actually happens?

To help simplify the discussion, let's consider a
flat (non-hierarchical) state machine that has
transition actions, but not entry or exit actions.

When an event is processed, a transition is triggered.
How does the double dispatch occur and cause the
appropriate action code to be executed? (Inline
executable code, function call, call through a
function pointer, etc.?) How does the state of the
state machine get set to the new state?

I guess another way of phrasing the question is if
I were to hand code the result of the compile-time
template meta-programming processing, what code
would I write?

> ...
> HTH,
> Christophe

Thanks for any insight into what is going on under
the hood.


K. Frank


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

> > The easiest way, which most people do, is to inherit a front-end
> > state machine class and provide a new table and initial
> > state. States being not part of the fsm, rewriting the table is
> > sufficient and only means a few lines of copying. >
> If I understand you correctly in this approach one
> completely rewrites the transition table.

Yes.

> If I take the perspective that the guts of the state machine, i.e.,
> its core "business logic" is its topology (i.e., the transition
> table), then this approach doesn't achieve my goal of letting a
> derived state machine reuse the bulk of its base state machine.

Yes and no. The bulk of the code (in lines of code), usually is in the
states, actions and guards.

> > The second way, provided as example inside
> > libs\msm\doc\HTML\examples is in the directory
> > distributed_table. In this case, the table is distributed in the
> > different states, and the fsm itself has none. A state then looks
> > like:
> > struct Empty : public msm::front::state<>
> > {
> > template <class Event,class FSM>
> > void on_entry(Event const&,FSM& ) {std::cout << "entering: Empty"
> > << std::endl;}
> > template <class Event,class FSM>
> > void on_exit(Event const&,FSM& ) {std::cout << "leaving: Empty" <<
> > std::endl;}
> > void open_drawer(open_close const&);
>
> > struct internal_transition_table : mpl::vector<
> > // Start Event Next
> > Action Guard
> > //+-------------+---------+-------------+---------
> > +---------------------------+----------------------+
> > msm::front::a_row2 < Empty , open_close , Open ,
> > Empty,&Empty:pen_drawer >
> > //+-------------+---------+-------------+---------
> > +---------------------------+----------------------+
> > > {};
>
> > };
>
> > See here the distributed table. The drawback of this method is
> > that it forces strong coupling between states (like in your
> > example) as they need to know each other. MSM can do it, but it
> > goes against its philosophy of reuse and I think very few have
> > really been interested in this capability. But it allows a very
> > good reuse while inheriting.
>
> Okay, if I use the terminology that that rows of a transition table
> are labelled by states and the columns by events, am I right that in
> this scheme each state contains its corresponding row in the
> transition table? (To avoid any confusion, I am using "row" here to
> denote a row in a two-dimensional table. I believe what you are
> calling a "row" is what I would call a "cell" or a "single entry" in
> the transition table.)

A "row" is a complete transition, with source state, target, event,
action and guard. In this approoach, a state contains a set of
transitions originating from this state.

> In this case I have two questions:
>
> First, in order to change the topology of my "derived" state machine
> by changing one entry in the transition table, would I then take the
> state that corresponds to the row containing that entry and derive a
> new state from it (or perhaps just replace the state with a new
> state?), and rewrite the entire row of the transition table in the
> derived state?

In this approach, there is not even necessarily a transition table in
the state machine, which means you can do whatever you want, derive a
new state or provide a new one. The state machine knows of its states
thanks to the explicit_creation typedef. In the doc example, all you
need in your state machine is:

typedef Empty initial_state; // to know where to start
typedef mpl::vector<Empty,Open> explicit_creation; // the states
contained in the fsm. MSM will look inside for a transition table

> So am I right that that in this scheme one can reuse unchanged rows
> of the transition table, but not individual unchanged cells?

You can provide a new state with either a new table, or Boost.MPL to
modify rows of an existing one, like I showed in my previous post.

> By way of explicit example, in my mod-2 modular-arithmetic example
> when in state stateZero, event eOne triggers a transition to state
> stateOne. In the mod-2 state machine, eOne sends stateOne back to
> stateZero, but in the derived mod-3 state machine, eOne sends
> stateOne to the new stateTwo. So I have to modify the stateOne row
> of the transition table. So in your scheme I would have a derived
> (or new) version of the stateOne state class that contains its
> modified row of the transition table. But now I go back to the
> original stateZero class. Presumably it has the following entry in
> its row of the transition table:
>
> _row< stateZero, eOne, stateOne >
>
> Do I now have to modify this part of the code for the stateZero
> class to something like this:
>
> _row< stateZero, eOne, derivedStateOne > // ?
>
> If this is necessary, it looks like I still have to rewrite the
> entire transition table, even though it is distributed across the
> state classes.
>
> Am I looking at this correctly?

You can still metaprogram if you feel like it. For example, if you use
Boost.MPL to find a row you want to modify, say we named it old_row:

typedef _row< stateZero, eOne, stateOne > old_row;

You can write:

typedef _row<old_row::Source,old_row::Evt,derivedStateOne >

You "only" need MPL. Frankly, I'd personally prefer to rewrite the few
lines of the state's table, but granted, it's less fun ;-)
> Can you clarify how I would rewire an existing transition (i.e.,
> entry in the transition table)?
>
> For example, in my modular-arithmetic example, how would I rewire
> something in my mod-2 state machine like
>
> _row< stateOne, eOne, stateZero >
>
> to become
>
> _row< stateOne, eOne, stateTwo >
>
> in my mod-3 state machine?

To continue on my last post, my table could become:
struct derived_player : public player_
{
// new transition Stopped => Playing
typedef Row<Stopped, new_event, Stopped> added_row_1;
typedef Row<added_row_1::Source,added_row_1::Evt,Playing> added_row;
// new transition table based on player_ with an added transition
typedef
boost::mpl:ush_back<player_::transition_table,ad ded_row>::type
transition_table;
};

HTH,
Christophe



--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

> But after the template meta-programming has done its
> work, how is the state machine then implemented? What
> actually happens at run time?
>
> The state machine is in some state. How is the state
> encoded? (Integral value, function pointer, type of
> a polymorphic variable, etc?) The state machine then
> processes some event. How is the event encoded?
>
> A double dispatch (state / event) still has to occur.
> What actually happens?
>
> To help simplify the discussion, let's consider a
> flat (non-hierarchical) state machine that has
> transition actions, but not entry or exit actions.
>
> When an event is processed, a transition is triggered.
> How does the double dispatch occur and cause the
> appropriate action code to be executed? (Inline
> executable code, function call, call through a
> function pointer, etc.?) How does the state of the
> state machine get set to the new state?
>
> I guess another way of phrasing the question is if
> I were to hand code the result of the compile-time
> template meta-programming processing, what code
> would I write?

To be honest, the idea is not mine but Dave's, so I hope I will do him
justice.
If you read Dave's and Aleksey's book, you
might see that the first level of the double-dispatch is done by the
templated process_event(), which makes process_event unique for
each event. This makes your first dispatch in O(1).
The second dispatching (state) is not done like in the book (which was
O(n)) but on the model of a more advanced example provided in the
Boost.MPL documentation. It amounts to building, for each event, an
array of pointers to static functions representing a transition, one
entry for each possible source state. A metafunction generates an
index for each state, so that dispatching on state also is O(1), which
is pretty much the best complexity you can get ;-)
Of course, MSM provides a lot of extra features to implement UML
niceties (like transition conflicts, submachines, etc.) but the
principle is still the same.

HTH,
Christophe


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

on Fri Apr 20 2012, Christophe Henry
<christophe.j.henry-AT-googlemail.com> wrote:

> To be honest, the idea is not mine but Dave's, so I hope I will do
> him justice. If you read Dave's and Aleksey's book, you might see
> that the first level of the double-dispatch is done by the templated
> process_event(), which makes process_event unique for each
> event. This makes your first dispatch in O(1). The second
> dispatching (state) is not done like in the book (which was O(n))
> but on the model of a more advanced example provided in the
> Boost.MPL documentation. It amounts to building, for each event, an
> array of pointers to static functions representing a transition, one
> entry for each possible source state. A metafunction generates an
> index for each state, so that dispatching on state also is O(1),
> which is pretty much the best complexity you can get ;-) Of course,
> MSM provides a lot of extra features to implement UML niceties (like
> transition conflicts, submachines, etc.) but the principle is still
> the same.

You did it justice of course, Christophe!

A few additional points:

* there are real scenarios where you don't know the event until
runtime, e.g. if events are queued somewhere. For those you need
an additional layer of dispatching. It's easy enough to build and
I presume MSM has some facility for that.

* The O(N) dispatch could turn out to be faster than the O(1) if the
number of states responding to any given event is very low.
However, I haven't done any measurements to support that.

* I'm pretty sure it's possible to eliminate one layer of indirection
in the dispatch by using C++11 constexpr.

Cheers,

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Hello Christophe!

Thank you for the clarification. I have a follow-up question,
below.

On Apr 19, 3:37 pm, Christophe Henry
<christophe.j.he...@googlemail.com> wrote:
> ...
> > Can you clarify how I would rewire an existing transition (i.e.,
> > entry in the transition table)?
>
> > For example, in my modular-arithmetic example, how would I rewire
> > something in my mod-2 state machine like
>
> > _row< stateOne, eOne, stateZero >
>
> > to become
>
> > _row< stateOne, eOne, stateTwo >
>
> > in my mod-3 state machine?
>
> To continue on my last post, my table could become:
> struct derived_player : public player_
> {
> // new transition Stopped => Playing
> typedef Row<Stopped, new_event, Stopped> added_row_1;
> typedef Row<added_row_1::Source,added_row_1::Evt,Playing> added_row;
> // new transition table based on player_ with an added transition
> typedef
> boost::mpl:ush_back<player_::transition_table,ad ded_row>::type
> transition_table;
> };

I see how to use mpl:ush_back to add transitions to an
existing transition table (or existing state machine), but
I'm still unclear on how to modify (or delete) an existing
transition.

So if I have

_row< stateOne, eOne, stateZero >

in my mpl::vector transition table, how to I modify my
transition table so that it contains

_row< stateOne, eOne, stateTwo >

instead?

I don't know enough about metaprogramming to answer the
question. Is it possible to modify the existing entry
in the mpl::vector? Or, barring that, is there a way
to delete the entry in question, after which one could
use mpl:ush_back to add the replacement row?

(As an aside, what happens if I have two entries in the
transition table for the same transition, i.e., for the
same current state and event, but different new states.
For example, what happens if my transition table contains
both

_row< stateOne, eOne, stateZero >

and

_row< stateOne, eOne, stateTwo >

where neither has a guard? Does the first (or, alternately,
the last) in the transition table take precedence, or do
things break somehow.)

> HTH,
> Christophe

Thanks. I appreciate your comments.


K. Frank


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Hi Christophe and Dave!

Let me reply to you both by replying to Dave's post.

On Apr 20, 10:16 am, Dave Abrahams <d...@boostpro.com> wrote:
> on Fri Apr 20 2012, Christophe Henry
> <christophe.j.henry-AT-googlemail.com> wrote:
> > To be honest, the idea is not mine but Dave's, so I hope I will do
> > him justice. If you read Dave's and Aleksey's book, you might see
> > that the first level of the double-dispatch is done by the templated
> > process_event(), which makes process_event unique for each
> > event. This makes your first dispatch in O(1). The second
> > dispatching (state) is not done like in the book (which was O(n))
> > but on the model of a more advanced example provided in the
> > Boost.MPL documentation. It amounts to building, for each event, an
> > array of pointers to static functions representing a transition, one
> > entry for each possible source state. A metafunction generates an
> > index for each state, so that dispatching on state also is O(1),
> > which is pretty much the best complexity you can get ;-) ...
> > ...

This is very interesting (to me, maybe not to others) to see
that you discriminate first on the event, and then on the state.

I have hand-coded state machines that worked this way. (Events
were handles -- typically function pointers -- to event-handler
functions, and the event-handler functions used a switch statement
to discriminate on the state.) For whatever reason, this felt
unnatural to me, and now I prefer to discriminate first on the
state, and then on the event. But I certainly can't give you a
good explanation of why I feel this way.

(Of course, as a user of msm, it really makes no difference to
me in which order the double dispatch in implemented under the
hood.)

Concerning complexity, if I understand things correctly, the
hand-coded pointer-to-member-function / switch-statement
state-machine implementation with which I began this thread
should also perform the double dispatch in O(1) (although
this is potentially implementation dependent). The state
variable is a pointer-to-member-function that is presumably
implemented as an offset into the vtable, so that should resolve
in O(1), and the switch-on-event switch statements in the
state-handler functions are presumably implemented with jump
tables, so that should also be O(1).

>
> You did it justice of course, Christophe!
>
> A few additional points:
>
> * there are real scenarios where you don't know the event until
> runtime, e.g. if events are queued somewhere.

I don't follow what you're saying here. Isn't the normal -- and
by far and away most common -- use case the one where you don't
know the events until runtime? Which gui button was clicked,
what signal came from some hardware controller, and so on?

Unless you're talking about something completely different
where the state machine is constructed at runtime. (I've seen
a number of state-machine frameworks that work this way. It's
certainly a legitimate approach, but it's not my preference.)

> For those you need
> an additional layer of dispatching. It's easy enough to build and
> I presume MSM has some facility for that.
> ...

{ Quoted signature removed -mod }

Thanks again for your answers and sharing your experience.


K. Frank


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

on Sun Apr 22 2012, "K. Frank" <kfrank29.c-AT-gmail.com> wrote:

>> A few additional points:
>>
>> * there are real scenarios where you don't know the event until
>> runtime, e.g. if events are queued somewhere.
>
> I don't follow what you're saying here. Isn't the normal -- and
> by far and away most common -- use case the one where you don't
> know the events until runtime? Which gui button was clicked,
> what signal came from some hardware controller, and so on?

I don't know what's most common. But, for example, it's very common
that you can attach different actions to different GUI buttons. So if
you can have one GUI button doing fsm.process_event(play()) and another
doing fsm.process_event(stop()), then discriminating the event has already
been taken care of for you "at runtime," by the GUI framework. There's
no need to pay the cost again in the FSM.

So I guess the answer is that it's probably most common that at some
level (in the hardware, if nowehere else) you don't know the events
until runtime, but it's also very common that something has already
given you a separate hook for each incoming event.

HTH,

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Hello Dave!

Thank you. That clears up my confusion.

On Apr 23, 12:16 pm, Dave Abrahams <d...@boostpro.com> wrote:
> on Sun Apr 22 2012, "K. Frank" <kfrank29.c-AT-gmail.com> wrote:
>
> >> A few additional points:
>
> >> * there are real scenarios where you don't know the event until
> >> runtime, e.g. if events are queued somewhere.
>
> > I don't follow what you're saying here. Isn't the normal -- and
> > by far and away most common -- use case the one where you don't
> > know the events until runtime? Which gui button was clicked, what
> > signal came from some hardware controller, and so on?
>
> I don't know what's most common. But, for example, it's very common
> that you can attach different actions to different GUI buttons. So
> if you can have one GUI button doing fsm.process_event(play()) and
> another doing fsm.process_event(stop()), then discriminating the
> event has already been taken care of for you "at runtime," by the
> GUI framework. There's no need to pay the cost again in the FSM.

Yes, that makes sense -- I now understand what you are saying here.
(Sorry for the misunderstanding.)

Do I take it correctly then -- reading between the lines -- that
when I write a line of code like

fsm.process_event(play());

the Boost.MSM framework uses template metaprogramming to dispatch
the event at compile time? I think I now better understand
Christophe's earlier comment. So the event is dispatched at
compile time, and then is the state dispatched at run time by
indexing in to an array of static function pointers?

> So I guess the answer is that it's probably most common that at some
> level (in the hardware, if nowehere else) you don't know the events
> until runtime, but it's also very common that something has already
> given you a separate hook for each incoming event.

Yes, I should have realized that this was what you were
talking about, because I've sometimes programmed state
machines this way in the past. Specifically (as I mentioned
in an earlier post) when events were event-handler functions
and the state machine first discriminated on the event, in
fact an event would be posted to the state machine by invoking
the event-handler function directly:

some_state_machine.event_three();

This approach has the advantage of being concise and
efficient, although it has the potential disadvantage
of being highly synchronous, in that a chain of events
can pile up on the call stack. For example, let's say
that when processing some "external" event, state_machine_A
posts event_one to state_machine_B, which then posts
event_two back to state_machine_A, which then posts
event_three back to state_machine_B. Then the call stack
looks like:

(top)
state_machine_B.event_three()
state_machine_A.event_two()
state_machine_B.event_one()
state_machine_A.external_event()
(bottom)

and the function call state_machine_A.external_event()
doesn't complete and exit until the processing of events
three, two, and one has completed.

Also, now I understand the motivation of your first point
in reply to Christophe, specifically where you say "e.g. if
events are queued somewhere."

Yes, when I've hand-coded state machines with event-handler
functions, and wanted to "defer" events, I had to set up a
separate facility to do so -- basically a queue of what were,
roughly speaking, function objects that wrapped the synchronous
event handler calls.

{ Quoted signature removed -mod }

Again, thank you for your thoughtful comments. This has been
most educational.


K. Frank


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]