|
|
11.4. Choosing a DSLOur next challenge is to design a domain-specific language that allows a programmer to describe a finite state machine like the one implemented by player. Later, we'll write metaprogram code that processes the FSM description to generate a class like player. As hinted earlier, the state machine author is going to deliver the description in the form of a state transition table, so let's start looking at possible syntaxes for representing it. 11.4.1. The Transition TableDeciding on a representation for transitions (the rows of our STT) is where things really start to get interesting. We have many options! Let's go through a few of the possible ways of writing just the first two rows of our table, and analyze each one to get a sense of the range of choices at our disposal. At this stage, we're not going to worry too much about how to use these syntaxes to build FSMs; the point is just to consider how STTs might map onto C++ syntax:
// Current Event Next Action
// State State
[ Stopped, play, Playing, &fsm::start_playback ]
[ Stopped, open_close, Open, &fsm::open_drawer ]
Our first attempt is sufficiently table-like to make the state machine's structure clear. What would it take to make this syntax work? To make the brackets legal, there would have to be a class, say TRansition_table, with an overloaded operator[]. Because the C++ compiler doesn't allow us to write bracketed expressions in isolation, users would have to precede the table with an instance of that class, something like:
transition_table STT; // provided by the FSM framework
...
// Current Event Next Action
// State State
STT[ Stopped, play, Playing, &fsm::start_playback ]
[ Stopped, open_close, Open, &fsm::open_drawer ]
Next, because operator[] is only allowed to have one argument, there would have to be at least one overloaded comma operator to consolidate the items in between the brackets. Having noticed that, we can make the syntax even more table-like by replacing the comma operator with operator|:
// Current Event Next Action
// State State
STT[ Stopped | play | Playing | &fsm::start_playback ]
[ Stopped | open_close | Open | &fsm::open_drawer ]
Given that our event names will denote types, however, both of the syntaxes we've explored present a problem: We can't just use a type in a runtime expression as though it were an object. Instead, we have to pass an instance of that type, so our table might end up looking more like this:
// Current Event Next Action
// State State
STT[ Stopped | play() | Playing | &fsm::start_playback ]
[ Stopped | open_close() | Open | &fsm::open_drawer ]
A couple of parentheses per row don't compromise the syntax too badly, though we appear to be requiring that events can be default-constructed. Default-constructibility requirements are a red flag to any experienced library designer: In this case, events won't necessarily all be lightweight types, and constructing instances just so we can build the transition table might not be appropriate. Applying the Fundamental Theorem of Software Engineering,[1] we might get around that problem by asking users to transmit the event's type information to the framework indirectly, in a little wrapper template:
// provided by the FSM framework
template <class Event>
struct on
{
typedef Event type;
};
...
// Current Event Next Action
// State State
STT[ Stopped |on<play>() | Playing |&fsm::start_playback ]
[ Stopped |on<open_close>()| Open |&fsm::open_drawer ]
That works in principle, but the syntax is starting to get a little bit heavy, obscuring event names with syntactic "noise." We might recover some of the readability by writing:
on<play> play_;
on<stop> stop_;
on<open_close> open_close_;
...
// Current Event Next Action
// State State
STT[ Stopped | play_ | Playing | &fsm::start_playback ]
[ Stopped | open_close_ | Open | &fsm::open_drawer ]
That's not bad at all. Unfortunately, there's one problem that is going to kill this lovely scheme. Remember our fourth design goal, "Efficiency?" The problem with all of the designs we've seen so far is that they are going to hurt the efficiency of our state machine in two ways:
We can avoid the cost of indirection through a function pointer on transition actions by passing the action member pointers as template arguments, as described in Chapter 9:
// Current Event Next Action
// State State
transition< Stopped, play, Playing, &fsm::start_playback >,
transition< Stopped, open_close, Open, &fsm::open_drawer >,
This syntax is not nearly so sweet, but we think it still looks sufficiently tabular. We can go a bit further in that direction just by moving the commas and adding comments:
// Current Event Next Action
// State State
// +---------+------------+---------+-----------------------+
row < Stopped , play , Playing , &fsm::start_playback >,
row < Stopped , open_close , Open , &fsm::open_drawer >,
// +---------+------------+---------+-----------------------+
row < Paused , play , Playing , &fsm::resume_playback >,
row < Paused , stop , Stopped , &fsm::stop_playback >,
row < Paused , open_close , Open , &fsm::stop_and_open >,
// +---------+------------+---------+-----------------------+
Although we had to replace transition with the less meaningful identifier row (so the example would fit on the page), the new format is more readable to our eye. This approach has two important practical advantages over previous attempts, no matter what layout you choose. First, it can be implemented using only type expressions, so there's no loss of efficiency due to a premature crossing of the compile-time/runtime boundary. Since the action function pointer is a template parameter, it is known at compile time and can be completely inlined. Second, because each row<...> instantiation is a type, we can pass a comma-separated list of them as parameters to an MPL sequence, and all the MPL tools for manipulating type sequences will be at our disposal. Now that we know the format we'd like to use for our transition table, we might as well choose the kind of C++ entity to which state names will refer. State machines are, well, stateful. In other words, they don't fit into the compile-time world of pure template metaprogramming very well. We need to be able to pass state names as template parameters to row<...>, but we also need to be able to store something representing any of the FSM's various states in a single data member. Integral constants meet both those constraints. Luckily, C++ gives us a convenient way to define collections of named integral constants with unique values:
enum states {
Stopped, Open, Empty, Playing, Paused
, initial_state = Empty
};
As you can see, we've defined an additional constant initial_state. We're endowing that particular identifier with special meaning: The framework will use it to decide the initial state of default-constructed FSM instances. 11.4.2. Putting It All TogetherExcept for a couple of small details, we've now explored all the syntactic aspects of the DSEL and are ready to show a complete example of how it might be used to describe a FSM:
// concrete FSM implementation
class player : public state_machine<player>
{
private:
// the list of FSM states
enum states {
Empty, Open, Stopped, Playing, Paused
, initial_state = Empty
};
// transition actions
void start_playback(play const&);
void open_drawer(open_close const&);
void close_drawer(open_ close const&);
void store_cd_info(cd_detected const&);
void stop_playback(stop const&);
void pause_playback(pause const&);
void resume_playback(play const&);
void stop_and_open(open_close const&);
friend class state_machine<player>;
typedef player p; // makes transition table cleaner
// transition table
struct transition_table : mpl::vector11<
// Start Event Next Action
// +---------+-------------+---------+---------------------+
row < Stopped , play , Playing , &p::start_playback >,
row < Stopped , open_close , Open , &p::open_drawer >,
// +---------+-------------+---------+---------------------+
row < Open , open_close , Empty , &p::close_drawer >,
// +---------+-------------+---------+---------------------+
row < Empty , open_close , Open , &p::open_drawer >,
row < Empty , cd_detected , Stopped , &p::store_cd_info >,
// +---------+-------------+---------+---------------------+
row < Playing , stop , Stopped , &p::stop_playback >,
row < Playing , pause , Paused , &p::pause_playback >,
row < Playing , open_close , Open , &p::stop_and_open >,
// +---------+-------------+---------+---------------------+
row < Paused , play , Playing , &p::resume_playback >,
row < Paused , stop , Stopped , &p::stop_playback >,
row < Paused , open_close , Open , &p::stop_and_open >
// +---------+-------------+---------+---------------------+
> {};
};
One new detail above is that player's base class is being granted friendship. Because all of player's nested definitionsits states, transition table, and actionsare exclusively for use by the state machine framework, and not for public consumption, we've marked them private. Aside from its default constructor, the state machine's public interface consists solely of the process_event member function that will be supplied by its base class. The other detail we ought to discuss is the use of the Curiously Recurring Template Pattern (CRTP), in which player is derived from state_machine<player>.[4] Like many of our other DSEL design choices, this one is driven by C++ language constraints. Consider how row might be declared so that it can accept a pointer-to-member-function of player as a template argument. It would have to be something like:
template <
int CurrentState
, class Event
, int NextState
, void (player::*) (Event const&)
>
struct row
{ ... };
In other words, row needs to know the type of player. We could ask the author of player to supply the FSM type herself, as an initial template parameter:
template<
class Fsm // explicit FSM specification
, int CurrentState
, class Event
, int NextState
, void (Fsm::*action)(Event const&)
>
struct row
{ ... };
That approach would add an extra column to the transition tablea column full of nothing more than redundant copies of the same class name. Since C++ already requires the state machine author to qualify all member function pointers with the FSM class name, we'd just be adding insult to injury. With CRTP, however, the FSM author passes the class name once, to the base class template state_machine. Since state_machine has full access to the derived class name, it can supply a convenient nested row template for that particular Derived state machine:
template<class Derived>
class state_machine
{
...
protected:
template<
int CurrentState
, class Event
, int NextState
, void (Derived::*action)(Event const&)
>
struct row
{
// for later use by our metaprogram
static int const current_state = CurrentState;
static int const next_state = NextState;
typedef Event event;
typedef Derived fsm_t;
// do the transition action
static void execute(Derived& fsm, Event const& e)
{
(fsm.*action) (e);
}
};
};
Notice that we've filled in the body of row above. The nested definitions serve only one purpose: They allow convenient access to the values of row's template parameters. It may seem a little strange that the action parameter is accessed through an execute function that calls it; unfortunately, in C++ a nested constant member pointer can never be a compile-time constant. Had action been assigned to a static const member like the other template parameters, calls through it would not be inlined. |
|
|