Hi Darryl Thanks for you review!

...

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.

Ok, I'll implement something like that, but it will take a while. I think there are more important things that should come first (like e.g. serialization).

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?

This has recently occurred to me also. I'll implement an in-state reaction the way you suggest in the very near future.

...

* 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.

Ok, noted. I now also lean more towards keeping fsm.

...

* 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.

I can't see how at the moment (the often empty innermost states are implemented differently already).

...

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).

That's very interesting to hear! I would have expected you seeing memory fragmentation problems within days. Could it be that the default operator new of your platform does some pooling internally? Best Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

Hi Jeff

I'm reviewing the FSM library and I'm wondering if there is any way for a transition to get a reference to the enclosing state machine. I couldn't see a way to do this in the docs.

This is explained right above the section heading "Getting state information out of the machine". Admittedly this might be a little hard to spot: <quote> Similar to when a derived class object accesses its base class portion, context<>() is used to gain access to the direct or indirect context of a state. This can either be a direct or indirect outer state (e.g. context< Active >()) or the state machine itself (context< StopWatch

()). </quote>

In addition, if you don't want to explicitly mention the StopWatch class, you can also use simple_state::outermost_context().

The reason I'm think I would like to get a reference to the machine itself is that I can see an alternative design that might be 'simplier'. Consider the following:

using boost::posix_time;

class StopWatch : fsm::state_machine< StopWatch, Active > { public: StopWatch() : m_elapsed(0,0,0), m_last_started(not_a_date_time) {}; time_duration elapsed() const { return m_elapsed; } private: //some sort of friend access that allows states to call these methods friend StopwatchState; void reset() { m_elapsed = time_duration(0,0,0) }; void start() { m_last_started = second_clock::local_time(); } void stop() { m_elapsed += second_clock::local_time() - m_last_started; }

time_duration m_elapsed; ptime m_last_started; };

The idea would be that the various transition constructors would

I guess you mean state constructors.

simply dispatch back to the stop watch machine. The structure of the machine would naturally prevent the calling of stop() before start() which would result in incorrect results (not_a_date_time - some_valid_time). And it would also prevent other erroneous sequences such as start(); start(); step();

Of course this will break the mapping to UML states and might be a bad idea,

I don't think this breaks any mapping to UML. Also, I don't think this is a bad idea at all. The functionality StopWatch implements is so simple that it can easily be implemented without the help of FSMs at all. So, the example kind of overuses the librarys' features to show the functionality. It's a classical "school example" (not sure whether one says this in English).

but I'm just trying to explore exactly how the library can be used. And maybe it would actually remove the need for the Active state. Anyway, thoughts?

Of course you can easily get rid of Active, when you put the variables in the state_machine<> subtype, as you did.

One small note, it would be nice if there was a second version of the UML diagram for the example that shows the transition details (that is, running exit updates active.elapsed) so that the code mapping was more obvious.

Ok, noted. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

Jeff Garland wrote:

...

I don't think this breaks any mapping to UML. Also, I don't think

Hmmm, ok. I was thinking the mapping was 'mechanical'. States/Transitions map to bubbles / lines respectively, etc.

It usually is. There are a few limitations (see Limitations in the Rationale) that rarely prevent you from performing the mapping purely mechanically. When I said that what you proposed doesn't break any UML mapping I meant the process of *moving* the variables from Running/Active into the FSM. Accoring to UML, auxillary state variables are stored in one place, which is accessibly from all states of a particular FSM (usually the state machine object). So, having variables in states is "un-UML" already.

...

So, the example kind of overuses the librarys' features to show the functionality. It's a classical "school example" (not sure whether one says this in English).

Understood. Getting an example of the right level is extremely difficult and I think overall you've done an excellent job in the tutorial. Of course the interesting design question is, at one point does the obvious increase in code complexity make using the library 'worth using'?

I guess you mean the increase in complexity compared to the traditional ways of implementing FSMs (nested switch case, state pattern, etc.). I think there's an increase only for small simple machines, like StopWatch. I think there is a (sometimes dramatic) reduction of complexity for bigger (and more real-world) machines.

For this discussion I'm presuming that there is no automated code generation which obviously changes things.

Currently there's no code generation and I doubt there'll ever be such a tool (I personally wouldn't use it). IMHO, a reverse engineering tool would be *much* more useful.

And, of course, there's no right answer to the question -- which is why I was exploring my implementation options to understand how the code complexity / mapping would change if the state was concentrated in a single class instead of distributed amoungst the states.

Usually, having variables concentrated in one place increases the complexity, because you then have to manage access and lifetime manually. Plus, the class hosting the variables becomes a change hotspot (during development you often need to add/remove/change variables). In the StopWatch example, you only have the "problem" that the startTime_ variable is valid only when the FSM is in the Running state. In bigger FSMs, like e.g. Camera, you might have an awful lot such variables, most of which are only used in a tiny part of the machine. Even worse, you might have multiple people working on parts of the same FSM. Joe simply doesn't care what variables Bob needs for the operation of his part of the machine.

So the other general design question is -- when is it better to but the variables asoociated with the machine in a state class versus pushing them up to the machine? Again there may be no answer here, but maybe someone that has implemented real code using fsm would have a design heuristic...

You usually make variables as local as you can (i.e. push them towards innermost states as much as possible). There would be more to say here but I'll be off soon. More on this later... Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

Jeff Garland wrote:

...

I guess you mean the increase in complexity compared to the traditional ways of implementing FSMs (nested switch case, state pattern, etc.). I think there's an increase only for small simple machines, like StopWatch. I think there is a (sometimes dramatic) reduction of complexity for bigger (and more real-world) machines.

I addressed what I meant by complexity in my response to Darryl. The thing is since we don't have an example of bad code that can be simplified by an fsm to compare agaisnt in the docs and we can all think of easier ways to write the StopWatch I worry that people will be put off.

The tutorial is primarily addressed to people who already have had exposure to FSMs (and also had to implement them one way or another). You are right, a beginner with only theoretical or even no prior knowledge about FSMs would probably shake his head before even following through the StopWatch example. I've spent quite some time thinking how I could also address newbies but have come to the conclusion that this would require a separate document at least as large as the tutorial.

So I think the remedy is to just say that stopwatch is too simple to bother with fsm, but with bigger state machines there is significant advantage.

I will try to do that, in particular I'll try to explain more thoroughly the issues with global variables.

...

Currently there's no code generation and I doubt there'll ever be such a tool (I personally wouldn't use it). IMHO, a reverse engineering tool would be *much* more useful.

Perhaps. If there was an XMI (UML to fsm generator or another state definition language) it might be easy to generate.

I think that a graphical state chart --> code generator surely helps beginners to get started. It provides them with *skeleton* code very soon. However, the generated skeleton is unlikely to do anything useful (I expect the generated code to be similar to the one right before the "State-local storage" heading). To get the code to do something, the programmer needs to fill statements into the action bodies. To be of help after doing so, the generator needs to be pretty sophisticated. To me, this seems too much work for something that can just as easily and probably faster be done manually. Sure, the initial effort to get something to compile is a little higher without a generator, but only a little.

...

You usually make variables as local as you can (i.e. push them towards innermost states as much as possible). There would be more to say here but I'll be off soon. More on this later...

Ok, good. I think this sort of discussion would be useful in the FAQ or somewhere in the docs.

Agreed. BTW, I think Darryl's take on variable scoping and heuristics hit the nail on the head. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

Hi Rob

...

The tutorial is primarily addressed to people who already have had exposure to FSMs (and also had to implement them one way or another). You are right, a beginner with only theoretical or even no prior knowledge about FSMs would probably shake his head before even following through the StopWatch example. I've spent quite some time thinking how I could also address newbies but have come to the conclusion that this would require a separate document at least as large as the tutorial.

A tutorial is typically assumed to be addressed at newbies. If you are aiming at a different, more advanced audience, just say so. That should eliminate the confusion.

I think I am saying so: http://tinyurl.com/3kkog (Audience)

To avoid misconceptions, a disclaimer stating that the StopWatch example is too simple to benefit much from Boost.FSM, but serves to show how to use the library, would probably be a good idea.

It seems that you haven't read the whole post. I've already agreed with Jeff that I will write something in this direction. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

Rob Stewart wrote:

...

I think I am saying so: http://tinyurl.com/3kkog (Audience)

I don't think that quite does it. The difference is that there you say that you assume familiarity with the subject matter and terminology, but nothing about experience. It is the latter that would permit the reader to recognize the StopWatch example as a toy and to map the code in the example to FSMs previously implemented other ways.

Fair enough. It is explained a little better in the rationale but I guess that would be too technical for a tutorial. I'll see what I can do...

...

...

To avoid misconceptions, a disclaimer stating that the StopWatch example is too simple to benefit much from Boost.FSM, but serves to show how to use the library, would probably be a good idea.

It seems that you haven't read the whole post. I've already agreed with Jeff that I will write something in this direction.

Actually, I did read it, but I was trying to suggest the flavor of what you might add to the document.

Ok, noted. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.

On Sun, 27 Feb 2005 11:40:52 +0000 (UTC), Darryl Green wrote

When the obvious increase in code complexity is smaller than the obvious decrease in code complexity?

I really need to ask - an obvious increase in complexity over what? I have seen some truly complex code arise from *not* using an fsm framework in some form or another.

The context of my comment was with respect to the stop watch example. I think we are all in agreement that the stop watch is too simple for the benefits of increased complexity required to use fsm. And I'm thinking we might want to say something about that in the docs -- I'm afraid alot of developers would be scared away looking at the code. A bunch of us understand that once the state machine gets a little more complicated the hand solutions tend to get ugly and buggy, but In particular I was thinking of some of the 'scary' code as: double ElapsedTime() const { return state_cast< const IElapsedTime & >().ElapsedTime(); } //class running virtual double ElapsedTime() const { return context< Active >().ElapsedTime() + std::difftime( std::time( 0 ), startTime_ ); } One part of the increased code complexity is just getting to understand the idioms to access other states. The other part is that that originally threw me was the locations of the time calculation functions. It wasn't obvious to me why I would code the addition to elapsed time was in the destructor of the Running state versus somehow making it part of the running->stopped transition. In this case I was thinking about how I would explain the rules of thumb to a 'junior' developer that actaully had to write the behavioral code. BTW, I think part of my trouble might have been that the code context< Active

is introduced before it is explained in the tutorial. So I think I got distracted trying to understand what that code meant...

My attempt at a heuristic is that one should consider using the fsm libary when:

1) There are more than a handful of transitions per state

2) There are more than a handful of states

3) The state space is naturally hierarchical

4) There is substantial context associated with (groups of) states

If you have only (1) or (2), it is likely that the problem doesn't warrant using boost fsm. If you have (1) and (2) it is worth at least thinking about using boost fsm, with substantial size or the presence of either of the other 2 features being enough to make it pretty much an immediate choice.

That's pretty good. I was thinking that probably more than few states and I think point 4 is critical. Most states don't just have a single bit of information with then. I'm thinking of telecom applications as an example. For every state in a phone call there's alot of state. As Andreas points out, one problem with handcrafted designs is there tends be alot of code to manage the context associated with these states and it gets lumped into one 'winnebago class' (a winnebago is a really large recreational vehicle with everything thrown in) that does everything and becomes a hotspot for change in the design.

...

So the other general design question is -- when is it better to but the variables asoociated with the machine in a state class versus pushing them up to the machine?

Innermost (leaf) states are usually empty, outer states are really a sort of sub-machine and it is just a scoping issue - if the variable scope is clearly tied to the lifetime of the outer state/sub-machine, put it there. Transition functions then naturally are placed in the same state/context as the variables they manipulate.

Also good.

...

Again there may be no answer here, but maybe someone that has implemented real code using fsm would have a design heuristic...

I have seen substantial reductions in code complexity arise out of using the fsm libary in a refactoring of some existing code. The result is also much easier to modify/maintain. This last point is particularly important if the fsm is not well specified to start with and/or may need to be modified in reaction to changes in requirements. Using boost fsm an iterative/exploratory design approach works fine. In many ways this is less painful than if there were a code generator. I'd actually prefer a diagram/documentation generator.

I was thinking that if you have XMI from a design tool it might be pretty easy to initially generate code -- but I won't disagree with wanting to reverse the transition table from the code. It's just that parsing C++ is probably harder than the other way around, but perhaps it wouldn't be too bad. Jeff

Hi Alexander Thanks for your review!

Most things are quite understandable. However, code snipsets are quite complex. On my first reading, I stopped trying to understand them after a second of third sample. May be it's only me who reads complex stuff in a such way but the fact that simple_state class accepts up to five parameters gives a hint to a user that there shall be not_so_simple_state class that accepts 6+ or is more complex in other ways.

Actually I never liked the name of the simple_state class template but I can't really think of a better one. The rationale is: You can do everything with state, "simple_state" should suggest that you can do less with it. It is difficult to pack the real difference in a short descriptive name. Suggestions welcome.

This appears at the beginning and I suspect some will stop reading the tutorial right at that point. I'd suggest using some smart intendation at least.

There's going to be an overhaul of the tutorial, including the indentation.

...

* What is your evaluation of the design? What features are supported better by alternative FSMs? What could be added (or removed) from the library?

I don't like the design. Primary goal of the library is to be close to UML and the secondary goal is performance. UML conformance is pushed so strongly that any attempt to improve performance makes design worse.

It would be interesting to hear how you came to that conclusion. The UML conformance has *nothing* to do with the current state of affairs regarding performance. I think it is possible to write a UML conformant FSM lib that has the often quoted "ruthless" efficiency. The main reason for the perceived "bad" performance are the scalability requirements. And believe me: There are applications that absolutely need that scalability.

For example, deferral<XXX> requires that event is allocated using new and pointed by intrusive_ptr. Ordinary events can be allocated differently. If performance was out of library scope, the library could copy _all_ events into heap-allocated buffer. From user point of view, all event kinds looked the same, then.

I don't understand. The requirement exists exactly because anything else would be less efficient (space, time, executable size). Users who don't care can heap-allocate all events anyway.

I believe that performance is not so important because even optimized, the library is too slow for FSM.

Too slow for Finite State Machines? I can't make any sense of this.

According to docs, process_event function has 10 steps and there is a search in a couple of steps. This means loops and branching.

Don't take this description too literally. Much of this searching could theoretically be eliminated. Some branches can be (and are) done at compile time.

I always thought that process_event in typical FSM is single jump followed by indirect function call.

Yes, that's the common way to implement simple FSMs. Problem is: You don't get very far that way when your FSMs become bigger.

There are other things I don't like. One example is that transit call in react is similar to "delete this;"

Please suggest an alternative.

The "Unstable state" and "Unstable state machine" sections are too among things I don't like. They exist because transition is a complex process which involves multiple destructions and constructions.

No. Any state machine can become unstable as soon as you have both of the following: 1. Hierarchical states 2. Failing actions (doesn't matter what: entry, exit, transition) This has *nothing* to do with the interface or the implementation of the proposed FSM library. If you were to use the library and you don't want your FSM to become unstable, then either: - Don't let actions fail - Don't use hierarchical states - Always use null_exception_translator You really do have a choice here!

Not only it affects performance

Yes, it does affect performance *slightly*, but what good is performance when your code isn't correct?

but it complicates recovering from exception.

The exact opposite is true. Please explain how you came to this conclusion.

...

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

I'm stongly against name FSM

As I said: I'm not against changing the name

because the library doesn't give enough guarantees common in FSM world. Because the library is not predicitable in real-time terms

I suggest you pinpoint the locations in the code that you think cause non-predictability. [snip]

...

* Are there performance bottlenecks? Does the library design fit requirements of real-time systems? How is it useable for embedded systems? Is the documentation clear on performance tradeoffs?

I don't think it's acceptable for real-time systems.

We seem to have different definitions of what real-time means. Real-time does *not* mean fast. Real-time means that you can specify an upper limit of how much time it will take to process an event. I don't think anything in the proposed FSM library prevents you from doing that.

...

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

It's definitely useful as a library for representing UML statechart but it covers only subset of FSM.

You mean it only covers the subset of FSMs that don't need ruthless efficiency? I could certainly agree with that. [snip]

I'm afraid not. Either it should be repositioned as Boost.Statecharts or redesigned for better real-time support.

See above. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.