Design for deriving one state-machine / double-dispatch class
from 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! ]