- Boost - lists.boost.org

Re: What I Hate About How We Abstract System Dependence
by Don G 12 Mar '05

12 Mar '05

I agree completely. It's nice to have a common/portable framework, but it is unrealistic to assume that the framework will be sufficient for all use cases. This is true going both directions though. I'll pick on files because they are easy<g>. There are FILE*, iostreams, int fd, etc.. There is a bidirectional relationship between FILE* and int (via fileno/fdopen), but no connection between those int's and whatever native type is used (ex: HANDLE in Windows). Visual C++ has undocumented methods to create a suitable int from a HANDLE, which allows one to pass any native flags or what-not when opening the HANDLE and still use the rest of the standard library. To be truly useful, a portability library must provide some means to connect to the native system and do so bidirectionally where possible. In my own code, I provide get_native() methods to get the native artifact and document the semantics as non-portable. I also provide a way to create classes given already created native "objects" (where appropriate). This kind of support differentiates libraries that have aesthetic appeal from those that work in the real world (IMHO). <digress>This has been a bone of contention I have with the C/C++ standard bodies. Given the computing environment today, there should at least be a Windows and *nix annex that describe non-portable, but yet standard bindings, much like CORBA does with languages. Any other environments that wanted to define their own annex should also do so. But, I've been around long enough to know the chances of this actually happening.. :( </digress> Don --- David Abrahams <dave(a)boost-consulting.com> wrote: > You have to understand, the Boost.Threads specification was > designed to become a standard, and as such it didn't include > anything nonportable. That said, there's no reason we shouldn't > expose the low-level thread IDs and document them in a special > section on platform specifics. __________________________________ Do you Yahoo!? Make Yahoo! your home page http://www.yahoo.com/r/hs

1 0

msvc + dinkumware?
by Bronek Kozicki 12 Mar '05

12 Mar '05

I need to build boost (more precisely Boost.Regex) on MSVC6 with Dinkumware (ie. resulting dynamic libraries should link directly with Dinkumware C++ runtime). Any ideas how to do it? TIA B.

5 11

[multi_array][RFC]fixed (or compile-time) ExtentList
by Larry Evans 12 Mar '05

12 Mar '05

In view of recent posts: http://article.gmane.org/gmane.comp.lib.boost.devel/119358 http://article.gmane.org/gmane.comp.lib.boost.devel/119684 suggesting an interest in fixed size matrices (I guess in order to speed execution) would it be desirable to have a variation of multi_array where ExtentList was one of the template arguments instead of an argument to the CTOR, as described here: http://www.boost.org/libs/multi_array/doc/reference.html#multi_array ? Of course the ExtentList would just contain compile time constants, something like mpl::vector_c<mpl::pair<index,index>,....> where: typedef multi_array_types::index index; and the args to pair<index,index> would correspond to the args to extent_range::extent_range(index start, index finish) where, of course, extent_range is the current multi_array class.

1 0

Updating Boost web site
by Misha Bergal 12 Mar '05

12 Mar '05

What is the process for updating the content of main Boost web site? -- Misha Bergal MetaCommunications Engineering

3 4

FSM Review
by Iain K. Hanson 12 Mar '05

12 Mar '05

I have a serrious problems with this library. FSM is a design pattern and they can be spellt in a wide variety of ways. E.g state transition tables Deterministic Finite Automata, Coloured Petri Nets, and Harrel / UML state charts. There are equallly, many ways of implementing FSMs. Calling this library the FSM libray would be like submitting multimap and calling it the collections library. * What is your evaluation of the documentation? How easy (or hard) it is to understand library features? What can be improved? On the whole, the documentation looks fairly good. Some nits are that the exampls use upper case class names and can be confusing when the same name is used for a template parameter. The performance charcteristics should have been formally documented before it came forward for review. * What is your evaluation of the design? What features are supported better by alternative FSMs? What could be added (or removed) from the library? This is where I have a problem. I don't have any problem with specifying an FSM using UML notation and certainly there plenty of users that will like this. But any state chart can be collapsed into a state table and there is no good reason that event dispatch performance has to suffer. The documentation suggests that Visitor patter / double dispatch is used. and it looks like ( from the code ) that states are iterated over from outer most to inner most searching for a state willing to consume the event. The performance of event dispatch will decay linnerly with the depth of the states. I can see not good reason why event dispatch could not be achieved with constant time. The reason it is like this is that the author has used state chart concepts for the design. The state_machine class has a total of 5 conatiners ( two std::list and three std::map ) two of the maps are for history and are present even if you don't specify history. This library does not follow the C++ convention of you only pay for what you use. The author has already admitted in discussion on the list that FSMs that generate events at high speed would not be appropiate for this library. Because of the libraries design a seperate async version was needed that requires mutexs. There are many situations where I would prefer to use a re-enterent disign using flyweight singleton states. TTThis tradeoff is not possible with the current design. Because of the above I vote against inclusion of this library into boost. * Are you knowledgeable about the problem domain? I have been building FSMs for the last 20 years as they are the one of the most common patterns I use. I have build them in assembler, C, C++, and Java and none of them have ever required the space and time overhead of this library If this library is accepted into boost I will continue building my FSM by hand, use Alexsey's FSM, or SMC or even boost function. 3. Exception handling support: Several people have rightly pointed out that the rationale for the exception handling support is too thin. The problems here stem from the design. 4. On some compilers (e.g. gcc), the asynchronous part of the library and most of the tests currently cannot be compiled with RTTI turned off. It is an unnecessary overhead that is an artifact of the design. * Are there performance bottlenecks? Does the library design fit requirements of real-time systems? How is it useable for embedded systems? Is the documentation clear on performance tradeoffs? I've discussed these above. I don't believe real-time system designers would consider using this library. It is to heavey weight in both space and time, they have to jump through extra hoops such as writting a custom alloactor and custom class operator new/delete to overcome the libraries use of heap allocation. And they definately won't like non constant time event dispatch. /ikh

10 42

[type_traits] fully qualified names
by Jody Hagins 12 Mar '05

12 Mar '05

The coding guidelines document (boost/more/int_const_guidelines.htm), states the following... Always use a fully qualified name to refer to an integral constant expression. For example: typedef myclass< ::boost::is_integral<some_type>::value> mytypedef; Rationale: at least one compiler (Borland's), doesn't recognise the name of a constant as an integral constant expression unless the name is fully qualified (which is to say it starts with ::). However, it appears that the same compiler (BCB6) has problems if the '::' is left in. For example... template <class T> struct Foo { typedef typename ::boost::remove_reference< T >::type type; typedef typename ::boost::add_reference< typename ::boost::add_const< type >::type >::type ref_to_const_type; }; fails to compile. Initially I thought it had something to do with typename (e.g., another BOOST_DEDUCED_TYPENAME) because, the first, simpler line compiles if I remove the "typename" keyword. Unfortunately, the following does not compile either template <class T> struct Foo { typedef ::boost::remove_reference< T >::type type; typedef ::boost::add_reference< ::boost::add_const< type >::type >::type ref_to_const_type; }; After seeing a notice on this list a few minutes ago, I decided to remove the '::' and whaddya know... template <class T> struct Foo { typedef typename boost::remove_reference< T >::type type; typedef typename boost::add_reference< typename boost::add_const< type >::type >::type ref_to_const_type; }; this compiles correctly. So, I am left scratching my head, wondering what to do if I want to use TypeTraits in a portbale manner. Thanks!

5 9

Re: [boost] Re: [review] hash functions
by JOAQUIN LOPEZ MU?Z 12 Mar '05

12 Mar '05

----- Mensaje original ----- De: Alberto Barbati <abarbati(a)iaanus.com> Fecha: Viernes, Marzo 11, 2005 9:01 pm Asunto: [boost] Re: [review] hash functions > Hi, > > I have a doubt about the proposed implementation of hash_value() > for > pointers, which is: > > template <class T> inline std::size_t hash_value(T* v) > { > return static_cast<std::size_t>(v - (T*)0); > } > > this code calls for undefined behaviour according to §5.7/6, each > time v > is a non-null pointer. > > IMHO, the only reasonable way to map generic pointer values to > integer > values is through reinterpret_cast<>. The mapping would be > implementation-defined, but it would be no worse than the intent > of the > proposed implementation (if it worked). Agreed. > > To be picky, in order to accomodate with implementations that may > have > sizeof(size_t) < sizeof(T*), we should use two casts: > > template <class T> inline std::size_t hash_value(T* v) > { > return static_cast<std::size_t>( > reinterpret_cast<boost::uintmax_t>(v)); > } > > (the right thing would be to use a C9X-ish uintptr_t type, but > boost/cstdint.hpp does not provide such a type). > > However, as the double cast may result in suboptimal code if > size_t is > large enough, a boost::enable_if trick might be used to provide an > optimized version with just a single use of reinterpret_cast. The > result > would be something similar to: [...] Please, no SFINAE! This would break not-so-conforming compilers. Let's stick to compilerwise macro-based branches. After all, for the vast majority of platforms (AFAIK) sizeof(size_t)==sizeof(T*) > > Unfortunately, there's one more thing... even if p == q, > reinterpret_cast<uintmax_t>(p) is not guaranteed to be equal to > reinterpret_cast<uintmax_t>(q) on implementations that have > multiple > internal representations for the same address. I don't think much > can be > done (in a portable way) for such platforms. > Another reason for resorting to macro-based alternatives, and not to SFINAE. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

2 1

Re: review of proposed fsm library
by Dave Gomboc 12 Mar '05

12 Mar '05

> > 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. > > A much better way to achieve that is with templated states, > as you seem to > have observed yourself. > > > The distinction made between state and state_machine, which I > > consider to be unfortunate, was not justified in the rationale. > > I didn't justify it because it feels natural to me that a > state machine has > only one event queue, and one place where history is stored (both are > containers inside state_machine). Admittedly, because the > outermost state > knows at compile time that it is the outermost state, the > state_machine class > template could be "abstracted away". You'd then only have > simple_state and > state. However, this seems at best obscure to me. 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? 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. > [snip] > > 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. > > While I might agree with your reasoning in theory, I don't > think that it would > work in practice. Even now I sometimes get complaints that > the examples are > too complex (too many templates) and changing all examples to > work with > templated states would make them even more so. Plus, often > there is no need to > use a state in more than one place, so why bother with > templated states then? 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). It is not presumptuous for a coder to assume that their machine will never be needed in another context? If templating improves reusability considerably, while not costing much, then it should be done. However, if there are other obstacles to component reuse, rather than say it's not worth it to template these, instead say these other obstacles must be cleared. One cannot build a library of fsm components that may be connected together to build more complex fsms without this, but I continue to think that this would be very useful. > [snip] > > 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 > > In its generality this remark is of course false and I should > have replaced it > with better reasoning long ago. What I want to say here is > that it is a bad > idea to use this library for parsing, as it is so general > that performance > tradeoffs are inevitable. For parsing, one is much better off > with a parser > framework, which is optimized for the task. The IMO important > observation is > the following: Parsers like Spirit only need to return when > they have finished > processing all "events" (characters). > > An FSM however must > return after > processing each event. Parsers can exploit this fact and > store state with > recursive calls, which is of course much faster (some stuff > can even be > inlined) than any super-clever double-dispatch scheme. > There is often a hard limit for stack space which - I think - > is the reason > why FSMs do make sense in parsers nevertheless. However, all > the FSM-employing > parsers I know are of the dynamic variant (e.g. regex) and > these FSMs are not > directly designed by humans but computed by an algorithm. For reading a identifier character-by-character, sure, one would not want to use an fsm to process each character individually. However, one can design the fsm to proceed to read an entire identifier at once. In situations where a parser might require extensive backtracking (and Spirit-1 doesn't actually backtrack after accepted symbols, which is something I could employ an fsm to work around!) the use of an non-deterministic FA may be well-justified. Also, if one is merely testing for the presence of a regular expression match, I agree that just signalling once when the match is complete is sufficient, however, often one wants substrings within a match that correspond to certain portions of the match, in which case actions at transition points may be a fine solution to the problem, both reasonably efficient and easily understood by the developer. Furthermore, the possibilities for error comprehension and recovery in a parsing process may be improved by the use of an fsm framework. It is certainly true that I have use for dynamically-arranged fsms -- and not only for parsing. It was a disappointment for me that I would not be able to do some tasks with this library. > Last but not least I > think it would be tedious for a human to implement a parser > on the state- > level, which is probably the reason why I dared to make the > admittedly dumb > remark in the first place. > I think Darryl puts this rather nicely: > <quote> > Fast flat fsms to process simple events and having little > additional context > are best implemented using other methods. However such > implementations are not > difficult, and there are plenty of domain specific tools > already (eg various > language recognisers). > </quote> This comment does not address myriad uses that I would have for an fsm library that met my needs. Don't forget that with the addition of storage, it's actaully fully Turing-complete, "fsm" notwithstanding. > > 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. > > See above. A regex library needs a dynamic FSM. Indeed, I had been hoping that the fsm library would accommodate such needs. I do, however, understand that one can't implement everything at once! > [snip] > > 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. > > Unless you use a perfect hashing algorithm (which is > infeasible because you > need to know all the ids beforehand), this would essentially > wreck the ability > to use this library in real-time systems. Hashed containers > are a bad idea for > real-time as there is no upper limit for a search operation. However, one would know the maximum dispatch time guarantee by the end of the compilation process, and it likely would be less time-consuming (where sufficient memory exists) than the linear search currently employed. > > 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. > > Which is exactly what this library is doing. There is a > lookup "table" within > each state and if that fails lookup considers the states > outer state. However, > this inevitably means that you cannot have constant time > lookup. The larger > your FSM becomes the longer lookup takes. BTW, as I've > written in another post > I don't see why reaction search is so important for people, > because in typical > FSMs I'd expect transition execution to be much more of a > performance hog. Perhaps it is because people would like the freedom to employ fsm in contexts that you did not target your solution for. As I'm sure you know, an fsm can be a very handy thing! > > 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. > > There are applications of state-machines where an ignored > event consitutes an > error. Since the library currently does not allow to define > transitions that > are triggered by any event there is no easy way to handle > such "ignored" > events. In that case, it seems quite reasonable to add one as you planned. > > I have an uneasy feeling about how differently asynchronous and > > synchronous machines are operated, but did not consider this issue > > in detail. > > Why? They are rather different things aren't they? 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). > > Allowing the tracking of history is intruiging; the prohibition > > against deep history of states with orthogonal regions is > > suspicious. > > Why? Why not? > > The explanation given is that it would be more > > complicated (but still possible) to implement. > > It would be much more complicated to be precise. > > > In my experience, > > that sort of reasoning just doesn't fly at Boost. > > Why? Must I really offer all the functionality in the first > version of the > library? Very few people use deep history and orthogonal states in > conjunction. For those that do I describe a work-around. I > have not received a > single request to implement full deep history. Well, you've received at least one, but your response was 'why?'. ;-) > > 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. > > Why? Otherwise, these items would be addressed, that's why. But see below. > > 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. > > 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. :-) > > There is no explicit discussion of non-deterministic fsms. Of > > course, every such fsm can be re-expressed deterministically. > > I don't see why I should discuss that. Because people may want the ability to use epsilon-transitions, which NFAs support and make finite automata modelling considerably simpler in many cases. > > 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. > > This has never been a goal and I don't see why I should provide such > functionality. Also I suspect that state-local storage could > prevent such a > minimization. > > > 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? > > Yes, the scalability requirements. As I explain above (and > you seem to have > found that yourself) there is no way to have a global view at an FSM > implemented with this library. I am not suggesting that you provide this functionality yourself. What I am asking is that if another needs this functionality can they add code to your library to do it without too much trouble, or are there implementation considerations that make it impossible? It should be clear that if one intends to perform a NFA->DFA or DFA minimization that it is recognized that they are forfeiting scalability by requiring whole-machine view. > > 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. > > I don't think that is feasible unless you limit yourself to > FSMs specified in > single TUs so that a global view is possible. Hmm. :-/ > > 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. > > > The "default" black disc in the diagrams is too large! Maybe make > > the radius about 2/3s of what it is now. > > I think the size is in line with the current UML standard, > but I'll check again. Sorry, I didn't realize that UML had picked a standard size. In Harel's paper, the default black discs were even smaller than what I had suggested. Dave

2 1

Re: Re: Re: FSM Review
by Dave Gomboc 11 Mar '05

11 Mar '05

> However, since each innermost state must know all its outer > states (1), > it is theoretically possible to collapse all the reactions of these > states into a STT that is local for each innermost state. At a rather > hefty price, this would give you constant-time lookup, > *separately* for > each innermost state. In FSMs with orthogonal regions multiple such > innermost states can be active at the same time, which makes lookup > linear again. Hence my previous remark to Dave. 1. And a state-superset transition table is not possible for compiler capability reasons? 2. You know, the NFA -> DFA conversion process is _exactly_ the process that one would use to take the state-supersets and flatten them out. Win: constant-time dispatch. Lose: scalability. Dave

2 1

[optional] new assignmet semantic and references
by Fernando Cacciola 11 Mar '05

11 Mar '05

Hello people, A few days ago, a problem with Boot.Optional's assignment not properly handling aliasing scenarios (like self assignment) was pointed out. We concluded that the solution was to use T's operator=() directly instead of the Destroy+Construct pattern that I was using. I changed the code, tested it, and I was updating the documentation when I recalled the following long-standing issue: Currently, with the Destroy+Construct pattern, references are re-bound in case of assignment: int a = 123 ; int b = 456 ; int& ra = a ; int& rb = rb ; optional<int&> ora(ra); optional<int&> orb(rb); ora = orb ; // now 'ora' contains a reference to 'b' instead of 'a' b = 789 ; cout << *ora ; Prints 789 cout << a ; Prints 123 This is not the way assignment of reference types work in C++: ra = rb ; // The value of 'a' referenced by 'ra' is changed, not the reference itself. cout << a ; Prints 789 This error in the way optional<T&> treated assignment of reference types was pointed out by Joel de Guzman long ago when he started using Optional in Spirit. However, at the time, Joel explicitely asked me not to change this and keep the current rebinding semantics in order to minimize any impact in Spitit itself (which certainly has, o had, a much larger user base). If I change the code now to use T's operator=(), assignment of optional<T&> will have a _radically_ different semantics. A correct one, that's for sure, but end user code might be fundamentally impacted. Note: if you look at Optional documentation you will discover that assignment is only documented for T not being of reference type. This was intentional.. I left this undocumented becasue I knew back then that the current semantics were wrong but I couldn't fix it at the time because Spirit was (or could be) depending on it; yet I didn't want other users to depend on it as well... Of course, users could have "discovered" the (incorrect) semantics themselves and now rely on it, but I hope that the intentionally missing documentation served to keep the amount of users depending on this incorrect semantics very low. [At least it served _me_ to remember about this since I had forgotten] I really want to 'fix' this, i.e, give it correct semantics, so unless Joel or anyone else speaks now I'll move on, finish the documentation updates and commit the new version. Best, Fernando Cacciola

6 26