[review] FSM Second Call for Reviews
The formal review for Andrey Semashev's Finite State Machines (FSM) library has been running for a week now and continues until the 20th. There have been some lively discussions about the library, but no one has yet entered an explicit yes or no vote. If there are no votes either way, the FSM library submission will be rejected by default. If you wish to review, but don't have time before the review period ends on the 20th, please let me know as it may be possible to extend the review period. And, finally, a reminder to include an explicit "for" or "against" vote in your review. ----------- The documentation (overview and reference) is available online: http://boost-extension.redshoelace.com/docs/boost/fsm/doc/state_machine.html http://boost-extension.redshoelace.com/docs/boost/fsm/doc/reference.html The current submission is available from the sandbox vault at http://tinyurl.com/yjozfn (or http://www.boostpro.com/vault/index.php?action=downloadfile&filename=FSM.zip &directory=&PHPSESSID=48493076c1ea60ae316f7b60f15b9ed1, if you prefer.) There has already been some discussion of the library since the rewiew was first announced: http://www.nabble.com/FSM-Review-Announcement-to18820219.html http://www.nabble.com/FSM-Review-Reminder-to18890305.html ----------- Description ----------- "The main goals of the library are: * Simplicity. It should be very simple to create state machine using this library. * Performance. The state machine infrastructure should not be very time and memory-consuming in order to be applicable in more use cases. * Extensibility. A developer may want to add more states to the existing state machine, and this addition should be relatively safe since it shouldn't interfere with the existing states. The developer should also be able to specify additional transitions and events for the machine with minimum modifications to the existing code." "Boost.FSM vs. Boost.Statechart There is another library in Boost that provides similar functionality: Boost.Statechart. Although it currently covers almost all major Boost.FSM features and provides ones that are not supported in this library, Boost.Statechart is more targeted to creation of big and complex state machines with possibility of distributed development. But this does not come at no price and Statechart has little tools for compile-time programming and does not provide as much run-time performance as Boost.FSM does. So there are main guidelines for users to make a decision between Boost.FSM and Boost.Statechart: [...]" "The following compilers are known to have problems or most likely will have ones: * Microsoft Visual C++ 6.0 and 7.0. Most probably will fail to compile due to lack of partial template specialization support. * Borland C++ Builder 5.5.1 (free version). Fails to compile due to lack of partial template specialization and in-class using declarations support. Some other minor problems also have been noticed. Newer versions of the compiler have not been tested. * OpenWatcom 1.5. Fails to compile due to problems with Boost.MPL code. Newer versions of the compiler have not been tested. * SunPro C++ Compiler 5.5 for Solaris (SPARC). Most likely will show problems with function overload resolution. Newer versions of the compiler have not been tested." The current submission is available from the sandbox vault at http://tinyurl.com/yjozfn (or http://www.boostpro.com/vault/index.php?action=downloadfile&filename=FSM.zip &directory=&PHPSESSID=48493076c1ea60ae316f7b60f15b9ed1, if you prefer.) ---------------------------------- What to include in Review Comments ---------------------------------- Your comments may be brief or lengthy, but basically the Review Manager needs your evaluation of the library. If you identify problems along the way, please note if they are minor, serious, or showstoppers. Here are some questions you might want to answer in your review: What is your evaluation of the design? What is your evaluation of the implementation? What is your evaluation of the documentation? What is your evaluation of the potential usefulness of the library? Did you try to use the library? With what compiler? Did you have any problems? How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? Are you knowledgeable about the problem domain? And, finally, every review should answer this question: Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. Thanks in advance for your participation in this review. MV
My review appears here with an attached cpp file implementing four approaches (not compiled): a manual nested switch/if function, the TMP book's mpl state table, boost.statechart, this FSM library.
What is your evaluation of the implementation? Did you try to use the library? With what compiler? Did you have any problems?
Didn't download the library code, just read through docs and tried to implement a simple state machine comparing other approaches.
What is your evaluation of the potential usefulness of the library?
I think there are many applications for a lightweight, expressive FSM library in areas not typically using FSM's such as mouse event processing, filtering/transforming iterators,...
What is your evaluation of the design? What is your evaluation of the documentation?
My view of the design is limited to what is described in the documentation. I was a little dismayed that some of the basic features that I needed are considered Advanced features such as sharing state and accessing the current state from outside the state machine. These are very easily accomplished in the TMP and StateChart libraries. The section on accessing state is not sufficient for me to determine which state the fsm is in between calls to process(). The data sharing approach between sibling states using a virtual base class is perplexing... there's no discussion of just what is the structure of the state machine. There is a lot of repititious boilerplate required relative to other libraries. There is a mixing of the transition "structure" in the procedural code which is better separated in the transition table approach. The FSM transition map may improve upon this, but I started getting lost in the description. Documentation terminology drifts from the familiar "transition", "table",... introducing new terms "switch_to" and "transition map" without describing how/why they are different from the standard terms. The documentation seems to become less clear as the interface becomes more complex and verbose. The StateChart library addresses much of the same issues but always seems to remain comprehensible and keeps the reader grounded in familiar concepts while introducing new ones. I don't seem to be able to grasp the overall design concepts of FSM from it's documentation.
How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? Are you knowledgeable about the problem domain?
I spent several hours reading the docs and putting together the attached example using the 4 different libraries/implementations applying them to a "paraphrased-from-an-in-production" use case. The state machines are used to iterate through an input stream of integers, extracting triplets of integers that are even or odd. Odd integers appearing within a even triplet are skipped, triplets of odd integers are extracted when they occur between even triplets. The transition table in the attached cpp file clearly depicts the UML state chart upon which the example is derived. I've spent several years developing software that integrates Matlab/StateFlow generated code with hardware in the loop systems. So I'm familiar with many of the concepts.
Do you think the library should be accepted as a Boost library?
No. I'd prefer that the performance and missing functionality be added to improve the existing StateChart library, and/or a true transition table approach be provided ala the TMP book's transition table. I dislike FSM's verbose interface along with it's procedural leaning paradigm. Jeff
Jeff Flinn wrote:
What is your evaluation of the design? What is your evaluation of the documentation?
My view of the design is limited to what is described in the documentation. I was a little dismayed that some of the basic features that I needed are considered Advanced features such as sharing state and accessing the current state from outside the state machine. These are very easily accomplished in the TMP and StateChart libraries.
It's just a name for the section. Everything that didn't fit into Tutorial went into that section.
The section on accessing state is not sufficient for me to determine which state the fsm is in between calls to process().
Huh? There is a section that tells precisely how to do this. The is_in_state and get_current_state_type methods fill your requirement.
The data sharing approach between sibling states using a virtual base class is perplexing... there's no discussion of just what is the structure of the state machine.
Actually, this feature is one of those I love in the library. The description of the structure is given in the "Common data and methods among states" section. I admit, however, there's no graphical representation of the design, but if I drew precisely what the structure is, I think, it would confuse you even more.
Do you think the library should be accepted as a Boost library?
No. I'd prefer that the performance and missing functionality be added to improve the existing StateChart library, and/or a true transition table approach be provided ala the TMP book's transition table.
I don't think that with current implementation approach Boost.StateChart can be optimized to the degree of Boost.FSM. As for TMP approach, I've shown that it is representable with Boost.FSM.
I dislike FSM's verbose interface along with it's procedural leaning paradigm.
Having a look at your example, I don't find Boost.FSM portion to be much more or less verbose than others.
Andrey Semashev wrote:
Jeff Flinn wrote:
What is your evaluation of the design? What is your evaluation of the documentation? My view of the design is limited to what is described in the documentation. I was a little dismayed that some of the basic features that I needed are considered Advanced features such as sharing state and accessing the current state from outside the state machine. These are very easily accomplished in the TMP and StateChart libraries.
It's just a name for the section. Everything that didn't fit into Tutorial went into that section.
The section on accessing state is not sufficient for me to determine which state the fsm is in between calls to process().
Huh? There is a section that tells precisely how to do this. The is_in_state and get_current_state_type methods fill your requirement.
Ok, not sure why I had trouble reading through that earlier, other than I had a hard time finding this section whenever I went to look for it. Perhaps if you moved the Table of contents to the top of the docs, as it is it gets lost in the clutter. So so I would use is_in_state<extracted_triplet>(); in the extractor::extracted method?
The data sharing approach between sibling states using a virtual base class is perplexing... there's no discussion of just what is the structure of the state machine.
Actually, this feature is one of those I love in the library.
The description of the structure is given in the "Common data and methods among states" section. I admit, however, there's no graphical representation of the design, but if I drew precisely what the structure is, I think, it would confuse you even more.
Perhaps a Design/Rationale section would better convey that this section describes the overall architecture of the system.
Do you think the library should be accepted as a Boost library? No. I'd prefer that the performance and missing functionality be added to improve the existing StateChart library, and/or a true transition table approach be provided ala the TMP book's transition table.
I don't think that with current implementation approach Boost.StateChart can be optimized to the degree of Boost.FSM. As for TMP approach, I've shown that it is representable with Boost.FSM.
What leads you to the conclusion that StateChart's performance could not be improved to that of FSM's? Can you direct me to that discussion/presentation on emulating the TMP approach?
I dislike FSM's verbose interface along with it's procedural leaning paradigm.
Having a look at your example, I don't find Boost.FSM portion to be much more or less verbose than others.
I'd say it's on par with StateChart. Like StateChart, there's boilerplate repetition of base classes, "void on_process", and "switch_to" not present in the TMP approach. Jeff
Jeff Flinn wrote:
Andrey Semashev wrote:
Jeff Flinn wrote: So so I would use is_in_state<extracted_triplet>(); in the extractor::extracted method?
Yes.
The data sharing approach between sibling states using a virtual base class is perplexing... there's no discussion of just what is the structure of the state machine.
Actually, this feature is one of those I love in the library.
The description of the structure is given in the "Common data and methods among states" section. I admit, however, there's no graphical representation of the design, but if I drew precisely what the structure is, I think, it would confuse you even more.
Perhaps a Design/Rationale section would better convey that this section describes the overall architecture of the system.
Agreed.
Do you think the library should be accepted as a Boost library? No. I'd prefer that the performance and missing functionality be added to improve the existing StateChart library, and/or a true transition table approach be provided ala the TMP book's transition table.
I don't think that with current implementation approach Boost.StateChart can be optimized to the degree of Boost.FSM. As for TMP approach, I've shown that it is representable with Boost.FSM.
What leads you to the conclusion that StateChart's performance could not be improved to that of FSM's?
AFAIR, StateChart uses dynamic memory allocation for event delivery and state switching. Aside from event delivery overhead, this means that states are destroyed and constructed on each transition, which leads to overhead from the user's data that may be contained in the states. I'm also not sure which approach of event/state dispatching StateChart uses, but I'm pretty sure that it is less efficient than a mere indirect call through a pointer taken from an array by index. This is because StateChart uses RTTI (built-in or ad-hoc) to dispatch events in run time. This isn't for an inefficient implementation of StateChart (in fact, I am sure the author have put a lot of effort to achieve the current performance), it's just a consequence of a quite extensive feature set. The question is, do you always need them?
Can you direct me to that discussion/presentation on emulating the TMP approach?
We discussed the matter with David during this review. Here's the link to one of my posts with two code samples. http://tinyurl.com/5mn2gq
I dislike FSM's verbose interface along with it's procedural leaning paradigm.
Having a look at your example, I don't find Boost.FSM portion to be much more or less verbose than others.
I'd say it's on par with StateChart. Like StateChart, there's boilerplate repetition of base classes, "void on_process",
"void on_process" is effectively replaced with "void set1" and so on.
and "switch_to" not present in the TMP approach.
True. Boost.FSM wouldn't have had "switch_to" too, if transition table was used.
What is your evaluation of the design?
When I look at finite state machine in Wikipedia, Fig. 1 shows me an "Example of a Finite State Machine". The blue words "state", "transition", "transition condition", "entry action" in this picture probably represent some of the important notions in this domain. How does the FSM library relate to these concepts? The "state" concept is modeled as a class that has to publicly derive from fsm::state<Classname, StateList>. More on this later. The "transition" concept is modeled as the class fsm::transition<InitialState, Event, FinalState>. User defined transition actions can derive from this class and overide the "transit" method. The "transition condition" is replaced with the "event" concept. I guess this is OK, since the Wikipedia article also mentions event driven finite state machines. The "event" concept is modeled as an arbitrary class. There doesn't seem to be an EventList (analogous to the StateList) that lists all allowed events, so it's probably possible to send an arbitrary object to the state machine, which will then react somehow to that (unexpected?) event. In case a reaction to the "any_event" class is defined, the single value constructor (without the explicit keyword) of this class will probably convert this event to the "any_event". I haven't investigated how the different types of "actions" are modeled by the library, or whether they are modeled at all. The most important design decision seems to be let the state machine have a member of a class that derives from all states in StateList. The switching between the states now changes which of these "base classes" is "in charge" of handling events. I see two reasons for this design choice. The first is performance, which is one of the main goals of the library, the second is that the library models a "state machine" instead of a "finite state machine". This is OK, but I would consequently prefer the name "state_machine" instead of "fsm" for the library. The modeling of the "transition" concept could and should probably be improved. The transition table where I can specify for given "intial states" and "events" the resulting "final states" and "actions" (modeled as functions that take a const reference to the corresponding event) to perform appears superior to me. There might be other good ways to model this concept, but pointing out a single superior alternative should be sufficient to prove that the current design can be improved here. The modeling of the events as arbitrary classes makes sense to me. I haven't investigated in detail the amount of support functionality related to the event concept. A predefined event class template that takes enums as template parameter, or some way to restrict (at compile time) the possible events handled by a state machine come to my mind. However, these are probably just minor details. So in conclusion, most important design decisions are probably OK, but the design as a whole is not finished and polished enough.
What is your evaluation of the implementation?
I did take a look at the implementation and tried to understand it. It may be OK, but it uses tools that I'm not sufficiently familiar with. An example of this is boost-preprocessor. The inh*.hpp files in boost/fsm/detail are all missing include guards. However, on closer inspection it turns out that this is intended, and that they are included multiple times (by some boost-preprocessor mechanism). But I ask myselfs whether they should not use a different extension than .hpp, since they are not really header files. The general conclusion is that my current knowledge is sufficient to understand the implementation of http://www.boostpro.com/mplbook/examples/player.cpp http://www.boostpro.com/mplbook/examples/player2.cpp but that I have a hard time understanding the implementation of boost/fsm/state_machine.hpp
What is your evaluation of the documentation?
The documentation is fine.
What is your evaluation of the potential usefulness of the library?
I don't know.
Did you try to use the library?
No.
With what compiler? Did you have any problems?
See above.
How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
A quick reading.
Are you knowledgeable about the problem domain?
No.
Do you think the library should be accepted as a Boost library?
No. However, this opinion is not really related to this review, but to the general reaction on the boost-mailing list about the potential usefulness of the library. There was nobody explicitly saying that he has an urgent need for this library. Why did I submit this review then, when I didn't really have an interest in this library? I was following the discussions about the library, and tried to understand how this library differs from the other proposed approaches. So I finally ended up having thought so much about these issues that it made sense for me to submit a review.
Thomas Klimpel wrote:
What is your evaluation of the design?
When I look at finite state machine in Wikipedia, Fig. 1 shows me an "Example of a Finite State Machine". The blue words "state", "transition", "transition condition", "entry action" in this picture probably represent some of the important notions in this domain. How does the FSM library relate to these concepts?
I haven't investigated how the different types of "actions" are modeled by the library, or whether they are modeled at all.
They are. The article defines the following actions: - Entry action. Is modeled with on_enter_state handlers. - Exit action. Is modeled with on_leave_state handlers. - Input action. Is modeled with on_process handlers. - Transition action. Is modeled with transit handlers.
The most important design decision seems to be let the state machine have a member of a class that derives from all states in StateList. The switching between the states now changes which of these "base classes" is "in charge" of handling events.
I see two reasons for this design choice. The first is performance, which is one of the main goals of the library, the second is that the library models a "state machine" instead of a "finite state machine".
Why? The machine is definitely finite, since it consists of finite number of states and defines finite number of transitions between them.
The modeling of the "transition" concept could and should probably be improved. The transition table where I can specify for given "intial states" and "events" the resulting "final states" and "actions" (modeled as functions that take a const reference to the corresponding event) to perform appears superior to me.
You already can do that, as I've shown in my replies to David. The only difference with TMP approach is that there's no need to specify actions in the transition table. Is this what bothers you?
The modeling of the events as arbitrary classes makes sense to me. I haven't investigated in detail the amount of support functionality related to the event concept. A predefined event class template that takes enums as template parameter, or some way to restrict (at compile time) the possible events handled by a state machine come to my mind. However, these are probably just minor details.
You can use any type as events, including fundamental types. There is support for automatic event generation, in which case you can tag events with intergal/enum or a type.
So in conclusion, most important design decisions are probably OK, but the design as a whole is not finished and polished enough.
Could you, please, elaborate which particular design flaws you are referring to?
What is your evaluation of the implementation?
I did take a look at the implementation and tried to understand it. It may be OK, but it uses tools that I'm not sufficiently familiar with.
It's true that the implementation could be simplified. It initially was quite simple, without Boost.Preprocessor usage. However, I moved to the current implementation to improve compile times and reduce the resulting binary size.
Andrey Semashev wrote:
The most important design decision seems to be let the state machine have a member of a class that derives from all states in StateList. The switching between the states now changes which of these "base classes" is "in charge" of handling events.
I see two reasons for this design choice. The first is performance, which is one of the main goals of the library, the second is that the library models a "state machine" instead of a "finite state machine".
Why? The machine is definitely finite, since it consists of finite number of states and defines finite number of transitions between them.
Other designs model 'states' as enums, while the fsm library models 'states' as classes. A 'state' modeled by an enum would be a "stateless state", while a 'state' modeled by a class can have "internal state". I'm quite sure that the "finite" in "finite state machine" refers to the number of "stateless states", because the Wikipedia article says: "A finite state machine is an abstract model of a machine with a primitive internal memory.". In other words, the resulting "machine" (created by "fsm::state_machine<...> machine") viewed as a black box is not guaranteed to only have a finite number of "stateless states", so it may exhibit behavior that is not possible for a finite state machine (like parsing a grammar that is too complex for a finite state machine) I don't say that this is a bad thing. I just say that I guess this is one of the reasons why fsm models 'states' as classes and not just as enums.
The modeling of the "transition" concept could and should probably be improved. The transition table where I can specify for given "intial states" and "events" the resulting "final states" and "actions" (modeled as functions that take a const reference to the corresponding event) to perform appears superior to me.
You already can do that, as I've shown in my replies to David. The only difference with TMP approach is that there's no need to specify actions in the transition table. Is this what bothers you?
What bothers me is that although the important design decisions of the fsm library seem to be OK, it doesn't seem to please its potentials users. But let's focus on this particular 'design flaw'. As I understand it, it's not true "that there's no need to specify actions". The actions need to be specified, not as entries in the transition table, but by overriding the "transit" method of the "fsm::transition<InitialState, Event, FinalState>" class. So I get the impression that I will have to create a new class for every transition, because this class will have to derive from the corresponding "fsm::transition<InitialState, Event, FinalState>" class, in order to be able to override the "transit" method. This seems to make to resulting code much more verbose (and difficult to read) than the resulting code for the TMP approach.
So in conclusion, most important design decisions are probably OK, but the design as a whole is not finished and polished enough.
Could you, please, elaborate which particular design flaws you are referring to?
I got the impression that the design was well thought out from a purely technical point of view. So you are able to tell a potential user how he can achieve a desired behavior with your fsm library. I noticed that the fsm library also seems to be able to emulate most other approaches quite well, from a purely technical point of view. However, the resulting client code often doesn't look beautiful. This is most striking for the "transition" concept. However, this also show up in other areas. The TMP approach uses enums to model states for example. I could emulate this by defining a state class template that takes the corresponding enum as template parameter. But the resulting client code will look clumsy. However, the important point is that the code following the "// Concrete FSM implementation" line for the player.cpp and player2.cpp examples (which seem to be examples of the TMP approach) simply looks nice. So it would be more important to emulate this "looks nice" than to emulate any concrete technical tools (like enums or transition tables). Note that I wasn't talking about design flaws, but about "not finished and polished enough". And that's what "looks nice" is all about.
Thomas Klimpel wrote:
Andrey Semashev wrote:
The most important design decision seems to be let the state machine have a member of a class that derives from all states in StateList. The switching between the states now changes which of these "base classes" is "in charge" of handling events.
I see two reasons for this design choice. The first is performance, which is one of the main goals of the library, the second is that the library models a "state machine" instead of a "finite state machine". Why? The machine is definitely finite, since it consists of finite number of states and defines finite number of transitions between them.
Other designs model 'states' as enums, while the fsm library models 'states' as classes. A 'state' modeled by an enum would be a "stateless state", while a 'state' modeled by a class can have "internal state". I'm quite sure that the "finite" in "finite state machine" refers to the number of "stateless states", because the Wikipedia article says: "A finite state machine is an abstract model of a machine with a primitive internal memory.". In other words, the resulting "machine" (created by "fsm::state_machine<...> machine") viewed as a black box is not guaranteed to only have a finite number of "stateless states", so it may exhibit behavior that is not possible for a finite state machine (like parsing a grammar that is too complex for a finite state machine)
Ok then. I didn't think of the internal data of the states as an additional sub-state.
The modeling of the "transition" concept could and should probably be improved. The transition table where I can specify for given "intial states" and "events" the resulting "final states" and "actions" (modeled as functions that take a const reference to the corresponding event) to perform appears superior to me. You already can do that, as I've shown in my replies to David. The only difference with TMP approach is that there's no need to specify actions in the transition table. Is this what bothers you?
What bothers me is that although the important design decisions of the fsm library seem to be OK, it doesn't seem to please its potentials users.
But let's focus on this particular 'design flaw'. As I understand it, it's not true "that there's no need to specify actions". The actions need to be specified, not as entries in the transition table, but by overriding the "transit" method of the "fsm::transition<InitialState, Event, FinalState>" class. So I get the impression that I will have to create a new class for every transition, because this class will have to derive from the corresponding "fsm::transition<InitialState, Event, FinalState>" class, in order to be able to override the "transit" method. This seems to make to resulting code much more verbose (and difficult to read) than the resulting code for the TMP approach.
Not exactly. You don't have to override the transit handler unless you want to define some non-trivial transition logic. If you stick to the same degree of functionality that TMP provides (IOW, no runtime conditions for the transition to take place), then you can use the fsm::transition class as a direct replacement for the row template in the TMP approach. If you have to decide when and which state to transit to in runtime, then yes, you have to define your custom transition rule.
Andrey Semashev wrote:
Not exactly. You don't have to override the transit handler unless you want to define some non-trivial transition logic. If you stick to the same degree of functionality that TMP provides (IOW, no runtime conditions for the transition to take place), then you can use the fsm::transition class as a direct replacement for the row template in the TMP approach.
If you have to decide when and which state to transit to in runtime, then yes, you have to define your custom transition rule.
But how can I specify the "transition action", if not by overriding the "transit" method? And even if I override the "transit" method, how should I handle the fact that the event will still be delivered to the target state?
On Sun, 2008-08-31 at 15:28 +0200, Thomas Klimpel wrote:
Andrey Semashev wrote:
Not exactly. You don't have to override the transit handler unless you want to define some non-trivial transition logic. If you stick to the same degree of functionality that TMP provides (IOW, no runtime conditions for the transition to take place), then you can use the fsm::transition class as a direct replacement for the row template in the TMP approach.
If you have to decide when and which state to transit to in runtime, then yes, you have to define your custom transition rule.
But how can I specify the "transition action", if not by overriding the "transit" method?
As I said, if you need some non-trivial (i.e. something more complex than a mere call to switch_to), you have to implement the transit handler. Otherwise, you don't have to do that and you get precisely what the TMP solution provides.
And even if I override the "transit" method, how should I handle the fact that the event will still be delivered to the target state?
Process the event. Every event passed to the state machine must be processed in some way - either in one of the on_process handlers, or in the unexpected events handler. You cannot cancel the event delivery because the machine has to return something from the FSM's process method.
Andrey Semashev wrote:
But how can I specify the "transition action", if not by overriding the "transit" method?
As I said, if you need some non-trivial (i.e. something more complex than a mere call to switch_to), you have to implement the transit handler. Otherwise, you don't have to do that and you get precisely what the TMP solution provides.
Your answers confirm my initial statement: "The modeling of the "transition" concept could and should probably be improved." Also, your statement "you get precisely what the TMP solution provides" is misleading. It's easiest for me to explain this with an example from graph theory. A graph can be described by an "adjacency list", but it can also be described by an "incidence list". The state-based approach of the FSM library corresponds to the description of a graph by the "adjacency list". The transition-based approach of the TMP solution corresponds to the "incidence list". The description by an "adjacency list" will often be more efficient than the description by an "incidence list", but the "incidence list" makes it easy to associate additional information to the edges of the graph. You basically claim that you also support the "incidence list" approach, but you don't provide support for associating additional information to the edges of the graph, because you consider this "too complex".
Thomas Klimpel wrote:
Andrey Semashev wrote:
But how can I specify the "transition action", if not by overriding the "transit" method? As I said, if you need some non-trivial (i.e. something more complex than a mere call to switch_to), you have to implement the transit handler. Otherwise, you don't have to do that and you get precisely what the TMP solution provides.
Your answers confirm my initial statement: "The modeling of the "transition" concept could and should probably be improved."
I'm just trying to understand how, exactly, it should be improved. Your previous posts were referring to the necessity to override transit handlers in order to define transition actions. I confirmed that but added that it is not worse than other solutions mentioned. So, I don't see how and why this particular feature should be improved.
Also, your statement "you get precisely what the TMP solution provides" is misleading. It's easiest for me to explain this with an example from graph theory. A graph can be described by an "adjacency list", but it can also be described by an "incidence list". The state-based approach of the FSM library corresponds to the description of a graph by the "adjacency list". The transition-based approach of the TMP solution corresponds to the "incidence list". The description by an "adjacency list" will often be more efficient than the description by an "incidence list", but the "incidence list" makes it easy to associate additional information to the edges of the graph. You basically claim that you also support the "incidence list" approach, but you don't provide support for associating additional information to the edges of the graph, because you consider this "too complex".
Yes, however, I'd rather say, it would be difficult to use an FSM with transitions that have internal states, while simplicity being one of the primary goals of the library. To my mind, this is quite an academical question, whether transitions should have internal data or be stateless. After all, transitions model actions, not the state of the machine. But even then, you still have access to states from the transition handler, so you can associate data to the transition, if you really need it.
on Tue Sep 02 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
transitions model actions
FWIW, It has always been my understanding that state transitions and the actions associated with them were separate concepts. The first class status of transitions seems to me to be essential for being able to understand the flow of the state machine. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
on Tue Sep 02 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
transitions model actions
FWIW, It has always been my understanding that state transitions and the actions associated with them were separate concepts. The first class status of transitions seems to me to be essential for being able to understand the flow of the state machine.
I'm confused. What are transitions are used then, if not for describing when, where and how to transit?
Andrey Semashev wrote:
Your answers confirm my initial statement: "The modeling of the "transition" concept could and should probably be improved."
I'm just trying to understand how, exactly, it should be improved. Your previous posts were referring to the necessity to override transit handlers in order to define transition actions. I confirmed that but added that it is not worse than other solutions mentioned. So, I don't see how and why this particular feature should be improved.
OK, maybe the purpose of this particular feature was different from what I thought. So I will change my statement to: The library should provide true support for the "transition" concept. I tried to explain why I think this is important. If you ask me, "how" this should be done, all I can say is that the TMP approach seems to look nice from the user perspective (disregarding compile times).
Also, your statement "you get precisely what the TMP solution provides" is misleading. It's easiest for me to explain this with an example from graph theory. A graph can be described by an "adjacency list", but it can also be described by an "incidence list". The state-based approach of the FSM library corresponds to the description of a graph by the "adjacency list". The transition-based approach of the TMP solution corresponds to the "incidence list". The description by an "adjacency list" will often be more efficient than the description by an "incidence list", but the "incidence list" makes it easy to associate additional information to the edges of the graph. You basically claim that you also support the "incidence list" approach, but you don't provide support for associating additional information to the edges of the graph, because you consider this "too complex".
Yes, however, I'd rather say, it would be difficult to use an FSM with transitions that have internal states, while simplicity being one of the primary goals of the library.
I don't think that transitions should have internal state. But I think that the user should have the possibility to model them explicitly. And this includes associating an action to them. This paragraph was more about Dave's statement "To start with, "states handle events" is not part of the abstraction of what an FSM is." and your reaction to it. Because I'm more familiar with graphs than with finite state machines, it's easier for me to think in terms of graphs. One of my thoughts is: "Why not? The "adjacency list" is a valid description of a graph, just as the "incidence list" is." But on the other hand, you insist to deliver each event to a state, so you somehow take the "states handle events" to the extreme. I understand that you prefer the "states handle events", because the "adjacency list" is the more efficient representation of the two. But I get the impression that you don't honor the advantages of the "incidence list" representation enough. Each "edge" or "transition" is simply a row in a table or list. Associating additional information is as easy as adding an additional column to the table. It seems like all we need to associate with a "transition" for a finite state machine is an action, but I'm no expert for finite state machine. Maybe somebody would also want to associate a probability with a "transition", or a time interval, or ???. For graphs, I know that it is common that one has to associate a bunch of additional information to the edges.
Thomas Klimpel wrote:
I don't think that transitions should have internal state. But I think that the user should have the possibility to model them explicitly. And this includes associating an action to them.
You can. However, not everyone liked the exact syntax the library provides in order to do that.
This paragraph was more about Dave's statement "To start with, "states handle events" is not part of the abstraction of what an FSM is." and your reaction to it. Because I'm more familiar with graphs than with finite state machines, it's easier for me to think in terms of graphs.
One of my thoughts is: "Why not? The "adjacency list" is a valid description of a graph, just as the "incidence list" is." But on the other hand, you insist to deliver each event to a state, so you somehow take the "states handle events" to the extreme. I understand that you prefer the "states handle events", because the "adjacency list" is the more efficient representation of the two.
It's not just for efficiency reasons, it's a consequence of my understanding of the FSM concept. I believe, the transitions should not be responsible for actually processing events, but instead should describe the state changes. While sometimes this is quite enough (e.g. in case of validators of different kinds), it is often needed to do other useful stuff on a certain event - IOW, to react on the event receipt. It is my belief that this is not what transitions are intended to do. That is why the proposed library is designed so that events eventually are processed in states (or put it another way, reactions on the events receipt are defined in states). However, I admit that there are possibilities that there is no need in reactions on events and the whole purpose of the state machine is to trace the transitions path, and the library is not perfectly suited for such use (although, it is still quite possible). I'm not sure if this is a significant flaw, since I, for one, have not yet encountered such a case through my experience and I can't tell how common it is.
But I get the impression that you don't honor the advantages of the "incidence list" representation enough.
I don't quite grasp what advantages these might be, with respect to the FSM concept and the proposed library in particular. I agree that in graph theory it might be very useful to embed data and meta-data (I guess, this is what you meant with "additional information") into graph edges. We both agreed that FSM transitions should not contain any data, which leaves meta-data on the table. Such meta-data may, indeed, be useful sometimes, however, I wouldn't say it is common. FWIW, this kind of information can be described with transition table entries (more precisely, their types and behavior) and thus is supported by the library. Since users can define their own transition rules and put them into the transition table, it is possible to embed any kind of information as long as it is possible in C++. However, I am not a specialist in graph theory and may well be missing something obvious. Am I?
Each "edge" or "transition" is simply a row in a table or list. Associating additional information is as easy as adding an additional column to the table. It seems like all we need to associate with a "transition" for a finite state machine is an action, but I'm no expert for finite state machine.
This part leads back to syntax issues. Well, I've already expressed my motivation for the chosen approach (for simplifying transition handlers overloading and templating), but, as I can see, this motivation is not considered significant enough by most of the reviewers. In that case I will change the transition handler specification syntax to be more close to the TMP approach.
It's not just for efficiency reasons, it's a consequence of my understanding of the FSM concept. I believe, the transitions should not be responsible for actually processing events, but instead should describe the state changes. While sometimes this is quite enough (e.g. in case of validators of different kinds), it is often needed to do other useful stuff on a certain event - IOW, to react on the event receipt. It is my belief that this is not what transitions are intended to do. That is why the proposed library is designed so that events eventually are processed in states (or put it another way, reactions on the events receipt are defined in states).
Because fsm will currently deliver events handled by transitions to the target state, it's more sort of a "transfer control to" than a "transition". This is probably a useful feature, especially for events that should always be handled by the same state, but it's not suited for a simple representation of a finite state machine in source code.
However, I admit that there are possibilities that there is no need in reactions on events and the whole purpose of the state machine is to trace the transitions path, and the library is not perfectly suited for such use (although, it is still quite possible).
I don't think that the difference is the use case, but the representation in source code. I guess one possible representation of a finite state machine (one with a finite number of stateless states) is the list of transitions with the corresponding actions. (Let's forget about C++ for a moment. Let's simply imagine a text file with this list, and some tools to process this list in order to perform certain tasks, like optimizing the finite state machine, or verifying some important properties of the finite state machine.) Some people seem to think that this is a particularly clear representation of the corresponding machine. I'm no expert in this domain, so I can't say whether this judgment is justified. But my evaluation lead me to the conclusion that the "transition" feature of the fsm library is ill suited for a direct translation of this representation into source code.
But I get the impression that you don't honor the advantages of the "incidence list" representation enough.
I don't quite grasp what advantages these might be, with respect to the FSM concept and the proposed library in particular.
I don't have enough experience with the FSM concept to be able to judge whether the advantages offered by the "incidence list" representation are important in this domain or not. But they can be very useful in the domain of graph theory.
on Thu Sep 04 2008, "Thomas Klimpel" <Thomas.Klimpel-AT-synopsys.com> wrote:
I don't think that the difference is the use case, but the representation in source code. I guess one possible representation of a finite state machine (one with a finite number of stateless states) is the list of transitions with the corresponding actions. (Let's forget about C++ for a moment. Let's simply imagine a text file with this list, and some tools to process this list in order to perform certain tasks, like optimizing the finite state machine, or verifying some important properties of the finite state machine.) Some people seem to think that this is a particularly clear representation of the corresponding machine. I'm no expert in this domain, so I can't say whether this judgment is justified. But my evaluation lead me to the conclusion that the "transition" feature of the fsm library is ill suited for a direct translation of this representation into source code.
For what it's worth, when I write an STT, I always group the transitions by source state, so the representation is ultimately not all that different than the state-based representation used by the proposed library. I think the main difference is in the ability to read the structure of the machine without too much interference from other code. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Monday 18 August 2008 7:21:51 pm Martin Vuille wrote:
The formal review for Andrey Semashev's Finite State Machines (FSM) library has been running for a week now and continues until the 20th.
What is your evaluation of the design? I completed my FSM review by attempting to convert an existing implementation of the FIX transport protocol (http://www.fixprotocol.org/specifications/fixt1.1spec) that currently uses an in-house event driven state machine and swap it for the FSM's framework. Unfortunately, I was unable to agreeably implement such a system and I will now enumerate over the issues I came upon.
The major architectural problem I see is the factoring of the transition handlers (which is usually defined in the transition table) into the state classes. This peculiar arrangement necessarily results in an overall verbose code structure. By placing the on_process() function in the state event handlers, FSM users are forced to define an is_applicable<> specialization and supply a static transit() function that defines the pattern matching rules the state machine applies to incoming events. Factoring the transition handler into the various states results in the dispersion of the very transition table that defines the identity of a finite state machine. This was more than likely done in an attempt to optimize away the linked list pattern match (dispatch) found in the more common approach. Abstractly thinking however, the run-time switch based upon the current state of the fsm is going to occurr whether it be found in the fsm driver; whether it be found in the linked-list dispatch of CTM's fsm example or whether it be split amongst the various states. I do note my agreement that transition handler concept should be allowed to return values on invalid events rather than be forced to throw exceptions since in many cases an invalid event for a particular state is an error only when viewed at the level of the state machine's "protocol" and often times occurs just as often as the situation in which there is a valid match. This is somewhat provided with the switch_to<> mechanism however this seems to exist outside the realm of the well-defined state machine's transition rules. This approach forces error handling into what would best be described as the lexer (state_machine::process()'s callee) and thus outside the domain of the state machine. A better approach would be to allow dynamic posting of events from within transition handlers. These "error events" are thus included in the definition of the state machine's transtition table. Furthermore, while CTM's example fsm does not allow transition handlers to prevent the transition from "matching", it mirrors my internal implementation in most other regards as it too is implemented as fold(transitions_for_current_state, default_event_dispatcher, event_dispatcher<_2, _1>>). The last note I would make regards the BOOST_FSM_MUST_HANDLE_ALL_EVENTS macro one uses to enforce compile-time state machine consistency. This is rather a suprise as my expectation would be for this to be an intrinsic function of an fsm.
Do you think the library should be accepted as a Boost library? I'd like to take this moment to thank Andrey for his submission as the submitted library's documentation was very complete and it is obvious how much time and effort was involved.
While I believe its purpose is certainly a valid one and found the implementation to be a novel approach that made me think in some interesting ways (like switching my fsm's implementation to allow for additional dispatch algorithms such as a hash lookup or a jump table (packed or unpacked vectors)). However, with the library considered as a whole, I respectfully submit my vote as No. - Chris Knight
Chris Knight wrote:
I do note my agreement that transition handler concept should be allowed to return values on invalid events rather than be forced to throw exceptions since in many cases an invalid event for a particular state is an error only when viewed at the level of the state machine's "protocol" and often times occurs just as often as the situation in which there is a valid match.
This is somewhat provided with the switch_to<> mechanism however this seems to exist outside the realm of the well-defined state machine's transition rules.
There's no connection between unexpected events handling and the switch_to mechanism. Unexpected events are detected before the FSM has a chance to call switch_to (effectively, such events are detected at compile time).
This approach forces error handling into what would best be described as the lexer (state_machine::process()'s callee) and thus outside the domain of the state machine.
I disagree. When an event is unexpected, there's no handler in the FSM that would be able to handle it. This is the whole point behind the term "unexpected". Since, as you said yourself, such unexpected events may actually appear quite often, the library must provide an option to customize the behavior when receiving them. This is accomplished with the unexpected events handler, which is basically a user-provided functor, that is called on such event receipt.
A better approach would be to allow dynamic posting of events from within transition handlers. These "error events" are thus included in the definition of the state machine's transtition table.
This would make these events quite expected. You can already include such events in the transition table and have the desired behavior. As for event posting, there's been a discussion about it during the review.
Furthermore, while CTM's example fsm does not allow transition handlers to prevent the transition from "matching", it mirrors my internal implementation in most other regards as it too is implemented as fold(transitions_for_current_state, default_event_dispatcher, event_dispatcher<_2, _1>>).
That's because the transition is matched at compile time only.
The last note I would make regards the BOOST_FSM_MUST_HANDLE_ALL_EVENTS macro one uses to enforce compile-time state machine consistency. This is rather a suprise as my expectation would be for this to be an intrinsic function of an fsm.
Do you mean that the FSM should never compile if it detects unexpected events?
On Saturday 30 August 2008 1:55:57 am Andrey Semashev wrote:
Chris Knight wrote:
I do note my agreement that transition handler concept should be allowed to return values on invalid events rather than be forced to throw exceptions since in many cases an invalid event for a particular state is an error only when viewed at the level of the state machine's "protocol" and often times occurs just as often as the situation in which there is a valid match.
This is somewhat provided with the switch_to<> mechanism however this seems to exist outside the realm of the well-defined state machine's transition rules.
There's no connection between unexpected events handling and the switch_to mechanism. Unexpected events are detected before the FSM has a chance to call switch_to (effectively, such events are detected at compile time).
Sorry, I should have chosen my words more carefully. What I meant by an "invalid event" in this case was really an "error event" - a well defined event that simply is posted from within another event handler to handle protocol level errors. My only point was that one could implement a post_event via the switch_to<> functionality.
This approach forces error handling into what would best be described as the lexer (state_machine::process()'s callee) and thus outside the domain of the state machine.
I disagree. When an event is unexpected, there's no handler in the FSM that would be able to handle it. This is the whole point behind the term "unexpected".
Once again f(x) := "invalid => error" transforms my statements to more sensible ones. :-)
Since, as you said yourself, such unexpected events may actually appear quite often, the library must provide an option to customize the behavior when receiving them. This is accomplished with the unexpected events handler, which is basically a user-provided functor, that is called on such event receipt.
Completely in agreement as there are really 3 forms of events. *) Expected and "correct" ones (a network packet with the next expected seqnum) *) Expected but "incorrect" ones (a packet with a seqnum indicating packet loss) *) Unexpected events (events that do not conform to the state machine)
A better approach would be to allow dynamic posting of events from within transition handlers. These "error events" are thus included in the definition of the state machine's transtition table.
This would make these events quite expected. You can already include such events in the transition table and have the desired behavior. As for event posting, there's been a discussion about it during the review.
Furthermore, while CTM's example fsm does not allow transition handlers to prevent the transition from "matching", it mirrors my internal implementation in most other regards as it too is implemented as fold(transitions_for_current_state, default_event_dispatcher, event_dispatcher<_2, _1>>).
That's because the transition is matched at compile time only.
The last note I would make regards the BOOST_FSM_MUST_HANDLE_ALL_EVENTS macro one uses to enforce compile-time state machine consistency. This is rather a suprise as my expectation would be for this to be an intrinsic function of an fsm.
Do you mean that the FSM should never compile if it detects unexpected events?
Yes. If I say state_machine.process(Logon) when, for instance, the machine is in the Disconnected state I would expect that to be detected by default if for no other reason than the cost of doing so should be trivial/zero since the check is done at compile time. It could potentially matter with the addition of a post_event functionality as that would necessarily add the additional requirement of state machien variant checking in the machine's event double dispatcher that would process and dispatch posted base_events.
On Sun, 2008-08-31 at 01:58 -0500, Chris Knight wrote:
Do you mean that the FSM should never compile if it detects unexpected events?
Yes. If I say state_machine.process(Logon) when, for instance, the machine is in the Disconnected state I would expect that to be detected by default if for no other reason than the cost of doing so should be trivial/zero since the check is done at compile time. It could potentially matter with the addition of a post_event functionality as that would necessarily add the additional requirement of state machien variant checking in the machine's event double dispatcher that would process and dispatch posted base_events.
IMHO, this would add too much burden for the FSM designers, especially in case of relatively big state machines with lots of events. They would have to add handlers in every state (or a generic template handler in a state base class) to explicitly process such events. Often users don't need such strict explicity in event processing and can simply rely on unexpected events handler (which could be used to post events for the state machine through a third-party scheduler). Having a macro to enable strict consistency check looks quite enough for me.
Hello, hope it is not too late for my review, but I am a specialist in missing deadlines ;) This review will be somewhat 'fair' on the technical issues that I don't feel to be able to discuss. I just want to report my feelings as a programmer. I mostly code robotics/machine vision tasks and use boost almost everywhere.
What is your evaluation of the design?
As a programmer I find FSM really clean and straightforward for my programming tasks. I have evaluated StateChart but really found it too complex when implementing and everytime switched to ad hoc solutions.
What is your evaluation of the implementation? Cannot evaluate the implementation. But following the discussion, I found that the author has replied consistently showing high knowledge on implementation issues.
What is your evaluation of the documentation? Very good. The author took care to offer a simple introductory example that let you familiarize with the interface very smoothly. The rest of the documentation is then appropriate.
What is your evaluation of the potential usefulness of the library? I believe it is really helpful. Almost in my day to day coding tasks. Following the discussion it is my impression that very few users use boost::statechart (correct me if I am wrong). And everyone uses ad hoc implementation considering it better than FSM. But .. I do not like 'ad hoc' solutions. And I believe that the author of FSM has given strong motivations to the design and implementation of FSM. I had problems in reading the code offered by others while I felt immediately confortable with FSM examples.
Did you try to use the library? With what compiler? Did you have any problems? I am developing a simple FSM for handling a process. Simple states and transitions. I am currently using Xcode 3.1 (apple), gcc 4.0.1. There seems to be problems with gcc-4.2 (the one shipped with apple developer tools) for a missing header but cannot be more precise now.
How much effort did you put into your evaluation? A glance? A quick reading? In-depth study?
Some coding afternoons.
Are you knowledgeable about the problem domain? As a computer science PhD student, I should. ;)
Do you think the library should be accepted as a Boost library? Yes.
again .. hope that my review will be considered. And finally I would like to express my appreciation to the author and all the audience that has participated to the review process, giving me very interesting information on FSM theory and c++ coding. regards, andrea carbone -- View this message in context: http://www.nabble.com/-review--FSM-Second-Call-for-Reviews-tp19042336p192405... Sent from the Boost - Dev mailing list archive at Nabble.com.
On Sun, 2008-08-31 at 02:15 -0700, andrea carbone wrote:
There seems to be problems with gcc-4.2 (the one shipped with apple developer tools) for a missing header but cannot be more precise now.
I don't have access to this platform to test the library. Could you send me a code example and the compiler output? Perhaps, I could fix the problem.
andrea carbone wrote:
What is your evaluation of the potential usefulness of the library? ... I had problems in reading the code offered by others while I felt immediately confortable with FSM examples.
The example folder of the fsm library contains the "Turnstile" example and the "BitMachine" example. Do there exists other "FSM examples" that I'm missing? I feel comfortable with the "Turnstile" example, but I'm having a hard time with the "BitMachine" example. (I'm not a computer science PhD student.) On the other hand, I had less problems with the statechart implementation of the same example. However, I admit that my problems are probably caused by the usage of boost/preprocessor and boost/mpl techniques again. Nevertheless, I find it surprising that somebody claims "I felt immediately comfortable with this code".
On Sun, 2008-08-31 at 15:50 +0200, Thomas Klimpel wrote:
andrea carbone wrote:
What is your evaluation of the potential usefulness of the library? ... I had problems in reading the code offered by others while I felt immediately confortable with FSM examples.
The example folder of the fsm library contains the "Turnstile" example and the "BitMachine" example. Do there exists other "FSM examples" that I'm missing? I feel comfortable with the "Turnstile" example, but I'm having a hard time with the "BitMachine" example. (I'm not a computer science PhD student.) On the other hand, I had less problems with the statechart implementation of the same example. However, I admit that my problems are probably caused by the usage of boost/preprocessor and boost/mpl techniques again. Nevertheless, I find it surprising that somebody claims "I felt immediately comfortable with this code".
Aside from these two examples, there are tests, which are quite descriptive, and a number of examples that I have posted during the discussion. As for the BitMachine example, this is the code I used for performance testing, which results are presented in the docs. It is not the typical way of using the library, however, it shows an example of how the library can be used to automatically generate state machines. PS: Please, don't take that as offense, but I don't think that not knowing some libraries or features may be given as an argument against another library that internally uses them.
participants (7)
-
andrea carbone -
Andrey Semashev -
Chris Knight -
David Abrahams -
Jeff Flinn -
Martin Vuille -
Thomas Klimpel