Re: [boost] Re: review of proposed fsm library
class state_machine: public state, private state_control { ... };
is a possibility. However, leaving the control manager separate from the state data (structure) might be better yet. Why does this separation of concerns seem obscure?
I don't see why an FSM should behave like a state. An FSM is not a state, it has a state.
Does your state code stand alone from the state machine code? e.g. Can I re-use "state" without buying "state_machine"? I guess that is what I'm really after.
Perhaps the control manager can iterate over the state data structure? operator++ advances to the next state; operator() performs the reaction, etc. Okay, I've entered pure brainstorming territory :-), but really, things might be improved by not commingling data and control.
Any use-cases?
Just brainstorming.
I think problems with examples are alleviated partially when people can take the source files comprising the example, compile them, and see them run -- a success was achieved immediately. For instance, Boost.Serialization does this with at least some of its examples (demo_xml.hpp and demo_xml.cpp, if I recall correctly).
How is this relevant?
I'm recommending that you adjust your documentation so that one can readily compile complete examples by downloading source and header code files via links embedded within the documentation page. You could also have a templated version of some code in separate files (given that you don't like the idea of templatizing regularly).
I guess I don't really understand what you want to say here. Making a component generic is always more work than leaving it the way you need it for your current problem at hand. E.g. for a submachine, you'd need to make the external transition targets template parameters.
What I'm asking for is an example of this to be included in the documentation, so that people who want to build a component library, plug those components together, etc. have a pre-made example conforming to best practice (as given by you, the expert) to consult. This is why I recommended an example involving a half-adder component, used twice to create a full-adder.
This comment does not address myriad uses that I would have for an fsm library that met my needs.
Please briefly describe one such use, non-parser related if possible.
I've come to realize that really what I was thinking about was using the hierarchical state mechanism, separate from the standard state machine execution procedure. The goal is to construct a hierarchical state representation of a search space as a program gathers information.
Perhaps it is because people would like the freedom to employ fsm in contexts that you did not target your solution for.
Maybe, an example of such use would be interesting.
One thing that fits within the rubric of FSM (as opposed to more general state categorization and manipulation) is simply to build an fsm at runtime. This was explicitly not a design goal of yours, though. I also have a desire for NFA -> DFA and DFA -> minimized DFA procedures; I still don't know if it's possible to do this or not with the library. With these items, I'm obviously willing to take the compilation time hit of everything being known to a single translation unit, if that is necessary (and you've made what looked to me like a good argument that it would be).
No, not really. Certainly, I would expect to be able to plug together an asynchronous and synchronous submachines into a larger, single fsm (which would need to be modelled asynchronously).
You can do that with the current version.
Good stuff.
Why? Must I really offer all the functionality in the first version of the library?
I think I suggested otherwise earlier.
I've just reread you original post and fail to see anything that resembles a request to support full deep history. Instead you find it suspicious that I have taken the liberty to not support something that is - in my experience - needed only very rarely and diffcult to implement too. It is of course your right to find that suspicious but for me that is not encouraging in any way. If you file such a request now I hope you understand that I will not make an attempt to implement full deep history until you have convinced me that it is a) absolutely necessary in some real-world cases (i.e. the workaround is not sufficient) b) needed by a sufficiently large group of people
My time is limited and I tend to address the issue that is the most pressing first. I seriously doubt that full deep history support will make it to the top of my to-do list in the near future.
[and]
Excuse me, I really don't understand what the problem is. Fork bars are not supported for the very same reasons that full deep history is not supported. They are - in my experience - needed only rarely and they are difficult to implement. I ask again: Why should I invest my time in such a feature now? Or, why should I have invested that time before submission?
Most libraries have some limitations, even the ones at boost.
[and]
The interface change for this is rather easy: Simply specify multiple rather than just one target state. I don't see the problem. BTW, this is connected to deep history not working for orthogonal sub-states.
I suspected so. I believe it was caused by starting with the fsm having abilities that applied to one state at a time, then later adding orthogonality support but without a full conversion to supporting state-supersets in all places of the code. However, this is sheer speculation on my part and may well be wrong. :-)
I can't answer this because I don't understand what a state-superset is.
The superset of the set S = {"0", "1", "2"} is S* = { { }, { "0" }, { "1" }, { "2" }, { "0", "1" }, { "0", "2" }, { "1", "2" }, { "0", "1", "2" } } A basic FSM machine M will map S x T -> S (S = state, T = transition); but when orthogonal states are supported, instead one must map S* x T -> S* (where S* is the superset of S). Where I wrote "state-superset", I was referring to S*. My speculation, which was not based on an in-depth examination of the code (though I did look at it briefly), was that your FSM code started out supporting S x T -> S, which is very natural, and that parts of it must yet be altered to fully support S* x T -> S*. I thought that this explained why fork bars are not supported, why join bars are not supported, and why the "orthogonal multiple-state-change from single transition" is not supported. But, as before, I readily concede that this intuition (or hunch) could well be wrong.
From a theoretical view, software that does not fully support the mapping S* x T -> S* cannot correctly adhere to the UML specification -- which seems important given that the main purpose of your library appears to be to provide a diagram-to-code implementation of that specification.
Accordingly, I consider this to be a "correctness of design" issue, not merely a "these features aren't needed that often" issue. As for your view, sure, it's completely understandable that you have to implement what is most pressing for "clients" of your code.
Because people may want the ability to use epsilon-transitions, which NFAs support and make finite automata modelling considerably simpler in many cases.
It seems such a discussion belongs into a state theory text and not a tutorial for a FSM library.
Why? Epsilon-transitions increase the ease with which one can specify a state machine. Does the UML state machine standard not support them at all? While it is true that their use would effectively make machine M require the use of S* x T -> S* instead of S x T -> S, is this not also true for join bars, or fork bars, or orthogonal states (at least, where there are actions that cause multiple simultaneous transitions)? The process of converting an NFA to a DFA is the process of transforming machine M: S* x T -> S* into a new machine M': S' x T' -> S' with identical behaviour, but without epsilon transitions. It seems to me that this same process can convert a machine that relies on fork bars, join bars, and "orthogonal multiple-state-change from single transition" to one that relies on none of the above. (Additionally, a DFA minimization pass may be run on it after conversion to try to combat state-space explosion.) Is it really a surprise that such fundamental algorithms could be of use? New comment: Andreas outlines 9 requirements that his library satisfies. Some users have the same requirements, or a subset of them, and they are no doubt extremely pleased with the library as proposed. Others have different requirements, some of which conflict with the 9 selected: 10. Dynamic (run-time) FSM construction. 11. Reusable finite automata components. 12. Modelling of non-determinism; availability of epsilon-transitions. 13. Constant-time dispatch. For my own purposes, all four of these are more important than Andreas' #3 and #4 requirements. For others, the situation will be different. I believe the crux of the review manager's task is to weigh the requirements that have been satisfied, plus its potential to fulfill the others against the requirements that the various potential users of the library have. Disclaimer: I hope I didn't blow it on any of the details in this message. It's getting a bit late! Dave
Dave Gomboc wrote:
class state_machine: public state, private state_control { ... };
is a possibility. However, leaving the control manager separate from the state data (structure) might be better yet. Why does this separation of concerns seem obscure?
I don't see why an FSM should behave like a state. An FSM is not a state, it has a state.
Does your state code stand alone from the state machine code? e.g. Can I re-use "state" without buying "state_machine"? I guess that is what I'm really after.
I'm not sure whether the following answers your question: State code can stand alone if you want it to, by making all your simple_state and state subtypes templates, accepting at least the Context a template parameter. See http://tinyurl.com/6xdh3 (Submachines & Parameterized states) for an example.
Perhaps the control manager can iterate over the state data structure? operator++ advances to the next state; operator() performs the reaction, etc. Okay, I've entered pure brainstorming territory :-), but really, things might be improved by not commingling data and control.
Any use-cases?
Just brainstorming.
Brainstorming can be fun but I hope you understand that I will not add or change anything for which there aren't any real-world use-cases.
I think problems with examples are alleviated partially when people can take the source files comprising the example, compile them, and see them run -- a success was achieved immediately. For instance, Boost.Serialization does this with at least some of its examples (demo_xml.hpp and demo_xml.cpp, if I recall correctly).
How is this relevant?
I'm recommending that you adjust your documentation so that one can readily compile complete examples by downloading source and header code files via links embedded within the documentation page. You could
That's already on the yet unpublished to-do list.
also have a templated version of some code in separate files (given that you don't like the idea of templatizing regularly).
Ok, I can do that for the keyboard example, where templatizing makes perfect sense.
I guess I don't really understand what you want to say here. Making a component generic is always more work than leaving it the way you need it for your current problem at hand. E.g. for a submachine, you'd need to make the external transition targets template parameters.
What I'm asking for is an example of this to be included in the documentation, so that people who want to build a component library, plug those components together, etc. have a pre-made example conforming to best practice (as given by you, the expert) to consult.
It's already there, see the link above.
This is why I recommended an example involving a half-adder component, used twice to create a full-adder.
I'll consider adding such an example.
This comment does not address myriad uses that I would have for an fsm library that met my needs.
Please briefly describe one such use, non-parser related if possible.
I've come to realize that really what I was thinking about was using the hierarchical state mechanism, separate from the standard state machine execution procedure. The goal is to construct a hierarchical state representation of a search space as a program gathers information.
That should be possible, you can use whatever CT algorithms you like to assemble your FSM. The BitMachine example does something in this direction, the number of states is dependent on the number of bits you want it to represent.
Perhaps it is because people would like the freedom to employ fsm in contexts that you did not target your solution for.
Maybe, an example of such use would be interesting.
One thing that fits within the rubric of FSM (as opposed to more general state categorization and manipulation) is simply to build an fsm at runtime. This was explicitly not a design goal of yours, though.
Yep, you'd lose validation at compile time.
I also have a desire for NFA -> DFA and DFA -> minimized DFA procedures; I still don't know if it's possible to do this or not with the library.
Well, I can certainly say that the library was never designed to enable such uses. However, provided you can do the minimization at compile time I don't see many obstacles, I probably need to add few typedefs here and there and you should be able to extract all the information you need.
With these items, I'm obviously willing to take the compilation time hit of everything being known to a single translation unit, if that is necessary (and you've made what looked to me like a good argument that it would be).
Ok.
Why? Must I really offer all the functionality in the first version of the library?
I think I suggested otherwise earlier.
Ok, I must have missed that.
I've just reread you original post and fail to see anything that resembles a request to support full deep history. Instead you find it suspicious that I have taken the liberty to not support something that is - in my experience - needed only very rarely and diffcult to implement too. It is of course your right to find that suspicious but for me that is not encouraging in any way. If you file such a request now I hope you understand that I will not make an attempt to implement full deep history until you have convinced me that it is a) absolutely necessary in some real-world cases (i.e. the workaround is not sufficient) b) needed by a sufficiently large group of people
My time is limited and I tend to address the issue that is the most pressing first. I seriously doubt that full deep history support will make it to the top of my to-do list in the near future.
[and]
Excuse me, I really don't understand what the problem is. Fork bars are not supported for the very same reasons that full deep history is not supported. They are - in my experience - needed only rarely and they are difficult to implement. I ask again: Why should I invest my time in such a feature now? Or, why should I have invested that time before submission?
Most libraries have some limitations, even the ones at boost.
[and]
The interface change for this is rather easy: Simply specify multiple rather than just one target state. I don't see the problem. BTW, this is connected to deep history not working for orthogonal sub-states.
I suspected so. I believe it was caused by starting with the fsm having abilities that applied to one state at a time, then later adding orthogonality support but without a full conversion to supporting state-supersets in all places of the code. However, this is sheer speculation on my part and may well be wrong. :-)
I can't answer this because I don't understand what a state-superset is.
The superset of the set S = {"0", "1", "2"} is
S* = { { }, { "0" }, { "1" }, { "2" }, { "0", "1" }, { "0", "2" }, { "1", "2" }, { "0", "1", "2" } }
A basic FSM machine M will map S x T -> S (S = state, T = transition); but when orthogonal states are supported, instead one must map S* x T -> S* (where S* is the superset of S). Where I wrote "state-superset", I was referring to S*.
Okay, I guess I got that.
My speculation, which was not based on an in-depth examination of the code (though I did look at it briefly), was that your FSM code started out supporting S x T -> S, which is very natural, and that parts of it must yet be altered to fully support S* x T -> S*.
FWIW, the code indeed started out by supporting S x T -> S. Of course, some parts of the code must be changed to fully support S* x T -> S* (otherwise the feature would already be there). If I were to implement support for fork bars (and subsequently also for full deep history) I wouldn't need to change a single line of code in the state representation. Apart from the obvious interface changes, I would "only" need to implement the CT algorithm that calculates which states need to be entered in what order as the result of a given innermost common context and a list of orthogonal states that should be entered. Currently this CT algorithm only accepts one state.
I thought that this explained why fork bars are not supported,
See above. why join bars are not
supported,
I don't think I will ever support join bars. This would require vast interface changes and you can easily work around this lack with guards.
From a theoretical view, software that does not fully support the mapping S* x T -> S* cannot correctly adhere to the UML specification -- which seems important given that the main purpose of your library appears to be to provide a diagram-to-code implementation of that specification. Accordingly, I consider this to be a "correctness of design" issue, not merely a "these features aren't needed that often" issue. As for
See above. I don't think the current design is incorrect in this regard.
your view, sure, it's completely understandable that you have to implement what is most pressing for "clients" of your code.
Exactly.
Because people may want the ability to use epsilon-transitions, which NFAs support and make finite automata modelling considerably simpler in many cases.
It seems such a discussion belongs into a state theory text and not a tutorial for a FSM library.
Why?
Epsilon-transitions increase the ease with which one can specify a state machine. Does the UML state machine standard not support them at all?
I'm not sure. From googling around it seems that epsilon transitions are the same as triggerless transitions in UML?
While it is true that their use would effectively make machine M require the use of S* x T -> S* instead of S x T -> S, is this not also true for join bars, or fork bars, or orthogonal states (at least, where there are actions that cause multiple simultaneous transitions)?
The process of converting an NFA to a DFA is the process of transforming machine M: S* x T -> S* into a new machine M': S' x T' -> S' with identical behaviour, but without epsilon transitions. It seems to me that this same process can convert a machine that relies on fork bars, join bars, and "orthogonal multiple-state-change from single transition" to one that relies on none of the above. (Additionally, a DFA minimization pass may be run on it after conversion to try to combat state-space explosion.)
Is it really a surprise that such fundamental algorithms could be of use?
I'm not sure whether such algorithms would be used more than rarely by the targeted user group. I do agree that such algorithms are probably extremely useful for FSMs that are generated by algorithms (regex) but I have my doubts whether the same is true for machines that are directly engineered by humans. As I have mentioned before, I think one significant obstacle for any such transformations is state-local storage (I might be wrong).
New comment:
Andreas outlines 9 requirements that his library satisfies. Some users have the same requirements, or a subset of them, and they are no doubt extremely pleased with the library as proposed.
Others have different requirements, some of which conflict with the 9 selected:
10. Dynamic (run-time) FSM construction. 11. Reusable finite automata components. 12. Modelling of non-determinism; availability of epsilon-transitions. 13. Constant-time dispatch.
For my own purposes, all four of these are more important than Andreas' #3 and #4 requirements. For others, the situation will be different. I believe the crux of the review manager's task is to weigh the requirements that have been satisfied, plus its potential to fulfill the others against the requirements that the various potential users of the library have.
I believe it is not feasible to implement a single library that satisfies all 13 requirements. It is probably possible but I seriously doubt that such a library would be of any use for more than a handful of people. All of these additional requirements inevitably complicate the interface and the implementation. I strongly believe that there are two groups of FSM users (as defined in the rationale) with a very small intersection. It would make little sense to provide one library that satisfies both groups. It makes much more sense to implement two distinct libraries. Regards, -- Andreas Huber When replying by private email, please remove the words spam and trap from the address shown in the header.
participants (2)
-
Andreas Huber -
Dave Gomboc