Proposal to add a Boost.FSM library
Hi, I would like to purpose a new library addition to Boost: Boost.FSM. FSM stands for Finite State Machine, so the library is aimed to ease creation and support of state machines in C++. State machine is a programming concept that allows to differentiate behavior of objects depending in their internal state. A simple example of such is a static variable in a function body. Before the first call to the function the memory that should hold the variable is in uninitialized state. During the first function call the variable constructs (in other words, it passes to an initialized state). And during any consequent calls the initialized variable is used (i.e. in the initialized state the function call does not lead to the variable construction). Of course, such simple logic may easily be implemented without any library support, using some boolean flags or state identifiers. But as the state machine complexity raises adding a new state to the machine gets more difficult and error-prone. This library is intended to hide basic state machine infrastructure and let the library user to focus on states and transitions between them. I've uploaded the library implementation, documentation and test to the Vault: http://boost-consulting.com/vault/index.php?action=downloadfile&filename=state_machine.zip&directory=& The implementation and documentation are quite stable, though there may be typos and mistakes in the documentation. The test still needs some cosmetic changes and a Jamfile, but it can be used as an example of the library usage. Please, post here your opinions on wether this library should have its place in Boost. Thank you. PS: Notes and suggestions about the implementation and documentation are also appreciated. -- Best regards, Andrey mailto:andysem@mail.ru
"Andrey Semashev" wrote:
I would like to purpose a new library addition to Boost: Boost.FSM. FSM stands for Finite State Machine, so the library is aimed to ease creation and support of state machines in C++.
[ snip ]
http://boost-consulting.com/vault/ + works Are you aware of Boost.Statechart? (will be released in 1.34, available from CVS now) It was originally called Boost.FSM. /Pavel
Hello Pavel, Sunday, December 17, 2006, 7:44:41 AM, you wrote:
"Andrey Semashev" wrote:
I would like to purpose a new library addition to Boost: Boost.FSM. FSM stands for Finite State Machine, so the library is aimed to ease creation and support of state machines in C++.
[deleted]
Are you aware of Boost.Statechart? (will be released in 1.34, available from CVS now)
It was originally called Boost.FSM.
No, not really. I'll take a look at it. -- Best regards, Andrey mailto:andysem@mail.ru
"Andrey Semashev" <andysem@mail.ru> wrote in message news:12010137442.20061217134912@mail.ru...
Hello Pavel,
Sunday, December 17, 2006, 7:44:41 AM, you wrote:
"Andrey Semashev" wrote:
I would like to purpose a new library addition to Boost: Boost.FSM. FSM stands for Finite State Machine, so the library is aimed to ease creation and support of state machines in C++.
Are you aware of Boost.Statechart? (will be released in 1.34, available from CVS now)
It was originally called Boost.FSM.
No, not really. I'll take a look at it.
Well, I have read the Boost.Statechart documentation. Its functionality covers and extends my proposed implementation, though I must note its several deficiences: - The author notes the performance issue of Boost.Statechart. I have not inspected the library implementation but as I can see from the documentation, the performance of transition between states and event delivery to a reaction handler linearly depends on the number of reactions in the state. Additionally, a transition between states involves memory allocations which, besides the performance losses in the first place, leads to memory fragmentation. A custom pooling allocator partially addresses the problem but in most real-world applications it will not evade the necessity of pool synchronization costs. In the proposed implementation no allocations take place neither on transitions nor on event delivery. In addition, none of these operations depend on state, transitions or reactions number. The implementation even tries to minimize virtual function usage. So, even though I haven't done experimental comparisons, IMO the proposed implementation will outperform Boost.Statechart. - In Boost.Statechart to declare a custom reaction on some event we must add it as an element to the "reactions" typedef besides defining a "react" member function. No such duplication is needed in the proposed implementation - only "on_process" (the synonym for "react") handler is needed. As a nice side effect it is possible to rely on C++ overload resolution rules and even declare "on_process" templates. That makes the state code cleaner and more natural, IMO. - I can see no way to return a value from a Boost.Statechart's machine except by passing a reference or a pointer in the event. There is such functionality in the proposed implementation. - I can see no easy way to describe a transition that should take place regardless of the current state of the machine in Boost.Statechart. To do this one must put the transition into each state's "reactions" type sequence. There is a much simplier way to do this in the proposed implementation. - Common state data in Boost.Statechart can be accessed via "context"s mechanism. Although this is a very nice solution, there is no need in such in the proposed addition. In most cases common data can be accessed just like it is another member of the state class. In rare cases a C++ scope qualification should be added. - Maybe some other minor things that may come up after a real-world evaluation of Boost.Statechart. To be honest, there is quite an amount of functionality of Boost.Statechart, that is not covered by the proposed Boost.FSM. Here is a brief list: - No UML support. Actually, in my practice a have never had a real need in one. Maybe that's just a lack of my experience. - No nested states support. The proposed Boost.FSM supports only flat machines. - No orthogonal states support, though in many cases they can be easilly replaced with additional state machines nested in a state. - No history support. This feature can be easilly implemented by user in the proposed Boost.FSM. A user may store state identifiers into a container that is accessible from any state. - Less support for modularity. Although it is possible to separate states of the proposed Boost.FSM state machine into several translation units, the complete state machine will still need all states to be defined, not just declared. - No support for posting events and asynchronous state machines. Though these features may be implemented as an outer layer to a regular state machine. That being said, I may only purpose my implementation as a lightweight addition to the Boost.Statechart aimed to solve performance and simplicity issues for small and light FSMs. Is there any need in such?
"Andrey Semashev" wrote: [ snip differences between Boost.Statechart and the proposed FSM ]
That being said, I may only purpose my implementation as a lightweight addition to the Boost.Statechart aimed to solve performance and simplicity issues for small and light FSMs. Is there any need in such?
The Statechart library is named as is not to give impression that this is the only possible FSM implementation in Boost. ------------- An interesting idea had bubbled up during the review - a FSM that could be "hidden" within a class and would simplify internals of the class. Something like that was described on: http://www.codeproject.com/cpp/statebased.asp but this implementation is IMHO too complicated for the end user. /Pavel
Pavel Vozenilek wrote:
The Statechart library is named as is not to give impression that this is the only possible FSM implementation in Boost.
-------------
An interesting idea had bubbled up during the review - a FSM that could be "hidden" within a class and would simplify internals of the class.
Something like that was described on: http://www.codeproject.com/cpp/statebased.asp but this implementation is IMHO too complicated for the end user.
Also, you can take a look at http://www.rsdn.ru/File/21403/Overloads.pdf -- Alexander Nasonov http://nasonov.blogspot.com Love is composed of a single soul inhabiting two bodies. -- Aristotle -- This quote is generated by: /usr/pkg/bin/curl -L http://tinyurl.com/veusy \ | sed -e 's/^document\.write(.//' -e 's/.);$/ --/' \ -e 's/<[^>]*>//g' -e 's/^More quotes from //' \ | fmt | tee ~/.signature-quote
Hello Alexander, Monday, December 18, 2006, 12:02:53 AM, you wrote:
Pavel Vozenilek wrote:
The Statechart library is named as is not to give impression that this is the only possible FSM implementation in Boost.
-------------
An interesting idea had bubbled up during the review - a FSM that could be "hidden" within a class and would simplify internals of the class.
Something like that was described on: http://www.codeproject.com/cpp/statebased.asp but this implementation is IMHO too complicated for the end user.
Also, you can take a look at http://www.rsdn.ru/File/21403/Overloads.pdf
Thanks for the article. It dropped me a thought of a way of improving my automatic transitions support in runtime. Although, I still don't catch the point of creating/destroying state objects during transitions. This can even be inconvenient if a state is intended to be visited more than once. -- Best regards, Andrey mailto:andysem@mail.ru
T'is possible that the state objects should be singletons, since they can be shared amongst all objects using the same set of states. The current state is that to which the object points.. On 12/18/06, Andrey Semashev <andysem@mail.ru> wrote:
Hello Alexander,
Monday, December 18, 2006, 12:02:53 AM, you wrote:
Pavel Vozenilek wrote:
The Statechart library is named as is not to give impression that this is the only possible FSM implementation in Boost.
-------------
An interesting idea had bubbled up during the review - a FSM that could be "hidden" within a class and would simplify internals of the class.
Something like that was described on: http://www.codeproject.com/cpp/statebased.asp but this implementation is IMHO too complicated for the end user.
Also, you can take a look at http://www.rsdn.ru/File/21403/Overloads.pdf
Thanks for the article. It dropped me a thought of a way of improving my automatic transitions support in runtime.
Although, I still don't catch the point of creating/destroying state objects during transitions. This can even be inconvenient if a state is intended to be visited more than once.
-- Best regards, Andrey mailto:andysem@mail.ru
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Andrey Semashev wrote:
Thanks for the article. It dropped me a thought of a way of improving my automatic transitions support in runtime. You're welcome! What idea, BTW?
Although, I still don't catch the point of creating/destroying state objects during transitions. This can even be inconvenient if a state is intended to be visited more than once. It's easy to draw a graph by analyzing signatures of transitions. It's not possible with switch_to<State>() because these calls can appear anywhere in the on_process body. This is very important use case, IMO.
You can always define a state with a pointer to the state's data. This is usually a good distinction especially if states hierarchy is used to model inner and outer states. In this case, states hierarchy in often not related to state's data hierarchy. -- Alexander Nasonov http://nasonov.blogspot.com Knowledge is knowing that we cannot know. -- Ralph Waldo Emerson -- This quote is generated by: /usr/pkg/bin/curl -L http://tinyurl.com/veusy \ | sed -e 's/^document\.write(.//' -e 's/.);$/ --/' \ -e 's/<[^>]*>//g' -e 's/^More quotes from //' \ | fmt | tee ~/.signature-quote
Hello Alexander, Tuesday, December 19, 2006, 12:46:01 AM, you wrote:
Andrey Semashev wrote:
Thanks for the article. It dropped me a thought of a way of improving my automatic transitions support in runtime. You're welcome! What idea, BTW?
Well, currently there's a two-phase transition lookup: a compile-time search of a transition rule in the map (with "is_applicable" MPL predicate) and a runtime check wether the statically found rule will actually trigger the transition (a static function "is_allowed"). You might have seen it in the library docs. This "is_allowed" is implemented in each transition rule. It takes an event and returns true if the transition should be performed or false otherwise. So it only allows or denies the library to perform the transition. The idea is to pass a reference to the current state to the function and let it switch the state itself (due to this change of semantic I will have to change its name to somewhat like "transit"). Although this exposes states' implementation to transitions, this would add more flexibility. The dark side of the change is that I'll probably have to add another layer of dispatch of the event (it will cost an additional function call via a function pointer in runtime) and probably some increase of compilation time.
Although, I still don't catch the point of creating/destroying state objects during transitions. This can even be inconvenient if a state is intended to be visited more than once. It's easy to draw a graph by analyzing signatures of transitions. It's not possible with switch_to<State>() because these calls can appear anywhere in the on_process body. This is very important use case, IMO.
Yes, I agree. That is why there is a support for transition maps in my implementation that I've spoken of above. Although in many cases the switch_to approach is more simple and flexible.
You can always define a state with a pointer to the state's data. This is usually a good distinction especially if states hierarchy is used to model inner and outer states. In this case, states hierarchy in often not related to state's data hierarchy.
A pointer to the state's data doesn't help if the state is actually destroyed when being left (the pointer is freed and the data is lost). And storing such pointer in a place somewhere out of the state (i.e. in a base state, a state machine or its some common storage like virtual bases in my implementation) means that data is exposed and is no longer specific to the state. IMO, this breaks the natural state encapsulation that is one of the main ideas of FSM concept. -- Best regards, Andrey mailto:andysem@mail.ru
Andrey Semashev wrote:
A pointer to the state's data doesn't help if the state is actually destroyed when being left (the pointer is freed and the data is lost). And storing such pointer in a place somewhere out of the state (i.e. in a base state, a state machine or its some common storage like virtual bases in my implementation) means that data is exposed and is no longer specific to the state. IMO, this breaks the natural state encapsulation that is one of the main ideas of FSM concept.
struct my_fsm : fsm<my_fsm> { // Events enum event { Start, Pause, Stop }; private: struct Data { /* ... */ }; // States struct Operational { Data* data_ptr; }; struct Paused : Operational {}; struct Running : Operational {}; struct Stopped {}; struct Initial {}; Data m_data; // Paused and Running will point to it. Running on_process(id<1>, Initial, integral_c<event,Start>) const; Paused on_process(id<2>, Running, integral_c<event,Pause>) const; Running on_process(id<3>, Paused, integral_c<event,Pause>) const; Stopped on_process(id<4>, Operational, integral_c<event,Stop> ) const; // Last function is most interesting because it defines transitions // for all states derived from Operational. public: my_fsm(); }; Running my_fsm::on_process( id<1> , Initial , integral_c<my_fsm::event,event::Start> ) const { Running result; result.data_ptr = &m_data; return result; } In this example, all states and state data are private. -- Alexander Nasonov http://nasonov.blogspot.com We need not think alike to love alike. -- Francis David -- This quote is generated by: /usr/pkg/bin/curl -L http://tinyurl.com/veusy \ | sed -e 's/^document\.write(.//' -e 's/.);$/ --/' \ -e 's/<[^>]*>//g' -e 's/^More quotes from //' \ | fmt | tee ~/.signature-quote
Hello Alexander, Wednesday, December 20, 2006, 12:15:57 AM, you wrote:
Andrey Semashev wrote:
A pointer to the state's data doesn't help if the state is actually destroyed when being left (the pointer is freed and the data is lost). And storing such pointer in a place somewhere out of the state (i.e. in a base state, a state machine or its some common storage like virtual bases in my implementation) means that data is exposed and is no longer specific to the state. IMO, this breaks the natural state encapsulation that is one of the main ideas of FSM concept.
struct my_fsm : fsm<my_fsm> { // Events enum event { Start, Pause, Stop };
private: struct Data { /* ... */ };
// States struct Operational { Data* data_ptr; }; struct Paused : Operational {}; struct Running : Operational {}; struct Stopped {}; struct Initial {};
Data m_data; // Paused and Running will point to it.
Running on_process(id<1>, Initial, integral_c<event,Start>) const; Paused on_process(id<2>, Running, integral_c<event,Pause>) const; Running on_process(id<3>, Paused, integral_c<event,Pause>) const; Stopped on_process(id<4>, Operational, integral_c<event,Stop> ) const; // Last function is most interesting because it defines transitions // for all states derived from Operational.
public: my_fsm(); };
[snip on_process]
In this example, all states and state data are private.
This is not quite what I meant. In your example the Data structure holds variables specific to Paused and Running states (let's assume the Operational state is only used as a simple base class, not a final state). But instead of being hidden inside of them it becomes the whole machine's member. Had I ten states with their specific data, the my_fsm class would get too crowded. Besides, nothing prevents you to access or modify this data from, say, "Running on_process(id<1>, Initial, integral_c<event,Start>) const;" handler which has nothing to do with neither Operational nor Running or Paused states. From my point of view a state should be a part of the state machine since it may contain some specifiс data. It may not be a lightweight compound and it may want to keep its internal state through the whole machine's lifetime, which may be long enough and even cyclic. -- Best regards, Andrey mailto:andysem@mail.ru
Sorry for the late reply. I was hoping to get some spare time last week but the last hours of this year is the earliest time. I'll go drink a bottle of champaine when I send this letter :-))) Andrey Semashev wrote:
In your example the Data structure holds variables specific to Paused and Running states
(let's assume the Operational state is only used as a simple base class, not a final state). This is correct, base classes are never states unless they are returned from on_process function.
But instead of being hidden inside of them it becomes the whole machine's member. Had I ten states with their specific data, the my_fsm class would get too crowded. I agree that if a user does it way, this may get messy.
Besides, nothing prevents you to access or modify this data from, say, "Running on_process(id<1>, Initial, integral_c<event,Start>) const;" handler which has nothing to do with neither Operational nor Running or Paused states.
I think it makes sense to support State&, reference_wrapper<State> and shared_ptr<State>. For example, // The framework should recognize a reference and act upon. Running& state_machine::on_process( id<1>, Initial, integral_c<event,Start>) const { // ... return m_RunningInstance; } This approach has two advantages: 1. You control a construction of m_RunningInstance (Not sure that it's always a best choice than automatic state management) 2. You have a better control during processing, e.g. you may return an object from a pool of objects rather than using only one state object.
From my point of view a state should be a part of the state machine since it may contain some specifiс data. It may not be a lightweight compound and it may want to keep its internal state through the whole machine's lifetime, which may be long enough and even cyclic.
I would rather say it depends. It may be lightweight but in general yes, you're right. My model is more static and lets you for example draw a machine without running it. In my opinion, this feature is absolutely necessary and state transition table shouln't be optional (it's so easy to forgot one transition among hunderds when it's optional). Happy New Year! С Новым годом! -- Alexander Nasonov http://nasonov.blogspot.com We need to find God, and he cannot be found in noise and restlessness. God is the friend of silence. See how nature -- trees, flowers, grass -- grows in silence; see the stars, the moon and the sun, how they move in silence. We need silence to be able to touch souls. -- Mother Teresa -- This quote is generated by: /usr/pkg/bin/curl -L http://tinyurl.com/veusy \ | sed -e 's/^document\.write(.//' -e 's/.);$/ --/' \ -e 's/<[^>]*>//g' -e 's/^More quotes from //' \ | fmt | tee ~/.signature-quote
Hello Alexander, Sunday, December 31, 2006, 10:43:37 PM, you wrote: [snip]
Besides, nothing prevents you to access or modify this data from, say, "Running on_process(id<1>, Initial, integral_c<event,Start>) const;" handler which has nothing to do with neither Operational nor Running or Paused states.
I think it makes sense to support State&, reference_wrapper<State> and shared_ptr<State>. For example,
// The framework should recognize a reference and act upon. Running& state_machine::on_process( id<1>, Initial, integral_c<event,Start>) const { // ... return m_RunningInstance; }
This approach has two advantages:
1. You control a construction of m_RunningInstance (Not sure that it's always a best choice than automatic state management) 2. You have a better control during processing, e.g. you may return an object from a pool of objects rather than using only one state object.
Although I was pointing out something different in my previous post, returning a state or a reference to it has one major drawback. What "on_process" should return if the next state depends on the event contents? Besides, when returning a reference, where should the state object be stored? It may not be the current state member since it is destroyed on state exit. So, once again, it may only be a member of some outer state. [snip] -- Best regards, Andrey mailto:andysem@mail.ru
Andrey Semashev wrote:
Although I was pointing out something different in my previous post, returning a state or a reference to it has one major drawback. What "on_process" should return if the next state depends on the event contents?
It would return variant<State1&, State2&, /* ... */ >. Visual representation of FSM would be fuzzy but it still better than no visual representation at all.
Besides, when returning a reference, where should the state object be stored? For example, in a state machine object.
It may not be the current state member since it is destroyed on state exit. So, once again, it may only be a member of some outer state. Not necessarily. It may be a member of a state machine.
-- Alexander Nasonov http://nasonov.blogspot.com Every generation laughs at the old fashions, but follows religiously the new. -- Henry Thoreau -- This quote is generated by: /usr/pkg/bin/curl -L http://tinyurl.com/veusy \ | sed -e 's/^document\.write(.//' -e 's/.);$/ --/' \ -e 's/<[^>]*>//g' -e 's/^More quotes from //' \ | fmt | tee ~/.signature-quote
Hello Alexander, Wednesday, January 3, 2007, 9:46:16 PM, you wrote:
Andrey Semashev wrote:
Although I was pointing out something different in my previous post, returning a state or a reference to it has one major drawback. What "on_process" should return if the next state depends on the event contents?
It would return variant<State1&, State2&, /* ... */ >. Visual representation of FSM would be fuzzy but it still better than no visual representation at all.
The "variant" has a limited set of possible types and it takes some time to dispatch the real type of the object it stores. Besides, I'd like to keep the ability to return something useful for the user from "on_process". IMHO, transition maps exist to make FSM transitions visible at the first glance. No need to involve event handlers into this and take away several useful features by this, such as return values and template event handlers, and add these "id< ... >" arguments on top of that.
Besides, when returning a reference, where should the state object be stored? For example, in a state machine object.
It may not be the current state member since it is destroyed on state exit. So, once again, it may only be a member of some outer state. Not necessarily. It may be a member of a state machine.
Actually, it's the way Boost.FSM is implemented except that it doesn't allow to access one state from another and therefore ensures encapsulation. -- Best regards, Andrey mailto:andysem@mail.ru
Andrey Semashev wrote:
Wednesday, January 3, 2007, 9:46:16 PM, you wrote:
It would return variant<State1&, State2&, /* ... */ >. Visual representation of FSM would be fuzzy but it still better than no visual representation at all.
The "variant" has a limited set of possible types
So does any state machine - it has a limited set of types ;-)
and it takes some time to dispatch the real type of the object it stores. It a resonable price for the flexibility.
Besides, I'd like to keep the ability to return something useful for the user from "on_process".
IMO, it doesn't outweight an ability to have a transition table available at compile-time.
IMHO, transition maps exist to make FSM transitions visible at the first glance. No need to involve event handlers into this and take away several useful features by this, such as return values and template event handlers, and add these "id< ... >" arguments on top of that.
An ability to define one function for transitions from several states is more important than template handlers. I agree that id<...> is not convinient. I'd be happy to get rid of it.
Actually, it's the way Boost.FSM is implemented except that it doesn't allow to access one state from another and therefore ensures encapsulation.
I couldn't build a sample program neither on gcc 3.4.6 nor on Intel Linux 8.1 so I can only guess that dynamic_cast<OtherState*>(this) would access OtherState from *this state. -- Alexander Nasonov http://nasonov.blogspot.com Nothing is more obstinate than a fashionable consensus. -- Margaret Thatcher -- This quote is generated by: /usr/pkg/bin/curl -L http://tinyurl.com/veusy \ | sed -e 's/^document\.write(.//' -e 's/.);$/ --/' \ -e 's/<[^>]*>//g' -e 's/^More quotes from //' \ | fmt | tee ~/.signature-quote
Hello Alexander, Wednesday, January 3, 2007, 11:45:15 PM, you wrote:
Andrey Semashev wrote:
Wednesday, January 3, 2007, 9:46:16 PM, you wrote:
It would return variant<State1&, State2&, /* ... */ >. Visual representation of FSM would be fuzzy but it still better than no visual representation at all.
The "variant" has a limited set of possible types
So does any state machine - it has a limited set of types ;-)
To my mind, the default limit for "variant" is 10 types. A medium-scaled FSM may easily have more states. So if there would be some dispatching state that decides further behavior of the machine, we'd have a problem here. Of course, the example is a bit theoretical but I had something of that kind in my experience, yet not that big.
and it takes some time to dispatch the real type of the object it stores. It a resonable price for the flexibility.
I'd rather say, in many cases it is.
Besides, I'd like to keep the ability to return something useful for the user from "on_process".
IMO, it doesn't outweight an ability to have a transition table available at compile-time.
The fact is, it doesn't actually prevent you from having one.
IMHO, transition maps exist to make FSM transitions visible at the first glance. No need to involve event handlers into this and take away several useful features by this, such as return values and template event handlers, and add these "id< ... >" arguments on top of that.
An ability to define one function for transitions from several states is more important than template handlers.
I can't agree with you here. First, transition maps don't prevent you from defining a transition that is applicable to more than one state. Moreover, you may define a transition that triggers on several events too. In fact, it is a far more flexible mechanism than trying to use state handlers for this purpose. Second, I found that template event handlers are very useful when the set of possible events is rather big and they are all (maybe, except several of them I'm interested in at the particular state) processed in a common way. Using event base classes and polymorphism isn't always suitable to solve the problem. From my point of view, performing a transition and processing an event are quite different and even may be orthogonal tasks. The first is aimed to control the internal state and behavior of the FSM, and the second implements the behavior.
I agree that id<...> is not convinient. I'd be happy to get rid of it.
Actually, it's the way Boost.FSM is implemented except that it doesn't allow to access one state from another and therefore ensures encapsulation.
I couldn't build a sample program neither on gcc 3.4.6 nor on Intel Linux 8.1 so I can only guess that dynamic_cast<OtherState*>(this) would access OtherState from *this state.
Ah, yes, the "dynamic_cast" would do the trick. :) But this looks more like a hack rather than intended feature, doesn't it? Could you be more specific about your problems with ICC and GCC on Linux? I don't have such configurations at my disposal, so I would appreciate any help with these. Thank you. -- Best regards, Andrey mailto:andysem@mail.ru
Andrey Semashev wrote:
Could you be more specific about your problems with ICC and GCC on Linux? I don't have such configurations at my disposal, so I would appreciate any help with these. Thank you.
It's not Linux, I run FreeBSD. Intel for Linux has been ported to FreeBSD. %uname -a FreeBSD fbx1000 6.2-PRERELEASE FreeBSD 6.2-PRERELEASE #0: Sat Oct 7 17:41:17 MSD 2006 alnsn@fbx1000:/home/OBJ/MAKEOBJDIRPREFIX/usr/src/sys/GENERIC i386 %pwd /home/alnsn/src/boost/vault/fsm/libs/fsm/test/fsm_test1 %g++ -v Using built-in specs. Configured with: FreeBSD/i386 system compiler Thread model: posix gcc version 3.4.6 [FreeBSD] 20060305 %g++ -I../../../.. -I/usr/pkg/include -L/usr/pkg/lib -lboost_test_exec_monitor-mt *.cpp | & tee gcc.err Output is in attached gcc.err.gz file. %/usr/local/intel_cc_80/bin/icpc -V Intel(R) C++ Compiler for 32-bit applications, Version 8.1 Build 20060606Z Package ID: l_cc_pc_8.1.038 Copyright (C) 1985-2006 Intel Corporation. All rights reserved. FOR NON-COMMERCIAL USE ONLY %/usr/local/intel_cc_80/bin/icpc -I../../../.. -I/usr/pkg/include -L/usr/pkg/lib -lboost_test_exec_monitor-mt *.cpp | & tee intel.err Output is in attached intel.err.gz file. I use boost 1.33.1 installed by NetBSD package system (www.pkgsrc.org). -- Alexander Nasonov http://nasonov.blogspot.com It is largely because the free-thinkers, as a school, have hardly made up their minds whether they want to be more optimist or more pessimist than Christianity that their small but sincere movement has failed. For the duel is deadly; and any agnostic who wishes to be anything more than a Nihilist must sympathize with one version of nature or the other. -- GK Chesterton -- This quote is generated by: /usr/pkg/bin/curl -L http://tinyurl.com/veusy \ | sed -e 's/^document\.write(.//' -e 's/.);$/ --/' \ -e 's/<[^>]*>//g' -e 's/^More quotes from //' \ | fmt | tee ~/.signature-quote
Hello Alexander, Thursday, January 4, 2007, 3:15:50 PM, you wrote:
Andrey Semashev wrote:
Could you be more specific about your problems with ICC and GCC on Linux? I don't have such configurations at my disposal, so I would appreciate any help with these. Thank you.
It's not Linux, I run FreeBSD. Intel for Linux has been ported to FreeBSD.
%uname -a FreeBSD fbx1000 6.2-PRERELEASE FreeBSD 6.2-PRERELEASE #0: Sat Oct 7 17:41:17 MSD 2006 alnsn@fbx1000:/home/OBJ/MAKEOBJDIRPREFIX/usr/src/sys/GENERIC i386
%pwd /home/alnsn/src/boost/vault/fsm/libs/fsm/test/fsm_test1
%g++ -v Using built-in specs. Configured with: FreeBSD/i386 system compiler Thread model: posix gcc version 3.4.6 [FreeBSD] 20060305
%g++ -I../../../.. -I/usr/pkg/include -L/usr/pkg/lib -lboost_test_exec_monitor-mt *.cpp | & tee gcc.err
Output is in attached gcc.err.gz file.
%/usr/local/intel_cc_80/bin/icpc -V Intel(R) C++ Compiler for 32-bit applications, Version 8.1 Build 20060606Z Package ID: l_cc_pc_8.1.038 Copyright (C) 1985-2006 Intel Corporation. All rights reserved. FOR NON-COMMERCIAL USE ONLY
%/usr/local/intel_cc_80/bin/icpc -I../../../.. -I/usr/pkg/include -L/usr/pkg/lib -lboost_test_exec_monitor-mt *.cpp | & tee intel.err
Output is in attached intel.err.gz file.
I use boost 1.33.1 installed by NetBSD package system (www.pkgsrc.org).
Hopefully, I have fixed those errors. I've attached patched files to replace the corresponding original ones. I'm not sure wether Intel compiler supports all GCC attributes I use and I cannot test it. Could you try to compile the test with these fixes? If it works then I wonder if I should update the version in the Vault. -- Best regards, Andrey mailto:andysem@mail.ru
Andrey Semashev wrote:
Hopefully, I have fixed those errors. I've attached patched files to replace the corresponding original ones. I'm not sure wether Intel compiler supports all GCC attributes I use and I cannot test it. Could you try to compile the test with these fixes?
It fixed gcc ICE but now it takes 39.5 seconds to build the test. %time g++ -I../../../.. -I/usr/pkg/include -L/usr/pkg/lib -lboost_test_exec_monitor-mt *.cpp /usr/pkg/lib/libboost_test_exec_monitor-mt.so: undefined reference to `test_main(int, char**)' 39.499u 1.261s 0:41.81 97.4% 4535+5563k 0+142io 0pf+0w Some Intel errors went away but I still see a lot of ../../../../boost/fsm/state_machine.hpp(486): error: function returning function is not allowed return_type (BOOST_FSM_FASTCALL*)(StatesCompoundT&, EventT const&), ^ ../../../../boost/fsm/state_machine.hpp(487): error: function returning function is not allowed return_type (BOOST_FSM_FASTCALL*)(StatesCompoundT&, EventT const&) ^ -- Alexander Nasonov http://nasonov.blogspot.com No man is entitled to the blessings of freedom unless he be vigilant in its preservation. -- Douglas MacArthur -- This quote is generated by: /usr/pkg/bin/curl -L http://tinyurl.com/veusy \ | sed -e 's/^document\.write(.//' -e 's/.);$/ --/' \ -e 's/<[^>]*>//g' -e 's/^More quotes from //' \ | fmt | tee ~/.signature-quote
Hello Alexander, Thursday, January 4, 2007, 11:42:32 PM, you wrote:
Andrey Semashev wrote:
Hopefully, I have fixed those errors. I've attached patched files to replace the corresponding original ones. I'm not sure wether Intel compiler supports all GCC attributes I use and I cannot test it. Could you try to compile the test with these fixes?
Some Intel errors went away but I still see a lot of
.../../../../boost/fsm/state_machine.hpp(486): error: function returning function is not allowed return_type (BOOST_FSM_FASTCALL*)(StatesCompoundT&, EventT const&), ^
.../../../../boost/fsm/state_machine.hpp(487): error: function returning function is not allowed return_type (BOOST_FSM_FASTCALL*)(StatesCompoundT&, EventT const&) ^
Seems that Intel has problems in parsing function pointer types inside template parameter types. I've attached a changed version that might fix the problem, please, try it if you have some time. I think, I'll update the documentation as you requested in your post in a couple of days and put the new version to the Vault. It will have all fixes I have made so far. BTW, it will have a fix that denies cross-casting between states, as you noticed earlier. Though, a conforming compiler is needed for the protection to work. -- Best regards, Andrey mailto:andysem@mail.ru
Andrey Semashev wrote:
Seems that Intel has problems in parsing function pointer types inside template parameter types. I've attached a changed version that might fix the problem, please, try it if you have some time.
%time /usr/local/intel_cc_80/bin/icpc -I../../../.. -I/usr/pkg/include -c *.cpp 27.303u 2.431s 0:30.70 96.8% 9952+47860k 0+436io 0pf+0w It now compiles the test.
I think, I'll update the documentation as you requested in your post in a couple of days and put the new version to the Vault. It will have all fixes I have made so far. BTW, it will have a fix that denies cross-casting between states, as you noticed earlier. Though, a conforming compiler is needed for the protection to work.
Please, also add a complete example from tutorial to libs/fsm/example. This would help a lot to reviewers of your library. -- Alexander Nasonov http://nasonov.blogspot.com Persistence and determination alone are omnipotent. The slogan `press on` has solved and always will solve the problems of the human race. -- Calvin Coolidge -- This quote is generated by: /usr/pkg/bin/curl -L http://tinyurl.com/veusy \ | sed -e 's/^document\.write(.//' -e 's/.);$/ --/' \ -e 's/<[^>]*>//g' -e 's/^More quotes from //' \ | fmt | tee ~/.signature-quote
Hello Pavel, Sunday, December 17, 2006, 11:28:26 PM, you wrote:
"Andrey Semashev" wrote:
[ snip differences between Boost.Statechart and the proposed FSM ]
That being said, I may only purpose my implementation as a lightweight addition to the Boost.Statechart aimed to solve performance and simplicity issues for small and light FSMs. Is there any need in such?
The Statechart library is named as is not to give impression that this is the only possible FSM implementation in Boost.
So, is that a "yes" answer?
-------------
An interesting idea had bubbled up during the review - a FSM that could be "hidden" within a class and would simplify internals of the class.
Something like that was described on: http://www.codeproject.com/cpp/statebased.asp but this implementation is IMHO too complicated for the end user.
Actually, the case in the article is quite common in my practice - I have an interface or a class that I'd rather implement as FSM. That's why I added a simplified events support based on tuples. Though, I couldn't find any automatic way to translate interface method calls into events except by hand or with a code generator. -- Best regards, Andrey mailto:andysem@mail.ru
Hi Andrey Andrey Semashev wrote:
Well, I have read the Boost.Statechart documentation. Its functionality covers and extends my proposed implementation, though I must note its several deficiences: - The author notes the performance issue of Boost.Statechart. I have not inspected the library implementation but as I can see from the documentation, the performance of transition between states and event delivery to a reaction handler linearly depends on the number of reactions in the state.
Correct. However, measurements have shown that this is not normally the performance bottleneck in a Boost.Statechart FSM (see conclusions under "Detailed performance data"): <http://www.boost-consulting.com/boost/libs/statechart/doc/performance.html#SpeedVersusScalabilityTradeoffs> Because everything is known at compile time, compilers are able to inline and optimize rather aggressively in the dispatch code.
Additionally, a transition between states involves memory allocations which, besides the performance losses in the first place, leads to memory fragmentation. A custom pooling allocator partially addresses the problem but in most real-world applications it will not evade the necessity of pool synchronization costs.
I don't think dynamic memory allocation by itself is the main performance bottleneck either. Rather, my performance measurements suggest that the main bottleneck is in the code that enters and exists the states during a transition. Currently, due to the fact that this code needs to work correctly even if user-supplied actions throw exceptions, some additional book-kepping is necessary even if the user does not need the error-handling features. My guess is that performance can be increased by 50% if this is optimized further.
In the proposed implementation no allocations take place neither on transitions nor on event delivery. In addition, none of these operations depend on state, transitions or reactions number.
As soon as an FSM needs to be able to process events of arbitrary types you usually need to allocate these events on the free store anyway, also allocating the states there just doubles the runtime needed for new/delete. Sure, you can save all those free store allocations when your FSMs only need to deal with one type of event and state but for many applications this simply is not flexible enough.
The implementation even tries to minimize virtual function usage. So, even though I haven't done experimental comparisons, IMO the proposed implementation will outperform Boost.Statechart.
That wouldn't surprise me at all. Again, please see: <http://www.boost-consulting.com/boost/libs/statechart/doc/performance.html#SpeedVersusScalabilityTradeoffs>
- In Boost.Statechart to declare a custom reaction on some event we must add it as an element to the "reactions" typedef besides defining a "react" member function. No such duplication is needed in the proposed implementation - only "on_process" (the synonym for "react") handler is needed. As a nice side effect it is possible to rely on C++ overload resolution rules and even declare "on_process" templates. That makes the state code cleaner and more natural, IMO. - I can see no way to return a value from a Boost.Statechart's machine except by passing a reference or a pointer in the event.
Correct. How do you return a value? With boost::any?
- I can see no easy way to describe a transition that should take place regardless of the current state of the machine in Boost.Statechart. To do this one must put the transition into each state's "reactions" type sequence.
There are two ways: 1. Define an outermost state that contains all other states and add a reaction triggered by event_base. 2. Add a member-function unconsumed_event to the state_machine<> subclass: <http://www.boost-consulting.com/boost/libs/statechart/doc/reference.html#unconsumed_event>
That being said, I may only purpose my implementation as a lightweight addition to the Boost.Statechart aimed to solve performance and simplicity issues for small and light FSMs. Is there any need in such?
I don't have time to look at your proposal right now, but I would guess that there is a need in a simple FSM lib that does not have all the bells and whistles of Boost.Statechart but does provide top-notch performance in return. However, I don't see how it can be a part of Boost.Statechart, it should probably be a separate library. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
Hello Andreas, Friday, December 22, 2006, 6:52:03 PM, you wrote:
Hi Andrey
[snip the performance discussion]
In the proposed implementation no allocations take place neither on transitions nor on event delivery. In addition, none of these operations depend on state, transitions or reactions number.
As soon as an FSM needs to be able to process events of arbitrary types you usually need to allocate these events on the free store anyway, also allocating the states there just doubles the runtime needed for new/delete. Sure, you can save all those free store allocations when your FSMs only need to deal with one type of event and state but for many applications this simply is not flexible enough.
I can't quite agree with you. As it comes from my experience, one of the most frequent FSM use cases is when the state machine implements some public interface. In this case interface method calls have to be translated into events that may be accepted by FSM. And most likely these events will be on the stack. As for states' allocation and deallocation, there may be other issues with it, besides of performance loss. I'm not quite sure you have read our discussion with Alexander Nasonov in this thread, where I pointed out that the fact that the state is deleted when being left may be inconvenient if the state has its local data. If the state is visited again all these data are lost. And moving these data to an outer state or even the to the state machine class makes it exposed to other states that shouldn't have had access to it. Additionally as the data amount and states number raises the code of these data-holding classes gets more messy. [snip]
- I can see no way to return a value from a Boost.Statechart's machine except by passing a reference or a pointer in the event.
Correct. How do you return a value? With boost::any?
Not necessarily. The return type is passed in a state machine's template parameter and may be any type, including boost::any. This feature is optional, so by default this type is "void" (IOW, the FSM returns nothing).
- I can see no easy way to describe a transition that should take place regardless of the current state of the machine in Boost.Statechart. To do this one must put the transition into each state's "reactions" type sequence.
There are two ways: 1. Define an outermost state that contains all other states and add a reaction triggered by event_base. 2. Add a member-function unconsumed_event to the state_machine<> subclass: <http://www.boost-consulting.com/boost/libs/statechart/doc/reference.html#unconsumed_event>
I see. Actually, the first way is what I was looking for. The second one allows a quite different thing, as I see it: to make a default reaction on any unexpected (not specific and maybe expected) event in any state. BTW, is there any way to make Boost.Statechart's machine not compiling if it doesn't expect some particular event type? IOW, to force the machine to support all event types being passed to it? There is a way to do so in Boost.FSM, though this feature is not pointed out in the documentation. I'll update it before formal review request.
That being said, I may only purpose my implementation as a lightweight addition to the Boost.Statechart aimed to solve performance and simplicity issues for small and light FSMs. Is there any need in such?
I don't have time to look at your proposal right now, but I would guess that there is a need in a simple FSM lib that does not have all the bells and whistles of Boost.Statechart but does provide top-notch performance in return. However, I don't see how it can be a part of Boost.Statechart, it should probably be a separate library.
Agreed, I too see it as a separate lib that complements Statechart. -- Best regards, Andrey mailto:andysem@mail.ru PS: Thank you for such a detailed answer. I have almost began thinking that there's too little interest in this library.
Andrey Semashev wrote:
As soon as an FSM needs to be able to process events of arbitrary types you usually need to allocate these events on the free store anyway, also allocating the states there just doubles the runtime needed for new/delete. Sure, you can save all those free store allocations when your FSMs only need to deal with one type of event and state but for many applications this simply is not flexible enough.
I can't quite agree with you. As it comes from my experience, one of the most frequent FSM use cases is when the state machine implements some public interface. In this case interface method calls have to be translated into events that may be accepted by FSM. And most likely these events will be on the stack.
Fair enough, my experience mainly comes from applications where an FSM either runs in its own thread or is fed by some kind of scheduler. As I've explained in the performance document, in such a scenario the inter-thread synchronization costs are usually far higher than cost of anything Boost.Statechart does.
As for states' allocation and deallocation, there may be other issues with it, besides of performance loss. I'm not quite sure you have read our discussion with Alexander Nasonov in this thread, where I pointed out that the fact that the state is deleted when being left may be inconvenient if the state has its local data. If the state is visited again all these data are lost.
Right, in my experience this is the behavior that is most commonly wanted. IIUC, what you want is something like the currently supported history but with the added feature that all local variables are also restored upon entry of the state. Such a feature has been suggested before but I've so far not found a satisfying way to implement it. IMO, you definitely need both options and sometimes a state even contains multiple variables with different needs of resetting/reconstitution.
And moving these data to an outer state or even the to the state machine class makes it exposed to other states that shouldn't have had access to it.
Correct, it's not an optimal solution, but it is in my experience not needed very often.
Additionally as the data amount and states number raises the code of these data-holding classes gets more messy.
You've lost me here: Which data-holding classes? In Boost.Statechart there are only states.
- I can see no way to return a value from a Boost.Statechart's machine except by passing a reference or a pointer in the event.
Correct. How do you return a value? With boost::any?
Not necessarily. The return type is passed in a state machine's template parameter and may be any type, including boost::any. This feature is optional, so by default this type is "void" (IOW, the FSM returns nothing).
I see that something like this could useful for the use-case you described. It's not supported in my library because for asynchronous machines the return value would be lost anyway and even for synchronous machines it would be meaningless when a machine processes multiple events in one call as a result of the posting of an internal event. It is probably for these reasons that the UML standard does not allow a return value.
BTW, is there any way to make Boost.Statechart's machine not compiling if it doesn't expect some particular event type? IOW, to force the machine to support all event types being passed to it?
No, as that would require the implementation of the whole machine in one TU. IMO, the ability to compile parts of a large machine separately is more important in practice. -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
Hello Andreas, Friday, December 22, 2006, 10:23:50 PM, you wrote:
Andrey Semashev wrote:
As soon as an FSM needs to be able to process events of arbitrary types you usually need to allocate these events on the free store anyway, also allocating the states there just doubles the runtime needed for new/delete. Sure, you can save all those free store allocations when your FSMs only need to deal with one type of event and state but for many applications this simply is not flexible enough.
I can't quite agree with you. As it comes from my experience, one of the most frequent FSM use cases is when the state machine implements some public interface. In this case interface method calls have to be translated into events that may be accepted by FSM. And most likely these events will be on the stack.
Fair enough, my experience mainly comes from applications where an FSM either runs in its own thread or is fed by some kind of scheduler. As I've explained in the performance document, in such a scenario the inter-thread synchronization costs are usually far higher than cost of anything Boost.Statechart does.
That's right, threading costs overcome the FSM infrastructure costs by far. I was comparing the two libraries both in single thread context.
As for states' allocation and deallocation, there may be other issues with it, besides of performance loss. I'm not quite sure you have read our discussion with Alexander Nasonov in this thread, where I pointed out that the fact that the state is deleted when being left may be inconvenient if the state has its local data. If the state is visited again all these data are lost.
Right, in my experience this is the behavior that is most commonly wanted. IIUC, what you want is something like the currently supported history but with the added feature that all local variables are also restored upon entry of the state. Such a feature has been suggested before but I've so far not found a satisfying way to implement it. IMO, you definitely need both options and sometimes a state even contains multiple variables with different needs of resetting/reconstitution.
Agreed, that's why I decided not to delete states during transitions. If some variables need to be reset when the state is being left, a user may implement such logic in the appropriate handler function. Just a thought of similar functionality support in Statechart. If there was an additional optional template parameter in the "state" or "simple_state" class template that would have a type of the state's context which lifetime would last from the first entrance into the state until the whole state machine destruction (let's call it a static state context), then a reference to the context might have been passed to the state's constructor. For example: // This will be the static context struct State1Ctx { int n; }; struct State1 : public sc::simple_state< State1, OuterState, State1Ctx > { // This reference will hold the context State1Ctx& static_ctx_; // In ctor we receive a reference to the static context. // No matter how many times we enter the state, // we get the reference to the same object here State1(State1Ctx& ctx) : static_ctx_(ctx) { } }; Or, alternatively, the static_ctx_ reference may even be in the "simple_state" class itself. It may be accessible via some public method.
And moving these data to an outer state or even the to the state machine class makes it exposed to other states that shouldn't have had access to it.
Correct, it's not an optimal solution, but it is in my experience not needed very often.
I wouldn't say it's vital for a user. It's just a question of quality of user's code that uses the library. But, IMHO, the FSM concept should help to distinguish and separate states of an object.
Additionally as the data amount and states number raises the code of these data-holding classes gets more messy.
You've lost me here: Which data-holding classes? In Boost.Statechart there are only states.
By "data-holding classes" I meant collectively states and the state machine classes that can hold data of inner states that we were discussing above. I was saying that as the amount of states grows so does the amount of data. And if it is stored in some outer state, the state becomes overweightened and messy. To my mind this issue should be of special concern since Statechart is more targeted to creation of bigger state machines.
- I can see no way to return a value from a Boost.Statechart's machine except by passing a reference or a pointer in the event.
Correct. How do you return a value? With boost::any?
Not necessarily. The return type is passed in a state machine's template parameter and may be any type, including boost::any. This feature is optional, so by default this type is "void" (IOW, the FSM returns nothing).
I see that something like this could useful for the use-case you described. It's not supported in my library because for asynchronous machines the return value would be lost anyway and even for synchronous machines it would be meaningless when a machine processes multiple events in one call as a result of the posting of an internal event. It is probably for these reasons that the UML standard does not allow a return value.
I see. Probably, you're right, there's little use of this functionality in cases you describe.
BTW, is there any way to make Boost.Statechart's machine not compiling if it doesn't expect some particular event type? IOW, to force the machine to support all event types being passed to it?
No, as that would require the implementation of the whole machine in one TU. IMO, the ability to compile parts of a large machine separately is more important in practice.
Ah, that's right. Modularity takes its toll. -- Best regards, Andrey mailto:andysem@mail.ru
Andrey Semashev wrote:
As for states' allocation and deallocation, there may be other issues with it, besides of performance loss. I'm not quite sure you have read our discussion with Alexander Nasonov in this thread, where I pointed out that the fact that the state is deleted when being left may be inconvenient if the state has its local data. If the state is visited again all these data are lost.
Right, in my experience this is the behavior that is most commonly wanted. IIUC, what you want is something like the currently supported history but with the added feature that all local variables are also restored upon entry of the state. Such a feature has been suggested before but I've so far not found a satisfying way to implement it. IMO, you definitely need both options and sometimes a state even contains multiple variables with different needs of resetting/reconstitution.
Agreed, that's why I decided not to delete states during transitions. If some variables need to be reset when the state is being left, a user may implement such logic in the appropriate handler function.
In your library, is there any way to do this automatically, a la RAII? I'm asking because in my experience, you often need to acquire a resource upon state entry and release it upon state exit. It's error-prone when you need to release explicitly, just as it is error-prone when you need to manually release resources at the end of a block scope. That's why Boost.Statechart has this strict state-exit to destructor mapping. If you need a variable to live longer you push it into an outer state, just as you do with a variable allocated on the stack when you push it into an outer scope. Yes, this is suboptimal in the sense that other inner states of the outer state can then also access said variable, but the same is true for stack variables.
Just a thought of similar functionality support in Statechart. If there was an additional optional template parameter in the "state" or "simple_state" class template that would have a type of the state's context which lifetime would last from the first entrance into the state until the whole state machine destruction (let's call it a static state context), then a reference to the context might have been passed to the state's constructor. For example:
// This will be the static context struct State1Ctx { int n; };
struct State1 : public sc::simple_state< State1, OuterState, State1Ctx > { // This reference will hold the context State1Ctx& static_ctx_;
// In ctor we receive a reference to the static context. // No matter how many times we enter the state, // we get the reference to the same object here State1(State1Ctx& ctx) : static_ctx_(ctx) { } };
Or, alternatively, the static_ctx_ reference may even be in the "simple_state" class itself. It may be accessible via some public method.
I'd hate to add yet another template parameter, but the same could be achieved via specializations of a template (suggested long ago by Dave Abrahams): In simple-state.hpp: template<class State> class private_state_context {}; // Probably needs a better name template< class MostDerived, ... > class simple_state { // ... private_state_context< MostDerived > & private_context(); const private_state_context< MostDerived > & private_context() const; // ... }; If a user needs a private context for a state, she can specialize the private_state_context template for said state. It should be pretty easy to add something like this. The only problem is that every added feature also increases the opportunities for abuse and confusion. I'll think about this some more and then maybe add it to the to-do list.
Additionally as the data amount and states number raises the code of these data-holding classes gets more messy.
You've lost me here: Which data-holding classes? In Boost.Statechart there are only states.
By "data-holding classes" I meant collectively states and the state machine classes that can hold data of inner states that we were discussing above.
Ok.
I was saying that as the amount of states grows so does the amount of data. And if it is stored in some outer state, the state becomes overweightened and messy.
I agree for the cases when you need to push outward a variable due to lifetime-issues only (i.e. the variable is still only accessed by the state that originally contained it). However, IME, outer states are almost never pure data holding classes, they *usually* have behavior of their own and often need to access precisely the variables that were pushed outward from inner states (e.g. see the Stopwatch example).
To my mind this issue should be of special concern since Statechart is more targeted to creation of bigger state machines.
It has been a concern, I'm just unsure how it is best solved.
BTW, is there any way to make Boost.Statechart's machine not compiling if it doesn't expect some particular event type? IOW, to force the machine to support all event types being passed to it?
No, as that would require the implementation of the whole machine in one TU. IMO, the ability to compile parts of a large machine separately is more important in practice.
Ah, that's right. Modularity takes its toll.
Precisely, as do many other features. I have to accept that the library cannot satisfy all needs, e.g. especially parser-like FSMs are better implemented by other means. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
Hello Andreas, Saturday, December 23, 2006, 1:16:14 PM, you wrote: [snip]
Agreed, that's why I decided not to delete states during transitions. If some variables need to be reset when the state is being left, a user may implement such logic in the appropriate handler function.
In your library, is there any way to do this automatically, a la RAII?
I'm asking because in my experience, you often need to acquire a resource upon state entry and release it upon state exit. It's error-prone when you need to release explicitly, just as it is error-prone when you need to manually release resources at the end of a block scope. That's why Boost.Statechart has this strict state-exit to destructor mapping. If you need a variable to live longer you push it into an outer state, just as you do with a variable allocated on the stack when you push it into an outer scope. Yes, this is suboptimal in the sense that other inner states of the outer state can then also access said variable, but the same is true for stack variables.
No, there's no automatic way to do this in my lib. Both approaches have their pros and cons. But some degree of automation may be achieved with little effort on user's behalf. A state may inherit some base class which will contain a stack of function objects to invoke when the state is left. Such stack is already implemented in my ScopeGuard library that I have yet to reintroduce (it was introduced long ago but due to some personal reasons I couldn't finish the library submission process). And this base class may also define the default handler of leaving the state that will call function objects in that stack. And since every state may inherit such base class, this functionality is written only once. The only thing user will have to do then is to push a functor to the stack that will release the resource in state exit. This may be done right in the place of the resource acquirement. I understand, this is not a complete automatization, but to my mind this might help to elide coding mistakes you were speaking of.
Just a thought of similar functionality support in Statechart.
[snip the code illustration]
I'd hate to add yet another template parameter, but the same could be achieved via specializations of a template (suggested long ago by Dave Abrahams):
In simple-state.hpp:
template<class State> class private_state_context {}; // Probably needs a better name
template< class MostDerived, ... > class simple_state { // ... private_state_context< MostDerived > & private_context(); const private_state_context< MostDerived > & private_context() const; // ... };
If a user needs a private context for a state, she can specialize the private_state_context template for said state. It should be pretty easy to add something like this. The only problem is that every added feature also increases the opportunities for abuse and confusion. I'll think about this some more and then maybe add it to the to-do list.
That solution would be fine too. [snip other parts] -- Best regards, Andrey mailto:andysem@mail.ru
Andrey Semashev wrote:
Hi,
I would like to purpose a new library addition to Boost: Boost.FSM. FSM stands for Finite State Machine, so the library is aimed to ease creation and support of state machines in C++.
I had time to scan the docs quickly, it looks promising. I have some ideas that may be useful: 1. In addition to typed events, it'd be great to support integral events (or enums). It can be archived by using mpl::integral_c in on_process function. 2. Use states hierarchy to model inner and outer states. 3. Make the library ROM friendly. Ignore this, if it's already implemented. 4. Make sure it may scale beyond default mpl::vector capacity. -- Alexander Nasonov http://nasonov.blogspot.com
Hello Alexander, Tuesday, December 19, 2006, 12:55:16 AM, you wrote:
Andrey Semashev wrote:
Hi,
I would like to purpose a new library addition to Boost: Boost.FSM. FSM stands for Finite State Machine, so the library is aimed to ease creation and support of state machines in C++.
I had time to scan the docs quickly, it looks promising. I have some ideas that may be useful:
1. In addition to typed events, it'd be great to support integral events (or enums). It can be archived by using mpl::integral_c in on_process function.
Nice idea.
2. Use states hierarchy to model inner and outer states.
I've been thinking about it, but I can't figure out a simple way to implement it. In some way it may already be implemented by user with virtual base classes, but from FSM's point of view these virtual bases are not states, so they don't have state_ids, for example. I'll be thinking further.
3. Make the library ROM friendly. Ignore this, if it's already implemented.
ROM friendly? What is it?
4. Make sure it may scale beyond default mpl::vector capacity.
You may use any MPL sequence when expressing states and transition rules, including mpl::list which is far less limited. But speaking frankly, I think a compiler may die even before mpl::vector limit is reached. -- Best regards, Andrey mailto:andysem@mail.ru
Andrey Semashev wrote:
ROM friendly? What is it?
This means in particular that the transition table should be initialized at static phase of static initialization so that a compiler can store it in read-only memory. I know it's very important in embedded environment where fsm are often used, to store as much as possible in read-only memory.
4. Make sure it may scale beyond default mpl::vector capacity.
You may use any MPL sequence when expressing states and transition rules, including mpl::list which is far less limited. But speaking frankly, I think a compiler may die even before mpl::vector limit is reached.
I remember I compiled the "unique" metafunction for a list of more than 400 transitions. I thought about spliting my global transition table to several smaller tables (for example, each table would represent all transitions from given state) and instantiate each table in separate translation units. -- Alexander Nasonov http://nasonov.blogspot.com Humanity is acquiring all the right technology for all the wrong reasons. -- Buckminster Fuller -- This quote is generated by: /usr/pkg/bin/curl -L http://tinyurl.com/veusy \ | sed -e 's/^document\.write(.//' -e 's/.);$/ --/' \ -e 's/<[^>]*>//g' -e 's/^More quotes from //' \ | fmt | tee ~/.signature-quote
"Alexander Nasonov" wrote:
Andrey Semashev wrote:
ROM friendly? What is it?
This means in particular that the transition table should be initialized at static phase of static initialization so that a compiler can store it in read-only memory. I know it's very important in embedded environment where fsm are often used, to store as much as possible in read-only memory.
Such ROMable classes also cannot have constructors or destructors. /Pavel
Hello Pavel, Wednesday, December 20, 2006, 5:33:23 AM, you wrote:
"Alexander Nasonov" wrote:
Andrey Semashev wrote:
ROM friendly? What is it?
This means in particular that the transition table should be initialized at static phase of static initialization so that a compiler can store it in read-only memory. I know it's very important in embedded environment where fsm are often used, to store as much as possible in read-only memory.
Such ROMable classes also cannot have constructors or destructors.
The transition rules are never created, so they are ROM friendly. :) I'm not quite sure if it is possible to make other entities of FSM read-only with no structors. There are quite a few static dispatching maps in the implementation, but they have to be filled sometime, even though they are constant through the rest of the state machine's lifetime. -- Best regards, Andrey mailto:andysem@mail.ru
participants (5)
-
Alexander Nasonov -
Andreas Huber -
Andrey Semashev -
Bryan Ewbank -
Pavel Vozenilek