[fsm review] Comparison with ad-hoc FSM coding
Dear All, I have just spent a few minutes comparing an ad-hoc FSM implementation with an implementation using the proposed library. The example that I've used is the USB device state machine, which I recently had to understand for an embedded application, and I've put an image of the state graph here: http://chezphil.org/tmp/fsm.png For more info, google("USB 2.0 spec") (you'll find a zip file with a PDF in it) and see the start of chapter 9. Note that it seems to me that the "power interruption" transition is wrong and should go to "attached" rather than "powered", and that I have ignored the "suspended" states. The behaviour is essentially as follows: a device is "attached" until the hub supplies power, when it becomes "powered". It then waits for a reset, at which point it starts listening for messages at the "default address" (zero); the host ensures that only one device is in this state at any time. When the host sends a set_address message it changes to the "address" state, and when the host sends a set_configuration message it changes to the "configured" state for normal operation. Here is my ad-hoc implementation (note that I haven't tried to even compile any of this code): struct usb_device { enum state_t { Attached, Powered, Default, Address, Configured }; state_t state; int addr; int configuration; usb_device(): state(Attached), addr(0), configuration(0) {} void power_on() { state = Powered; } void power_off() { state = Attached; } void reset() { state = Default; addr = 0; configuration = 0; } void set_address(int addr_) { addr = addr_; state = (addr==0) ? Default : Configured; } void set_configuration(int configuration_) { configuration = configuration_; state = (configuration==0) ? Address : Configured; } }; In comparison, here's what I've come up with using Boost.FSM: struct Attached; struct Powered; struct Default; struct Address; struct Configured; typedef mpl::vector<Attached, Powered, Default, Address, Configured>::type StateList; struct PowerOn; struct PowerOff; struct Reset; struct SetAddress { int addr; SetAddress(int addr_): addr(addr_) {} }; struct SetConfiguration { int configuration; SetConfiguration(int configuration_): configuration(configuration_) {} }; struct Common { int addr; int configuration; }; struct Attached: fsm::state<Attached,StateList>, Common { void on_process(const PowerOn&) { switch_to<Powered>(); } }; struct Powered: fsm::state<Powered,StateList>, Common { void on_process(const PowerOff&) { switch_to<Attached>(); } void on_process(const Reset&) { switch_to<Default>(); } }; struct Default: fsm::state<Default,StateList>, Common { void on_enter_state() { addr = 0; } void on_process(const PowerOff&) { switch_to<Attached>(); } void on_process(const Reset&) { } void on_process(const SetAddress& set_address) { addr = set_address.addr; if (addr != 0) { switch_to<Address>(); } } }; struct Address: fsm::state<Address,StateList>, Common { void on_process(const PowerOff&) { switch_to<Attached>(); } void on_process(const Reset&) { switch_to<Default>(); } void on_process(const SetAddress& set_address) { addr = set_address.addr; if (addr == 0) { switch_to<Default>(); } } void on_process(const SetConfiguration& set_configuration) { configuration = set_configuration.configuration; if (configuration != 0) { switch_to<Configured>(); } } }; struct Configured: fsm::state<Configured,StateList>, Common { void on_process(const PowerOff&) { switch_to<Attached>(); } void on_process(const Reset&) { switch_to<Default>(); } void on_process(const SetConfiguration& set_configuration) { configuration = set_configuration.configuration; if (configuration == 0) { switch_to<Address>(); } } }; The latter is clearly more verbose than the former. Some of the verbosity would go if I put the common events (e.g. PowerOff) into a base class, but that adds verbosity of its own. There are a few characteristics of this particular design that favour the ad-hoc code. Firstly, the device's behaviour is allowed to be undefined if an unexpected event occurs. Secondly, many events have the same effect irrespective of the state (e.g. power off). Finally, the effect of events often depends on their data (i.e. zero has a special meaning). I would also say that the turnstile example given in the library documentation could be implemented more concisely using an ad-hoc approach (would someone like to try?). Perhaps more complex FSMs would benefit more from what this library offers. In that case, can we see an example? I note that this library is targeted at simpler FSMs than Boost.Statechart (which I have not used). Is there a category of FSMs that are simple enough that Boost.Statechart's features are not needed (e.g. hierarchy) yet too complex for an ad-hoc implementation? Regards, Phil.
Phil Endecott wrote:
Here is my ad-hoc implementation (note that I haven't tried to even compile any of this code):
struct usb_device {
enum state_t { Attached, Powered, Default, Address, Configured }; state_t state;
int addr; int configuration;
usb_device(): state(Attached), addr(0), configuration(0) {}
void power_on() { state = Powered; }
void power_off() { state = Attached; }
void reset() { state = Default; addr = 0; configuration = 0; }
void set_address(int addr_) { addr = addr_; state = (addr==0) ? Default : Configured; }
void set_configuration(int configuration_) { configuration = configuration_; state = (configuration==0) ? Address : Configured; } };
Phil - While the term state machine can mean a lot of things, I'm not sure that the ad-hoc implementation would represent what we all have in mind. For example, according to your fsm.png diagram the only valid transition from the Attached state is to Powered. However, nothing stops me from simply calling the set_address method which will result in either a Default or Configured state. Even an ad-hoc state machine implementation should have some type of "tick" or "clock" type method that takes a token or message (with or without payload). So, while your ad-hoc machine will track a state if the methods are called in a valid order, I'm not sure I would refer to it as a state machine. Best Regards - Michael -- ---------------------------------- Michael Caisse Object Modeling Designs www.objectmodelingdesigns.com
on Sat Aug 16 2008, Michael Caisse <boost-AT-objectmodelingdesigns.com> wrote:
While the term state machine can mean a lot of things, I'm not sure that the ad-hoc implementation would represent what we all have in mind. For example, according to your fsm.png diagram the only valid transition from the Attached state is to Powered. However, nothing stops me from simply calling the set_address method which will result in either a Default or Configured state.
He intentionally described that as undefined behavior.
Even an ad-hoc state machine implementation should have some type of "tick" or "clock" type method that takes a token or message (with or without payload).
I can't picture what you have in mind here.
So, while your ad-hoc machine will track a state if the methods are called in a valid order, I'm not sure I would refer to it as a state machine.
I would. It's certainly no less valid than the one presented in C++TMP. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
Even an ad-hoc state machine implementation should have some type of "tick" or "clock" type method that takes a token or message (with or without payload).
I can't picture what you have in mind here.
What Phil described tracks state just fine; however, I wouldn't call it a *machine*. State machines consist of states and transitions. Transitions are transversed upon some stimulus. The *machine* part of the state machine receives the stimulus and then causes the transition to a new state. It is not uncommon to call the stimulus a token or a message consisting of the stimulus and data. Often the state machine "method" operating on the stimulus is called a tick or clock. What was described allows the user to take any transition at any time by invoking a method which then stores the new state. It lacks a concept of stimulus causing a transition.
So, while your ad-hoc machine will track a state if the methods are called in a valid order, I'm not sure I would refer to it as a state machine.
I would. It's certainly no less valid than the one presented in C++TMP.
I apologize, I am not familiar with that presentation. State machines are not foreign to me. I commercially offer my own UML (Real-time Object Oriented Methodology ROOM) package that takes a graphical representation through code generation and targets many OS's or bare metal. I extensively use state machines in FPGA implementations. Perhaps I am missing something. Maybe we are not talking about event driven state machines? I am happy to be shown something else. Best Regards - Michael -- ---------------------------------- Michael Caisse Object Modeling Designs www.objectmodelingdesigns.com
on Sat Aug 16 2008, Michael Caisse <boost-AT-objectmodelingdesigns.com> wrote:
David Abrahams wrote:
Even an ad-hoc state machine implementation should have some type of "tick" or "clock" type method that takes a token or message (with or without payload).
I can't picture what you have in mind here.
What Phil described tracks state just fine; however, I wouldn't call it a *machine*.
I suppose you'll explain why not here...
State machines consist of states and transitions. Transitions are transversed upon some stimulus. The *machine* part of the state machine receives the stimulus and then causes the transition to a new state.
Sure, I'm familiar with the abstraction. So far his code meets the definition.
It is not uncommon to call the stimulus a token or a message consisting of the stimulus and data.
OK, or an "event," as I've heard it.
Often the state machine "method" operating on the stimulus is called a tick or clock.
Well, sure, you could make all the member functions overloads of the same member function taking different event types (as does the one in C++TMP), and then it looks more like there's only one "tick" or "clock" entry point. However, the effect is nearly the same even though the abstraction is slightly weaker. The specific function being called is chosen at compile-time, and that's perfectly adequate for many applications. It's true that in some designs events can be queued or otherwise need to be dispatched dynamically, but there's no need to make all FSM users pay for dynamic double-dispatch, and it's easily handled in a layer on top of the statically-dispatched design.
What was described allows the user to take any transition at any time by invoking a method which then stores the new state. It lacks a concept of stimulus causing a transition.
I disagree. Each entry point called can be viewed as a stimulus.
So, while your ad-hoc machine will track a state if the methods are called in a valid order, I'm not sure I would refer to it as a state machine.
I would. It's certainly no less valid than the one presented in C++TMP.
I apologize, I am not familiar with that presentation.
I'll re-post the links: http://www.boostpro.com/mplbook/examples/player.cpp http://www.boostpro.com/mplbook/examples/player2.cp Please keep in mind that these are simple frameworks designed to demonstrate how template metaprogramming can be used to build domain-specific languages, and not intended to be complete FSM libraries. That said, I've heard of several people picking up this design and using it successfully when they needed to build an FSM.
State machines are not foreign to me. I commercially offer my own UML (Real-time Object Oriented Methodology ROOM) package that takes a graphical representation through code generation and targets many OS's or bare metal. I extensively use state machines in FPGA implementations.
I bow to your greater depth of experience with FSMs.
Perhaps I am missing something.
Or perhaps I am.
Maybe we are not talking about event driven state machines?
What's the difference between an "event" and a "token" or "message?" -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
State machines consist of states and transitions. Transitions are transversed upon some stimulus. The *machine* part of the state machine receives the stimulus and then causes the transition to a new state.
Sure, I'm familiar with the abstraction. So far his code meets the definition.
I figured you were familiar with the abstraction; however, I was unsure what part you couldn't "picture" so I got verbose. His code has states and transitions but it does not handle events. Calling a method is not an event. The methods in the structure are transitions.
OK, or an "event," as I've heard it.
I personally like "event".
Well, sure, you could make all the member functions overloads of the same member function taking different event types (as does the one in C++TMP), and then it looks more like there's only one "tick" or "clock" entry point. However, the effect is nearly the same even though the abstraction is slightly weaker. The specific function being called is chosen at compile-time, and that's perfectly adequate for many applications. It's true that in some designs events can be queued or otherwise need to be dispatched dynamically, but there's no need to make all FSM users pay for dynamic double-dispatch, and it's easily handled in a layer on top of the statically-dispatched design.
There are many ways to perform the dispatching but what I am suggesting is that dispatching an event in the form of a transition is what makes it a *machine*. If I have a state machine that is in state A and I receive event Q then the logic to determine what occurs is part of the state machine. I've also implemented USB engine state machines, so lets just continue with that example (and we also have a nice little diagram). If you are in the Address state there are four valid transitions: Bus Inactive, Device Configured, Reset and Power Interruption. Associated with each of those transitions is some event that will cause the transition to be taken. Receiving an event not associated with one of the valid transitions must also be considered. The logic to determine which transition to take based on the current state and event received is part of the state machine. Without that logic you do not have a machine.
What was described allows the user to take any transition at any time by invoking a method which then stores the new state. It lacks a concept of stimulus causing a transition.
I disagree. Each entry point called can be viewed as a stimulus.
By using that definition every class or structure that has a member function and modifies a member variable is a state machine. While that could be an academic use of the term it surely isn't going to be very useful for event driven state machines. The methods described in the ad-hoc machine are transitions, not events. Events must be evaluated against the current state to determine a transition.
I'll re-post the links:
http://www.boostpro.com/mplbook/examples/player.cpp http://www.boostpro.com/mplbook/examples/player2.cp
Please keep in mind that these are simple frameworks designed to demonstrate how template metaprogramming can be used to build domain-specific languages, and not intended to be complete FSM libraries. That said, I've heard of several people picking up this design and using it successfully when they needed to build an FSM.
Thank you for the links. I will take some time later to look at them.
State machines are not foreign to me. I commercially offer my own UML (Real-time Object Oriented Methodology ROOM) package that takes a graphical representation through code generation and targets many OS's or bare metal. I extensively use state machines in FPGA implementations.
I bow to your greater depth of experience with FSMs.
Sorry, my text does sound a bit rude doesn't it? That was not the intent but I haven't written a book that I can point at for credibility (o;
What's the difference between an "event" and a "token" or "message?"
I think event and token can be used interchangeably. I prefer event personally but token seems more prevalent in hardware settings. Message seems to typically hold one of two meanings: equivalent to event or a package containing both the event and a payload (data). -- ---------------------------------- Michael Caisse Object Modeling Designs www.objectmodelingdesigns.com
on Sat Aug 16 2008, Michael Caisse <boost-AT-objectmodelingdesigns.com> wrote:
David Abrahams wrote:
State machines consist of states and transitions. Transitions are transversed upon some stimulus. The *machine* part of the state machine receives the stimulus and then causes the transition to a new state.
Sure, I'm familiar with the abstraction. So far his code meets the definition.
I figured you were familiar with the abstraction; however, I was unsure what part you couldn't "picture" so I got verbose. His code has states and transitions but it does not handle events. Calling a method is not an event.
Why not?
The methods in the structure are transitions.
Or you could say that they're events with bundled transition actions.
Well, sure, you could make all the member functions overloads of the same member function taking different event types (as does the one in C++TMP), and then it looks more like there's only one "tick" or "clock" entry point. However, the effect is nearly the same even though the abstraction is slightly weaker. The specific function being called is chosen at compile-time, and that's perfectly adequate for many applications. It's true that in some designs events can be queued or otherwise need to be dispatched dynamically, but there's no need to make all FSM users pay for dynamic double-dispatch, and it's easily handled in a layer on top of the statically-dispatched design.
There are many ways to perform the dispatching but what I am suggesting is that dispatching an event in the form of a transition is what makes it a *machine*.
Sorry, "in the form of a transition" doesn't make any sense to me in this context. In my world: An _event_ triggers a _state change_ and an associated _transition action_. The triggered state change may depend on the machine's _current state_.
If I have a state machine that is in state A and I receive event Q then the logic to determine what occurs is part of the state machine.
No argument there. I don't see how it relates to the example.
I've also implemented USB engine state machines, so lets just continue with that example (and we also have a nice little diagram). If you are in the Address state there are four valid transitions: Bus Inactive, Device Configured, Reset and Power Interruption. Associated with each of those transitions is some event that will cause the transition to be taken. Receiving an event not associated with one of the valid transitions must also be considered.
Depending on the application, yes. As the OP said, he was assuming that any effects at all were allowable on an invalid event, i.e. undefined behavior. A valid assumption, as long as its stated.
The logic to determine which transition to take based on the current state and event received is part of the state machine. Without that logic you do not have a machine.
I see that logic in the OP's code plain as day.
What was described allows the user to take any transition at any time by invoking a method which then stores the new state. It lacks a concept of stimulus causing a transition.
I disagree. Each entry point called can be viewed as a stimulus.
By using that definition every class or structure that has a member function and modifies a member variable is a state machine.
As long as it doesn't allocate memory. Once a class ;-) Seriously, though: the point is that the OP's code was a fairly direct translation into code of (a portion of) the FSM in the picture.
While that could be an academic use of the term it surely isn't going to be very useful for event driven state machines. The methods described in the ad-hoc machine are transitions, not events. Events must be evaluated against the current state to determine a transition.
Would your objection be satisfied if one of those functions tested the current state to determine the next state and/or transition action? Maybe it's a degenerate and not-very-interesting FSM, but it's still a FSM AFAICT. Would you say that the equivalent code posted that used the FSM library was also not an FSM?
State machines are not foreign to me. I commercially offer my own UML (Real-time Object Oriented Methodology ROOM) package that takes a graphical representation through code generation and targets many OS's or bare metal. I extensively use state machines in FPGA implementations.
I bow to your greater depth of experience with FSMs.
Sorry, my text does sound a bit rude doesn't it?
Not in the least.
That was not the intent but I haven't written a book that I can point at for credibility (o;
My book shouldn't be viewed as giving me any significant credibility in the area of FSMs. However, I have thought quite a bit about abstractions and their representations. I think that's what this argument is primarily about.
What's the difference between an "event" and a "token" or "message?"
I think event and token can be used interchangeably. I prefer event personally but token seems more prevalent in hardware settings. Message seems to typically hold one of two meanings: equivalent to event or a package containing both the event and a payload (data).
Good. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
However, nothing stops me from simply
calling the set_address method which will result in either a Default or Configured state.
He intentionally described that as undefined behavior.
Sorry for breaking in, I'm no expert on state machines at all but.. isn't the goal of expressing a FSM by the aid of the proposed to library to minimize the chance of undefined behaviour? If the OP's state machine doesn't guarantee its valid state, why is that a useful reference to compare against in the first place? If I don't care what happens when I run my program (leaving bigger parts of it as undefined behaviour), there's is little need for me to use any boost library at all =) Cheers, / Christian
on Sat Aug 16 2008, "Christian Holmquist" <c.holmquist-AT-gmail.com> wrote:
However, nothing stops me from simply
calling the set_address method which will result in either a Default or Configured state.
He intentionally described that as undefined behavior.
Sorry for breaking in, I'm no expert on state machines at all but.. isn't the goal of expressing a FSM by the aid of the proposed to library to minimize the chance of undefined behaviour?
*The* goal? There are lots of potential reasons one might want to use a library. In general, a library that allows a fairly direct expression of the FSM as described in its "native" language (OK, maybe graph diagrams won't work, but you could use state transition tables) should lead to code that is more correct and maintainable. I find the code written using the proposed library rather procedural in nature (rather than declarative), thus the OP's comparison is very apt from my point-of-view. The hand-rolled code actually looks clearer and more direct to me. Note that when the OP wrote "undefined behavior" I don't think he meant that the C++ standard would say it was undefined; rather that his state machine implementation was not going to promise any particular results on invalid inputs. Avoiding undefined behavior is certainly not always the primary goal of using a library.
If the OP's state machine doesn't guarantee its valid state,
It guarantees a valid state as long as the inputs are valid, just as x / y or *p do, where x, y, and p are primitive types. Most libraries I know have similar contracts. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
on Sat Aug 16 2008, "Christian Holmquist" <c.holmquist-AT-gmail.com> wrote:
calling the set_address method which will result in either a Default or Configured state. He intentionally described that as undefined behavior. Sorry for breaking in, I'm no expert on state machines at all but.. isn't
However, nothing stops me from simply the goal of expressing a FSM by the aid of the proposed to library to minimize the chance of undefined behaviour?
*The* goal? There are lots of potential reasons one might want to use a library. In general, a library that allows a fairly direct expression of the FSM as described in its "native" language (OK, maybe graph diagrams won't work, but you could use state transition tables) should lead to code that is more correct and maintainable.
David, you won't argue that every tool has its purpose, will you? I'm sure it is possible to put a nail in the wall with a microscope, but it's not the microscope's flaw that it's too fragile for that. State machines, as I see it, are meant to define an object behavior, IOW reduce the amount of undefined behavior. It is pointless to use them to implement undefined behavior.
I find the code written using the proposed library rather procedural in nature (rather than declarative), thus the OP's comparison is very apt from my point-of-view. The hand-rolled code actually looks clearer and more direct to me.
Please, have a look at my reply to Phil. I've attached a code snippet with a transition map. Does that look more declarative?
Note that when the OP wrote "undefined behavior" I don't think he meant that the C++ standard would say it was undefined; rather that his state machine implementation was not going to promise any particular results on invalid inputs. Avoiding undefined behavior is certainly not always the primary goal of using a library.
If the OP's state machine doesn't guarantee its valid state,
It guarantees a valid state as long as the inputs are valid, just as
x / y
or
*p
do, where x, y, and p are primitive types. Most libraries I know have similar contracts.
I don't fully agree with this. On the one hand, yes, most libraries rely on the valid input and this is "the right thing". On the other hand, FSMs are often used in domains where input is not always valid (parsers, protocol clients, GUI and so on). And FSMs are one of the tools to define behavior even in face of invalid input. It's the difference between a good and bad application: the good one doesn't blow up the Sun if you push the wrong button. :)
on Sun Aug 17 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
David Abrahams wrote:
on Sat Aug 16 2008, "Christian Holmquist" <c.holmquist-AT-gmail.com> wrote:
Sorry for breaking in, I'm no expert on state machines at all but.. isn't the goal of expressing a FSM by the aid of the proposed to library to minimize the chance of undefined behaviour?
*The* goal? There are lots of potential reasons one might want to use a library. In general, a library that allows a fairly direct expression of the FSM as described in its "native" language (OK, maybe graph diagrams won't work, but you could use state transition tables) should lead to code that is more correct and maintainable.
David, you won't argue that every tool has its purpose, will you?
?? I wouldn't waste my time making that argument since it is a bit tautological.
I'm sure it is possible to put a nail in the wall with a microscope, but it's not the microscope's flaw that it's too fragile for that.
Sorry, I don't see your point. I was just saying that there is more than one good reason why someone should use an FSM library, and no single reason has greater absolute importance.
State machines, as I see it, are meant to define an object behavior, IOW reduce the amount of undefined behavior. It is pointless to use them to implement undefined behavior.
So std::vector is pointless because it exhibits undefined behavior when misused? There are at least two good reasons for allowing the result of certain operations to be undefined: 1. There's no way of checking that the input is valid. If someone hands you an invalid pointer there's not much you can do about it. 2. Efficiency. Checking that the input is valid would slow your application down.
I find the code written using the proposed library rather procedural in nature (rather than declarative), thus the OP's comparison is very apt from my point-of-view. The hand-rolled code actually looks clearer and more direct to me.
Please, have a look at my reply to Phil. I've attached a code snippet with a transition map. Does that look more declarative?
Not really, to me. It's very difficult for me to see the transitions in that code. Compare that with either of my player examples. IMO, a good FSM library should present the FSM such that it's easy to see the machine's structure, preferably in a form that is *already* used to describe FSMs, outside of code, such as a state diagram. It would be great if we could embed the state diagram in our code, but C++ doesn't do that. You have to leave that level of abstract expressiveness to GUI tools that generate code. My code uses the "state transition table" abstraction instead, which seems to be about the best we can hope for in straight C++.
If the OP's state machine doesn't guarantee its valid state,
It guarantees a valid state as long as the inputs are valid, just as
x / y
or
*p
do, where x, y, and p are primitive types. Most libraries I know have similar contracts.
I don't fully agree with this. On the one hand, yes, most libraries rely on the valid input and this is "the right thing". On the other hand, FSMs are often used in domains where input is not always valid (parsers, protocol clients, GUI and so on).
Yes, a generalized FSM library should offer strong guarantees. The OP was building a specialized FSM from scratch. For any particular domain, the choice to allow undefined behavior may be appropriate (though I doubt USB is such a domain). -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
on Sun Aug 17 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
State machines, as I see it, are meant to define an object behavior, IOW reduce the amount of undefined behavior. It is pointless to use them to implement undefined behavior.
So std::vector is pointless because it exhibits undefined behavior when misused?
No, vector is not pointless, because its purpose is to store elements, not to define behavior. I will need vector to store elements even with undefined behavior on invalid pointers as its input. But why would I need FSM if it doesn't define my object's behavior? Or if I am adamant on what particular input will come from the environment (IOW, the behavior is already defined by the environment)?
I find the code written using the proposed library rather procedural in nature (rather than declarative), thus the OP's comparison is very apt from my point-of-view. The hand-rolled code actually looks clearer and more direct to me. Please, have a look at my reply to Phil. I've attached a code snippet with a transition map. Does that look more declarative?
Not really, to me. It's very difficult for me to see the transitions in that code. Compare that with either of my player examples.
Hmm... I don't see much difference, except for comments markup. Both code samples use transition maps, both use vectors... Is it because the transition map in your code is a member of the complete FSM?
on Sun Aug 17 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
Please, have a look at my reply to Phil. I've attached a code snippet with a transition map. Does that look more declarative?
Not really, to me. It's very difficult for me to see the transitions in that code. Compare that with either of my player examples.
Hmm... I don't see much difference, except for comments markup. Both code samples use transition maps, both use vectors... Is it because the transition map in your code is a member of the complete FSM?
No state transition table (STT) is immediately apparent to me in your code. Could you post just that fragment? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
on Sun Aug 17 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
David Abrahams wrote:
on Sun Aug 17 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
State machines, as I see it, are meant to define an object behavior, IOW reduce the amount of undefined behavior. It is pointless to use them to implement undefined behavior.
So std::vector is pointless because it exhibits undefined behavior when misused?
No, vector is not pointless, because its purpose is to store elements, not to define behavior.
Sorry, but you're making no sense to me. The defined behaviors of vector are just as important as the defined behaviors of your FSM library.
I will need vector to store elements even with undefined behavior on invalid pointers as its input. But why would I need FSM if it doesn't define my object's behavior?
Well, it would define useful behaviors for valid inputs.
Or if I am adamant on what particular input will come from the environment (IOW, the behavior is already defined by the environment)?
The OP's assumption only works when you have sufficient control over the inputs.
I find the code written using the proposed library rather procedural in nature (rather than declarative), thus the OP's comparison is very apt from my point-of-view. The hand-rolled code actually looks clearer and more direct to me. Please, have a look at my reply to Phil. I've attached a code snippet with a transition map. Does that look more declarative?
Not really, to me. It's very difficult for me to see the transitions in that code. Compare that with either of my player examples.
Hmm... I don't see much difference, except for comments markup. Both code samples use transition maps, both use vectors... Is it because the transition map in your code is a member of the complete FSM?
Sorry, I don't know what a "transition map" is. In fact, when I google ``fsm "transition map"'' all the top hits come from your library, which tells me it's almost certainly not a known term in the FSM domain. I'm talking about a State Transition Table (STT) (http://en.wikipedia.org/wiki/State_transition_table). The STT in my code is clearly visible at http://svn.boost.org/trac/boost/browser/trunk/libs/mpl/example/fsm/player1.c... Where's yours? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Sun, 2008-08-17 at 15:27 -0800, David Abrahams wrote:
on Sun Aug 17 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
David Abrahams wrote:
on Sun Aug 17 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
State machines, as I see it, are meant to define an object behavior, IOW reduce the amount of undefined behavior. It is pointless to use them to implement undefined behavior.
So std::vector is pointless because it exhibits undefined behavior when misused?
No, vector is not pointless, because its purpose is to store elements, not to define behavior.
Sorry, but you're making no sense to me. The defined behaviors of vector are just as important as the defined behaviors of your FSM library.
Andrey appears to be saying that the whole concept of an FSM is built around defining the behaviour in reaction to events, while the concept of a vector is about storage and access to elements. His use of "behaviour" was a bit loose/context dependent/needed an FSM to interpret :-). Anyway, the OP (Phil) seems to believe that this particular issue arose out of a bad choice of example than being what he was trying to illustrate. That said, I'm still not clear on what exactly that was.
I will need vector to store elements even with undefined behavior on invalid pointers as its input. But why would I need FSM if it doesn't define my object's behavior?
Well, it would define useful behaviors for valid inputs.
Fair enough.
Or if I am adamant on what particular input will come from the environment (IOW, the behavior is already defined by the environment)?
The OP's assumption only works when you have sufficient control over the inputs.
Right. However, in this trivial FSM where much of the state is directly encoded in a couple of variables,there is no need to deal with invalid inputs and the FSM has no deeper behaviour/actions; *any* FSM library looks verbose. What we are comparing is DSELs, and, while you say that it would be good to be able to embed the diagram, the diagram in the USB example is an incredibly verbose representation (by count of nodes and edges) of what is described by Phils code. Obviously you don't infer from this that any attempt to embed state diagram (like) representations in code is pointless, but you do seem to find the proposed libraries representation less useful. Is it simply that the "states that handle events" model is intrinsically not as clear as a diagram or transition table, or is there some unnecessary verbosity or lack of clarity in way that model is expressed in the language implemented by the library?
Please, have a look at my reply to Phil. I've attached a code snippet with a transition map. Does that look more declarative?
Not really, to me. It's very difficult for me to see the transitions in that code. Compare that with either of my player examples.
Hmm... I don't see much difference, except for comments markup. Both code samples use transition maps, both use vectors... Is it because the transition map in your code is a member of the complete FSM?
There are 2 examples attached - the second with a transition map. I rather like the fact that the library allows transitons to be defined by a transition table as well as by defining event handlers/transitions within each state.
The STT in my code is clearly visible at http://svn.boost.org/trac/boost/browser/trunk/libs/mpl/example/fsm/player1.c...
Where's yours?
I've pasted it here: typedef mpl::vector< fsm::transition<Attached, fsm::event<PowerOn>, Powered>, SetAddressTrans<Default, std::not_equal_to, Address>, SetAddressTrans<Address, std::equal_to, Default>, SetConfigurationTrans<Address, std::not_equal_to, Configured>, SetConfigurationTrans<Configured, std::equal_to, Address>, fsm::transition<fsm::any_state, fsm::event<Reset>, Default>, fsm::transition<fsm::any_state, fsm::event<PowerOff>, Attached>
::type Transitions;
Regards Darryl
on Sun Aug 17 2008, Darryl Green <darryl.green-AT-aanet.com.au> wrote:
in this trivial FSM where much of the state is directly encoded in a couple of variables,
I don't know what the number of variables has to do with anything. For all practical purposes, unless you allow nested states or other esoteric extensions to the traditional CS meaning of FSM, 16 bits is more than enough to encode the state of arbitrarily complex state machines.
there is no need to deal with invalid inputs and the FSM has no deeper behaviour/actions; *any* FSM library looks verbose. What we are comparing is DSELs, and, while you say that it would be good to be able to embed the diagram, the diagram in the USB example is an incredibly verbose representation (by count of nodes and edges) of what is described by Phils code.
But Phil didn't encode the whole machine represented in the diagram.
Obviously you don't infer from this that any attempt to embed state diagram (like) representations in code is pointless,
I do think it's pointless in C++, although I don't do it by inference from anything you're mentioning.
but you do seem to find the proposed libraries representation less useful. Is it simply that the "states that handle events" model is intrinsically not as clear as a diagram or transition table,
I think so. To start with, "states handle events" is not part of the abstraction of what an FSM is. Look it up in Wikipedia or any CS text. You won't see any such description. Instead, that's a point-of-view unnecessarily imposed by the proposed library. So the library's DSL isn't a faithful reflection of the ways we already talk about FSMs.
or is there some unnecessary verbosity or lack of clarity in way that model is expressed in the language implemented by the library?
Well, that too.
Please, have a look at my reply to Phil. I've attached a code snippet with a transition map. Does that look more declarative?
Not really, to me. It's very difficult for me to see the transitions in that code. Compare that with either of my player examples.
Hmm... I don't see much difference, except for comments markup. Both code samples use transition maps, both use vectors... Is it because the transition map in your code is a member of the complete FSM?
There are 2 examples attached the second with a transition map. I rather like the fact that the library allows transitons to be defined by a transition table as well as by defining event handlers/transitions within each state.
The STT in my code is clearly visible at http://svn.boost.org/trac/boost/browser/trunk/libs/mpl/example/fsm/player1.c...
Where's yours?
I've pasted it here:
typedef mpl::vector< fsm::transition<Attached, fsm::event<PowerOn>, Powered>, SetAddressTrans<Default, std::not_equal_to, Address>, SetAddressTrans<Address, std::equal_to, Default>, SetConfigurationTrans<Address, std::not_equal_to, Configured>, SetConfigurationTrans<Configured, std::equal_to, Address>, fsm::transition<fsm::any_state, fsm::event<Reset>, Default>, fsm::transition<fsm::any_state, fsm::event<PowerOff>, Attached>
::type Transitions;
The bits enclosed by fsm::transition look like they might be rows in an STT, although they're awfully verbose, with a great deal of surrounding syntactic noise that distracts from being able to read the actual semantics. AFAICT, the other parts do not bear any obvious resemblance to rows in an STT. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
on Sun Aug 17 2008, Darryl Green <darryl.green-AT-aanet.com.au> wrote:
in this trivial FSM where much of the state is directly encoded in a couple of variables,
I don't know what the number of variables has to do with anything. For all practical purposes, unless you allow nested states or other esoteric extensions to the traditional CS meaning of FSM, 16 bits is more than enough to encode the state of arbitrarily complex state machines.
I'm sorry, I don't follow you. The question was not about how to encode the state but about whether FSM concept is needed here. No matter, though.
but you do seem to find the proposed libraries representation less useful. Is it simply that the "states that handle events" model is intrinsically not as clear as a diagram or transition table,
I think so. To start with, "states handle events" is not part of the abstraction of what an FSM is. Look it up in Wikipedia or any CS text. You won't see any such description.
So, you're saying that the library must be designed as Wikipedia says? No less, no more? How discouraging.
Instead, that's a point-of-view unnecessarily imposed by the proposed library. So the library's DSL isn't a faithful reflection of the ways we already talk about FSMs.
The library supports both approaches for defining the FSM - the state-based and the transition-based. I for one prefer state-based approach and you, I assume, prefer transition-based. To my mind, it is advantage that the library can be used both ways.
or is there some unnecessary verbosity or lack of clarity in way that model is expressed in the language implemented by the library?
Well, that too.
Where's yours?
I've pasted it here:
typedef mpl::vector< fsm::transition<Attached, fsm::event<PowerOn>, Powered>, SetAddressTrans<Default, std::not_equal_to, Address>, SetAddressTrans<Address, std::equal_to, Default>, SetConfigurationTrans<Address, std::not_equal_to, Configured>, SetConfigurationTrans<Configured, std::equal_to, Address>, fsm::transition<fsm::any_state, fsm::event<Reset>, Default>, fsm::transition<fsm::any_state, fsm::event<PowerOff>, Attached>
::type Transitions;
The bits enclosed by fsm::transition look like they might be rows in an STT, although they're awfully verbose, with a great deal of surrounding syntactic noise that distracts from being able to read the actual semantics. AFAICT, the other parts do not bear any obvious resemblance to rows in an STT.
Sorry, I don't see why the code above is worse than this: struct transition_table : mpl::vector11< row < Stopped , play , Playing , &p::start_playback >, row < Stopped , open_close , Open , &p::open_drawer >, row < Open , open_close , Empty , &p::close_drawer >, row < Empty , open_close , Open , &p::open_drawer >, row < Empty , cd_detected , Stopped , &p::store_cd_info >, row < Playing , stop , Stopped , &p::stop_playback >, row < Playing , pause , Paused , &p::pause_playback >, row < Playing , open_close , Open , &p::stop_and_open >, row < Paused , play , Playing , &p::resume_playback >, row < Paused , stop , Stopped , &p::stop_playback >, row < Paused , open_close , Open , &p::stop_and_open >
{};
In fact, I find your syntax more verbose for the unneeded fourth column of the table.
on Mon Aug 18 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
David Abrahams wrote:
on Sun Aug 17 2008, Darryl Green <darryl.green-AT-aanet.com.au> wrote:
in this trivial FSM where much of the state is directly encoded in a couple of variables,
I don't know what the number of variables has to do with anything. For all practical purposes, unless you allow nested states or other esoteric extensions to the traditional CS meaning of FSM, 16 bits is more than enough to encode the state of arbitrarily complex state machines.
I'm sorry, I don't follow you. The question was not about how to encode the state but about whether FSM concept is needed here.
I'm as baffled as you are about why Darryl brought up the number of variables required to encode the state. :-)
but you do seem to find the proposed libraries representation less useful. Is it simply that the "states that handle events" model is intrinsically not as clear as a diagram or transition table,
I think so. To start with, "states handle events" is not part of the abstraction of what an FSM is. Look it up in Wikipedia or any CS text. You won't see any such description.
So, you're saying that the library must be designed as Wikipedia says?
No, I'm saying that a library addressing a particular domain (FSMs in this case) with has well-established and effective notation should, if possible, allow the user to express his code in a manner that maps directly onto the established notation. See for example Boost.Spirit syntax and its relationship to EBNF. Or the fact that we use operators in C++ to manipulate numbers!
Instead, that's a point-of-view unnecessarily imposed by the proposed library. So the library's DSL isn't a faithful reflection of the ways we already talk about FSMs.
The library supports both approaches for defining the FSM - the state-based and the transition-based. I for one prefer state-based approach and you, I assume, prefer transition-based.
I prefer the established FSM notations.
To my mind, it is advantage that the library can be used both ways.
Maybe; the "transition based" description as you present it doesn't look like an STT to me.
typedef mpl::vector< fsm::transition<Attached, fsm::event<PowerOn>, Powered>, SetAddressTrans<Default, std::not_equal_to, Address>, SetAddressTrans<Address, std::equal_to, Default>, SetConfigurationTrans<Address, std::not_equal_to, Configured>, SetConfigurationTrans<Configured, std::equal_to, Address>, fsm::transition<fsm::any_state, fsm::event<Reset>, Default>, fsm::transition<fsm::any_state, fsm::event<PowerOff>, Attached>
::type Transitions;
The bits enclosed by fsm::transition look like they might be rows in an STT, although they're awfully verbose, with a great deal of surrounding syntactic noise that distracts from being able to read the actual semantics. AFAICT, the other parts do not bear any obvious resemblance to rows in an STT.
Sorry, I don't see why the code above is worse than this:
struct transition_table : mpl::vector11< row < Stopped , play , Playing , &p::start_playback >, row < Stopped , open_close , Open , &p::open_drawer >, row < Open , open_close , Empty , &p::close_drawer >, row < Empty , open_close , Open , &p::open_drawer >, row < Empty , cd_detected , Stopped , &p::store_cd_info >, row < Playing , stop , Stopped , &p::stop_playback >, row < Playing , pause , Paused , &p::pause_playback >, row < Playing , open_close , Open , &p::stop_and_open >, row < Paused , play , Playing , &p::resume_playback >, row < Paused , stop , Stopped , &p::stop_playback >, row < Paused , open_close , Open , &p::stop_and_open >
{};
Because the rows that don't begin with fsm::transition are opaque to me and don't appear to be symmetric with the other rows, whereas with one line of comments I can make my table completely transparent to anyone who knows what an FSM is: // Start Event Next Transition Action
In fact, I find your syntax more verbose for the unneeded fourth column of the table.
It's only unneeded if you think it doesn't convey information that's important to understanding the FSM. From my POV, it does. That's why arcs in an FSM diagram are often labeled with their associated transition actions. How does a user of your library associate actions with transitions if they don't go in the table? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
On Mon, 2008-08-18 at 14:49 -0800, David Abrahams wrote:
on Mon Aug 18 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
David Abrahams wrote:
on Sun Aug 17 2008, Darryl Green <darryl.green-AT-aanet.com.au> wrote:
in this trivial FSM where much of the state is directly encoded in a couple of variables,
I don't know what the number of variables has to do with anything. For all practical purposes, unless you allow nested states or other esoteric extensions to the traditional CS meaning of FSM, 16 bits is more than enough to encode the state of arbitrarily complex state machines.
I'm sorry, I don't follow you. The question was not about how to encode the state but about whether FSM concept is needed here.
I'm as baffled as you are about why Darryl brought up the number of variables required to encode the state. :-)
I assumed we all agreed that the number of variables required to encode the state is 1, and that the number of bits required was/is utterly irrelevant. My point is that the example is so trivial that it didn't need an FSM. Andrey had said effectively the same thing but it degenerated into a debate about input checking. I was trying to approach it from a different angle to avoid that. Last try: The following is not an FSM by any reasonable definition and implements the same behaviour as Phils code. Is it now clear why I was saying that the whole discussion surrounding this non-FSM is completely non-productive in evaluating the utility of an FSM library? struct usb_device { bool power; int address; int configuration; void power_on() { power = true; } void power_off() { power = false; address = 0; configured = 0; } void reset() { power = true; address = 0; configured = 0; } void set_address(int addr) { address = addr; } void set_configuration(int cfg) { configuration = cfg; } };
David Abrahams wrote:
Because the rows that don't begin with fsm::transition are opaque to me and don't appear to be symmetric with the other rows, whereas with one line of comments I can make my table completely transparent to anyone who knows what an FSM is:
// Start Event Next Transition Action
As Darryl already noted, pure STT does not allow to describe data-dependent transitions, which is a crucial feature. Aside from that, my syntax is equivalent to yours. As for data-dependent transitions, I've decided to allow users to put their custom rules of transition. That makes each row in the table, actually, a rule, which in trivial case always transit the FSM to the target state. I could define another syntax, for example: typedef mpl::vector< fsm::transition<Attached, PowerOn, Powered>, fsm::transition_if<Default, SetAddress, Address, is_address_not_zero>, fsm::transition_if<Address, SetAddress, Default, is_address_zero>, fsm::transition_if<Address, SetConfig, Configured, is_config_not_zero>, fsm::transition_if<Configured, SetConfig, Address, is_config_zero>, fsm::transition<fsm::any_state, Reset, Default>, fsm::transition<fsm::any_state, PowerOff, Attached>
::type Transitions;
But it doesn't make it significantly better and, in fact, is more limiting, because it doesn't allow to specify rules that apply to a subset of states and events. A small example from the docs. // Let's define the fsm::transition's analogue that triggers // not only when the event type is equal to the specified, // but even when it is derived from it. template< typename CurrentStateT, typename EventT, typename TargetStateT
struct same_or_derived_event_transition : public fsm::basic_transition< TargetStateT > { // We only need to specify the static predicate // that selects the transition template< typename StateT, typename EvtT > struct is_applicable : public mpl::and_< // We should check that state type is correct mpl::or_< is_same< CurrentStateT, fsm::any_state >, is_same< CurrentStateT, StateT > >, // Now we shall check the event type mpl::or_< is_same< EventT, EvtT >, is_base_and_derived< EventT, EvtT > > > { }; }; I feel that such flexibility is more important than syntactic sugar.
In fact, I find your syntax more verbose for the unneeded fourth column of the table.
It's only unneeded if you think it doesn't convey information that's important to understanding the FSM. From my POV, it does. That's why arcs in an FSM diagram are often labeled with their associated transition actions. How does a user of your library associate actions with transitions if they don't go in the table?
The action is totally defined by the event and the current state. Handler names are always the same and thus need not to be present in the table.
on Tue Aug 19 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
David Abrahams wrote:
Because the rows that don't begin with fsm::transition are opaque to me and don't appear to be symmetric with the other rows, whereas with one line of comments I can make my table completely transparent to anyone who knows what an FSM is:
// Start Event Next Transition Action
As Darryl already noted, pure STT does not allow to describe data-dependent transitions, which is a crucial feature. Aside from that, my syntax is equivalent to yours.
As for data-dependent transitions, I've decided to allow users to put their custom rules of transition. That makes each row in the table, actually, a rule, which in trivial case always transit the FSM to the target state. I could define another syntax, for example:
typedef mpl::vector< fsm::transition<Attached, PowerOn, Powered>, fsm::transition_if<Default, SetAddress, Address, is_address_not_zero>, fsm::transition_if<Address, SetAddress, Default, is_address_zero>, fsm::transition_if<Address, SetConfig, Configured, is_config_not_zero>, fsm::transition_if<Configured, SetConfig, Address, is_config_zero>, fsm::transition<fsm::any_state, Reset, Default>, fsm::transition<fsm::any_state, PowerOff, Attached>
::type Transitions;
But it doesn't make it significantly better
It is much more obvious what's going on from my POV. But you could do a lot with CRTP and smart naming choices to clean up the syntactic junk: typedef mpl::vector< row<Attached, PowerOn, Powered >, row<Default, SetAddress, Address, is_nonzero >, row<Address, SetAddress, Default, is_zero >, row<Address, SetConfig, Configured, is_nonzero >, row<Configured, SetConfig, Address, is_zero >, row<any_state, Reset, Default >, row<any_state, PowerOff Attached >,
::type Transitions;
and, in fact, is more limiting, because it doesn't allow to specify rules that apply to a subset of states and events. A small example from the docs.
// Let's define the fsm::transition's analogue that triggers // not only when the event type is equal to the specified, // but even when it is derived from it. template< typename CurrentStateT, typename EventT, typename TargetStateT
struct same_or_derived_event_transition : public fsm::basic_transition< TargetStateT > { // We only need to specify the static predicate // that selects the transition template< typename StateT, typename EvtT > struct is_applicable : public mpl::and_< // We should check that state type is correct mpl::or_< is_same< CurrentStateT, fsm::any_state >, is_same< CurrentStateT, StateT > >,
Isn't the above "or" clause always true, and if not, why not?
// Now we shall check the event type mpl::or_< is_same< EventT, EvtT >, is_base_and_derived< EventT, EvtT > > > { }; };
I feel that such flexibility is more important than syntactic sugar.
If syntactic sugar didn't matter, we'd all be programming in assembly language. I believe it's possible to design an expressive DSL that still has all the capabilities your library delivers.
In fact, I find your syntax more verbose for the unneeded fourth column of the table.
It's only unneeded if you think it doesn't convey information that's important to understanding the FSM. From my POV, it does. That's why arcs in an FSM diagram are often labeled with their associated transition actions. How does a user of your library associate actions with transitions if they don't go in the table?
The action is totally defined by the event and the current state.
I don't see how that answers my question.
Handler names are always the same and thus need not to be present in the table.
Do you mean to say that every transition action is named the same and the one to execute is chosen by overload resolution? -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
on Tue Aug 19 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
and, in fact, is more limiting, because it doesn't allow to specify rules that apply to a subset of states and events. A small example from the docs.
// Let's define the fsm::transition's analogue that triggers // not only when the event type is equal to the specified, // but even when it is derived from it. template< typename CurrentStateT, typename EventT, typename TargetStateT struct same_or_derived_event_transition : public fsm::basic_transition< TargetStateT > { // We only need to specify the static predicate // that selects the transition template< typename StateT, typename EvtT > struct is_applicable : public mpl::and_< // We should check that state type is correct mpl::or_< is_same< CurrentStateT, fsm::any_state >, is_same< CurrentStateT, StateT > >,
Isn't the above "or" clause always true, and if not, why not?
No, it's not. The FSM instantiates is_applicable on every state and every event type. The above condition yields true only for the selected state (CurrentStateT), unless CurrentStateT is any_state. If it is, then yes, the above "or" is true for all states.
// Now we shall check the event type mpl::or_< is_same< EventT, EvtT >, is_base_and_derived< EventT, EvtT > > > { }; };
In fact, I find your syntax more verbose for the unneeded fourth column of the table. It's only unneeded if you think it doesn't convey information that's important to understanding the FSM. From my POV, it does. That's why arcs in an FSM diagram are often labeled with their associated transition actions. How does a user of your library associate actions with transitions if they don't go in the table? The action is totally defined by the event and the current state.
I don't see how that answers my question.
Handler names are always the same and thus need not to be present in the table.
Do you mean to say that every transition action is named the same and the one to execute is chosen by overload resolution?
Yes. Every transition rule (or a row in STT) has one or more "transit" member functions that accept references to the current state and the event being processed. So, when a particular transition rule is chosen, the library simply calls the "transit" member in that particular rule.
On Sun, 2008-08-17 at 22:12 -0800, David Abrahams wrote:
on Sun Aug 17 2008, Darryl Green <darryl.green-AT-aanet.com.au> wrote:
the diagram in the USB example is an incredibly verbose representation (by count of nodes and edges) of what is described by Phils code.
But Phil didn't encode the whole machine represented in the diagram.
No - but most of what he left out was checking for invalid inputs that you have been claiming is not necessarily required. Adding in the suspended state tracking in an ad-hoc way would only need: bool suspended; void bus_inactive() { suspended = true; } void bus_activity() { suspended = false; } A simple "flat" state diagram and a similarly simple state transition table are always going to be very verbose.
Obviously you don't infer from this that any attempt to embed state diagram (like) representations in code is pointless,
I do think it's pointless in C++, although I don't do it by inference from anything you're mentioning.
Wow! Does that mean you are against any FSM library or only one that tries to represent a diagram by some method other than an attributed edge list (state trainstion table)?
"states handle events" is not part of the abstraction of what an FSM is. Look it up in Wikipedia or any CS text. You won't see any such description. Instead, that's a point-of-view unnecessarily imposed by the proposed library. So the library's DSL isn't a faithful reflection of the ways we already talk about FSMs.
Ok - it is not the state that handles the event but the machine. I was just trying for an abridged title for the model - not a formal definition. That said I talk about FSMs in a lot of ways, often to people who have never read a CS text in their lives. Some of the things that they might have read include ITU Z.100 (SDL) which maps rather nicely to Andrey's DSL (except for the lack of a way to send an event back to the machine from within the event handler, something that Andrey cosnders out of scope for the library).
typedef mpl::vector< fsm::transition<Attached, fsm::event<PowerOn>, Powered>, SetAddressTrans<Default, std::not_equal_to, Address>, SetAddressTrans<Address, std::equal_to, Default>, SetConfigurationTrans<Address, std::not_equal_to, Configured>, SetConfigurationTrans<Configured, std::equal_to, Address>, fsm::transition<fsm::any_state, fsm::event<Reset>, Default>, fsm::transition<fsm::any_state, fsm::event<PowerOff>, Attached>
::type Transitions;
The bits enclosed by fsm::transition look like they might be rows in an STT, although they're awfully verbose, with a great deal of surrounding syntactic noise that distracts from being able to read the actual semantics. AFAICT, the other parts do not bear any obvious resemblance to rows in an STT.
I agree that the convenience classes that Andrey put together to encapsulate the data dependend (gated) transitions are irregular. Can you suggest a better approach to deal with them?
on Mon Aug 18 2008, Darryl Green <darryl.green-AT-aanet.com.au> wrote:
On Sun, 2008-08-17 at 22:12 -0800, David Abrahams wrote:
on Sun Aug 17 2008, Darryl Green <darryl.green-AT-aanet.com.au> wrote:
the diagram in the USB example is an incredibly verbose representation (by count of nodes and edges) of what is described by Phils code.
But Phil didn't encode the whole machine represented in the diagram.
No - but most of what he left out was checking for invalid inputs that you have been claiming is not necessarily required. Adding in the suspended state tracking in an ad-hoc way would only need:
bool suspended;
void bus_inactive() { suspended = true; } void bus_activity() { suspended = false; }
yes, well I wasn't expecting such an ad-hoc approach; it's not a very direct translation from the diagram.
Obviously you don't infer from this that any attempt to embed state diagram (like) representations in code is pointless,
I do think it's pointless in C++, although I don't do it by inference from anything you're mentioning.
Wow! Does that mean you are against any FSM library or only one that tries to represent a diagram by some method other than an attributed edge list (state trainstion table)?
Umm, no, I just think there's no reasonable way to draw state diagrams in C++ syntax (outside of comments).
typedef mpl::vector< fsm::transition<Attached, fsm::event<PowerOn>, Powered>, SetAddressTrans<Default, std::not_equal_to, Address>, SetAddressTrans<Address, std::equal_to, Default>, SetConfigurationTrans<Address, std::not_equal_to, Configured>, SetConfigurationTrans<Configured, std::equal_to, Address>, fsm::transition<fsm::any_state, fsm::event<Reset>, Default>, fsm::transition<fsm::any_state, fsm::event<PowerOff>, Attached>
::type Transitions;
The bits enclosed by fsm::transition look like they might be rows in an STT, although they're awfully verbose, with a great deal of surrounding syntactic noise that distracts from being able to read the actual semantics. AFAICT, the other parts do not bear any obvious resemblance to rows in an STT.
I agree that the convenience classes that Andrey put together to encapsulate the data dependend (gated) transitions are irregular. Can you suggest a better approach to deal with them?
not yet, I guess. I don't understand what they do. -- Dave Abrahams BoostPro Computing http://www.boostpro.com
David Abrahams wrote:
on Sun Aug 17 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
David Abrahams wrote:
on Sun Aug 17 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:
State machines, as I see it, are meant to define an object behavior, IOW reduce the amount of undefined behavior. It is pointless to use them to implement undefined behavior. So std::vector is pointless because it exhibits undefined behavior when misused? No, vector is not pointless, because its purpose is to store elements, not to define behavior.
Sorry, but you're making no sense to me. The defined behaviors of vector are just as important as the defined behaviors of your FSM library.
I believe, Darryl Green has already cleared this point (thanks, Darryl).
I will need vector to store elements even with undefined behavior on invalid pointers as its input. But why would I need FSM if it doesn't define my object's behavior?
Well, it would define useful behaviors for valid inputs.
That's right, I didn't think about it.
Please, have a look at my reply to Phil. I've attached a code snippet with a transition map. Does that look more declarative? Not really, to me. It's very difficult for me to see the transitions in that code. Compare that with either of my player examples. Hmm... I don't see much difference, except for comments markup. Both code samples use transition maps, both use vectors... Is it because the transition map in your code is a member of the complete FSM?
Sorry, I don't know what a "transition map" is. In fact, when I google ``fsm "transition map"'' all the top hits come from your library, which tells me it's almost certainly not a known term in the FSM domain. I'm talking about a State Transition Table (STT) (http://en.wikipedia.org/wiki/State_transition_table).
transition map == STT. I didn't know the term is that strictly defined.
Phil Endecott wrote:
Dear All,
I have just spent a few minutes comparing an ad-hoc FSM implementation with an implementation using the proposed library. The example that I've used is the USB device state machine, which I recently had to understand for an embedded application, and I've put an image of the state graph here:
[snip]
Here is my ad-hoc implementation (note that I haven't tried to even compile any of this code):
[snip code] Well, your code is not an FSM. I mean, the usb_device behavior does not in any way depend on its state. I could simply remove the state variable and have the same result. And I agree, in case when there are two variables that need to be changed in arbitrary order, there is no need in an FSM library (no matter which FSM library we may have in mind). However, if you try to implement state/event correctness checks and define the device behavior in each state (given that the behavior differs, of course), I'm sure that your code will eventually become less obvious.
In comparison, here's what I've come up with using Boost.FSM:
[snip]
The latter is clearly more verbose than the former. Some of the verbosity would go if I put the common events (e.g. PowerOff) into a base class, but that adds verbosity of its own.
Why? Base classes for states help a lot to reduce code redundancy. I've attached a slightly modified version of the code above, with base classes and library-provided events (this allows you not to define event classes, which also reduces the code). See usb_fsm_state_based.cpp.
There are a few characteristics of this particular design that favour the ad-hoc code. Firstly, the device's behaviour is allowed to be undefined if an unexpected event occurs.
IMO, undefined behavior usually is a design flaw, and this case is clearly one of the "usual" ones. Otherwise, like I said, you don't need FSM, because its whole purpose is to _define_ the behavior.
Secondly, many events have the same effect irrespective of the state (e.g. power off).
This, as you noted yourself, can be handled with base classes. Also, one can use transition maps to define state changes, and transition maps provide an any_state placeholder for this purpose. I've attached another version of the example with a transition map (see usb_fsm_transition_based.cpp). Note that all transition logic is encapsulated in transitions and all processing is in states.
Finally, the effect of events often depends on their data (i.e. zero has a special meaning).
In fact, this is quite common, according to my experience. That's why the events can be processed in run time both in transitions and states.
Perhaps more complex FSMs would benefit more from what this library offers. In that case, can we see an example? I note that this library is targeted at simpler FSMs than Boost.Statechart (which I have not used). Is there a category of FSMs that are simple enough that Boost.Statechart's features are not needed (e.g. hierarchy) yet too complex for an ad-hoc implementation?
Generally, if performance matters and if you don't need to span your FSM across several dlls and you don't need to create an asynchronous FSM, you should be fine with Boost.FSM. For example, various protocols (INAP, for what I had experience with) and their clients may benefit from using Boost.FSM. Simple parsers can also be implemented on top of the library.
Andrey Semashev wrote:
Dear All,
I have just spent a few minutes comparing an ad-hoc FSM implementation with an implementation using the proposed library. The example that I've used is the USB device state machine, which I recently had to understand for an embedded application, and I've put an image of the state graph here:
[snip]
Here is my ad-hoc implementation (note that I haven't tried to even compile any of this code):
[snip code]
Well, your code is not an FSM. I mean, the usb_device behavior does not in any way depend on its state. I could simply remove the state variable and have the same result.
If I had realised sooner how degenerate that particular example was going to turn out I would have chosen something else. But I realised too late, and I thought it was better to use a real application than a contrived one. I will try to come up with another example before the end of the review period so that we can discuss the real problem and not be sidetracked by this. I do hope that others will also post some code.
Some of the verbosity would go if I put the common events (e.g. PowerOff) into a base class, but that adds verbosity of its own.
Why? Base classes for states help a lot to reduce code redundancy. I've attached a slightly modified version of the code above, with base classes and library-provided events (this allows you not to define event classes, which also reduces the code). See usb_fsm_state_based.cpp.
Unfortunately I'm unable to easily read attachments because these links:
A non-text attachment was scrubbed... Name: usb_fsm_state_based.cpp Type: text/x-c++src Size: 2214 bytes Desc: not available URL: <http://lists.boost.org/MailArchives/boost/attachments/20080817/737190e0/attachment.bin>
still don't work. I'll try to find your code in one of the list archives.
IMO, undefined behavior usually is a design flaw, and this case is clearly one of the "usual" ones. Otherwise, like I said, you don't need FSM, because its whole purpose is to _define_ the behavior.
I disagree. If I have a guarantee of how the environment will behave it is unnecessary to check it, except perhaps in some sort of debug mode. Picking up on one of Dave's comments, do you put a test in every function that takes a pointer to test whether you have been passed a null? Of course, when the behaviour of the environment is not guaranteed then I do need to check. If the scope of the proposed library is intended to be limited to applications where the environment is untrusted, please make a note of that in the documentation. Anyway, I will make sure that my next example is of the "untrusted environment" type. Regards, Phil. P.S. Many thanks to Dave A for fielding a whole series of messages while I was wasting my Sunday morning writing my tax return....
on Sun Aug 17 2008, "Phil Endecott" <spam_from_boost_dev-AT-chezphil.org> wrote:
Well, your code is not an FSM. I mean, the usb_device behavior does not in any way depend on its state. I could simply remove the state variable and have the same result.
If I had realised sooner how degenerate that particular example was going to turn out I would have chosen something else. But I realised too late, and I thought it was better to use a real application than a contrived one. I will try to come up with another example before the end of the review period so that we can discuss the real problem and not be sidetracked by this.
If you had only implemented the entire state diagram as shown, you would have transitions depending on state (see the transitions that occur due to bus activity). -- Dave Abrahams BoostPro Computing http://www.boostpro.com
Phil Endecott wrote:
Andrey Semashev wrote:
IMO, undefined behavior usually is a design flaw, and this case is clearly one of the "usual" ones. Otherwise, like I said, you don't need FSM, because its whole purpose is to _define_ the behavior.
I disagree. If I have a guarantee of how the environment will behave it is unnecessary to check it, except perhaps in some sort of debug mode.
Agreed. But in such a case, do you need an FSM in the first place? If you have the guarantee that function A will always be called before function B, you will simply rely on it and assume that while in B, A has already been called.
Picking up on one of Dave's comments, do you put a test in every function that takes a pointer to test whether you have been passed a null? Of course, when the behaviour of the environment is not guaranteed then I do need to check. If the scope of the proposed library is intended to be limited to applications where the environment is untrusted, please make a note of that in the documentation.
There's nothing in the library that prevents you from using it in a predictable environment. You certainly can implement "undefined behavior" with the library as long as you can express it in C++. I just don't see the point of using FSM (as a concept, not the particular library) in such a case.
Sorry to jump in, but... On Mon, Aug 18, 2008 at 3:55 AM, Andrey Semashev <andrey.semashev@gmail.com> wrote:
Picking up on one of Dave's comments, do you put a test in every function that takes a pointer to test whether you have been passed a null? Of course, when the behaviour of the environment is not guaranteed then I do need to check. If the scope of the proposed library is intended to be limited to applications where the environment is untrusted, please make a note of that in the documentation.
There's nothing in the library that prevents you from using it in a predictable environment. You certainly can implement "undefined behavior" with the library as long as you can express it in C++. I just don't see the point of using FSM (as a concept, not the particular library) in such a case.
I might digress a bit, but you can (and most efficiently should) implement random number generators using a non-deterministic finite state machine. For example, generating a stream of random bytes can (and should, for efficiency purposes, IMO) be implemented using a simple finite-state machine but the actual transitions performed are non-deterministic. This is useful for thread-safe implementations of an 'entropy source'. There are a lot more experts out there in this field who may know more than I do, so I'll stop there. For a generic finite state machine library (that wants to be part of the Boost Library), I think there ought to be a balance between efficiency and safety. For instance: high efficiency, less "safety": disable check for nullness, state-ful-ness high efficiency, more "safety": enforce supported transitions at compile-time (class structure, see MPL approach) low efficiency, more "safety": check everything and throw for recoverability low efficiency, less "safety": check everything, throw on undefined, allow illegal state-changes These may have to be controlled through either macro definitions or different classes (specialized through parametric tags) to allow users to choose which implementation they prefer. This is by no means a complete review, but this is more to give perspective as to the expectations are with regards to something as fundamental (and useful) as a finite state machine implementation. HTH -- Dean Michael C. Berris Software Engineer, Friendster, Inc.
Dean Michael Berris wrote:
Sorry to jump in, but...
On Mon, Aug 18, 2008 at 3:55 AM, Andrey Semashev <andrey.semashev@gmail.com> wrote:
There's nothing in the library that prevents you from using it in a predictable environment. You certainly can implement "undefined behavior" with the library as long as you can express it in C++. I just don't see the point of using FSM (as a concept, not the particular library) in such a case.
I might digress a bit, but you can (and most efficiently should) implement random number generators using a non-deterministic finite state machine. For example, generating a stream of random bytes can (and should, for efficiency purposes, IMO) be implemented using a simple finite-state machine but the actual transitions performed are non-deterministic. This is useful for thread-safe implementations of an 'entropy source'. There are a lot more experts out there in this field who may know more than I do, so I'll stop there.
I'm by far no expert too, but I thought that the algorithm of random number generation is quite defined. The source of entropy is usually either an initial value of seed or some external non-constant value (like system time, CPU temperature, remote seed provider or something like that) which is used as input to calculate the next seed. Anyway, the library does not prevent you from making such random transitions.
For a generic finite state machine library (that wants to be part of the Boost Library), I think there ought to be a balance between efficiency and safety. For instance:
high efficiency, less "safety": disable check for nullness, state-ful-ness high efficiency, more "safety": enforce supported transitions at compile-time (class structure, see MPL approach) low efficiency, more "safety": check everything and throw for recoverability low efficiency, less "safety": check everything, throw on undefined, allow illegal state-changes
These may have to be controlled through either macro definitions or different classes (specialized through parametric tags) to allow users to choose which implementation they prefer.
I'm not sure I understand you correctly. There are nearly no places in the library where correctness checks are needed (the only one I could remember on spot is the dynamic state switching - an exception is thrown in case if FSM tries to transit to a non-existing state in run time). And I don't think that this additional "if" would matter anything in a real-world FSM. In all other cases the invalid code just won't compile. If you meant safety from the user's perspective (e.g. how the FSM should react on unexpected input), then it's totally user's choice.
Andrey Semashev wrote:
Phil Endecott wrote:
Andrey Semashev wrote:
IMO, undefined behavior usually is a design flaw, and this case is clearly one of the "usual" ones. Otherwise, like I said, you don't need FSM, because its whole purpose is to _define_ the behavior.
I disagree. If I have a guarantee of how the environment will behave it is unnecessary to check it, except perhaps in some sort of debug mode.
Agreed. But in such a case, do you need an FSM in the first place? If you have the guarantee that function A will always be called before function B, you will simply rely on it and assume that while in B, A has already been called.
An environment that makes guarantees about how it will or will not behave is not generally a completely deterministic environment. Example: say I'm receiving UTF-8, and I'm guaranteed by the sender that it's valid UTF-8. I still need to track the state of the stream as I process the bytes, even though I'm going to allow undefined behaviour (either in the C++ language sense, or in some other sense) if those bytes are invalid. This particular problem could certainly be usefully expressed using an FSM. But don't worry if you disagree; this is unimportant. The intention of my original message was to suggest that your library seems to add a lot of verbosity to my implementation, without much obvious benefit. I would like to be convinced otherwise, preferably through examples. Phil.
Phil Endecott wrote:
Andrey Semashev wrote:
Phil Endecott wrote:
Andrey Semashev wrote:
IMO, undefined behavior usually is a design flaw, and this case is clearly one of the "usual" ones. Otherwise, like I said, you don't need FSM, because its whole purpose is to _define_ the behavior.
I disagree. If I have a guarantee of how the environment will behave it is unnecessary to check it, except perhaps in some sort of debug mode.
Agreed. But in such a case, do you need an FSM in the first place? If you have the guarantee that function A will always be called before function B, you will simply rely on it and assume that while in B, A has already been called.
An environment that makes guarantees about how it will or will not behave is not generally a completely deterministic environment.
Example: say I'm receiving UTF-8, and I'm guaranteed by the sender that it's valid UTF-8. I still need to track the state of the stream as I process the bytes, even though I'm going to allow undefined behaviour (either in the C++ language sense, or in some other sense) if those bytes are invalid. This particular problem could certainly be usefully expressed using an FSM.
Agreed. I admit, I didn't think about it.
Picking up on one of Dave's comments, do you put a test in every function that takes a pointer to test whether you have been passed a null?
If the pointer would be guaranteed to be nonzero, I would prefer to use a reference (in the function signature) instead of a pointer. I admit that it's not always possible to use references, because pointer arithmetic is not applicable to references. But in this case, an iterator would be more suitable than a pointer.
Andrey Semashev wrote:
I've attached another version of the example with a transition map (see usb_fsm_transition_based.cpp). Note that all transition logic is encapsulated in transitions and all processing is in states.
I'm unable to see how the "transition map" enters into the code. You make a typedef typedef mpl::vector< ...
::type Transitions;
but I cannot see "Transitions" used anywhere in the code. Is there some magic that the included headers use this typedef? That would be scary to me.
Thomas Klimpel wrote:
Andrey Semashev wrote:
I've attached another version of the example with a transition map (see usb_fsm_transition_based.cpp). Note that all transition logic is encapsulated in transitions and all processing is in states.
I'm unable to see how the "transition map" enters into the code. You make a typedef
typedef mpl::vector< ...
::type Transitions;
but I cannot see "Transitions" used anywhere in the code. Is there some magic that the included headers use this typedef? That would be scary to me.
Sorry, I missed that. The transition table should be provided as the third template parameter for the state machine. fsm::state_machine< StateList, void, Transitions > machine;
participants (8)
-
Andrey Semashev -
Christian Holmquist -
Darryl Green -
David Abrahams -
Dean Michael Berris -
Michael Caisse -
Phil Endecott -
Thomas Klimpel