- Boost - lists.boost.org

review of proposed fsm library
by Dave Gomboc 10 Mar '05

10 Mar '05

Reviewer info: ============== I have an M.Sc. in computing science. Much of my experience is with state-space search, which has certain similarities to the topic at hand. Also, lately I have been working daily with code that ought to have been written using an FSM library, but wasn't! :-( I have been following the FSM discussion on the list, and have focussed on the library for one day, reading through the docs and rationale, plus Harel's initial statechart paper. The rationale document did not convince me of the correctness of some design choices, so I did not attempt to write code with the library. Reviewer comments: ================== Let us consider that we have multiple fsms and we would like to apply operations to these fsms, e.g. direct concatenation (the terminal state of one automata becomes the start state of another), or choice (depending on an action of, or an accept/reject by fsm a, proceed to execute fsm b or fsm c). This is apparently straightforwared when working at the level of states; however, the library draws a distinction between a state_machine and a state. This acts as a barrier to the direct composition of state machines that we would like to use as components within large state machines. The distinction made between state and state_machine, which I consider to be unfortunate, was not justified in the rationale. For naturally recursive structures, distinguishing between the structure's frontier and its interior by type is best avoided. (Analogously, the head of a (singly-linked) list and the root of a tree would not be distinguished by type from their successors and children, respectively.) Composition is critical! See, for instance, section 12.4 of Keller (http://www.cs.hmc.edu/claremont/keller/webBook/ch12/) An example of multiple-machine composition into a large machine should also exist in the tutorial. The simplest useful such case would likely be connecting two half-adders to make a full-adder machine. There is a brief note in the tutorial re: submachines that fails to do this topic justice. If the template approach recommended there is to be the canonical form for a reusable component, that style should be propagated through all but the simplest examples in the tutorial. Each submachine should clearly be labelled as part of its own .hpp file. I was pleased that the tutorial and rationale collectively contain considerable discussion of exception handling. In the speed vs. scalability trade-off section of the rationale page, it is claimed that using an fsm for a parsing task is an abuse, excusing the relatively low performance of the library. However, finite-state automata are inextricably linked with the acceptance of regular languages: see, for instance, section 12.2 of Keller (again, http://www.cs.hmc.edu/claremont/keller/webBook/ch12/) it is not too much to ask that an fsm library to be able to serve as the underpinning of a reasonably efficient regex library. The lack of support for dynamically-configurable automata is also unfortunate, though not unexpected given the requirements list. Other reviewers have also already commented upon the lack of a table-lookup dispatch method. From the rationale: "To warrant fast table lookup, states and events must be represented with an integer. To keep the table as small as possible, the numbering should be continuous, e.g. if there are ten states, it's best to use the ids 0-9. To ensure continuity of ids, all states are best defined in the same header file. The same applies to events. Again, this does not scale." However, I think that for table lookup there is no requirement that ids be consecutive -- a compile-time write-once read-many hash table could do the trick. But even that may be an aside. I am unconvinced by: "To satisfy requirement 6 [to support the development of arbitrarily large and complex state machines], it should be possible that to spread a single state machine over several translation units. This however means that the dispatch table must be filled at runtime and the different trnaslation units must somehow make themselves 'known' so that their part of the state machine can be added to the table. There simply is no way to do this automatically and portably." While perhaps each state (compilation module) must know of its successor states, no central table of "current state x action x next state" encompassing the entire machine need be explicitly created. Under the "Limitations" section, reference is made to "lost events": "It is currently not possible to specially handle events that have not triggered a recation (and would thus be silently discarded). However, a facility allowing this will probably be added in the not-too-distant future." If the event is irrelevant at that point in the state machine, it is most properly ignored. If it is not irrelevant, there ought to be a transition (perhaps a self-transition). Therefore, I don't understand the comment. I have an uneasy feeling about how differently asynchronous and synchronous machines are operated, but did not consider this issue in detail. Allowing the tracking of history is intruiging; the prohibition against deep history of states with orthogonal regions is suspicious. The explanation given is that it would be more complicated (but still possible) to implement. In my experience, that sort of reasoning just doesn't fly at Boost. The discussion of fork and join bars, combined with the event dispatch to orthogonal regions discussion immediately below that, suggests that the implementation is not truly designed to handle concurrent states. I think, however, if one is to claim that UML statecharts are supported that the semantics of execution ought to be the same! I can well imagine that this "would complicate the implementation quite a bit", but Boost is also about interface, not only implementation, and if the wrong interface is standardized (whether de jure or de facto) it's worse for everybody in the end. There is no explicit discussion of non-deterministic fsms. Of course, every such fsm can be re-expressed deterministically. Similarly, a given fsm may be non-minimal, but such minimization procedures exist. Both of these procedures necessarily require a global view of the fsm. As this is contrary to the scalability requirement listed in the rationale, I conclude that neither are present. :-) However, I would like to ask if (excepting possible compiler limitations) is there anything about the library that precludes extending it such that NDFAs could be specified in code, and converted into the minimized DFA during compilation? (http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE207.HTM# SECTION03177000000000000000 gives a toy example of FSM minimization). We had tuple and mpl separately before fusion; it seems reasonable for boost to have both compile- and run-time fsm libraries, if ultimately they may be similarly fused. Reviewer conclusion: ==================== I like this library, but I'm not satisfied with it. What level of library is good enough for boost? The library is not ready for standardization, however, this doesn't appear to be the standard that most people use when deciding upon their vote. This library is certainly good enough for people to make successful use of. Ultimately, I think there are issues of design and rationale that must be sorted through, appropriate modifications made, followed by re-review. Less weighty issues: ==================== struct Greeting; struct Machine: fsm::state_machine<Machine, Greeting> {}; (and all similar) should be changed to struct Machine: fsm::state_machine<Machine, struct Greeting> {}; If necessary, the old way can be metioned as a workaround for older compilers in a footnote. The "default" black disc in the diagrams is too large! Maybe make the radius about 2/3s of what it is now. Change "Such transitions are currently flagged" to "Transitions across orthogonal regions are currently flagged". It's the first sentence in the last paragraph of the rationale.

4 4

Hash review: hash_float_test broken?
by John Maddock 10 Mar '05

10 Mar '05

Sorry if this has come up before, but all the compilers I tested with refuced to compile hash_float_test: hash_float_test.cpp ..\..\..\..\libs\functional\hash\test\hash_float_test.cpp(99) : error C2501: 'BOOST_META_FUNC_TEST_CASE' : missing storage-class or type specifiers ..\..\..\..\libs\functional\hash\test\hash_float_test.cpp(99) : error C2440: 'initializing' : cannot convert from 'void (__cdecl *)(T1 *)' to 'int' Context does not allow for disambiguation of overloaded function ..\..\..\..\libs\functional\hash\test\hash_float_test.cpp(105) : error C2275: 'float_types' : illegal use of this type as an expression ..\..\..\..\libs\functional\hash\test\hash_float_test.cpp(104) : see declaration of 'float_types' ..\..\..\..\libs\functional\hash\test\hash_float_test.cpp(105) : error C3861: 'BOOST_FUNC_TEMPLATE_TEST_CASE': identifier not found, even with argument-dependent lookup "cl" /Zm800 -nologo /EHsc -c /Z7 /Od /Ob0 /EHsc /GR /MDd /Op /Zc:forScope Zc:wchar_t -I"..\..\..\..\bin\boost\libs\functional\hash\test" -I"C:\Program Files\Microsoft Visual Studio .NET 003\VC7\include" -I"c:\data\boost\develop\boost" -Fo"..\..\..\..\bin\boost\libs\functional\hash\test\hash_float_test.test\vc-7_1\debug\threading-multi\hash_float_test.obj" -Tp"..\..\..\..\libs\functional\hash\test\hash_float_test.cpp" Thanks, John.

3 3

RE: [boost] [optional]output
by Martin Bonner 10 Mar '05

10 Mar '05

----Original Message---- From: Gennadiy Rozental [mailto:gennadiy.rozental@thomson.com] Sent: 07 March 2005 07:18 To: boost(a)lists.boost.org Subject: [boost] [optional]output > Hi, > > Maybe it's something that I missed, but why optional doesn't define > output operator something like this: > > template<typename T> > inline std::ostream& > operator<<( std::ostream& ostr, optional<T> const& v ) > { > if( v ) > ostr << *v; > return ostr; > } I don't think optional should define an output operator at all. There are too many possibly useful definitions. For example: template<typename T> inline std::ostream& operator<<( std::ostream& ostr, optional<T> const& v ) { if( v ) { ostr << true << ' ' << *v; } else { ostr << false; } return ostr; } -- Martin Bonner Martin.Bonner(a)Pitechnology.com Pi Technology, Milton Hall, Ely Road, Milton, Cambridge, CB4 6WZ, ENGLAND Tel: +44 (0)1223 441434

8 22

boost/python: how to: call memberfunctions of an existing c++ object from python?
by Marco Borm 10 Mar '05

10 Mar '05

Hi Boost/Python developers, at first I have to say that I am no boost nor a python expert. I've searched for hours now on the web for my problem but was unable to find some solution for my problem: Currently I am working on the possibility that an python-script is called by an existing c++ object. This was "easy" to do with and without the boost python-classes. To make this more complicate, the script must be able to call some member functions of this object. So to make this possible I created an BOOST_PYTHON_MODULE() containing the class and the to be called member function-definitions. Now it is possible to create new instances of the class and call them from python. It is also possible to do the following in my c++ object-code: "ret = boost::python::call<int>(PyFunction.ptr(), this );" But now my problem: boost copies the object and passes only that copy to the function. Is it and how is it possible to make the object accessible to the function within the python-script? I have found some hints in the boost-source for using smartptr but I was unable to use them as an parameter for call(): "TypeError: No to_python (by-value) converter found for C++ type: class boost::shared_ptr<TYPE>". I am also don't known if this is the right way to do. Thanks for help! Marco Borm

2 3

Re: [boost] [review] hash functions
by brangdon＠cix.compulink.co.uk 10 Mar '05

10 Mar '05

In-Reply-To: <00cd01c524e3$bf3cb4d0$6501a8c0@pdimov2> pdimov(a)mmltd.net (Peter Dimov) wrote (abridged): > A pure function would entice you to define hash_value for (x, y) > as hash_combine(x, y). And that would be bad because...? template <typename T1, typename T2> size_t hash_value( const std::pair<T1,T2> &pair ) { return hash_combine( hash_value(pair.first), hash_value(pair.second) ); } looks good to me. 1 line of code instead of 4, no spurious variable, no side effects, half as many calls to hash_combine(), easier to exploit instruction-level parallelism. > We can fix this by initializing the seed in hash_range with something > other than zero. It isn't a problem for strings, where \0 is rare, but > may be a problem for arbitrary sequences. That would help. How about fixing it in hash_combine instead? At the moment hash_combine(0,0) == 0. If you fix it in hash_range, you also need to fix it in every other place a seed is used, eg for pairs. -- Dave Harris, Nottingham, UK

3 2

indirecter_unary, indirecter_binary
by Matthias Kaeppler 10 Mar '05

10 Mar '05

Hello, because of the lack of a generic adaptor which indirects operations on pointers to the pointees, i.e. sorting a collection of pointers with predicates applying to the pointees, I have come up with two classes, indirecter_unary and indirecter_binary which do exactly that (thanks again to the people from boost users and comp.lang.c++ for assisting me). Both adaptors accept adaptable function objects as well as plain functions. Ex.: inline int plus( int a, int b ) { return a + b; } // ... std::vector<int> vec; // ... std::sort(vec.begin(),vec.end(),indirect_binary(std::less<int>())); // ... std::transform(vec.begin(),vec.end(),vec.begin(),std::ostream_iterator<int>(std::cout,"\n"),indirect_binary(plus)); I have attached the source file. Your feedback would be greatly appreciated. -- Matthias Kaeppler

8 31

Re: [boost] [shmem] Uploaded to Vault+documentation questions...
by ION_G_M 10 Mar '05

10 Mar '05

Hi James, I missed your message in the big diggest! QuickBook seems to offer all that I need, so I will definitely look at it. >I've attached a larger sample based on your "Quick Guide" (which might >be out of date...). Take a look, and if your interested check out the >Boost Documentation list at >https://lists.sourceforge.net/lists/listinfo/boost-docs. There's quite >a bit happening with QuickBook. Ok, thank you for all. Regards, Ion

1 0

Visual Studio 2005 IDE: Improving Class View(() instead of (void)) [Repost]
by Pavel Chikulaev 10 Mar '05

10 Mar '05

Visual Studio 2005 Beta2 CTP December 2004 still uses (void) as empty parameter list in Class View, Add Member Wizard and other IDE windows. I am asking you: Is there any official paper that shows that syntax (void) deprecated? It's possible to retire current (void) syntax in VS's IDE in case of showing Microsoft Visual Studio developers some official paper that shows it. I am posting it here because I believe there are some of us who also dislike it VS and knows/reads some C++ official papers. P.S. As for me, It is really annoying.

2 2

RE: [boost] Logo Contest
by Mark Blewett 10 Mar '05

10 Mar '05

At 22:38 09/03/2005, you wrote: I really want to respond to a comment at the end of Reid's post.. but there are a few interesting comments on the way... so I've added my thoughts "Spot on. I'd further add that most of the best commercial logos are pretty simple--not all, but it's a lot harder to make a complex one appealing." I agree, and add a further comment. Yes there have been some well drawn/rendered logos, however many seem (IMHO to me) like taking a average idea, but adding as many effects to make it look good. What I think (and hope) we should be looking at is the concept, not the frills. "Without singling any of the entries out, I think that most of the currently-posted entries are too complex. As a side note, and not a very relevant one (maybe), it's pretty clear the list is populated by a mostly left-brained crowd; look at how many of the entries depend on word play, acrostics, and the like. " Again I agree.. there are a few graphical people here, but most are "left-brained crowd".. but what's Boosts target audience? It's actually a serious question.. first line would be developers.. so a "left-brained crowd" logo would be ok, second line are companies.. which probably don't look at the logo, more the legal use of boost. What I'm trying to say is most logo's are for the general population.. in the case of boost (unfortunately) we don't have world domination.. so we should be producing a logo for the selected target audience. "Not saying that's bad, but again, the logos people tend to remember are more likely to be graphic than semiotic. Yeah, I guess that one deserves a smiley, on the grounds of self-referential irony. So here: <g>. Now, if there were just a way to make emoticons tail-recursive...come to think of it, I'm surprised no one used recursion as a means of indicating "boostness." If it weren't too late, I'd maybe have a go at that. Although most of my ideas were based around shapes, color use, and shading." I agree with "graphic than semiotic" for the general population.. does it apply to potential Boost users? I'm not so sure... but believe its probably true. "Incidentally, I'm also surprised no one has tried to define a coherent color scheme, especially given that there *are* graphic designers present. Is it just that everyone unconsciously accepted the existing "cool" scheme? Only a couple of the entries even try to do much with color, and I can't find any consistency in the usage (possibly my fault; it's just a hobby with me). Okay, <\kibitz>" I started writing an email awhile back (which I didn't posted), commenting on various designs.. however writing it I felt as it I was actually questioning the process rather than the produced logos (I'm not knocking the designers or anyone else.. just questioning) Why I'm responding to your email is a similar thought... Before we have a boost logo, do we need to define the boost "colours", the boost "font".. the foundations of a "corporate" logo? Or another example, capitalization.. should should Boost be "boost", "Boost" or "BOOST".. my thought is "Boost" in documentation, and "boost" (because coding standards apply) in code. Buts what about in a logo? Going back to colours.. I'm not sure what you mean about the "existing cool scheme".. I presume variants of blue.. there's are good reasons... 1) (unfortunately) most of us are male (and our target audience).. and we have a preference for the colour. 2) Industry Conventions.. I posted a link awhile back (http://lists.boost.org/MailArchives/boost/msg75724.php) which gives another reason; <quote> I'm no expert either but http://graphicdesign.about.com/od/logotips/a/8logoelements_2.htm has a interesting point about colour which I haven't seen mentioned here; Works Within Industry Conventions Often there are consistencies among logos in certain industries, and following these conventions can help customers more easily identify what you do or what you sell. This doesn't mean you should sacrifice originality, but it does mean you (or the firm creating your logo design) should be aware of patterns among logos in your industry and somehow incorporate these consistencies into your design. For example, did you realize that the main color for the logos for Microsoft, IBM, Dell, Hewlett Packard and Intel is blue? The color blue is associated with stability and progress and has long been a standard color among high-tech companies. So if you were a technology company, you would probably want to incorporate blue into your logo design to take advantage of these positive built-in associations. </quote> I guess choosing a logo is very personal and emotive (compared to accepting, or not, a new library).. but personally I trust the judgement of the people here and the process.. discussion is the key I feel. Regards Mark

4 4

RE: [boost] Logo Contest
by Mark Blewett 10 Mar '05

10 Mar '05

At 01:57 10/03/2005, you wrote: Firstly there are a lot of things I agree with you in your previous post... and was responding to it because it was (I feel) it is good starting point (because it summarized a lot of my concerns) to make the comments to the list as a whole that I felt needed making, not against your own post... perhaps I should of been clearer about that. Unfortunately with a brief scan of your response.. your interpretation of my post maybe different, I guess I have a lot to learn about posting "correctly" here. >My personal take is that it says "safety" to an industry that's anything but >predictable. Which isn't to denigrate it. I like blue. Got blue color >schemes on all my machines (or teal, which is close). It just seemed that >no one had given it any thought, That's what I'm trying to say.. (ok doing it badly)... about getting the basics (things like colour / font / capitalization) sorted.. however perhaps these will come out in post selection changes. >and I was trying to, well, *goose* people a >bit, maybe get someone to try something else. If you noticed it as it >breezed past and sank, my one early attempt was blue, and I thought at that >time (seem to recall some posts that made me think that) we were supposed to >keep the old color, to minimize collateral changes to color in the page >content. I guess most of use like stability.. which is strange given the innovative libraries in boost. >As for "targeting the audience," I harbor a deep suspicion that just because >coders work with text doesn't mean they'll necessarily *respond* positively >to it. Sadly, I have a wee bit of experience to tell me that (don't ask, >don't tell <g>). For one thing, yeah, we're working in a text medium, but I >don't really think the bulk of us are really all that language-oriented. That's actually a very good observation! I'd been thinking of the day to day textual side.. not thinking of what goes on inside the mind. >I'd wager that better than 95% of the people who track this list are male >(which I do *not* say to belittle women, or even to suggest that the logo >should just target males--I'm just talking numbers), Unfortunately its the world we live in :o( >which dictates a pretty >strong statistical leaning towards problem-solving techniques based on some >form of physical visualization. (About to commit the sin of generalizing >from a single particular, but...) I'm about as language-oriented as it goes, >with an advanced degree in writing and Lit, but when I code, I *picture* >things. Abstract patterns of colored blocks, actually. It's subtle, but >there. Now, after all that disquisition, I'll observe that a text logo can >work. Good ones are pretty hard to do, but you can think of some if you >try. However, apart from IBM, can you really think of many others? Look >closely at HP's logo, or Motorola's, any of that ilk, and you'll see there's >a graphic component even to them. Hell, there's one to IBM's. Check out >what their trademark actually is. Block serif lettering in a particular >shade of blue, broken by horizontal drop-outs. Hmmmn. I'm looking at the >Dell logo on my monitor; not sure what it means to do. Looks like it's got >"lazy E syndrome." <g> It may be that a large percentage of the submissions >are text-based simply because that's the first idea anyone will have, on >average. I think you are right about the submissions, and right that perhaps (if I understand you correctly) an abstract logo is a better way to go. >I would say that, yes you *do* need to be thinking about all those >foundations, if you expect to get it trademarked, because anything not >explicitly specified in the description will *not* be considered part of the >trademark. You also have to be careful not to over-constrain the >definition, or you can arrive at situations where you can't claim copyright >protection for certain usages. For instance, a logo I once did (still think >it's my best) for a rock band was largely defined by a geometric pattern >that surrounded and dominated the opening capital of the band's name. There >was also a backdrop done in a flame scheme by airbrush, and I'd designed a >custom font for the name that echoed patterns in the geometric figure. The >description finally filed mentioned only the figure and the name. Including >the font would have forced the band to always use only that font. Likewise >the backdrop; that logo had to appear on a number of things, and lots of >them wouldn't have been conducive to having a lot of deep saturated reds, >oranges, and yellows on them. I'm speaking of US trademark law, of course. >I don't know the conventions in other countries. But yeah, I do think of >this process as "establishing a brand," in the full commercial sense. That's one of the thinks I was questioning in my head.. what's a logo.. why is a new one needed.. what I personally came back to each time was actually we are trying to establish a brand.. and that the logo is just part of it. Maybe my interpretation as a causal observer is wrong. >Were >I at liberty to drop names, I could tell you a tale of a company that >neglected to trademark a very important part of what had come to be a >long-established and well-known brand, and their main competitor simply >appropriated it for their own advertising, undoubtedly luring customers who >associated that very key thing with the wrong company. But I ain't. And I >ain'ta gonna. <g> Okay, Boost isn't a "company" in the traditional sense. >But it's got to work with laws designed for corporate protection, and that >means really working with them. That's an interesting comment, one which I'd never of thought of... has anyone? >Yeah, it's personal. Since Boost isn't a company I "own" or do branding for >though, I'm not emotional about it. If it's seemed that way, I apologize >for the impression I managed to import into my messages. Sorry what I meant was the choice of logo is personal and emotive to everyone here.. everyone has their own reasons, its not (as) logical like voting for a library submission. >And yep, >discussion is the key. Which is what we're doing, I thought. <g> Yeah.. and you have made me think of a few areas, problems, and ideas which I hadn't even considered before. Thanks! Regards Mark

1 0