[boost] Re: Finite state machine requirements

From: Andreas Huber (spam2002_at_[hidden])
Date: 2002-09-05 17:02:10

Hi David,

> Sorry, I'm late to the party. ;)

I guess the party is not going to happen here anyway, unless you'd call two
people (you and me) a party ;-).

The lack of interest for my proposal here at boost made me think more about
your approach to FSMs. Maybe everyone thinks a boost FSM should be
dynamically configurable? Or maybe I just overestimated the utility of state
machines in everyday programming (that's what boost libs are all about,
aren't they)? I don't know. What also made me question my approach more is
template code bloat. I guess I would carefully investigate the memory
footprint of a program using my approach vs. a program using your approach
if I had to develop for an embedded system. OTOH, tools such as Rhapsody do
something very similar with a code generator to what I do with templates.
That is, the framework bit of Rhapsody (the code residing in libs supplied
by ILogix) is essentially just classes encapsulating queues, threads and
timers. All the behavior (guards, sequence of entry- transition- and
exit-actions, ...) is generated anew for each state machine and Rhapsody
_has_ a reputation within the embedded world.

So I'm more or less at the same point I was when I started the
comp.lang.c++.moderated thread:
- I still strongly believe there should be something better than I've seen
so far.
- I'm less convinced that a fixed-layout framework is needed more than a
dynamically configurable framework.

One argument why I still somewhat lean towards a fixed-layout framework for
human-designed state machines is that a strong user code <-> statechart
relationship is enforced by my approach and that some of the state-chart
bugs could be caught at compile-time.
I know, you'd do this with appropriate builder-classes which do both:
enforce whatever compile-time rules you'd like to enforce _and_ build the
runtime data structure representing the FSM. However, I've never seen a
similar approach anywhere and it seems somewhat wasteful to me: Why would
you care to build an exact runtime-counterpart of something that is already
caught in compile-time relationships of the user code?
Another argument for fixed-layout is type-safe state-local storage. We've
used Rhapsody for our past project (an ATM), where all guards and actions
run in the same machine-global context (they are all non-static members
functions of the same class). As a result of this, you could come across a
state machine class having some 50+ data members, most of which were only
used in a small part of the machine (and worse: some of them even
reused!!!). I have always missed the ability to confine that data to the
state machine part that actually used the data. I think you can't do this
cleanly with a dynamically configurable framework. Thoughts?

> I've been doing some reading on Boost. I know we've already discussed
> the differences in our approaches in comp.lang.c++.moderated, so I won't
> go into that here. However, after looking through the BGL, I think it is
> a great candidate for representing an FSM. Add in the right traversal
> policy (take into account guards) plus functors for Actions and Guards,
> and you are basically done.

I haven't had a close look at BGL, but I guess you are right. Building the
graph from a given state-chart is probably not a terrible challenge and
graph-traversal should be quite efficient. However, you would have to
flatten state-machines to "fit" into a graph what could make deeply nested
state-machines use a lot of memory. I guess I will attempt to create a
primitive FSM framework building on top of BGL just too get a more balanced
view of the two approaches. However, I'm slowly but surely running out of
time as I will be away from reasonably equipped computers for 3 months by
October 3rd. Hopefully I know what I want by then ;-)...

Best regards,

Andreas