11.8. Exercises

11-0.	It might be useful to be able to group transitions by their start state, so that each start state only has to be written once. Design such a grouped representation and modify the FSM framework design to support it. Evaluate the success of your changes in reducing redundancy and boilerplate.
11-1.	We didn't really have to give up on expression template-based designs so quickly. How could the efficiency lost by passing function pointers be recaptured? (Hint: They must be passed as template arguments.) Rework your favorite expression template DSEL syntax to use this technique and evaluate its success as a DSEL.
11-2.	Implement and test the expression-template-based FSM DSEL we explored but then discarded earlier in section 11.4.1. Evaluate its ease-of-use and efficiency tradeoffs.
11-3.	Evaluate the possibility of implementing the following expression-template-based FSM DSEL: player() { Stopped[ play => Playing | &player::start_playback , open_close => Open | &player::open_drawer ] , Open[ open_close => Empty | &player::close_drawer ] // ... ; } Based on your evaluation, explain why this syntax is unachievable, or, if it is viable, implement a prototype that demonstrates it.
11-4.	Extend the FSM implementation to support optional state entry and exit actions.
11-5.	Transition guards are additional predicates that you can assign to certain transitions to suppress/enable them depending on some condition. Although formally redundant,[6] they help to reduce the FSM's size and complexity, sometimes significantly, and therefore are often desired. Design a notation and implement support for optional transition guards in this chapter's example. [6] Any finite state machine that uses transition guards can be always transformed into an equivalent "pure" FSM that doesn't.
11-6.	Extend the FSM implementation to support "catch-all" transitions, making any of the following possible: // whatever the current state is, allow "reset_event" to // trigger a transition to "initial_state" row< _, reset_event, initial_state, &self::do_reset > // any event received in "error" state triggers a transition // to "finished" row< error, _, finished, &self::do_finish > // any event received in any state triggers a transition // to "done" row< _, _, done, &self::do_nothing > Choose and implement a deterministic scheme for handling transitions with overlapping conditions.
11-7*.	Extend the FSM implementation to support nested (composite) states. A sketch of a possible design is provided below: class my_fsm : fsm::state_machine< my_fsm > { // ... struct ready_to_start_; typedef submachine<ready_to_start_> ready_to_start; struct transition_table : mpl::vector< row< ready_to_start, event1, running, &self::start > , row< running, event2, Stopped, &self::stop > // ... > {}; }; // somewhere else in the translation unit template<> struct my_fsm::submachine<ready_to_start_> : state_machine< submachine<ready_to_start_> > { // states struct ready; struct closed; struct recently_closed; struct transition_table : mpl::vector< row< ready, event3, closed, &self::close > , row< closed, event4, recently_closed > // ... > {}; };
11-8.	Our dispatching code searches linearly over the states with outgoing transitions on a given event. In the worst case, that takes O(S) time, where S is the total number of states in the FSM. In the examples directory of the code that accompanies this book, player2.cpp illustrates a state_machine that dispatches using O(1) lookup into a static table of function pointers. That, however, incurs runtime memory access and function pointer indirection overhead. Implement and test a third dispatching scheme that avoids all of these disadvantages by generating an O(log2S) binary search.