Exercises





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.


     Python   SQL   Java   php   Perl 
     game development   web development   internet   *nix   graphics   hardware 
     telecommunications   C++ 
     Flash   Active Directory   Windows