- Boost - lists.boost.org

[fsm review] Comparison with ad-hoc FSM coding
by Phil Endecott 20 Aug '08

20 Aug '08

Dear All, I have just spent a few minutes comparing an ad-hoc FSM implementation with an implementation using the proposed library. The example that I've used is the USB device state machine, which I recently had to understand for an embedded application, and I've put an image of the state graph here: http://chezphil.org/tmp/fsm.png For more info, google("USB 2.0 spec") (you'll find a zip file with a PDF in it) and see the start of chapter 9. Note that it seems to me that the "power interruption" transition is wrong and should go to "attached" rather than "powered", and that I have ignored the "suspended" states. The behaviour is essentially as follows: a device is "attached" until the hub supplies power, when it becomes "powered". It then waits for a reset, at which point it starts listening for messages at the "default address" (zero); the host ensures that only one device is in this state at any time. When the host sends a set_address message it changes to the "address" state, and when the host sends a set_configuration message it changes to the "configured" state for normal operation. Here is my ad-hoc implementation (note that I haven't tried to even compile any of this code): struct usb_device { enum state_t { Attached, Powered, Default, Address, Configured }; state_t state; int addr; int configuration; usb_device(): state(Attached), addr(0), configuration(0) {} void power_on() { state = Powered; } void power_off() { state = Attached; } void reset() { state = Default; addr = 0; configuration = 0; } void set_address(int addr_) { addr = addr_; state = (addr==0) ? Default : Configured; } void set_configuration(int configuration_) { configuration = configuration_; state = (configuration==0) ? Address : Configured; } }; In comparison, here's what I've come up with using Boost.FSM: struct Attached; struct Powered; struct Default; struct Address; struct Configured; typedef mpl::vector<Attached, Powered, Default, Address, Configured>::type StateList; struct PowerOn; struct PowerOff; struct Reset; struct SetAddress { int addr; SetAddress(int addr_): addr(addr_) {} }; struct SetConfiguration { int configuration; SetConfiguration(int configuration_): configuration(configuration_) {} }; struct Common { int addr; int configuration; }; struct Attached: fsm::state<Attached,StateList>, Common { void on_process(const PowerOn&) { switch_to<Powered>(); } }; struct Powered: fsm::state<Powered,StateList>, Common { void on_process(const PowerOff&) { switch_to<Attached>(); } void on_process(const Reset&) { switch_to<Default>(); } }; struct Default: fsm::state<Default,StateList>, Common { void on_enter_state() { addr = 0; } void on_process(const PowerOff&) { switch_to<Attached>(); } void on_process(const Reset&) { } void on_process(const SetAddress& set_address) { addr = set_address.addr; if (addr != 0) { switch_to<Address>(); } } }; struct Address: fsm::state<Address,StateList>, Common { void on_process(const PowerOff&) { switch_to<Attached>(); } void on_process(const Reset&) { switch_to<Default>(); } void on_process(const SetAddress& set_address) { addr = set_address.addr; if (addr == 0) { switch_to<Default>(); } } void on_process(const SetConfiguration& set_configuration) { configuration = set_configuration.configuration; if (configuration != 0) { switch_to<Configured>(); } } }; struct Configured: fsm::state<Configured,StateList>, Common { void on_process(const PowerOff&) { switch_to<Attached>(); } void on_process(const Reset&) { switch_to<Default>(); } void on_process(const SetConfiguration& set_configuration) { configuration = set_configuration.configuration; if (configuration == 0) { switch_to<Address>(); } } }; The latter is clearly more verbose than the former. Some of the verbosity would go if I put the common events (e.g. PowerOff) into a base class, but that adds verbosity of its own. There are a few characteristics of this particular design that favour the ad-hoc code. Firstly, the device's behaviour is allowed to be undefined if an unexpected event occurs. Secondly, many events have the same effect irrespective of the state (e.g. power off). Finally, the effect of events often depends on their data (i.e. zero has a special meaning). I would also say that the turnstile example given in the library documentation could be implemented more concisely using an ad-hoc approach (would someone like to try?). Perhaps more complex FSMs would benefit more from what this library offers. In that case, can we see an example? I note that this library is targeted at simpler FSMs than Boost.Statechart (which I have not used). Is there a category of FSMs that are simple enough that Boost.Statechart's features are not needed (e.g. hierarchy) yet too complex for an ad-hoc implementation? Regards, Phil.

8 35

[asio] Resolving Aliases
by Dean Michael Berris 20 Aug '08

20 Aug '08

Hi Guys, While writing the HTTP client in the C++ Networking Library, I ran into a bizarre problem: resolving virtual hosts. For example, given a host named 'bucket.s3.amazonaws.com', trying to resolve it with Boost.Asio (in 1.35) causes a 'Host not found (authoritative)' error. Is this a known issue, and if so what's my alternative? TIA -- Dean Michael C. Berris Software Engineer, Friendster, Inc.

4 5

Need opinion on implementation issue
by Daryle Walker 19 Aug '08

19 Aug '08

I have a class that has the cool pubic member access without "()", like "left" and "right" for boost::bimap. In my case, it's meant to simulate a function object, so it can be passed to functions like std::for_each, and the return value from said functions (the updated function object) can be assigned back to the special member. This function object forwards to the actual computation object within my class object. I implemented this by making a special inner private class and have the auxiliary function object be a public data member of that private type. The actual computation object isn't directly in my class object, but within the public auxiliary member. So the auxiliary function object can be passed by copy or assignment and everything works. The problem is in a class derived from my first one. It also has a public auxiliary function object data member. However, it forwards to the SAME actual computation object as the base class's auxiliary member. I implemented this by the derived class's auxiliary keeping a pointer to the computation object within the base's auxiliary. The issue is when I create temporary derived-auxiliaries for use in std::for_each. I have to create a copy of the computation object with new and delete on destruction. The derived-auxiliary keeps a bool flag indicating whether the pointer points to a contained object or a heap one. I was thinking of making a boost::variant<CompObj, CompObj*> instead, but trades use of the heap for temporaries for making all derived-auxiliaries huge (if sizeof(CompObj) > sizeof (CompObj*)): Current: base's CompObj + derived's CompObj* and bool New: base's CompObj + derived's variant -> base's CompObj + derived's max(CompObj, CompObj*) -> 2 * CompObj (None of these include the various administrative padding or "otherwise empty" bytes.) I haven't changed it yet because I suspect this is a bad trade-off. But what happens on systems with low/no heaps? Should this be some sort of macro switch? -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com

1 0

I need someone with a little-endian system to test an optimization.
by Daryle Walker 19 Aug '08

19 Aug '08

I just added an optimization to some code for systems with octet- sized bytes. I have such a system; so I tested that code. I added a further optimization for little-endian systems. Unfortunately, my computer is big-endian, so I have no way to test the second change. So if you have access to a computer with octet-sized bytes (CHAR_BIT == 8) and larger integers in little-endian format, can you help? The code is on our Subversion server, in the sandbox section, just checked in as revision 48224. Check-out or export the <http:// svn.boost.org/svn/boost/sandbox/md5> directory. The headers are in the "boost" subdirectory, of course. There is one mandatory source file at "libs/coding/src/md5.cpp". There are three test files at "libs/coding/test/md5*test.cpp". Compile all those together with our Unit Test and Serialization libraries. (On my system, I made a project file with a three sub-targets: Boost.Test unit-test, Boost.S11N, and md5.cpp; which the target with the test files compiled linked to.) The "md5.cpp" has the optimized code. The optimized code doesn't activate unless CHAR_BIT is 8 and the file's BOOST_CONTROL_OPTIMIZE_OCTET_BYTES macro is set (or overridden) to 1. The little-endian extra optimization is activated with the BOOST_LITTLE_ENDIAN macro and is mandatory (if valid). I added three now-commented-out #error lines to test which case was activated, which confirmed I'm using a not-little endian system. You can un- comment those to check for yourself. Let me know if the little endian code works, or tell me how to fix it (if not). If you want, you can comment-out the little endian code to test the endian- agnostic code, and then redefine or override BOOST_CONTROL_OPTIMIZE_OCTET_BYTES to be 0 to test the octet-agnostic code (which explodes the packed array into a bool array before combining). Thanks in advance.... -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com

1 0

[Units+Lambda+Math] Functor wrappers for overloaded cmath functions to avoid static_cast in boost::lambda::bind calls
by Torsten Maehne 19 Aug '08

19 Aug '08

Hello, nearly three months ago, I started a thread <http://thread.gmane.org/gmane.comp.lib.boost.devel/175774> on Boost-devel to propose a header, which interfaces Boost.Units with Boost.Lambda. An improved version <boost/units/lambda.hpp> became official part of Boost.Units. However, this header only addresses the mathematical operators (+, -, *, /, ...) and not the common mathematical functions defined cmath (overloaded for boost::units::quantity<Unit, Y> in <boost/units/cmath.hpp>). In an lambda expression, their invocation needs to be postponed till the execution of the whole lambda expression, using boost::lambda::bind to bind the function arguments to the function pointer. The problem is that for overloaded functions, a lengthy static_cast is required to avoid an "unresolved overloaded function type" error as for example in the following code fragment taken from <libs/units/example/lambda.cpp>: using namespace boost::units; using namespace boost::units::si; using boost::function; using boost::lambda::bind; using boost::lambda::_1; function<quantity<current> (quantity<time>) > i = iamp * bind(static_cast<quantity<dimensionless, double> (*)( const quantity<plane_angle>&)>(sin), 2.0 * M_PI * radian * f * _1) + i0; Steven Watanabe proposed in <http://thread.gmane.org/gmane.comp.lib.boost.devel/175774> to create functor wrappers for each cmath function to allow Boost.Lambda to automatically determine the return type of the overloaded functions. As this solution is not Boost.Units specific, he proposed to put the functor wrappers under a more general place like boost::math::functional. I implemented his proposal in the attached header "boost/units/math_functional.hpp" for all the functions overloaded in <boost/units/cmath.hpp>. There is also a unit test "libs/units/test/test_math_functional.cpp" and example "libs/units/examples/math_functional_lambda.cpp". In the latter, the above code snippet simplifies down to: using namespace boost::units; using namespace boost::units::si; using boost::function; using boost::lambda::bind; using boost::lambda::_1; using boost::math::functional; using boost::units::functional; function<quantity<current> (quantity<time>) > i = iamp * bind(sin_t(), 2.0 * M_PI * radian * f * _1) + i0; The functor wrappers include either a sig template or a result_type typedef, which allows Boost::Lambda's bind to choose the correct overloaded function depending on the types passed through the lambda placeholders. The cmath function calls are not prefixed by a namespace qualifier thus allowing argument dependent lookup (ADL, a.k.a. Koenig lookup). All functor wrappers have a '_t' prefix to avoid interference with the ADL. The functor wrappers for functions from <cmath> are defined in namespace boost::math::functional (to anticipate a generalization of this header). Functor wrappers for Boost.Units specific functions are defined in boost::units::functional (for boost::units::pow<long>, boost::units::pow<Rat>, boost::units::root<long>, boost::units::root<Rat>). The implementation has still some issues: * TODO: Functor wrappers for fma, nearbyint, rint (the boost::units implementations are unfinished in trunk). * TODO: Remove limitation of functor wrapper nexttoward to only boost::units::nexttoward, which is currently implemented in terms of boost::math::nextafter because boost::math::nexttoward is not yet available. * Is there a way to organize the code to allow dropping the _t prefix of the functor wrappers so that it would not interfere with the ADL to find the correct overloaded function in the namespaces of the function arguments? The only solution I came up with was by putting using declarations for each function defined in <cmath> and <boost/units/cmath.hpp> in a cmath_ namespace and prefix the function call inside functor wrapper with this namespace, e.g.: namespace cmath_ { using std::sin; using boost::units::sin; } struct sin { template<typename Args> class sig { private: typedef typename boost::tuples::element<1, Args>::type arg1_type; BOOST_TYPEOF_NESTED_TYPEDEF(nested, \ cmath_::sin(typeof_::make<arg1_type>()))) public: typedef typename nested::type type; }; template<typename T> typename sig<typename boost::tuples::tuple<sin, T> >::type operator()(const T& arg) const { return cmath_::sin(arg); } }; However, this has the drawback, that ADL is bypassed and only functions imported into cmath_ are found. * Is there a way to merge the functors for pow<long>, pow<Rat> and root<long>, root<Rat>? Currently, they have rather long names to disambiguate between the template arguments: static_rational_pow_t<Rat>, static_integer_pow_t<long>, static_rational_root_t<Rat>, and static_integer_root_t<long>. I'm looking for comments on this solution, especially, how it can be improved and how it should be restructured to maybe become part of Boost itself. Best regards, Torsten Maehne

1 0

[shifted_ptr] QA
by Phil Bouchard 19 Aug '08

19 Aug '08

Hello, If anybody is able to make shifted_ptr<> break, please share the replication test. It looks to be working fine but the possibility of having something I forgot could still be present. To give everybody a quick idea on the different states both the pointer and the pointee will have are defined as such: shifted_ptr<> (pointer): - part of the pool (local heap) - part of anything else (stack, data, system heap) shifted<> (pointee): - initialized - uninitialized When the shifted<> is initialized it means it knows what "set" it belongs to. If it is uninitialized it means it is still part of a construction sequence that is not yet finalized, hence not yet attached to any "set". Please disregard anything related to shifted_allocator<> because this is of pure shifted_ptr<> concerns. Some test examples can be found at: https://svn.boost.org/svn/boost/sandbox/shifted_ptr/libs/smart_ptr/example/ Regards, -Phil

1 2

Re: [boost] "SuperC"
by Phil Bouchard 19 Aug '08

19 Aug '08

"David Abrahams" <dave(a)boostpro.com> wrote in message news:877iae4oeq.fsf@mcbain.luannocracy.com... [...] >> Let's put it this way. All new "unordered" and multiset containers could >> easily be implemented as: >> 1) superc1st<double, list, vector> s1; >> 2) superc2nd<string, double, map, vector> s2; >> 3) superc2nd<string, double, map, map> s3; > > Sounds reminiscent of boost::graph::adjacency_list. It's a n-th dimensional container as opposed to adjacent_list. All in all we will benefit from: - "unordered" when list is part of the container. Ex.: superc<char, _map<char>, _list> s; - multisets or unordered multisets. Ex.: superc<employee, _map<string>, _map<string>, _map<double>, _map<double>, list> s; - the vector O(1) access when fragmentation is minimal - accessing sorted nodes (using map) but still adjacent in memory (vector). Ex.: superc<char, _map<char>, _vector> s = (_node<_map<char>, _vector> []) {'T', 'h', 'i', 's', ' ', 'i', 's', ' ', 'a', ' ', 't', 'e', 's', 't', '.'}; - interchanging vector iterators to map iterators. Ex.: superc<char, _map<char>, _vector> s; superc<char, _map<char>, _vector>::iterator i = s[10]; // if new _vector<>::operator [] returns: _node<> & s.find(i, s.end()); // O(log n) find from within a range of iterators only - STL code reuse - easy implementation - easy to use -Phil

1 0

[fsm review] Terminal emulator example
by Phil Endecott 19 Aug '08

19 Aug '08

Dear All, Here's another FSM example which I hope is a bit less trivial than the last one. It's for the escape sequence handling in a terminal emulator. If you're curious you can see the real code here: http://svn.anyterm.org/anyterm/trunk/common/Terminal.cc The terminal emulator has to understand: - Normal characters like 'A' that write themselves on the screen at the current cursor position. - Normal control characters like tab, carriage return etc. A peculiar feature is that these characters can occur within escape sequences, where they have their normal effect. - Escape sequences, which consist of ESC followed by one character (normally a letter) and have effects like clearing the screen. - "CSI sequences", which perform more complex operations that may require parameters (e.g. scroll lines N to M up). They have the form ESC [ n1 ; n2 ; n3 ; ... X where the final letter X determines the operation and the number of numeric parameters is variable. So the state machine needs to track whether it is in an escape sequence, in a CSI sequence, or in "normal operation". The transitions are as follows: Current state | Condition | Next state ------------------------------------------------ Normal | ESC | ESC ESC | end of sequence | Normal ESC | [ | CSI ESC | char 26 | Normal CSI | end of sequence | Normal CSI | char 26 | Normal Character 26 explicitly abandons any escape sequence that is in progress. A terminal emulator should behave sensibly when it receives invalid input. One reasonable behaviour on receiving an invalid character is to ignore the preceding incomplete input and to treat the new character as if it had been received in normal mode; or, we could ignore the preceding incomplete input AND the new character and switch to normal mode. The following transitions do something along those lines: Normal | char 26 | Normal ESC | ESC | ESC ESC | invalid sequence | Normal CSI | ESC | ESC CSI | invalid sequence | Normal One thing that we don't want to do is to throw an exception when we get invalid input. My (stripped-down) ad-hoc implementation of this follows: class Terminal { screen_t screen; // basically a 2D array, with some features // for efficient scrolling int cursor_col, cursor_row; int params[MAX_PARAMS]; int nparams; enum state_t { normal, esc, csi }; state_t state; Terminal(): cursor_col(0), cursor_row(0), state(normal) {} void carriage_return() { cursor_col = 0; } void cursor_line_up() { cursor_row--; } void csi_CUU() { cursor_row -= params[0]; } // Lots more functions like those omitted. void write_normal_char(char c) { if (cursor_col>=cols) { cursor_col = 0; cursor_line_down(); } screen(cursor_row,cursor_col) = c; cursor_col++; } void process_char(char c) { // Control chars like tab, newline etc. work even inside // escape sequences: if (c <= 31) { switch (c) { .... case 13: carriage_return(); break; .... case 26: // This code abandons any escape sequence that is in progress state = normal; break; case 27: // Escape state = esc; break; .... } } else { switch (state) { case normal: write_normal_char(c); break; case esc: switch (c) { .... case 'M': cursor_line_up(); state=normal; break; .... case '[': state=csi; nparams=0; break; default: state=normal; break; } break; case csi: if (isdigit(c)) { if (nparams==0) { nparams=1; params[0]=0; } params[nparams-1] = params[nparams-1]*10 + (c-'0'); } else if (c==';') { if (nparams>=MAX_PARAMS) { return; } nparams++; params[nparams-1] = 0; } else { switch (c) { .... case 'A': csi_CUU(); break; .... } state = normal; } } } } }; OK, so let's try to implement that with the proposed library. As before, I haven't tried to compile any of this code: struct Normal; struct Esc; struct CSI; typedef mpl::vector<Normal,Esc,CSI>::type StateList; struct Common { screen_t screen; // BTW, how can I access this from outside? int cursor_col, cursor_row; void carriage_return() { cursor_col = 0; } void handle_control_chars(char c) { switch (c) { .... case 13: carriage_return(); break; .... case 26: // This code abandons any escape sequence that is in progress this->switch_to<Normal>(); break; case 27: // Escape this->switch_to<Esc>(); break; .... } } }; template <typename StateT> struct TermState: fsm::state<StateT,StateList>, virtual Common { // I think I need some using declarations here. Or do they have to be in each of // the derived classes? } struct Normal: TermState<Normal> { void write_normal_char(char c) { if (cursor_col>=cols) { cursor_col = 0; cursor_line_down(); } screen(cursor_row,cursor_col) = c; cursor_col++; } void on_process(const char& c) { if (c<=31) { handle_control_char(c); } else { write_normal_char(c); } } }; struct Esc: TermState<Esc> { void cursor_line_up() { cursor_row--; } void on_process(const char& c) { if (c<=31) { handle_control_char(c); } else { switch (c) { .... case 'M': cursor_line_up(); switch_to<Normal>(); break; .... case '[': switch_to<CSI>(); break; default: switch_to<Normal>(); break; } } } }; struct CSI: TermState<CSI> { int params[MAX_PARAMS]; int nparams; void on_enter() { nparams=0; // doing this here is nice } void csi_CUU() { cursor_row -= params[0]; } void on_process(const char& c) { if (c<=31) { handle_control_char(c); } else { if (isdigit(c)) { if (nparams==0) { nparams=1; params[0]=0; } params[nparams-1] = params[nparams-1]*10 + (c-'0'); } else if (c==';') { if (nparams>=MAX_PARAMS) { return; } nparams++; params[nparams-1] = 0; } else { switch (c) { .... case 'A': csi_CUU(); break; .... } switch_to<Normal>(); } } } }; My view is that the ad-hoc version of the code is sufficiently readable and efficient for my needs, and that the Boost.FSM version does not improve on it. What do other people think? Am I choosing bad examples? If so, please can someone post an example that does demonstrate the library's advantages? (Maybe off-topic, but if any Spirit or Expressive experts would like to show how their libraries would deal with this problem I'd be interested to see that.) Regards, Phil.

2 3

FSM Review Announcement
by Martin Vuille 19 Aug '08

19 Aug '08

The formal review for Andrey Semashev's Finite State Machines (FSM) library is scheduled for August 11th to 20th. Quoting from the documentation: "The main goals of the library are: * Simplicity. It should be very simple to create state machine using this library. * Performance. The state machine infrastructure should not be very time and memory-consuming in order to be applicable in more use cases. * Extensibility. A developer may want to add more states to the existing state machine, and this addition should be relatively safe since it shouldn't interfere with the existing states. The developer should also be able to specify additional transitions and events for the machine with minimum modifications to the existing code." "The following compilers are known to have problems or most likely will have ones: * Microsoft Visual C++ 6.0 and 7.0. Most probably will fail to compile due to lack of partial template specialization support. * Borland C++ Builder 5.5.1 (free version). Fails to compile due to lack of partial template specialization and in-class using declarations support. Some other minor problems also have been noticed. Newer versions of the compiler have not been tested. * OpenWatcom 1.5. Fails to compile due to problems with Boost.MPL code. Newer versions of the compiler have not been tested. * SunPro C++ Compiler 5.5 for Solaris (SPARC). Most likely will show problems with function overload resolution. Newer versions of the compiler have not been tested." The current submission is available from the sandbox vault at http://tinyurl.com/yjozfn (or http://www.boostpro.com/vault/index.php?action=downloadfile&filename=FSM.zip &directory=&PHPSESSID=48493076c1ea60ae316f7b60f15b9ed1, if you prefer.) MV

15 47

[exception] doc error
by Daryle Walker 19 Aug '08

19 Aug '08

[This is based of an unrelated post that mentioned a file in the 1.36 release branch. I just looked and the trunk also has it.] <http://svn.boost.org/svn/boost/trunk/libs/exception/doc/ enable_current_exception.html>, as of revision 47496, has an error in its beginning. It wants T to be a user-defined type so it can derived publicly from it. However, user-defined type doesn't mean class type; it also includes enums, which can't be derived from. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com

2 1