March 2005 - Boost - lists.boost.org

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 12 Mar '05

12 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

patches for embedded VC4
by Ulrich Eckhardt 11 Mar '05

11 Mar '05

Hello! I'm currently trying to port Boost to embedded Visual C++ 4. Attached are a patch against this afternoon's CVS and toolset definition for Boost build v1. Some explanations for the patch: --------------------------------- EVC4 comes with several different compilers, all of which are cross compilers for various architectures. Else, those compilers are mostly bug-to-bug compatible to the one that comes with VC6. One problem though is that e.g. the ARM compiler has _MSC_VER=1201 while the MIPS compiler has _MSC_VER=1202 and the one for x86 has _MSC_VER=1200 (like VC6). The C++ standardlibrary is IMHO barely worth talking about, anything but the most primitive types of use require STLport, unfortunately in their yet unreleased version 5 (use 'cvs checkout -r STLPORT_5_0 STLport' in case you want to try). There are a change to boost/config/stdlib/stlport.hpp that is required for STLport 5. If you look at the patch, you will see that most changes are explained by removing '#if _MSC_VER==1200' in favour of '#if _MSC_VER<1300'. At first glance those are not really equivalent, but there are some considerations that will make it sensible: - if (which I doubt will ever happen) there come any updates to those compilers they will still have version numbers < 1300 - if VC6 and similar suffer a defect, chances are good that older compilers also suffer the same problems - there is a line that generates an error anyways should you try to compile boost code with <1200, older compilers are simply not supported. Another set of changes is that sometimes the use of '#pragma once' was made dependant on _MSC_VER>=1200, while other places used _MSC_VER>=1020. MS themselves use _MSC_VER>=1000. I think this pragma was already supported long before VC6, so the second alternative seems to be right. I replaced a few of such cases. I noticed that some places use BOOST_WORKAROUND while others use _MSC_VER directly. For #pragma once that makes still sense, since you don't want to first include the header for the macro, but in other cases I'm not so sure. Is there a tendency to uniformly use BOOST_WORKAROUND? If so, and since I'm touching a lot of those checks already, should I replace those? The change in boost/detail/lwm_win32.hpp is something where I don't claim I really understand what it does. Removing it breaks compilation, I don't know how to test if it really works. The changes in boost/function/function_template.hpp are something that shouldn't break anything, except if the brackets where in fact an undocumented workaround for some other bug.... Working on this, I noticed that some files I checked out of CVS were write protected!? Is that just my setup, intentional or by accident? I didn't investigate further. Some explanations on the toolset file: --------------------------------------- This is far from complete. There are several architectures that aren't yet supported, some aren't even supported by STLport (yet). Lots of debug code are still present. This also requires changes to some other places, in particular the names of libraries need to be changed, for autolinking in the headers, for building in some part (I forgot which) of the build files. Also, I found that MS Windows CE suffers from not being able to load DLLs with names longer than 31 chars, meaning that the normal boost naming conventions can't be used. This is a major bummer, but I don't see a workaround other than that. I'm throwing this work in progress at the list so I can get feedback earlier. So, if there are issues, don't hesitate to bring them forth. cheers Ulrich Eckhardt

4 5

The case for fold_seq
by Larry Evans 11 Mar '05

11 Mar '05

Is there any interest in a proposed mpl sequence, fold_seq, derived from mpl::fold and contained in boost-sandbox.sourceforge.net/vault/ in cppljevans/mpl/fold_seq_test.zip? This zip contains: * a test driver, fold_seq_test.cpp * a header file, fold_seq.hpp * bjam output of driver for intel * bjam output of driver for gcc. A better name for fold_seq might be cummulative_app since each element is a "partial_application" of the ForwardOp "operation" to part of the Seqence, where ForwardOp and Seqence are the arguments to fold, as described here: http://www.boost.org/libs/mpl/doc/refmanual/fold.html The reason for term "partial_application" is that it corresponds to "partial sum" described here: http://mathworld.wolfram.com/PartialSum.html Alternative names include "prefix reduction" or "scan": http://nf.apac.edu.au/training/MPIRefs/MPI_1.1/node84.html#Node84 Anyway, it seems that it's a useful extension to fold, since, as seen by the above references, the corresponding math concept occurs often. In addition, the test driver in the vault contains test_partial_product, where the value's at each element of the fold_seq correspond to elements in a cummulative product: http://mathworld.wolfram.com/CumulativeProduct.html Such a cummulative product could be used to calculate, at compile time, the strides for an instance of mult_array. Also, fold_seq could be used as a replacement for the get_side_type template class mentioned here: http://article.gmane.org/gmane.comp.lib.boost.devel/118867 and used to access the elements in a tuple, as demonstrated by the test_tuple_access function in the test driver. I'd be glad to discuss improvements or reasons why it's unneeded. TIA.

1 1

Need help: for N-arity operators in C++.
by Pavel Chikulaev 11 Mar '05

11 Mar '05

Hi all! Can anyone help me? I've got a problem with my library "Lazy". Here's the code: template<typename T, int N> class B {}; template<typename T> class C : B<T, max_possible_N_of_all_specializations_B<T> > {}; //The question is - How To write //max_possible_N_of_all_specializations_B? So, if I have these template specializations of B: template<> class B<int, 4> { enum { value = 4}; }; template<> class B<int, 920234> { enum { value = 920234 }; }; C<int>::value should be 920234. Does anyone knows how to do it? Thanks in advance. P.S. It's critical for my library to have max_possible_N_of_all_specializations_B. -- Pavel Chikulaev

5 15

Log utility
by Suman Cherukuri 11 Mar '05

11 Mar '05

I wrote a logging library using boost libraries and other standard C++ functions. I'm fairly satisfied with it and using in my own product. I think it'd be a good addition to Boost. What do you all think? --Suman

3 2

Update of the (not yet officially proposed) Function Types library
by Tobias Schwinger 11 Mar '05

11 Mar '05

Dear Boost community, after three complete rewrites and numerous steps of incremental refinement (some of it based on feedback from you) I am proud to hereby present my attempt to provide a "truely boostish" metaprogramming facility to work with function-, function reference - and (member) function pointer types. The functional range includes: - type classification ("is T a * function ?") - type decomposition (e.g. "what is the result of the function T describes ?") - type synthesis ("create a * function with these subtypes !") All of the above work with variadic functions and (configuration dependent) with arbitrary calling conventions. Common applications are: - generating callbacks (the most prominent special case of this is argument binding) - extracting meta infromation from function prototypes - concept checking (e.g. "let's see if this is a setter/getter pair...") - systematic overload selection See the Documentation for further information. [ -> http://tinyurl.com/4fw9n ] A downloadable archive has been put into the vault. [ -> http://tinyurl.com/4oe7q ] Its quality has improved by an order of magnitude since my first naive attempts, last year - and not at least because of those of you who helped. Thank you ! I decided to use the next couple of days for finalizing refinement and to wait for some more feedback to confirm or disprove my suspicion that the submission is "review ready", before sending out a formal request. Regards, Tobias

2 7

[boost::foreach] and bcc32-5.6.4
by Russell Hind 11 Mar '05

11 Mar '05

Has anyone tried BOOST_FOREACH with bcc32-5.6.4? I've just tried the example BOOST_FOREACH(char ch, "Hello") { std::cout << ch; } And get a string of errors of the following: (line 11 of main.cpp is the BOOST_FOREACH line). I'd really like to be able to use this library so if anyone can give any help in getting it to work, it would be really useful. Thanks Russell [C++] main.cpp(1): [C++ Error] main.cpp(11): E2354 Two operands must evaluate to the same type [C++ Warning] main.cpp(11): W8032 Temporary used for parameter 1 in call to 'boost::for_each::boost::for_each::container<char *,boost::mpl::false_> wrap<char *>(char * &)' [C++ Error] main.cpp(11): E2354 Two operands must evaluate to the same type [C++ Error] main.cpp(11): E2285 Could not find a match for 'boost::for_each::contain<T>(undefined,bool,undefined)' [C++ Warning] main.cpp(11): W8032 Temporary used for parameter 1 in call to 'boost::for_each::boost::for_each::container<char *,boost::mpl::false_> wrap<char *>(char * &)'

10 28

[date_time] test failures
by Caleb Epstein 11 Mar '05

11 Mar '05

http://tinyurl.com/5hnvv The date_time regression tests in the gregorian subdir called "testgenerators" and "testgenerators_dll" fail to compile on Solaris due to the use of a variable called "sun". Unfortunately, there is a preprocessor macro sun == 1 which gets defined on this platform that ends up turning the declaration: greg_weekday sat(Saturday), tue(Tuesday), fri(Friday), sun(Sunday); into greg_weekday sat(Saturday), tue(Tuesday), fri(Friday), 1(Sunday); I'd suggest either #undef sun at the top of the file or changing the name of this variable. Also, there are few other failures (testclocks, testlocal_time, testlocal_time_facet) due to a missing declaration of time_ in local_date_time_base. Example: http://tinyurl.com/5xd8h testtz_database is failing because it can't find its input file (probably because of the working directory the tests are run from). Perhaps this file should be found starting from $BOOST_ROOT? -- Caleb Epstein caleb dot epstein at gmail dot com

1 0