- Boost - lists.boost.org

RE: [boost] ANN: review of FSM library starts
by Simon Gittins 24 Feb '05

24 Feb '05

I think the library should be accepted in boost. Comments below. > -----Original Message----- > From: boost-bounces(a)lists.boost.org > [mailto:boost-bounces@lists.boost.org] > On Behalf Of Pavel Vozenilek > Sent: Monday, February 21, 2005 11:31 AM > To: boost(a)lists.boost.org > Subject: [boost] ANN: review of FSM library starts [snip] > > * What is your evaluation of the documentation? > How easy (or hard) it is to understand library > features? What can be improved? > The tutorial is good. The few times I've needed the reference, it has been sufficient. > > * What is your evaluation of the design? > What features are supported better by > alternative FSMs? What could be added > (or removed) from the library? > Three appealing features of boost::fsm for me are: - No code generation - Hierarchical. - State local data ('state is an object'). In my application (5 state machines, each with 8 - 40 states), I was able to use the fsm to manage the lifetime of objects local to the state (and any inner states). To me, it seems natural that states have the option of 'owning' information. Managing the lifetime and access rights of some 50+ variables used by a state machine would be unpleasant. I think that custom_reactions that act like guards should be discouraged, as they effectively hide part of the state chart in the implementation. When I read a particular fsm, I want to be able to clearly see all possible transitions and actions without having to search through any decision logic code to fill in the gaps. We should be able to specify guards as part of the state definition. Something like this: struct StState: fsm::simple_state<StState,StOuter, mpl::list < fsm::guard2<EvEvent, fsm::switch<StRes0,StRes0ActCtxt,&StRes0ActCtxt::Action0>, fsm::switch<StRes1,StRes1ActCtxt,&StRes1ActCtxt::Action1> > > >; I guess this might make the cpp code look like this: fsm::guard2::result StState::guard2(const EvEvent& ev) { if(cond) return fsm::guard2::result<0>(); else return fsm::guard2::result<1>(); } I haven't thought about the implementation too much admittedly. Having this would be a big help in automatically generating UML state charts. > > * The library documentation contains > few not yet solved issues (name, > separating the library into two parts, > exception handling). What is you opinion here? > I have no opinion on the possibility of splitting the library in two. I've avoided using the exception handling feature of boost::fsm, but the description in the documentation looks fairly sensible. > > * What is your evaluation of the implementation? > Are there parts of code too obscure or > duplicating exiting Boost functionality? > Can something be factored out to standalone > library or among general utilities? > Implementation appears concise. No real concerns here. I was able to add a new type of reaction (in_state_transition - trivial though it is) with no problems. > > * 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? > The library produces large binaries. It does however, appear to scale reasonably well (anecdotally, it seems about linear with the number of states). The in memory footprint is of the same order of magnitude as the binary size. My application is fairly soft real time, and runs on an embedded 486-like system, with a few hundred individual state machines and a few hundred events delivered per second. In this case, the performance of boost::fsm is acceptable, and does not threaten any timing constraints of the system. > > * What is your evaluation of the potential > usefulness of the library? Can you compare > this FSM to other implementations? > The library has already been useful, and I see myself using the library again. I believe that boost::fsm is a good solution for many non trivial compile time fsms. > > * Did you try to use the library? With what > compiler? Did you have any problems? > Do you have tips for better support of older > compilers? What are possible portability problems? > I've been using an older version of the library with gcc-3.2.3 > > * How much effort did you put into your > evaluation? > A glance? A quick reading? In-depth study? > I've spent quite a few hours developing using boost::fsm, and about half an hour catching up the on the latest documentation. > * Are you knowledgeable about the problem domain? > Not overly. I've built state machines with switch(), and have had to build a flat dynamic fsm framework (and use it) in the past. > > And finally, every reviewer should answer this question: > > > * Do you think the library should be accepted as a > Boost library? Be sure to say this explicitly so that > your other comments don't obscure your overall opinion. > Yes Simon Gittins ########################################################################## This e-mail is for the use of the intended recipient(s) only. If you have received this e-mail in error, please notify the sender immediately and then delete it. If you are not the intended recipient, you must not use, disclose or distribute this e-mail without the author's prior permission. We have taken precautions to minimise the risk of transmitting software viruses, but we advise you to carry out your own virus checks on any attachment to this message. We cannot accept liability for any loss or damage caused by software viruses. ##########################################################################

3 3

type_info/typeid
by Jody Hagins 23 Feb '05

23 Feb '05

As noted eariler, I have been working on moving the type_info/typeid stuff into a more common place. I have been using the implementation in boost/python/type_id.hpp as a reference, because that code seems to have addressed many issues related to different compilers. However, some of the workaround code prohibits standard confirming calls, so I wanted to get some input here. I am conflicted as to giving a summary or providing full details. I will probably end up doing a bit of both... The biggest problem is that on some older compilers, calls to the typeid() operator incorrectly leave outer reference and cv-qualifiers when returning type_info. Some interesting code exists to workaround this problem, resulting in a type_id() function. I have expanded this functionality to get most of 5.2.8 working. However, there are several pieces of 5.2.8 that are not possible (at least to me), using a fix like this. I have tried using macros, and some other tricks, but can not get full conformance to 5.2.8. So, maybe I can get a little help. The "bad" compilers are currently recognized by this incantation. #if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) \ || (defined(BOOST_INTEL_CXX_VERSION) \ && BOOST_INTEL_CXX_VERSION <= 700) What versions of MSVC/Intel does this include? Is support for them still necessary? If so, is it reasonable to leave in a type_id function that does not conform to 5.2.8, letting the buyer beware? Also, it is remotely possible that implemeting 5.2.8 fully is possible with a workaround, but I have been unsuccessful using gcc. I basically "force" the workaround to be used by adding defined(__GNUC__) so I can test the workaround code. The closest I can come is defining a macro... #if (defined(BOOST_MSVC) && BOOST_MSVC <= 1300) \ || (defined(BOOST_INTEL_CXX_VERSION) \ && BOOST_INTEL_CXX_VERSION <= 700) # define BOOST_TYPEID(x) \ // Some funky stuff #else # define BOOST_TYPEID(x) typeid(x) #endif but still under the "bad" compilers, some code does not compile, and other code causes tests to fail. This leaves users with some leeway. If you do not care about compiler bug workarounds, use typeid(). If you do care, use the BOOST_TYPEID() macro. However, if you are using a "bad" compiler, some things will either not compile, or will give the wrong behavior. FWIW, the current workaround only supports static types, and does not support lvalue at all. I have added this, but it has some problems. FWIW, the most difficult parts of 5.2.8 to get right with the workaround are: 5.2.8.2: I am having problems stripping the qualifiers and still leaving the most derived information 5.2.8.2: once the expression is evaluated, unless call directly to typeid(), a segv happens instead of std::bad_typeid exception being thrown. 5.2.8.3: The expression is not supposed to be evaluated (the expression is only allowed to be evaluated if the expression results in a polymorphic type or a pointer to a polymorphic type is dereferenced -- see 5.2.8.2). I would gladly appreciate any questions/comments.

1 0

Yet another typo fix
by Julio M. Merino Vidal 23 Feb '05

23 Feb '05

Hi again, you can find attached another typo fix; this time it's a change from neccessary to necessary. I first noticed this in a documentation file (from Boost.Build v2), but then decided to cleanup the whole source tree. It's gzipped to keep it small. Can anybody please apply this one (and possibly the other patches attached to my last two emails)? Thanks a lot, -- Julio M. Merino Vidal <jmmv84(a)gmail.com> http://www.livejournal.com/users/jmmv/ The NetBSD Project - http://www.NetBSD.org/

2 3

Re: Compile-time conditional function invocation
by Jeff Mirwaisi 23 Feb '05

23 Feb '05

documentation, but just for completeness. Given a type trait TT which you want to select upon. Given a template function TF which you would like to call only for types that TT selects from within template function G. We need a type which will delegate to TF, that doesn't bind the template parameter types and is a first class type (a holder) template <typename T> void TF(T) {} struct TF_holder { typedef void result_type; template <typename T> result_type invoke(T t) {return TF(t);} }; template <typename U> void G(U u) { execute_if< TT< U >::invoke< TF_holder >(u); } G is the generic template function for all types, TF is the conditionally targeted template function for types for which TT is true. Hope that helps. Jeff Mirwaisi

1 0

format lib patch
by François Dumont 23 Feb '05

23 Feb '05

Here is a small typo fix for the BOOST_NO_LOCALE_ISDIGIT macro that is sometimes spell with an additional I (ISIDIGIT). It is even spell correctly only once!

2 1

Boost TSS crash under Win32
by Schalk_Cronje＠McAfee.com 23 Feb '05

23 Feb '05

We have encountered a Boost TSS crash when used under the following circumstances with VC6: * Main program dynamically loads DLLs via LoadLibrary. * The main program does not use TSS at all. * TSS is used by the components as class variables. * Main program explicitly unloads DLLs before exiting * Data in TSS is reset long before the unload occurs. The issue seems to be related to the fact that the final cleanup handler kicks in after the DLLs have already unloaded. I hope I have not missed something from the archives related to such an issue. The following diff show the changes made to fix this problem: --- boost/libs/thread/src/tss.cpp 2005-01-07 13:01:27.000000000 +0000 +++ tss.cpp 2005-02-23 12:11:38.000000000 +0000 @@ -52,10 +52,14 @@ tss_slots* slots = static_cast<tss_slots*>(p); for (tss_slots::size_type i = 0; i < slots->size(); ++i) { - boost::mutex::scoped_lock lock(tss_data->mutex); - (*tss_data->cleanup_handlers[i])((*slots)[i]); - (*slots)[i] = 0; + if ((*slots)[i]) + { + boost::mutex::scoped_lock lock(tss_data->mutex); + (*tss_data->cleanup_handlers[i])((*slots)[i]); + (*slots)[i] = 0; + } } + // delete slots; // Should we be deleting the slot data as well, when the thread exits? } void init_tss_data() The above diff also contains one line that is currently commented. Should we delete the tss_slots instance for the specific thread?

1 0

format lib patch
by François Dumont 23 Feb '05

23 Feb '05

Config: STLport 5.0 beta and MSVC 8 (but also reported with 7.1) It looks like this compiler has a problem with the relation between the basic_string::size_type and basic_format::size_type as soon as the library is not the native one. Here is a patch proposition that return a basic_string::size_type rather than the basic_format::size_type. I think it is quite a secure patch as the method is already using a static_cast<typename string_type::size_type> to return its result and not a simple static_cast<size_type>. Bests

2 1

[Determine interest] Deterministic/nondeterminisatic multitape Turing machine
by Alex Vinokur 23 Feb '05

23 Feb '05

Is there any interest in a library which simulates a deterministic/nondeterminisatic multitape Turing machine? Current version C++ Simulator of a Turing Machine can be downloaded at : * http://sourceforge.net/projects/turing-machine/ * http://alexvn.freeservers.com/s1/turing.html The program simulates Deterministic and Nondeterministic Multitape Turing Machine (TM). Detailed log file is generated. Resources used (input size, output size, TM-space, TM-time) are computed as well. A simulated Turing machine is defined by the set of setup files and data : * description file (optional), * number of tapes, * state file, * alphabet file, * transition file, * file(s) of input word(s). Set of simulated Turing machines is defined by a metafile. Each row of the metafile contains data related to some Turing machine. The following demo Turing machines are demonstrated with using the C++ Simulator : 1. An addition program : Deterministic, 1 tape 2. An addition program with marker : Deterministic, 1 tape 3. An addition program : Deterministic, 2 tapes 4. A multiplication program : Deterministic, 1 tape 5. An Euclid algorithm : Deterministic, 1 tape 6. Recognition of palindromes : Deterministic, 2 tapes 7. Partition problem : Nondeterministic, 3 tapes 8. Conversion unary-to-binary : Deterministic, 1 tape 9. Computing Fibonacci numbers : Deterministic, 1 tape 10. Computing Huffman codes : Deterministic, 3 tapes Log file fragments are shown below ----------------------- --- File metafile ----------------------- add.dsc 1 add.sta add.abt add.rul add1.in add2.in add3.in add4.in add5.in add6.in add7.in addm.dsc 1 addm.sta add.abt addm.rul add1.in add2.in add3.in add4.in addt.dsc 2 addt.sta addt.abt addt.rul addt1.in addt2.in mult.dsc 1 mult.sta mult.abt mult.rul mult1.in mult2.in mult3.in euclid.dsc 1 euclid.sta euclid.abt euclid.rul euclid1.in euclid2.in euclid3.in euclid4.in euclid5.in palindr.dsc 2 palindr.sta palindr.abt palindr.rul palindr1.in palindr2.in palindr3.in part.dsc 3 part.sta part.abt part.rul part1.in part2.in part3.in un2bin.dsc 1 un2bin.sta un2bin.abt un2bin.rul un2bin1.in un2bin2.in un2bin3.in fib.dsc 1 fib.sta fib.abt fib.rul fib1.in fib2.in fib3.in fib5.in fib7.in huffman.dsc 3 huffman.sta huffman.abt huffman.rul equ.in fib.in arb.in ----------------------- ========== Data selected from Metafile metafile ========== ---------- Nondeterministic Turing Machine# 1 ---------- Description file name : add.dsc Number of tapes : 1 States file name : add.sta Alphabet file name : add.abt Transitions file name : add.rul Input words files names : add1.in add2.in add3.in add4.in add5.in add6.in add7.in %%=========================================== %%=== Nondeterministic Turing Machine# 1 ==== %%======= Machine Definition : BEGIN ======== %%=========================================== ###### Nondeterministic Turing Machine Definition ###### ###### This Machine is actually Deterministic!!! ###### ====== Description ====== An addition program. The program adds two numbers. A number 'n' is represented by n 1-s. Sample : 5 is represented as 1 1 1 1 1 3 is represented as 1 1 1 Input : Two numbers separated by symbol '*' Sample : 1 1 1 1 1 * 1 1 1 Output : Resulting number without '*' Sample : 1 1 1 1 1 1 1 1 ====== States Definition ====== Initial states : q0 Halting states : qf Internal states : q1 q2 ====== Alphabet Definition ====== ------ Tape# 0 ------ Empty symbols alphabet : b Input alphabet : 1 * Internal alphabet : x ====== Transition Rules Definition ====== Rule# 0 : q0 [ * ] ---> q1 [ (1, N) ] Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] Rule# 2 : q0 [ b ] ---> q0 [ (b, R) ] Rule# 3 : q1 [ 1 ] ---> q1 [ (1, R) ] Rule# 4 : q1 [ b ] ---> q2 [ (b, L) ] Rule# 5 : q2 [ 1 ] ---> qf [ (b, L) ] %%=========================================== %%======= Machine Definition : END ======== %%=== Nondeterministic Turing Machine# 1 ==== %%=========================================== %%=========================================== %%=== Nondeterministic Turing Machine# 1 ==== %%========= Processing Input Words ========= %%============= Set# 1 : BEGIN ============== %%=========================================== ##### < Run 1.1 > Input word(s) & head start position(s) on tape(s) ##### Tape#0 : Word = 1 1 1 1 1 * 1 1 1 ; Head pos = 0 ##### < Run 1.1 > Processing ##### ----- < Run 1.1 > Initial Configuration ----- State : q0 Tape#0 : [1] 1 1 1 1 * 1 1 1 < Run 1.1 > Applied Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] ----- < Run 1.1 > Configuration#1 ----- State : q0 Tape#0 : 1 [1] 1 1 1 * 1 1 1 < Run 1.1 > Applied Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] ----- < Run 1.1 > Configuration#2 ----- State : q0 Tape#0 : 1 1 [1] 1 1 * 1 1 1 < Run 1.1 > Applied Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] ----- < Run 1.1 > Configuration#3 ----- State : q0 Tape#0 : 1 1 1 [1] 1 * 1 1 1 < Run 1.1 > Applied Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] ----- < Run 1.1 > Configuration#4 ----- State : q0 Tape#0 : 1 1 1 1 [1] * 1 1 1 < Run 1.1 > Applied Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] ----- < Run 1.1 > Configuration#5 ----- State : q0 Tape#0 : 1 1 1 1 1 [*] 1 1 1 < Run 1.1 > Applied Rule# 0 : q0 [ * ] ---> q1 [ (1, N) ] ----- < Run 1.1 > Configuration#6 ----- State : q1 Tape#0 : 1 1 1 1 1 [1] 1 1 1 < Run 1.1 > Applied Rule# 3 : q1 [ 1 ] ---> q1 [ (1, R) ] ----- < Run 1.1 > Configuration#7 ----- State : q1 Tape#0 : 1 1 1 1 1 1 [1] 1 1 < Run 1.1 > Applied Rule# 3 : q1 [ 1 ] ---> q1 [ (1, R) ] ----- < Run 1.1 > Configuration#8 ----- State : q1 Tape#0 : 1 1 1 1 1 1 1 [1] 1 < Run 1.1 > Applied Rule# 3 : q1 [ 1 ] ---> q1 [ (1, R) ] ----- < Run 1.1 > Configuration#9 ----- State : q1 Tape#0 : 1 1 1 1 1 1 1 1 [1] < Run 1.1 > Applied Rule# 3 : q1 [ 1 ] ---> q1 [ (1, R) ] ----- < Run 1.1 > Configuration#10 ----- State : q1 Tape#0 : 1 1 1 1 1 1 1 1 1 [b] < Run 1.1 > Applied Rule# 4 : q1 [ b ] ---> q2 [ (b, L) ] ----- < Run 1.1 > Configuration#11 ----- State : q2 Tape#0 : 1 1 1 1 1 1 1 1 [1] < Run 1.1 > Applied Rule# 5 : q2 [ 1 ] ---> qf [ (b, L) ] ----- < Run 1.1 > Configuration#12 ----- State : qf Tape#0 : 1 1 1 1 1 1 1 [1] < Run 1.1 > Success : Current state (qf) is halting one ------------------------------------------------------------- --- < DTM #1, Input #1 > Result : Input word(s) ACCEPTED --- ------------------------------------------------------------- < DTM #1, Input #1 > Resource Report ------------------------------------- < DTM #1, Input #1 > * Input size : 9 symbols < DTM #1, Input #1 > * Output size : 8 symbols < DTM #1, Input #1 > * TM-Space used : 10 cells < DTM #1, Input #1 > * TM-Time used : 12 transitions |==================| |--- Statistics ---| |... Transition ...| |------------------| | Rules : Times | |------------------| | 0 : 1 | | 1 : 5 | | 2 : 0 | | 3 : 4 | | 4 : 1 | | 5 : 1 | |------------------| | Total : 12 | |==================| %%=========================================== %%============= Set# 1 : END ============== %%========= Processing Input Words ========= %%=== Nondeterministic Turing Machine# 1 ==== %%=========================================== -- Alex Vinokur email: alex DOT vinokur AT gmail DOT com http://mathforum.org/library/view/10978.html http://sourceforge.net/users/alexvn

3 3

RE: [boost] [iterators] request for utility iterator
by Eyal Farago 23 Feb '05

23 Feb '05

you can easily achieve this using (make_)transform_iterator and boost bind: make_transform_iterator( map.begin(), boost::bind( &MAP_TYPE::value_type::first, _1 ) ) (give or take a typename before MAP_TYPE::...) I think it's so simple that you don't really need a utility class for it. I'm also quite sure that boost bind takes better care of const/mutable return type and any other bad things that you may stumble across when trying to implement this functor youself (same goes for boost.lambda). eyal. -----Original Message----- From: Thorsten Ottosen [mailto:nesotto@cs.auc.dk] Sent: Monday, February 14, 2005 4:19 AM To: boost(a)lists.boost.org Subject: [boost] [iterators] request for utility iterator Hi all, I often want to iterate over just the values of a map or perhaps just the keys of a map. Therefore I would like to see the following iterator adapters in the iterator library: template< class Map > struct map_key_iterator; template< class Map > struct map_value_iterator; template< class Map > struct map_const_value_iterator; I have outlined an implementation in the attached file, but basically it just a wrapper around transform_iterator<typename Map::iterator>. Comments? br Thorsten

4 8

typeid wrapper
by Felipe Magno de Almeida 22 Feb '05

22 Feb '05

Ive searched in boost a typeid wrapper like the one Andrei Alexandrescu uses in his book (Modern C++ Design), but didnt found any, except one in the python library. It seemed very much what Im searching, so I'm wondering why it is in the python library. I think it is a very useful feature outside python library either. So Im asking if it shouldnt be a general class in the boost library, instead of being a feature to be used by the python library only? Thanks in advance, -- Felipe Magno de Almeida UIN: 2113442 email: felipe.almeida@ic unicamp br, felipe.m.almeida@gmail com I am a C, modern C++, MFC, ODBC, Windows Services, MAPI developer from synergy, and Computer Science student from State University of Campinas(UNICAMP). To know more about: Unicamp: http://www.ic.unicamp.br Synergy: http://www.synergy.com.br current work: http://www.mintercept.com

7 7