- Boost - lists.boost.org

Re: [boost] [msm] Review
by Christophe Henry 15 Dec '09

15 Dec '09

>It seems to me that waiting to add a great library until some particular >compiler supports it isn't a great strategy. Msm works on our >production compiler, and it seems to me that the compiler support is >documented. I agree. Besides, if not used, eUML will wait long for compiler support. Compiler writers do need some users complaints as I just saw a few weeks ago. >If we fear rejection due to incorrect usage by potential >users who haven't read the documentation, perhaps the library could have >some built-in support for detecting compilers that are known not to work >and issue a coherent compiler-time error message. I think it's a good idea! EUML could simply refuse to compile if provided the wrong compiler. >So long as MSM works on multiple, highly-regarded compilers, and its failure on others >can be demonstrated reasonably to be due to failure to comply with the standard, then its portability >will have been demonstrated. If it only works on one compiler, then its portability case is diminished. EUML compiles well on g++4.3, and reasonably well on VC9/10 and g++4.4. Darryl, I understand your point and appreciate that you want to protect eUML but I think that propagating it is the best solution to make compilers improve. More warnings in the doc would also help.

2 1

library proposal: odeint
by Karsten Ahnert 14 Dec '09

14 Dec '09

Hi, I am new on this list and want to start a discussion if a library for solving ordinary differential equations (ODEs) would fit into boost. We are developing a lib - odeint - for such problems. odeint can be found in the sandbox: https://boost.org/svn/boost/sandbox/odeint, but the current stage is far away from being ready for release or submission. ODEs are usually solved iteratively. Therefore, we have introduced two stepper concepts, one for steppers with- and one for steppers without error estimation. At the moment some explicit solvers are implemented: Euler, RK4, Cash Karp, RK78,midpoint and Burlisch-Stoer. Here are some examples: typedef std::tr1::array< double , 3 > state_type; // define the ODE void lorenz( state_type &x , state_type &dxdt , double t ) { const double sigma = 10.0 , R = 28.0 , b = 8.0 / 3.0 dxdt[0] = sigma * ( x[1] - x[0] ); dxdt[1] = R * x[0] - x[1] - x[0] * x[2]; dxdt[2] = x[0]*x[1] - b * x[2]; } state_type x = {{ 1.0 , 0.0 , 0.0 }}; ode_step_euler< state_type > stepper; double t = 0.0; // iterate the ODE by hand with constant stepsize for( size_t oi=0 ; oi<10000 ; ++oi,t+=dt ) stepper.next_step( lorenz , x , t , 0.01 ); // integrate the ODE with constant stepsize // from t = 0.0 to t = 100.0 with dt = 0.01 // and write t and x[0] to cout integrate_const( rk4 , lorenz , 0.0 , 0.01 , x , 100.0 , cout << _1 << tab << _2[0] << "\n" ); // stepsize controller for rk5 cash-karp controlled_stepper_standard< stepper_rk5_ck< state_type > > rk5_controlled( rk5 , eps_abs, eps_rel, 1.0, 1.0); // solve the ODE with an adaptive stepsize controller size_t steps = integrate_adaptive( controlled_rk5, lorenz, x, 0.0, 10.0 , 0.01, cout << _1 << tab << _2[0] << "\n" ); Best regards, Karsten

7 6

Re: [boost] [msm] Review
by Christophe Henry 14 Dec '09

14 Dec '09

Hi Darryl, >Your responses come across as though you feel you are under attack. >Please accept that is not my intent I'm sorry if I gave this impression. While I was unsure what were your concerns at the beginning, I now appreciate a lot your contribution! You'll probably recognize your suggestions in the next versions :) >I see these as incredibly closely related in a C++ FSM model. This is >because, in my experience, the actions done in entry and exit actions >are resource management-like, very similar to the role of constructors >and destructors (or more generally scope entry/exit). I had intuited >that the rational for including entry/exit actions in fsm notations was >to model that scope concept. Actually, my take on the use of entry and exit was not scope entry/exit but rather a way to factorize behaviour out of the transition. So, to sum up our discussion: - I agree that using entry/exit for RAII sounds interesting. - paying 1 byte/state even if you don't need them is almost not visible on the performance level but I agree that it's still feeling not right. - on_entry and on_exit have in my opinion, compared to constructor and destructor, the advantage of flexibility (such as getting the event or fsm or the ability to throw). - while you would prefer to have no states, using them for tag dispatching still looks interesting to you. - I'm positive persisting data in states favors reuse in another fsm context. I hope to bring later some reusable state concept to prove this point. This pretty much sums up our discussion, right? We had a rocky start (due to my misunderstanding) but I understand this is the where we now are. I think that it's possible to have all this at the same time, constructor/destructor and entry/exit, persistent states and non-persistent, maybe in the same state machine. I can imagine a few possible solutions but need to think more about them. I'm pretty sure that it's possible to have at least non-persistent states (using no memory) while being still compatible with the front-ends (who require a source/target state). So, I thank you for the interesting discussion which delivered valuable points. I'll be happy to continue the discussion as soon as I can offer a solution. Christophe

1 0

[msm] Review
by Michael Caisse 14 Dec '09

14 Dec '09

Let me start with a thank you. Thank you Christophe for taking the time to "boostify" and submit this library. Thank you also for your quick responses to questions and discussions through out the review. I apologize that this is "late". I was unable to complete the review over the weekend. I am afraid that this review is somewhat disjointed. There are two parts. The top section answers the standard questions and provides some overview. The bottom section provides some specific details about the documentation and also discussions about specific features covered in each document section. I found that reviewing in order of the tutorial provided some structure to the review. Some of the points I make have been brought out in other emails/reviews ... but this is my review so I felt compelled to write down what I found important. Best regards - Michael Caisse ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Executive Summary: I personally find this library both useful and well implemented for many of my needs. The documentation is lacking and must be extended to include a library reference. Additionally, I would like to see SimpleStates implemented to support internal transitions as called out in the standard. Other issues are detailed; however, do not affect my qualified vote of "acceptance". My conditional recommendation for acceptance (yes vote) is based on resolving the documentation issues and lack of SimpleState internal transitions. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ------------------------------------------------------ What is your evaluation of the design? ------------------------------------------------------ The design seems sound; however, it has a feel of being in flux when reading the documentation. There are perhaps too many methods to create row entries. I haven't thought too much about this, but it seems that the functor (Row) mechanism might be extended further to replace the various "arow" syntax completely. ------------------------------------------------------ What is your evaluation of the implementation? ------------------------------------------------------ From the point-of-view of a UML implementation, I think this library does a good job of implementing the most used features of the language. I would like to see the addition of internal transitions for SimpleStates before the acceptance of the library. Lack of this feature makes it awkward at best to implement constructs that are the UML state machine equivalent of RAII. Entry and exit code for a state are often used to do things like start/stop timers and other such resource management. Not being able to handle internal transitions (transitions that don't leave the state and therefore do not cause an exit/entry cycle) make modeling this concept impossible. Hacks can be applied to work around the shortcoming ... but implementing the feature is the right solution. I find myself missing choice points. Using "anonymous transitions" nearly allows the same semantic... but not quite. I am used to being able to define multiple triggers for a transition. This is not a deal-killer but it would be nice to be able to somehow do this. Perhaps I could by having event 'a' and event 'b' derive from a common base and then using the 'base' as the event. I'm not sure. I also miss not having a "any" or "*" trigger definition. In essence, if no transition match is found for the active trigger ... take this transition. I have not spent enough time with the source code to provide an evaluation of the source. ------------------------------------------------------ What is your evaluation of the documentation? ------------------------------------------------------ The provided documentation is basically a tutorial. I found that a library reference guide was lacking. Though the tutorial was excellent, not having a library reference made using/reviewing the library difficult. I'm sure that there are many features and exploits that I didn't discover because the only route left to the reviewer was hope an example was in the tutorial, used in the example source code or by rummaging through the library source. Please make sure to add a section describing the run-to-completion semantics as well as the ordering of evaluation/execution when a trigger if fired. Additionally, an example of converting a runtime int to a type is in order. Most people doing statemachine work are acting on some trigger that now needs to be translated to a data type. There are many ways to slice this but none are listed. When showing this to another programmer the response I got was, "but I have ints or chars that I'm acting on. How do I make that into a type?" External stimulus is not a type so some hint on ways to do this will be nice for those getting introduced the concept for the first time. As an aside, I would be happy to review and offer feedback with documentation modifications. I may be able to offer some assistance with modifications also. Additional documentation edits can be found at the end of this review. ------------------------------------------------------ What is your evaluation of the potential usefulness of the library? ------------------------------------------------------ I find this library very useful. I have already begun modifying my code generators that take ArgoUML and Poseidon diagrams and generate code based on distributed machines to use MSM as a backend. This will allow me to fully understand the usefulness of the library to medium/large projects. At this time I have started using MSM for a smaller state machine project. I am finding the library useful. ------------------------------------------------------ Did you try to use the library? ------------------------------------------------------ - With what compiler? gcc-4.3.3 and VC 8 My experience with gcc has been fine. My experience with VC8 ran into problems with the eUML. I just switched to linux/gcc since my target almost always involves a gcc compiler. I don't have enough concrete experience with VC8 and MSM to provide a solid viewpoint ... but my soft view is that it might need some more help. - Did you have any problems? eUML (as expected) didn't work with VC 8 ------------------------------------------------------ How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? ------------------------------------------------------ I spent about 25 hours reviewing this library. I did not spend very much time with the source code but instead reviewing the documentation and testing the concepts/implementation as they stack up to the UML 2.0 standard. I also spent time implementing several of my own machines with the MSM library to determine how applicable and conforming the library might be. ------------------------------------------------------ Are you knowledgeable about the problem domain? ------------------------------------------------------ Yes. I have been dealing with UML based statemachine notation before it was part of UML. I have my own product that implements ROOM/UML distributed hierarchical FSMs that are generated from diagrams. I have implemented several UML compliant state machine libraries in a variety of languages. ------------------------------------------------------ Additional Documentation Comments Other MSM comments in order of the docs... ------------------------------------------------------ General: Inconsistent use of eUML. Sometimes it is EUML (particularly at the start of a sentence.) I believe it should always be eUML. Sub-state machines and composite states are not *exactly* the same in UML. It seems that it is implied or stated in a few places that it is. I would just state up front that Msm does not support composite states; however, it does support the more general solution of sub-state machines. ---------------------------- Section "Why Msm v2?" "UML designers are also used to write..." should be "UML designers are also used to writing..." ---------------------------- "Msm v1.x Features / Design Goals" If you are taking votes about multithreading ... please make it some non-required layer or policy or let the user's discretion play out. I will be using Msm on targets without an OS. "Msm v1.x Features / Founding Example" It might make sense to utilize UML terminology when discussing the parts of a transition: current state -> source state next state -> target state action method -> effect or behavior event -> trigger So... maybe not the event to trigger change. This is an interesting concept in Msm. Often an event is considered as having a trigger and optional data payload. The Msm event is a struct with possible data members. Event is fine I guess. "The event being passed the" -> "The event being passed to the" --------------------------- "A more advanced example" "The UML specification isn't too clear about the difference between composite states and sub-state machines..." That statement isn't exactly true. The specification is clear; however, Msm has implemented the more feature rich concept which is a superset of composite state. If there isn't a runtime (resource) penalty for this, then I don't see a problem. -------------------------- "Orthogonal States..." While the implementation of deferred events is correct according to UML I have found that the ROOM concept is extremely useful and have implemented it in my own libraries. You may want want to consider it as a feature to MSM. The defer mechanism is the same (you can defer any event in any state); however, you can later "recall" from the defer queue. This has the benefit of allowing a "simple" construct for handling deferred events. You can defer the events at a parent composite state. Once you enter the sub state handling certain (potentially deferred) events you can then do a recall from the queue. This is often done in the state's entry code. This pattern reduces the work involved by taking advantage of the hierarchical aspect of UML states. -------------------------- "Adding an history" should be "Adding a history" I personally am happy with the UML definition of histories and use them often in error handling patterns for example. Part of the power of UML states is the fact that they are hierarchical. Without a deep history concept in MSM I am required to specify a history policy for each contained sub-state machine (composite state). I do find this rather annoying though it is workable. I do like the AlwaysHistory policy since that is my normal use case when using histories. -------------------------- "Using 'flags'" My initial reaction to flags is "composite states already supply this information". I can see that flags can provide multiple slices of meta state information and *might* be useful. I am in general leery of abstractions that obfuscate additional state information. From a diagram POV, that state information is missing. In my world this typically means that the granularity of machines is wrong (I use distributed state machines) or the state hierarchy is not quite right. I have the same negative feeling about storing a lot of *state* information in variables that are acted upon in guards and such. It hides important information from the diagram and makes the machine harder to review and understand. This is not an argument to remove flags. It is just my first impression of the feature. I will need to play some more with it. I can see potential uses. -------------------------- "Anonymous transitions" In the UML standard the term "Completion Transition" is used for this concept. I like this term because it is descriptive of what is happening. I also like it it because this is a UML compliant library and using the UML terminology helps understanding the concepts more quickly. -------------------------- "The many ways to enter a composite state" Explicit exit is often a problem. I found that in two of my machines I tried converting that I use this mechanism. I used an exit point to work around the missing feature. This works ... but wasn't my intent. That said... I think what you have is proper for a submachine state. If MSM actually implemented composite states, then the lack of this notation would concern me. This might just be me, but the purpose of a submachine is to wrap a composite state into a reusable object. Entry and exit points therefore represent the public interface. Explicit entry and exit would be like accessing private data. "Important note 3" - I think this is important behavior for the proper use of submachine states. -------------------------- "Advanced" -------------------------- "Conflicting Transitions" This information is important. I think expanding the section to discuss the run-to-completion semantics and the order/execution rules followed when a trigger is received is vitally important. Example, trigger A is received. The following steps are performed in this order: .... -------------------------- "Contaning state machine (deprecated)" This type of thing just confuses the situation. You have a recommended practice and the library is just now in review. I would leave this out or if you feel it is important... add an appendix for those using pre-boost versions of the library. -------------------------- "New Msm V2.0 Features" -------------------------- "Functor rows" I personally like this format for describing a row. I hate to suggest yet one more mechanism... but having "row" utilize a "none" would be nice. Then there would be two mechanisms in the table -- 'Row' for functors and 'row' for other types. Better yet would be figuring out how to combine those into one. -------------------------- "eUML" I played with eUML some and I find myself on the fence. First off as I had related earlier, I think the ordering is not natural. I do like Rob Stewart's suggestion of: DestState() = CurrentState() + cool_event()[guard()]/(action()) I find my fence riding odd because I have always thought a DSEL like this would be the cat's meow. I think it might be the copious use of BOOST_TYPEOF is just hard on my eyes and getting used to the ordering of build_state. All of those instantiations of objects with the ().... it just looks messy to me. I love the idea and I think it is nearly there. It just 'looks' complicated when I quickly view the source. In the end I didn't have enough time to finish reviewing this portion of the library. My gut says that it might be almost ready for prime time. It might just need some more help with the sugar coating. -------------------------- "Executable size" A lot of my state machine targets have 256k flash (or less) and minimal RAM. Size is a big concern to me. I'm also unsure about these claims. Not that the claims are wrong ... but my own testing has yet to convince me that I will be able to use MSM for those targets yet. I always use -Os but I am still experimenting with the impact of size with the various front-ends and row options. eUML seems to be a non-starter for me and these platforms. -- ---------------------------------- Michael Caisse Object Modeling Designs www.objectmodelingdesigns.com

1 0

Review Request: boost.lockfree
by Tim Blechmann 14 Dec '09

14 Dec '09

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 hi all, since my first review request for boost.lockfree [1] was completely ignored, here a second version for review. the main differences are bug fixes provided by various people, trying to run boost.lockfree on different compilers/platforms. the original review request was: i would like to submit a small library of lock-free data structures for review. boost.lockfree provides implementations of lock-free data structures. lock-free data structures can be accessed by multiple threads without the necessity of blocking synchronization primitives such as guards. lock-free data structures can be used in real-time systems, where blocking algorithms may lead to high worst-case execution times, to avoid priority inversion, or to increase the scalability for multi-processor machines. boost.lockfree provides: * boost::lockfree::fifo, a lock-free fifo queue * boost::lockfree::stack, a lock-free stack updated links: the code is available from the boost vault: http://www.boostpro.com/vault/index.php?action=downloadfile&filename=boost_… and from my personal git repository: git://tim.klingt.org/boost_lockfree.git http://tim.klingt.org/git?p=boost_lockfree.git the documentation is available at: http://tim.klingt.org/boost_lockfree/ would be nice if someone could add this library to the review schedule or even would be willing to manage a review ... best, tim [1] http://article.gmane.org/gmane.comp.lib.boost.devel/192779 - -- tim(a)klingt.org http://tim.klingt.org Avoid the world, it's just a lot of dust and drag and means nothing in the end. Jack Kerouac -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (GNU/Linux) iEYEARECAAYFAksLtukACgkQdL+4qsZfVssO7wCfel+ro8wr9TXA5fCHdq3+Dv0z 47sAniqHVyaQ4m4vOwr1SyRp9liUr9Dh =FZao -----END PGP SIGNATURE-----

12 18

Performance problem with boost thread
by ellan 14 Dec '09

14 Dec '09

My code is in C++; I am using thread_group directly. The thread group call a function member of the same class. In side this function member I called another class's function member to finish the task. The task is completely "embarrassingly parallel", thus I expect it scale very well. But it didn't, the performance of my code I describe above is even worse than when I use boost thread to call a executable instead of the function member of the same class. I don't understand what's going on. Any suggestions are really appreciated!!! -- View this message in context: http://old.nabble.com/Performance-problem-with-boost-thread-tp26779904p2677… Sent from the Boost - Dev mailing list archive at Nabble.com.

1 0

Re: [boost] [MSM] Comparison with ad-hoc FSM implementation
by Christophe Henry 14 Dec '09

14 Dec '09

>One interesting feature is that there are several buttons that have >different actions associated with short and long presses. So I can >imagine per-button state machines that do something like: > > UP --pressed--> DOWN --timeout--> LONG_DOWN > <--released---- | > <---------------------released--------+ > >These could feed events like left_button_short_press, >right_button_long_release etc into a main state machine. > >Can you outline how you would implement this in MSM? I implemented it exactly as you described. >I can see how you >could store the button identifier as event state and send e.g. >short_press(left_button) to the main state machine, but this would then >need transition rules using guards to test the button id. (I don't >think this is an application for a sub state machine because each >button's machine runs concurrently, right?) To make the follwowing answer clear, I just added in the sandbox (msm/libs/msm/doc) a BoostCon09 subdirectory. You will find the diagrams (top fsm, menu and playing submachines) and an implementation using a standard front-end and for the fun, another one using eUML (tested with VC9 and g++-4.3). I didn't generalize like you suggested. Though I like your solution and it is probably going to work, I didn't want to make the example more complicated (it is already complicated enough). To solve the concurrency problems, I simply added more regions and each button is handled in one of them. It is not such a big repetition because the south button has its own handling anyway. The interesting and complex part is not so much the button handling, which could be done with an ad-hoc solution too, but the separation of tasks between the regions. One handles the hold button and stops all processing using an interrupt state, some handle the buttons, and others are simply here to give to an hardware event (like using the middle button) a different meaning according to the state where the state machine is. For example, CheckMiddleButton is doing just this. Only one state. All regions are small, and each handles a very specific part of the problem. See it as a sort of "divide and conquer" ;-) The whole point of the example was to show how, using UML techniques supported by MSM, writing a mock-up for an iPod was easier than using an ad-hoc solution. We spent 90mn purely on diagram and used a tool to generate the code instantly. And this was the second point, to show how MSM was supporting a model-based approach and that such a tool was feasible. Christophe

2 1

[svn] merge to release HOWTO?
by Eric Niebler 14 Dec '09

14 Dec '09

I clearly am doing something wrong when it comes to merging changes from trunk to release. I feel that as one of the release managers, this is something I should know. :-P Long ago, the agreed procedure was to use svnmerge.py to merge individual revisions (or revision ranges) from trunk to release, running it from the root of the release branch. I have been faithfully doing it this way. But look at the result of my most recent merge: https://svn.boost.org/trac/boost/changeset/58336 The revisions I merged had only changes to proto and xpressive, but what actually got merged includes property changes to files and directories all over the map. What's going on? Am I not doing it the right way? -- Eric Niebler BoostPro Computing http://www.boostpro.com

6 7

Re: [boost] [msm] Review
by Christophe Henry 14 Dec '09

14 Dec '09

Hi David, Hi Darryl, >It is simply great EXCEPT for lack of instructions on how to actually leverage the design decision >to separate front and back end fully, i.e., helping me to define my OWN front end or back end for MSM. >So, I must take the design claim of separability with a tiny grain of salt. I didn't dream that someone would really ask me this :) Ok then I'll document this part. The interface between front- and back-end is pretty simple. Should you need any extension of it, please let me know, I'm very interested in your idea. > Yes, yes, yes! thanks :) >The name Meta State Machine is misleading. An FSM acting on other FSMs? >Or, to add the C++ modern (and in my view quite improper...) semantics of 'meta': an FSM being executed in compile-time? Nah. Short before the 1.0, there was only one class, state_machine (now the backend). So, like a metalanguage, which is a language used to build other languages, MSM was a state_machine to build state machines. Granted, afterwards, the pun looks less funny ;-) >I agree - how about ffsm - fast finite state machine - or should that be >frightfully fast state machine :-) Sounds cool :)

1 0

Re: [boost] [msm] eUML guard/action location
by Christophe Henry 14 Dec '09

14 Dec '09

>Yes it is an interesting "hack".How "pretend" have you been able to make >this? > >I was actually thinking about exactly this today (long drive - actually >- correction - I was thinking about it yesterday - it's now early >morning here) and wondering what the consequences were. Does it result >in actually default constructing all these (temporary) objects? Won't >that be expensive and/or have undesirable side effects? This is actually what I find so cool with the typeof feature (is it too late to donate a kidney for it? ;-) ). We are calling constructors and lots of operators and it costs nothing run-time because typeof only evaluate the return value of build_stt(...). So no call actually happens. All what you have really is a typedef. The only side effect (besides compiler support) is that you need an empty constructor or would be forced to pass some dummy value.

1 0