[fsm review] Not quite a review
I don't know if I will have time to do a proper review of the library. The following are my notes on it so far. I've read the documentation for the libary, but haven't tried to use it. Good points: Simple. Relatively fast at runtime. Docs are quite good, but perhaps lack enough rationale style documentation on how the library models FSM concepts. Would benefit from some "how to" examples of more realistic usage and some "how to" docs on translating FSMs expressed using UML (or Harel) statecharts into a form implementable using FSM. Bad points: Unusual terminology. While there are obvious performance reasons for avoiding the Boost Statechart approach of applying an RAII model to state activation, it is not clear why at least basic concepts and terminology have not been used in FSM - especially as most Statechart terminology and FSM behavioural concepts are straight from UML terminology (it is a standard, you could pick another one, but why not stick with this one)? Note that this is *not* a request that the library include more features - just for some consistent ones. Some idiosyncratic behaviour. The FSM delivers the event to the on_process() handler in the "switched to" state when the transition is specified using the transition map, while delivering it to the on_process() handler in the current state if no transition map entry matches. There are warnings against mixing the transition map and switch_to() approaches to FSM specification, but even so it seems that the 2 uses of the on_process() handler are completely different. Would it not be better to have a model similar to Boost.Statechart where a custom reaction (implemented by a react() method) in a state is used to perform actions within the start state, generally including making a (gated) transition, while any action to occur on a transition is specified as part of the transition? Further, that transition action should be performed after the exit action of the current state and before the entry action of the new state. No event queuing mechanism, so no way to post an event while processing an event - although I see there has been some discussion about adding event deferral - which might be (almost) enough. Slow at compile time. I have not tested as yet, but if it is as slow as the mpl example state machine implementation, this will be a problem (I have previously had to abandon use of the MPL FSM due to compilation time issues on only moderately complex FSMs). Lacks real world use? I don't know if that is true, but I haven't seen anything other than toy examples. I was thinking that in the cases where the performance of Statechart was inadequate for complex augumented FSM implementation I would consider using FSM - but it would mean building a fair bit of additional scaffolding around FSM - maybe this should be part of the library? Or at least some examples of ideomatic use should be included? I found myself wondering if anyone had actually tried to use it in this way? Conversely, I don't find it compelling for implementing something like a lexer or even the terminal emulator example. What is the application domain? Not quite a conclusion: This is a hard one. At one extreme, Boost.Statechart is extremely powerful and well worth using in certain application domains (but there are performance implications), and at the other, as has been illustrated, various hand-rolled solutions of varying degrees of elegance get the job done. There seems to be a lot of space in between, and I'm not sure that the proposed FSM library fills enough of it.
Darryl Green wrote:
I don't know if I will have time to do a proper review of the library. The following are my notes on it so far.
Thank you for your effort.
Docs are quite good, but perhaps lack enough rationale style documentation on how the library models FSM concepts. Would benefit from some "how to" examples of more realistic usage and some "how to" docs on translating FSMs expressed using UML (or Harel) statecharts into a form implementable using FSM.
Ok, I will add a separate rationale section. As for "how-to", I thought the tutorial would play this role. I'll think about it.
Bad points:
Unusual terminology. While there are obvious performance reasons for avoiding the Boost Statechart approach of applying an RAII model to state activation, it is not clear why at least basic concepts and terminology have not been used in FSM - especially as most Statechart terminology and FSM behavioural concepts are straight from UML terminology (it is a standard, you could pick another one, but why not stick with this one)? Note that this is *not* a request that the library include more features - just for some consistent ones.
I'm not sure what parts of documentation you are referring to when saying "unusual terminology". I'm sure, my English is far from perfect and may not know some formal terms. I would be glad to fix all inconsistencies.
Some idiosyncratic behaviour. The FSM delivers the event to the on_process() handler in the "switched to" state when the transition is specified using the transition map, while delivering it to the on_process() handler in the current state if no transition map entry matches.
There's a rationale in the docs for this behavior. The main reason is that if the transition rule is executed after the on_process handler in the current state, it is possible that the on_process handler switches to another state itself, which would make the chosen transition invalid.
There are warnings against mixing the transition map and switch_to() approaches to FSM specification, but even so it seems that the 2 uses of the on_process() handler are completely different. Would it not be better to have a model similar to Boost.Statechart where a custom reaction (implemented by a react() method) in a state is used to perform actions within the start state, generally including making a (gated) transition, while any action to occur on a transition is specified as part of the transition? Further, that transition action should be performed after the exit action of the current state and before the entry action of the new state.
That would completely change the purpose of transitions and transition table. Now the transition table is used to define the conditions when to transit and which state to transit to. With your approach the transition table would define _how_ to transit, i.e. what to do while transiting. This would leave the logic of deciding whether to transit or not to event handlers only.
No event queuing mechanism, so no way to post an event while processing an event - although I see there has been some discussion about adding event deferral - which might be (almost) enough.
Like I said, the functionality of event scheduling, with event priorities, delivery delay support, event cancellation, periodical events, etc. deserves its own library. It's not only FSMs where such functionality would be useful. However, I will think about it more.
Slow at compile time. I have not tested as yet, but if it is as slow as the mpl example state machine implementation, this will be a problem (I have previously had to abandon use of the MPL FSM due to compilation time issues on only moderately complex FSMs).
True. I'm not sure there can be done much with it.
Lacks real world use? I don't know if that is true, but I haven't seen anything other than toy examples. I was thinking that in the cases where the performance of Statechart was inadequate for complex augumented FSM implementation I would consider using FSM - but it would mean building a fair bit of additional scaffolding around FSM - maybe this should be part of the library? Or at least some examples of ideomatic use should be included? I found myself wondering if anyone had actually tried to use it in this way? Conversely, I don't find it compelling for implementing something like a lexer or even the terminal emulator example. What is the application domain?
The library was definitely useful for me. I used a somewhat similar library to implement FSMs for INAP dialog users and telephony services, where performance was critical. The code is commercial, so I cannot post it here, however these applications would be perfectly supported by this library as well. I also made a quick C++ parser on this library to markup the code samples I used in the library docs. The latter, indeed, was just a toy. I think, the library would be most suitable for various protocol clients, which should maintain internal state and act according to it and where different event types can be distinguished.
Not quite a conclusion:
This is a hard one. At one extreme, Boost.Statechart is extremely powerful and well worth using in certain application domains (but there are performance implications), and at the other, as has been illustrated, various hand-rolled solutions of varying degrees of elegance get the job done. There seems to be a lot of space in between, and I'm not sure that the proposed FSM library fills enough of it.
Thanks again for your opinion.
On Tue, 2008-08-19 at 23:03 +0400, Andrey Semashev wrote:
Darryl Green wrote:
I don't know if I will have time to do a proper review of the library. The following are my notes on it so far.
Thank you for your effort.
This is as close to a review as I am going to have time for. I've had a bit of a look at the code, but still haven't tried to use the library. The code is clear, but I do wonder at the necessity of some of the low level "hacks" used to implement the state "container" used. Could a fusion set not have done the same job?
Docs are quite good, but perhaps lack enough rationale style documentation on how the library models FSM concepts. Would benefit from some "how to" examples of more realistic usage and some "how to" docs on translating FSMs expressed using UML (or Harel) statecharts into a form implementable using FSM.
Ok, I will add a separate rationale section. As for "how-to", I thought the tutorial would play this role. I'll think about it.
Using the tutorial is ok - it just needs to illustrate some of the mappings from concepts that can be expressed i a UML staechart to your library better/more comprehensively.
Unusual terminology. I'm not sure what parts of documentation you are referring to when saying "unusual terminology".
I wasn't referring to the documentation but to the naming conventions in the library itself.
I'm sure, my English is far from perfect and may not know some formal terms. I would be glad to fix all inconsistencies.
I did not intend to critique the English or the internal consistency of the documentation. Rather I think adopting a terminology consistent with some published standard state machine representation/model such as UML is almost essential. If boost is to ccontain 2 libraries for implementing state machines, there should at least be a clear mapping between concepts in one and the other. Identical terminology should be used where possible. Note that for the most part, adopting Statechart terminology aligns with UML. If you need to adopt different concepts with their own definitions it will need some rationale and additional documentation.
Some idiosyncratic behaviour. The FSM delivers the event to the on_process() handler in the "switched to" state when the transition is specified using the transition map, while delivering it to the on_process() handler in the current state if no transition map entry matches.
There's a rationale in the docs for this behavior. The main reason is that if the transition rule is executed after the on_process handler in the current state, it is possible that the on_process handler switches to another state itself, which would make the chosen transition invalid.
I agree - there is a conflict between the transition map and the on_process handler in the current state. As a potential FSM user I am concerned that I could accidentally completely change the FSM by ending up with what should have been a simple action, executed on a transition, executed as the only reaction to an event (due to an error in the transition table) or have what was intended to be a gated reaction in one state actually be invoked as a result of a transition from another state, producing an effect somewhat like duplicating an event. An action to be executed during a transition defined by the transition table should never, as far as I can see, itself cause a state change (ie. contain a switch_to) while one intended to process events in the absence of a transition row for the event and state concerned should contain a switch_to unless it is being used to define an in-state reaction. These seem like 2 completely separate concepts.
Would it not be better to have a model similar to Boost.Statechart [snip]
That would completely change the purpose of transitions and transition table. Now the transition table is used to define the conditions when to transit and which state to transit to. With your approach the transition table would define _how_ to transit, i.e. what to do while transiting. This would leave the logic of deciding whether to transit or not to event handlers only.
That was not my intent. I was relying on the specification for transitions and custom reactions in Boost Statechart to define the semantics. Statechart transitions define the conditions on which to transit (state is implicit as the reactions typelist is a member of the state, while the event is a parameter of the transition) as well as the how to transit (the optional transition action). Statechart custom reactions also define both when and how to transit. The Statechart transit function (similar to switch_to) can only be used within a custom reaction react() function (which is broadly similar to the on_process function, and provides the "when") and takes an optional transition action parameter (along with the state to transit to) to provide the "how". You cannot define both a custom reaction and a transition for the same event in the same state. This all results in a set of well defined and separate concepts and classes. I am struggling with the on_process duality in FSM and would like to see it resolved with something closer to the Statechart approach.
I also made a quick C++ parser on this library to markup the code samples I used in the library docs. The latter, indeed, was just a toy.
It sounds like an interesting toy. Is the code available?
I think, the library would be most suitable for various protocol clients, which should maintain internal state and act according to it and where different event types can be distinguished.
That is my main area of interest/experience with FSMs as well. Boost Statechart is very effective in this space. If FSM were able to offer the same ease of use and direct translation of statecharts to code as Statechart or offer an even better DSL along with higher performance it would be fantastic. As it is it offers high performance, but at a considerable cost in both the other areas, as well as scaleability. I'm going to abstain from passing a yes or no vote. I don't have a use for the library as is, but that doesn't seem like a very strong reason to vote against it. I won't vote for it because I hold out hope that something better is possible - although it won't be easy. Regards Darryl
Darryl Green wrote:
The code is clear, but I do wonder at the necessity of some of the low level "hacks" used to implement the state "container" used. Could a fusion set not have done the same job?
No, AFAIK, Boost.Fusion does not inherit the container from the stored types. Besides, there was no Fusion when I wrote the library.
I also made a quick C++ parser on this library to markup the code samples I used in the library docs. The latter, indeed, was just a toy.
It sounds like an interesting toy. Is the code available?
Nothing really special. Just quickly made tool to do the job. The code is attached.
participants (2)
-
Andrey Semashev -
Darryl Green