- Boost - lists.boost.org

Two FSM libraries, one interface
by Christophe Henry 07 Dec '09

07 Dec '09

Hi David, >Anyway, I just got tired of being a grumpy old passive man, so decided to put some of my money >(or time) where my mouth is. I will write more about this side effect of my analysis in a blog post later I find it great and worth of respect that you spent time making a useful contribution to the discussion by going the extra mile (or even 2-3) to present your point. While I am by no mean a friend of the preprocessor, I find your solution interesting and encourage you to push it a bit further by supporting at least guards. If you allow a few comments: - I suggest you to give the action a name because you won't always manage to name an action actState1EventState2, for example with 2 transitions with the same source and target. - this would also remove the need for direct code writing, which could break the preprocessor - What about adding some entry/exit? I'm sure you manage to pack this one too. Otherwise I find the idea surprising but fun and think that it could gain being pushed a bit further. If you do, you could even tempt me to reuse it in an eUML front-end ;-) Christophe

2 1

[msm] internal/external conflicting transitions
by Christophe Henry 07 Dec '09

07 Dec '09

Hi Michael, Looks like you are thoroughly testing MSM and I find it great :) >The docs have a section on "Conflicting Transitions". It has >two conflicts described: > >1. an event enables multiple transitions because > multiple guards test valid, > >2. an internal and external transition are both enabled > >I see a clear definition for the behavior of #1 in the >discussion; however, it is not clear that #2 will follow >the same rule. I was maybe unclear with "internal" so let's see if we can converge. With internal, I mean internal to a composite. Suppose we have a fsm named Top containing a state State and a composite Sub. Top has a transition on Event from Sub to State. Sub has 2 states, SubState1 and SubState2 and a transition on Event from SubState2 to SubState1. If the fsm is in the state Sub::SubState2 and Event is detected, we now have a conflict between Sub->State and SubState2->SubState1. UML defines this as a conflict and orders that SubState2->SubState1 wins. It also surprised me a bit until I implemented exit points, which are in themselves a conflict (they are defined as a connection between a transition inside a composite and one outside, triggered by the same event). So, if SubState1 were an exit point, it would still work. >It was actually a little surprising to me that the order <of the transition definitions affected #2. (Well, maybe >not surprising ... but not what I wanted). I used >the SimpleTutorial to test the behavior with: > > a_row < Stopped , play , Stopped , &p::test_conflict >, > a_row < Stopped , play , Playing , &p::start_playback >, > a_row < Stopped , open_close , Open , &p::open_drawer >, > >and > > a_row < Stopped , play , Playing , &p::start_playback >, > a_row < Stopped , play , Stopped , &p::test_conflict >, > a_row < Stopped , open_close , Open , &p::open_drawer >, > > >The last transition defined "wins" in a conflict. This is were I'm unsure if I follow you. SimpleTutorial has no composite, so no internal transition so we must be talking about different things. I can, however, still answer about the order of evaluation. UML orders that conflicts be solved by guards which are mutually exclusive, so your machine is currently ill-formed (no guards) and UML says the behavior is undefined and I, as implementer, am allowed to punish you like I wish ;-) Seriously, if you have guards and they are mutually exclusive, your machine is correct and all will work as expected, no matter the order of evaluation. If you still want to know how it works, with pleasure (this is where normal users could stop reading ;-) ). First, for every event used inside a composite, MSM adds a forwarding row at the end of your table (at the end, so they have no influence on the state index calculation system). Then, for a given event, MSM iterates at compile-time through the STT, from back to front and replaces the conflicts by a new row containing all of the conflicts (this is were your compiler suffers). Thus, transitions internal to a composite are given higher priority in the evaluation. This also means that for "normal" conflicts, the last transition wins. I was already asked if I would change it. It is implementation-specific so you should not rely on it, but it is very unlikely that I will ever want to change it. I hope I brought enough elements to bring clarity. If not, please let me know. Christophe

2 1

Re: [boost] Meta State Machine (MSM) review
by Christophe Henry 07 Dec '09

07 Dec '09

Hi Robert, >I wonder if the library can provide a debugging mode that would provide a helpful default implementation >of no_transition that could help identify the unknown transition rather than requiring the user to write something? >Such a function might access internal details, perhaps only provided in the said debugging mode, >that would be clearer about the source state and event for which no transition was provided than would user-level code. Right now you only get an assert in debug mode. I also wonder if more would be possible. About the event, sure, it is already done, about the source state, I can't promise anything, but I will have a look at it. If I understand correctly, you would be satisfied with an assert or error message bringing a bit more debug information? Christophe

2 1

Interprocess regexes
by Mike Spertus 07 Dec '09

07 Dec '09

I would like to store regexes in shared memory, but it seems like Boost regex falls just barely short of supporting this. In the basic_regex documentation, it says "The definition of basic_regex... is based very closely on class basic_string and fulfils the requirements for a constant-container of charT." This may be technically correct, however basic_string and other containers take an allocator template argument, while basic_regex does not. If basic_regex had an allocator it would reap all the same benefits that other string and container types do. In particular, it would be possible to use boost::interprocess to place them in shared memory. Since the allocator would be defaulted to allocator<charT>, I think it would IMO be compatible with the vast majority of existing code (not quite all because template<class charT, class traits> void f(basic_regex<charT, traits>) wouldn't work). Does this make sense? Do others agree that it would make regexes more like other strings and containers as advertised? Thanks, Mike

7 16

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

07 Dec '09

Hi Franz, > SC 19.63630 s > Rhapsody 4.95109 s > MSM 0.90754 s Thanks for the review and for the very interesting comparison with Rhapsody, which I found impressive for several reasons: - Rhapsody is, I think, a pretty costly tool (I heard 15k€) so I expected some cool fsm framework and instead the event dispatching really is just a simple switch on states of if/else on event ids, so a pretty basic implementation (though it would be interesting to see how more complicated machines are generated). Of course, as it is made for embedded development, this is understandable. - although this is such basic C-like implementation, Msm is 5 times faster. This is fascinating, the rootState_processEvent is so simple, one can wonder how it is possible to be faster. I find this a good example of the power of metaprogramming. I love C++ :) Thanks, Christophe

17 47

[msm] choice (point) pseudo state
by Christophe Henry 07 Dec '09

07 Dec '09

Hi Michael, >I do not see the concept of a choice point. Did >I miss it? It looks like it can be modeled with >a state having only anonymous transitions and >appropriate guards. Correct, there is currently no choice point as it can be easily emulated and I'm still scratching my head about what to do with it. I'm actually unsure whether and how it should be implemented. It'd be a normal state with an incoming anonymous transition (as you mentioned) and several guards. Even the "else" is optional. So I admit I'm a bit confused if I should simply provide a typedef or if something makes it different from a state. That's the reason why it's not implemented yet. If you or anybody else sees a good use for it and why it's more than a normal state, I'd be quite thankful and could implement it. Christophe

1 0

GGL review (JTF)
by Jonathan Franklin 07 Dec '09

07 Dec '09

=== What is your evaluation of the design? === The design seems to adequately capture important geometric concepts, such as dimensionality and coordinate systems, as well as numerical precision, etc. The 4-type overload for assign (center + radius for a sphere) deviates from the semantics of the 2-/3-arg versions, which I dislike. I have not reviewed any of the extensions, so perhaps there is a good reason doing this... Other than the fact that more people will probably use center+radius than 4-d polygons. Then again, assign is parameterized by the geometry type, so this is probably just an omission. Issues w/ units continue to nag at the back of my mind. However, specifying units for specific geometries (e.g. radians), and requiring consistency of units within a given geometry seems appropriate. Any design issues that would prevent strong robustness guarantees (without drastic refactoring) in the future should be identified and fixed prior to release. I *think* we are okay here, but have not put sufficient effort to make that call (because I don't need it). === What is your evaluation of the implementation? === I didn't have time to review the implementation, other than general poking-around in the code. I was happy to note that some of the functionality already works for k-dimensional euclidean geometries, even though it is technically not supported at the moment. And by k-dimensional, I mean k=4. :-) I didn't have time to push the limits. === What is your evaluation of the documentation? === In a nutshell, the documentation is inadequate, and IMO must be completed prior to release. I'm not sure whether it is best to require a mini-review, or some other process. A few anecdotes that illustrate the problem: The example code on the main page didn't compile, which isn't a problem in and of itself. However, it took an inspection of random code in the separate Examples section, and inductive reasoning to determine that I needed some additional includes beyond ggl.hpp to make the snippets work. I suggest a direct link to a working example program anywhere example code snippets are provided. I also had a bit of difficulty getting several algorithms to work, like union/intersection. The concepts were decently documented, however, translating the concepts to working code took some leg-work. The doxygen documentation seems incomplete. I expected a tab for functions, like union_inserter, but was only able to drill down to the functions by looking at the header docs. An algorithms page seems apropos. However, I couldn't find a page listing the available algorithms. I arrived at the union_inserter page via the doxygen-generated union.hpp header page. Average and worst case performance, as well as any known/suspected numerical issues or other bugs (such as the non-minimal result returned by union_inserter) IMO *must* be listed in the docs for each algorithm. This is the trade-off for not providing a 100% robustness guarantee. Even then, the pre/post conditions for algorithms must be specified, which seemed to be lacking from the docs. A note (personal opinion) regarding Doxygen documentation: Doxygen is best suited for a reference manual. For a User's/Programmer's guide, not so much. === What is your evaluation of the potential usefulness of the library? === This is a generally useful library across *many* domains. In particular, I am excited to make use of this library at work in our graphics/visualization infrastructure code, as well as our actual GIS features. In my academic research, I plan to make use of this library in statistical machine learning/data mining algorithms. However, it is a shame that the library lacks a first-class spatial index capability in it's present state (e.g. what is up for review). Even a relatively naive reference implementation using an R-tree would be useful to me. === Did you try to use the library? === Yup. * With what compiler? g++ (Ubuntu 4.4.1-4ubuntu8) 4.4.1 * Did you have any problems? The internal headers #include <ggl/blah.hpp>, which requires a -I<BOOST_ROOT>/boost directive, in addition to the usual -I required to find the boost headers. This needs to be fixed prior to release, such that only -I<BOOST_ROOT> is required. I am assuming that this is broken for the same reason that Barends chose not to put ggl in the boost namespace. Other than having to use the 'find' command to locate the appropriate headers for inclusion, and other documentation-related issues listed elsewhere in this review, I didn't experience much difficulty using the library. === How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? === On average, a couple hours a day, over the course of a week. Admittedly, I squandered too many hours justifying my own use case on the ML, which may have been better spent reviewing the implementation, and/or writing useful test cases. === Are you knowledgeable about the problem domain? === I have been a casual user (and occasional developer) of Computational Geometry and GIS algorithms at my current job for ~ 4 years. I have also taken a few (recent) graduate-level C.G. and numerical analysis courses. === Miscellany === The existing GGL mailing list(s) should probably be moved to boost/boost-users, and/or a boost-ggl list. Unless there is a compelling reason to maintain an external list (i.e. paid support, etc) , this will best serve the GGL users/developers. === Do you think the library should be accepted as a Boost library? === Yes, contingent on meeting a minimum level of documentation, as determined by the review manager and/or community. Thanks for putting so much work into this library! Jon

5 7

[Review] GGL review starts today, November 5th
by Hartmut Kaiser 07 Dec '09

07 Dec '09

Hi all, The formal review of the Generic Geometry Library (GGL) starts today, November 5, 2009 and will finish November 15, 2009. GGL is being developed by Barend Gehrels, Bruno Lalande and Mateusz Loskot, with substantial input from this Boost mailing list. ------------------------------------------------ About the library: GGL defines concepts for geometries and implements some algorithms on such geometries. GGL is header-only, and can be applied in all software where geometry plays a small or a larger role. Users of the library can use just only one function, such as distance: int a[2] = {1,1}; int b[2] = {2,3}; double d = ggl::distance(a, b); Library users can also use the library in combination with std::vector, boost::tuple's and boost::ranges, such as: std::vector<boost::tuple<double, double, double> > line; line.push_back(boost::make_tuple(1, 2, 3)); line.push_back(boost::make_tuple(4, 5, 6)); line.push_back(boost::make_tuple(7, 8, 9)); double length = ggl::length(line); GGL can also be used in combination with custom or legacy geometries, adapting them to the library specializing traits classes or using registration macro's. Formally, GGL contains a dimension-agnostic, coordinate-system-agnostic and scalable kernel, based on concepts, meta-functions and tag-dispatching. On top of that kernel, algorithms are built: area, length, perimeter, centroid, convex hull, intersection (clipping), within (point in polygon), distance, envelope (bounding box), simplify, transform, convert, and more. The library is also designed to support high precision arithmetic numbers, such as GMP. The GGL might be used in all domains where geometry plays a role: mapping and GIS, gaming, computer graphics and widgets, robotics, astronomy... The core is designed to be as generic as possible and support those domains. However, for now the development has been mostly GIS-oriented. The GGL team proposes an extension model, very similar to what is used by GIL. The proposal as it is in the Boost Sandbox included three extensions: - SVG because it is used in the samples and to generate the documentation - WKT because it is used in the tests - The geographic coordinate system because it is used in some of the examples, also showing how other coordinate systems can be implemented There are more extensions, not included now, a.o.: - Spatial index - Map projections The proposed GGL has seen four previews, many discussions and many changes in design and implementation, based on those discussions. Previews were published on this list January '08, March'08, October'08 and February'09. GGL can be found in the sandbox https://svn.boost.org/svn/boost/sandbox/ggl/formal_review, including source code, examples, unit tests and documentation. Documentation can also be found online: http://geometrylibrary.geodan.nl/formal_review ------------------------------------------------------- Everybody on this list is invited to participate in this formal review. I hope to see your review of this library, including your vote, and I welcome your participation in the discussions on the Boost mailing list. Please always state in your review, whether you think the library should be accepted as a Boost library. Additionally, please consider giving feedback on the following general topics: - What is your evaluation of the design? - What is your evaluation of the implementation? - What is your evaluation of the documentation? - What is your evaluation of the potential usefulness of the library? - Did you try to use the library? With what compiler? Did you have any problems? - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? - Are you knowledgeable about the problem domain? Regards Hartmut Review Manager ------------------- Meet me at BoostCon http://boostcon.com

20 78

[msm] internal/external conflicting transitions
by Michael Caisse 07 Dec '09

07 Dec '09

Christophe - The docs have a section on "Conflicting Transitions". It has two conflicts described: 1. an event enables multiple transitions because multiple guards test valid, 2. an internal and external transition are both enabled I see a clear definition for the behavior of #1 in the discussion; however, it is not clear that #2 will follow the same rule. It was actually a little surprising to me that the order of the transition definitions affected #2. (Well, maybe not surprising ... but not what I wanted). I used the SimpleTutorial to test the behavior with: a_row < Stopped , play , Stopped , &p::test_conflict >, a_row < Stopped , play , Playing , &p::start_playback >, a_row < Stopped , open_close , Open , &p::open_drawer >, and a_row < Stopped , play , Playing , &p::start_playback >, a_row < Stopped , play , Stopped , &p::test_conflict >, a_row < Stopped , open_close , Open , &p::open_drawer >, The last transition defined "wins" in a conflict. I believe that there is strong historical precedent that internal transitions are always considered before external transitions. I suspect that if this is the behavior that I desire then I can order the transitions so that internals are listed last. Perhaps some additional clarification for case #2 in the docs would be helpful. Thanks - michael -- ---------------------------------- Michael Caisse Object Modeling Designs www.objectmodelingdesigns.com

1 0

[msm] choice (point) pseudo state
by Michael Caisse 07 Dec '09

07 Dec '09

Christophe - I am modifying my code generator to target MSM so that I can evaluate some larger machines and run existing test suites that I use. I do not see the concept of a choice point. Did I miss it? It looks like it can be modeled with a state having only anonymous transitions and appropriate guards. michael -- ---------------------------------- Michael Caisse Object Modeling Designs www.objectmodelingdesigns.com

1 0