[boost] Re: ANN: review of FSM library starts

From: Darryl Green (darryl.green_at_[hidden])
Date: 2005-02-24 04:06:05

Pavel Vozenilek <pavel_vozenilek <at> hotmail.com> writes:

> 
>     * What is your evaluation of the documentation?

The documentation is very good. The tutorial in particular is excellent,
and the progression from simple to more elaborate usage is well thought out.
The rationale is also good. Cross linking between the sections is used
judiciously to give a very comprehensive coverage of all topics without
duplication/fragmentation.

>       How easy (or hard) it is to understand library
>       features? What can be improved?

Very easy to understand.

>     * What is your evaluation of the design?

The design is very well suited to an important (perhaps under-appreciated
outside specific communications, control and simulation) class of fsm, where
there is significant context associated with a particular state (typically a
state having a number of inner states).

>       What features are supported better by
>       alternative FSMs?

Fast flat fsms to process simple events and having little additional context
are best implemented using other methods. However such implementations are not
difficult, and there are plenty of domain specific tools already (eg various
language recognisers). Note that it is perfectly reasonable to implement simple
fsms using boost.fsm, they just won't be as fast as some alternative approaches.

Also, there is space for dynamic state machines of various types.

> What could be added
>       (or removed) from the library?

I'm with Simon in the desire to declare all transitions including guards and
in-state reactions in the header (rather than just declare a custom reaction).
It isn't just automated tools that find this easier to follow - it simplifies
the process of doodling a transition diagram with one hand while scrolling
through the code with the other - or reading the doodle and touchtyping the
declarations. I think it is highly desirable that the full set of allowed
transitions be clearly visible from declarations alone. The documentation
suggests "Custom reactions can of course also be implemented directly in the
state declaration, which is often preferable for easier browsing." but this
breaks encapsulation unless the guard actually calls a number of sub-functions
in a way similar to Simon's suggested templated guard.

Andreas has previously pointed out a problem in providing in-state reaction
declarations in that any such transition is then forced to use an outer context
(incomplete type otherwise) which seem somewhat odd for an in-state reaction,
however I haven't actually found it to be a big problem in practice (innermost
states tend to be empty). Maybe it would be sufficient to provide a declaration
that simply specifies that a particular event is handled by an in-state
reaction (ie. similar to the custom reaction declaration), but with the handler
having no ability to return a transition object?

> 
>     * The library documentation contains
>       few not yet solved issues (name,
>       separating the library into two parts,
>       exception handling). What is you opinion here?

Naming: Please keep UML out of it ;-). High Level is simply too vague. How
about Matrioshka (a bit obscure I guess)... I don't think some unpronounceable
abbreviation intended to distinguish it from other possible fsm libraries is
useful.

Exceptions: Andreas has addressed all my concerns re. exception handling and
exit actions. I think the provided exception handling policies are both useful,
it really depends on whether the whole object (or a significant part of it) *is*
a state machine, in which case destroying it on an exception may be a bit
dramatic or whether it just uses one or more state machines which can reasonably
fail and recovery is outside of the fsm framework. I think these 2 policies
should adequately cover almost all uses of the library.

Breaking up the library: It is already in 2 parts to the extent that alternate
async machine schedulers can be used. The fact that the supplied one is not
useful for anything but use with the rest of the fsm library is fine. There is
no need to change this.

> 
>     * What is your evaluation of the implementation?

Very good.

>       Are there parts of code too obscure or
>       duplicating exiting Boost functionality?

No.

>       Can something be factored out to standalone
>       library or among general utilities?

Not that I can see.

> 
>     * Are there performance bottlenecks?

The various performance tradeoffs are well described in the rationale. I wonder
if there isn't some way of optimising empty (ie no associated context) states
better to improve performance, but it isn't a big issue for me.

>       Does the library design fit requirements
>       of real-time systems?

To the extent that anything that uses dynamic memory allocation does, yes. The
documentation does cover the issues well. In long running (uptimes of months)
soft real-time embedded systems, we are not seeing any problems (this is even
without using custom allocators). Running in an mmu-less environment would
likely require more careful memory management, which appears to be quite
practical to implement using custom allocators, though I haven't tried to do so.

> How is it useable for embedded systems?

On a reasonably memory rich but low performance system it is fine. The cost of
the fsm transitions is not significant compared to the associated processing in
this system.

>       Is the documentation clear on performance
>       tradeoffs?

Yes. Exceptionally so.

> 
>     * What is your evaluation of the potential
>       usefulness of the library? Can you compare
>       this FSM to other implementations?

The expressive power of this library is very high for some applications. I
haven't seen anything that comes close in this respect. The scaleability of the
library also appears to be very good.

We did experiment with an mpl-based fsm (extended version of the mpl example),
around the time Andreas first announced his fsm. While it is not fair to compare
a quick example to a full library submission, I think it is worth noting that
Andreas's library did address all the issues we found when trying to apply the
mpl fsm to a real-world problem.

>     * Did you try to use the library?  With what
>       compiler? Did you have any problems?

See Simon's review for details. I also played with it a bit (just examples)
using mingw gcc 3.4 - no problems.

>       Do you have tips for better support of older
>       compilers?

Don't bother ;-)

> What are possible portability problems?

None I can see. The core fsm shouldn't be platform dependent, and the scheduler
is a policy.

> 
>     * How much effort did you put into your
>       evaluation?

I've followed the evolution of this library closely and tried various versions
of it. I haven't tried to use all the features (history in particular) but I
have studied the documentation in detail and the code to a lesser extent.

>     * Are you knowledgeable about the problem domain?

Reasonably. I have some experience in telecommunications protocol
implementation, SDL etc. I've also done a fair bit of hardware fsm design.
 
> 
> And finally, every reviewer should answer this question:
> 
>     * Do you think the library should be accepted as a
>       Boost library?

Yes, it should be accepted.

Formal fsms seem never to catch on in general programming, but this library
makes fsm implementation very easy. The resource management and exception safety
features significantly simplify writing "industrial-strength" modern C++ using
fsms.

I should note that the alignment of Simon's and my responses is a little
unsurprising given that we are both working on the same project, though the
coincidence of our views on transition declarations is merely (statistically
significant?) coincidence.

Regards
Darryl Green.