Please, comment design decision of simple FSM
After playing with my overloads library and trying to apply it to FSM I realized that some metaprogramming can be replaced with natural overload resolution rules. After realizing it, I come to conclusion that simple FSM can be implemented as a set of call operators and a list of states. Each call operator represents a transition and follows this pattern: NewState operator()(State,Event) const; Transition functions are generated in process_event function on first call (in a constructor of static variable, for example). Each function extracts current state from StatesAsVariant (boost::variant of all states): template<class StatesAsVariant, class State, class Event> void transition(FSM& fsm, StatesAsVariant states, Event event) { states = fsm( get<State>(states), event); // select best transition // according to overload // resolution rules } The only metaprogramming algorithm is for_each<States> to initialize transition table for the event. Comments? -- Alexander Nasonov
Alexander Nasonov wrote:
Comments?
This all looks very nice. Is it possible to use this scheme with polymorphic states, as follows: struct Active {}; struct Stopped : Active {}; struct Running : Active {}; struct EvStartStop {}; struct EvReset {}; struct Fsm { Stopped operator()( Running, EvStartStop ) { return Stopped(); } Running operator()( Stopped, EvStartStop ) { return Running(); } Stopped operator()( Active, EvReset ) { return Stopped(); } }; Note that the EvReset transition should be triggered when the state machine currently resides in either Stopped *or* Running. ? Regards, Andreas
Alexander Nasonov wrote:
Andreas Huber wrote:
This all looks very nice. Is it possible to use this scheme with polymorphic states, as follows:
See attachment. It is slow but demonstrates the idea and can be improved later.
Wow! So simple and yet powerful. It naturally supports nested states and polymorphic events. I guess this could quite easily be developed into a fast & lightweight boost::fsm alternative. Cool! Regards, Andreas
"Andreas Huber" <ah2003@gmx.net> writes:
Alexander Nasonov wrote:
Andreas Huber wrote:
This all looks very nice. Is it possible to use this scheme with polymorphic states, as follows:
See attachment. It is slow but demonstrates the idea and can be improved later.
Wow! So simple and yet powerful. It naturally supports nested states and polymorphic events. I guess this could quite easily be developed into a fast & lightweight boost::fsm alternative. Cool!
It's very close to the organization of the MPL FSM samples I have posted in the past... only there's no dumb O(N) for_each dispatching in my samples: they're O(1). -- Dave Abrahams Boost Consulting http://www.boost-consulting.com
David Abrahams wrote:
"Andreas Huber" <ah2003@gmx.net> writes:
Alexander Nasonov wrote:
Andreas Huber wrote:
This all looks very nice. Is it possible to use this scheme with polymorphic states, as follows:
See attachment. It is slow but demonstrates the idea and can be improved later.
Wow! So simple and yet powerful. It naturally supports nested states and polymorphic events. I guess this could quite easily be developed into a fast & lightweight boost::fsm alternative. Cool!
It's very close to the organization of the MPL FSM samples I have posted in the past...
Yep, I had noticed that. What I like better about Alexander's approach is that the transition table is implemented with ordinary C++ what makes it quite a bit more expressive than the MPL collections you used in your examples. Don't get me wrong, I personally love MPL, but I've found that the average programmer is easily scared away with even very simple MPL constructs.
only there's no dumb O(N) for_each dispatching in my samples: they're O(1).
Unless I'm missing something one could easily modify Alexander's code to be O(1) too...? Regards, Andreas
Andreas Huber wrote:
David Abrahams wrote:
"Andreas Huber" <ah2003@gmx.net> writes:
Wow! So simple and yet powerful. It naturally supports nested states and polymorphic events. I guess this could quite easily be developed into a fast & lightweight boost::fsm alternative. Cool!
It's very close to the organization of the MPL FSM samples I have posted in the past...
I saw them. They are cool :)
Yep, I had noticed that. What I like better about Alexander's approach is that the transition table is implemented with ordinary C++ what makes it quite a bit more expressive than the MPL collections you used in your examples. Don't get me wrong, I personally love MPL, but I've found that the average programmer is easily scared away with even very simple MPL constructs.
I didn't expected that simplicity. In order to check my ideas I need some metaprogramming. For example, if I number every call-operator (overload_id<N> in a first argument), I can collect all states automatically (unique_at algorithm). I can also collect all events (unique_at again) and move transition table for those events to cpp file if a user puts static initializer in Fsm class. I can also check with find_if and is_convertible if there is a match for given state and event. If not, I can dispatch to alternative. If you have other ideas, please share them with me. I'm really interested to make implementation more complex :)
only there's no dumb O(N) for_each dispatching in my samples: they're O(1).
Unless I'm missing something one could easily modify Alexander's code to be O(1) too...?
Yep -- Alexander Nasonov
Alexander Nasonov <alnsn <at> yandex.ru> writes:
I didn't expected that simplicity. In order to check my ideas I need some metaprogramming. For example, if I number every call-operator (overload_id<N> in a first argument), I can collect all states automatically (unique_at algorithm). I can also collect all events (unique_at again) and move transition table for those events to cpp file if a user puts static initializer in Fsm class.
Hmmm, but I guess you still need to have the whole transition table in one translation unit, right?
I can also check with find_if and is_convertible if there is a match for given state and event. If not, I can dispatch to alternative.
Why would you need to do that?
If you have other ideas, please share them with me. I'm really interested to make implementation more complex :)
I guess the most important thing is to implement O(1) dispatch. After that, I'd try to add entry and exit action support, though I guess that is going to wreck the current simplicity. Regards, Andreas
Andreas Huber wrote:
Hmmm, but I guess you still need to have the whole transition table in one translation unit, right?
There is no "whole transition table" in my example. The process_event function instantiates a part of the table for a given event, Therefore, it possible that they are instantiated in different TU.
I guess the most important thing is to implement O(1) dispatch.
Done. See attachment. -- Alexander Nasonov
Alexander Nasonov wrote:
Andreas Huber wrote:
Hmmm, but I guess you still need to have the whole transition table in one translation unit, right?
There is no "whole transition table" in my example. The process_event function instantiates a part of the table for a given event, Therefore, it possible that they are instantiated in different TU.
You're right. However, it would be more useful the other way round (if one could pack all the transitions for a each state in a different TU), but I think spreading such an FSM over multiple TUs is probably not that important anyway.
I guess the most important thing is to implement O(1) dispatch.
Done. See attachment.
Cool. Nitpick: By convention, if there's no transition for the current event from the current state then the event is simply discarded. If I read your code right, then it wouldn't compile if this is attempted. Wait, it seems that it doesn't compile if a given state has no transition for *any* of the events? Is that what you were talking about in one of your previous posts with enable_if, etc.? Regards, Andreas
Andreas Huber wrote:
Nitpick: By convention, if there's no transition for the current event from the current state then the event is simply discarded. If I read your code right, then it wouldn't compile if this is attempted. Wait, it seems that it doesn't compile if a given state has no transition for *any* of the events? Is that what you were talking about in one of your previous posts with enable_if, etc.?
Right. If you add unique id to each transition function (vector of states can be removed after that) and apply my algorithms you'll get it. This is how it will look like from a user point of view: struct Fsm : state_machine<Fsm> { Stopped operator()( overload_id<1>, Running, EvStartStop ) { return Stopped(); } Running operator()( overload_id<2>, Stopped, EvStartStop ) { return Running(); } Stopped operator()( overload_id<3>, Active, EvReset ) { return Stopped(); } typedef mpl::range_c<1,4> transitions; }; There is no states because they can be collected from result types of call operators (unique_at<Fsm,Fsm::transitions,0>::type gives a list of positions, list<int_<1>, int_<2> > in the example, and for_all algorithm transforms sequence of positions into sequence of signatures and then execute something like create variant or destoy it). -- Alexander Nasonov
Alexander Nasonov <alnsn <at> yandex.ru> writes: [interface & explanation snipped] The interface looks really nice. I'd volunteer for beta testing... Regards, Andreas
Andreas Huber wrote:
Alexander Nasonov <alnsn <at> yandex.ru> writes: [interface & explanation snipped] The interface looks really nice. I'd volunteer for beta testing...
That would be great. I don't know when exactly I'll finish new version. I'm "reserved" by my wife this weekend. Probably, next week I'll have time for this.
Andreas Huber wrote:
Alexander Nasonov <alnsn <at> yandex.ru> writes: [interface & explanation snipped] The interface looks really nice. I'd volunteer for beta testing...
Done. You can download it from SF: https://sourceforge.net/project/showfiles.php?group_id=45323&package_id=130862 FSM example is in examples directory, files fsm.hpp and fsm.cpp (attached). -- Alexander Nasonov
participants (3)
-
Alexander Nasonov -
Andreas Huber -
David Abrahams