Applying the State pattern

Martin Vuille

unread,

Sep 1, 2000, 10:34:11 PM9/1/00

to

I am designing a number of classes with behavior that can be
most easily described in terms of FSMs so, naturally, I
thought of the State pattern and its myriad variants.

However, I'm stumped by one thing: is there a way to apply
this pattern in such a way that a class can be refined
later through inheritance?

For example, let's say that I want two variants of the
same class that differ from each other only in their
response to a certain message/event. Is there a way
to have both of these classes inherit from a common
class with a minimum of duplication?

What if the difference is in the FSM, i.e. one class
needs an additional state?

Any thoughts appreciated.
MV

Charles Rapp

unread,

Sep 2, 2000, 10:27:51 AM9/2/00

to

Martin Vuille wrote:
<snip>

> For example, let's say that I want two variants of the
> same class that differ from each other only in their
> response to a certain message/event. Is there a way
> to have both of these classes inherit from a common
> class with a minimum of duplication?
>
> What if the difference is in the FSM, i.e. one class
> needs an additional state?
>
> Any thoughts appreciated.
> MV

Martin,

According to the state pattern, a class interacts with the state map via
a Context class. Since your classes differ on in behavior (they have
different FSMs), you *can* use inheritance and each derived class will
contain a different FSM context:

class BaseClass
{
// Put common method and data here.
}

class DerivedClass1 : public BaseClass
{
FSMContext1 *_fsm;

DerivedClass1()
: BaseClass()
{
...
// See "Design Patterns" pp. 305 - 313
// re: State pattern.
_fsm = new FSMContext1();
...
}

// If you want to issue a transition, then ...
void handleEvent(Event e)
{
_fsm->transition(this, e);
}
}

DerivedClass2 will be similar.

Regarding your second question, if the FSMs are different, then you will
need to create two different FSM context classes and all the concrete
states. I know there is the idea regarding have one FSM inherit and
extend a base FSM but I that idea does not make sense to me. While the
State pattern shows how to implement an FSM via objects, an FSM is not
object-oriented - it's a finite state machine.

I hope I've help to resolve your questions.

<SOAPBOX>
Now, an advertisement for some open source software.

Do you like the State pattern but hate updating it?
How about maintaining all those concrete classes?
Do you have the time to add a new transition?

The State pattern is great - until you start to implement a
large or complex FSM. Then writing all those concrete classes
*almost* exactly the same is more busy work than programming.

That's where SMC - the State Map Compiler comes in. It takes
an FSM description and generates the State pattern classes
for you - in C++ or Java or [incr Tcl] (more languages are
being added). Plus SMC adds the following features:

+ Multiple state maps per FSM allowing you to break your FSM
down into easier-to-understand parts.
+ "push" and "pop" transitions - you can push to a state much
like a subroutine call and later pop (return) back to the
original calling state.
+ Transition guards - only if the guard is true will that
transition occur.
+ Default transitions - you only have to define those
transitions which make sense for a state and use the
default mechanisms for the rest.

SMC is available for download from http://smc.sourceforge.net.
The programmer's guide is also available on-line at that
website.
</SOAPBOX>

--
Chuck Rapp
ra...@acm.org

Martin Vuille

unread,

Sep 2, 2000, 9:31:33 PM9/2/00

to

In article <39B10DE2...@acm.org>, ra...@acm.org wrote:

>According to the state pattern, a class interacts with the state map via
>a Context class. Since your classes differ on in behavior (they have
>different FSMs), you *can* use inheritance and each derived class will
>contain a different FSM context:
>
> class BaseClass
> {
> // Put common method and data here.
> }
>
> class DerivedClass1 : public BaseClass
> {
> FSMContext1 *_fsm;
>
> DerivedClass1()
> : BaseClass()
> {
> ...
> // See "Design Patterns" pp. 305 - 313
> // re: State pattern.
> _fsm = new FSMContext1();
> ...
> }
>
> // If you want to issue a transition, then ...
> void handleEvent(Event e)
> {
> _fsm->transition(this, e);
> }
> }
>
>DerivedClass2 will be similar.

This is not how I had interpreted the GoF's description of the
State pattern. In my mind, DerivedClass1 _is_ the Context Class,
i.e. the class that the rest of the system sees and uses. I
don't see what benefit is provided by the FSMContext1 class
above.

>Regarding your second question, if the FSMs are different, then you will
>need to create two different FSM context classes and all the concrete
>states. I know there is the idea regarding have one FSM inherit and
>extend a base FSM but I that idea does not make sense to me.

It may not make sense in terms of an IS-A relationship, but what I'm
really after is a mechanism for reusing the implementation of a
class that is implemented as an FSMs.

What I have come up with so far is to define a vector
of pointers to the FSM's concrete states in the Context class, so
that the concrete states do not refer to specific concrete state
instances. This allows polymorphism in the concrete states and would
allow me to to reuse the bulk of the concrete state classes and
modify the ones I need to modify.

Each derived Context class' constructor would populate the list
of states with pointers to the appropriate state instances for
that derivative's FSM.

By using the Template pattern on the Context class for the methods
implementing the FSM actions, the actions of the base FSM can be
overriden in derived FSM's when necessary.

I haven't yet figured out how the concrete states would refer
to this list of next state pointers to set the next state.

Only thing is, this is anything but elegant, or easily comprehensible.

delr...@my-deja.com

unread,

Sep 5, 2000, 5:11:42 PM9/5/00

to

In article <96808270...@news.aei.ca>,
mar...@jpmvrealtime.com (Martin Vuille) wrote:
[snip]
>
> It would be more accurate to state it thus:
>
> I have two classes of objects that are variants of a base class and
> are therefore derived from that base class.
>
> The objects' behaviour is best described by an FSM (because the
> objects represent FSMs.) The two variants have very similar (say 80%)
> but not identical FSMs.
>
> What is the best way of implementing these objects to avoid as much
> as possible any duplication of the common 80%.
>
> MV
>

Wow. That's a pretty neat problem. Here's a suggestion:
The different state objects represent different behavior sets.
If the BEHAVIOR of the two objects is pretty much the same in
a given state, then you want that state represented by the same state
class. How do you make it connect to a different follow-state?
By having a pointer to the appropriate follow-state as a member of
the preceed-state. That way you can run the same code, just instantiate
the two instances of the state class with different follow-states. This
requires that you have one class which knows (or reads from a file) the
entire FSM. This also makes it more difficult to use the flyweight
pattern in support of the state pattern, which is a common
implementation.

If you have two objects with the same FSM, but different behavior when
they are in the same state, then you really aren't duplicating code,
and you do have to write them independently.

Hope this helps. Very cool problem.

Cheers,
delrayva

Sent via Deja.com http://www.deja.com/
Before you buy.

Robert C. Martin

unread,

Sep 6, 2000, 10:01:49 PM9/6/00

to

"Martin Vuille" <mar...@jpmvrealtime.com> wrote in message
news:96786205...@news.aei.ca...

> I am designing a number of classes with behavior that can be
> most easily described in terms of FSMs so, naturally, I
> thought of the State pattern and its myriad variants.
>
> However, I'm stumped by one thing: is there a way to apply
> this pattern in such a way that a class can be refined
> later through inheritance?
>
> For example, let's say that I want two variants of the
> same class that differ from each other only in their
> response to a certain message/event. Is there a way
> to have both of these classes inherit from a common
> class with a minimum of duplication?
>
> What if the difference is in the FSM, i.e. one class
> needs an additional state?

Yes, there is a way. See "Three Level Finite State Machine", in the "PLOP
94 Submission" in the "publications" section of http://www.objectmentor.com.
This paper shows how the state pattern can be extended in two different
ways. One extention changes the wiring of the FSM, the other changes the
actions of the FSM. Both extentions can be applied simultaneously.

--

"One of the great commandments of science is:
'Mistrust arguments from authority.'" -- Carl Sagan