C++是一门非常适合用来构建DSL(Domain Specific Language)的语言，它的多范式特点为它提供了丰富的工具，尤其是C++提供了：
- 一个静态类型系统；
- 近似于零抽象惩罚的能力（包括强大的优化器）；
- 预处理宏，能够以文本替换的方式操纵源代码；
- 一套丰富的内建符号运算符，它们可以被重载，且对重载的语义几乎没有任何限制；
- 一套图灵完备的模板计算系统（模板元编程），可以用于：
- 生成新的类型和函数；
- 在编译期执行任何计算；
- 提供静态反射的能力；
结合这些武器，使得通过C++构建兼顾语法表达力及运行时效率的DSL成为了可能。可以说，模板元编程是上述所有武器中最为重要的，接下来我们使用模板元编程设计一个用于描述有限状态机(FSM)的DSL。该设计最初来自于《C++模板元编程》一书，由于作者在书中所举状态机的例子比较晦涩，而且实现使用了更晦涩的boost mpl库，为了让这个设计更加易懂并且代码更加清晰，我对例子和代码进行了重新设计。
有限状态机(FSM)是计算机编程中非常有用的工具，它通过抽象将紊乱的程序逻辑转换成更易于理解的形式化的表达形式。
有限状态机的领域模型由三个简单的元素构成：
-
状态（state）：FSM某一时刻总是处于一个状态中，不同状态决定了FSM可响应的事件类型以及响应的方式。
-
事件（event）：事件触发FSM状态的改变，事件可以携带具体信息。
-
转换（transition）：一个转换标记了在某个事件的激励下FSM从一个状态到另一个状态的跃迁。通常转换还会有一个关联动作（action），表示在状态跃迁时进行的操作。将所有的转换放在一起可以构成一个状态转换表（State Transition Table，STT）。
我们假设有一个跳舞机器人，它的状态转换关系如下图：
图可能是表示FSM最直观的工具了，但是如果图中出现太多的细节就会导致很凌乱，例如上图为了简洁就没有标示每个转换对应的action。为了让FSM的表示更加形式化，我们将其装换成如下表格的形式：
| Current State | Event | Next State | Action |
|---|---|---|---|
| closed | open | opened | sayReady |
| opened | close | closed | sayClosed |
| opened | play | dancing | doDance |
| dancing | stop | opened | sayStoped |
| dancing | close | closed | sayClosed |
如上，对于跳舞机器人，它有三种状态：closed，opened，dancing；它可以接收四种事件：close，open，play，stop；它有四个action：sayReady，sayClosed，doDance，sayStoped。上表中的每一行表示了一种可以进行的转换关系。用表格来表示FSM同样易于理解，而且这种表示是相对形式化的，且容易通过代码来描述。
对于这样一个由FSM表示的跳舞机器人，最常见的实现如下：
// Events
struct Close {};
struct Open {};
struct Play
{
std::string name;
};
struct Stop {};
// FSM
struct DanceRobot
{
void processEvent(const Open& event)
{
if(state == closed)
{
sayReady(event);
state = opened;
}
else
{
reportError(event);
}
}
void processEvent(const Close& event)
{
if(state == opened)
{
sayClosed(event);
state = closed;
}
else if(state == dancing)
{
sayClosed(event);
state = closed;
}
else
{
reportError(event);
}
}
void processEvent(const Play& event)
{
if(state == opened)
{
doDance(event);
state = dancing;
}
else
{
reportError(event);
}
}
void processEvent(const Stop& event)
{
if(state == dancing)
{
sayStoped(event);
state = opened;
}
else
{
reportError(event);
}
}
private:
// Actions
void sayReady(const Open&)
{
std::cout << "Robot is ready for play!" << std::endl;
}
void sayClosed(const Close&)
{
std::cout << "Robot is closed!" << std::endl;
}
void sayStoped(const Stop&)
{
std::cout << "Robot stops playing!" << std::endl;
}
void doDance(const Play& playInfo)
{
std::cout << "Robot is dancing (" << playInfo.name << ") now!" << std::endl;
}
template<typename Event>
void reportError(Event& event)
{
std::cout << "Error: robot on state(" << state
<< ") receives unknown event( "
<< typeid(event).name() << " )" << std::endl;
}
private:
// States
enum
{
closed, opened, dancing, initial = closed
}state{initial};
};
int main()
{
DanceRobot robot;
robot.processEvent(Open());
robot.processEvent(Close());
robot.processEvent(Open());
robot.processEvent(Play{.name = "hip-hop"});
robot.processEvent(Stop());
robot.processEvent(Close());
robot.processEvent(Stop()); // Invoke error
return 0;
}
上面的代码中为了简化只有Play事件携带了消息内容。Robot通过函数重载实现了processEvent方法，用于处理不同的消息。reportError用于在某状态下收到不能处理的消息时调用，它会打印出当前状态以及调用运行时RTTI技术打印出消息类名称。
通过代码可以看到，上面的实现将整个有限状态机的状态关系散落在每个消息处理函数的if-else语句中，我们必须通过仔细分析代码逻辑关系才能再还原出状态机的全貌。当状态机的状态或者转换关系发生变化时，我们必须非常小心地审查每个消息处理函数，以保证修改不出错。而且当状态和事件变多的时候，每个函数的if-else层数将会变得更深。
如果你精通设计模式，可能会采用状态模式改写上面的代码。状态模式为每个状态建立一个子类，将不同状态下的消息处理函数分开。这样当我们修改某一状态的实现细节时就不会干扰到别的状态的实现。状态模式让每个状态的处理内聚在自己的状态类里面，让修改变得隔离，减少了出错的可能。但是状态模式的问题在于将状态拆分到多个类中，导致一个完整的FSM的实现被分割到多处，难以看到一个状态机的全貌。我们必须在多个状态类之间跳转才能搞明白整个FSM的状态关系。而且由于采用了虚函数，这阻止了一定可能上的编译期优化，会造成一定的性能损失。
有经验的C程序员说可以采用表驱动法来实现，这样就可以避免那么多的if-else或者子类。表可以将状态机的关系内聚在一起，从而展示整个FSM的全貌。表是用代码表示FSM非常好的一个工具，可惜C语言的表驱动需要借助函数指针，它和虚函数本质上一样，都会导致编译器放弃很多优化，性能都没有第一种实现高。
那么有没有一种方法，让我们可以以表来表示整个FSM，但是运行时效率又能和第一种实现相当？前面我们说了，可以利用模板元编程的代码生成能力。我们利用模板元编程创建一种描述FSM的DSL，让用户可以以表的形式描述一个FSM，然后在C++编译期将其生成类似第一种实现的代码。这样我们即得到了吻合于领域的表达力，又没有造成任何运行时的性能损失！
接下来我们看看如何实现。
既然提到了使用表来表达，那么我们已经有了一种熟识的编译期表数据结构了，没错，就是TypeList。TypeList的每个元素表示一个转换（transition），代表表的一行。按照前面给出的DanceRobot的表格表示，每行应该可以让用户定义：当前状态，事件，目标状态，以及对应的action。所以我们定义一个模板Row，它的参数是：int CurrentState, typename EventType, int NextState, void(Fsm::*action)(const EventType&)，一旦它具现化后将表示一个transition，作为状态转换表的一行。
除了表之外，用户还应该负责给出表中元素的定义，包括每个状态、事件和action的定义。我们希望整个DSL框架和用户的代码分离开，用户在自己的类中定义state，event，action以及转换表，然后DSL框架负责为用户生成所有的事件处理函数processEvent。
有了上面的思考后，我们通过DanceRobot展示我们构思的DSL的用法：
// Events
struct Close {};
struct Open {};
struct Play
{
std::string name;
};
struct Stop {};
// FSM
struct DanceRobot : fsm::StateMachine<DanceRobot>
{
private:
friend struct StateMachine<DanceRobot>;
enum States
{
closed, opened, dancing, initial = closed
};
// actions
void sayReady(const Open&)
{
std::cout << "Robot is ready for play!" << std::endl;
}
void sayClosed(const Close&)
{
std::cout << "Robot is closed!" << std::endl;
}
void sayStoped(const Stop&)
{
std::cout << "Robot stops playing!" << std::endl;
}
void doDance(const Play& playInfo)
{
std::cout << "Robot is dancing (" << playInfo.name << ") now!" << std::endl;
}
// table
using R = DanceRobot;
using TransitionTable = __type_list(
// +----------+----------+----------+----------------+
// | current | event | target | action |
// +----------+----------+----------+----------------+
Row < closed , Open , opened , &R::sayReady >,
// +----------+----------+----------+----------------+
Row < opened , Close , closed , &R::sayClosed >,
Row < opened , Play , dancing , &R::doDance >,
// +----------+----------+----------+----------------+
Row < dancing , Stop , opened , &R::sayStoped >,
Row < dancing , Close , closed , &R::sayClosed >
// +----------+----------+----------+----------------+
);
};
如上，我们希望客户只用定义好Event，State，Action以及按照DSL的语法定义TransitionTable。最终所有消息处理函数的生成全部交给DSL背后的fsm::StateMachine框架，它负责根据TransitionTable生成所有类似前面第一种实现中的processEvent函数，并且要求性能和它相当。fsm::StateMachine框架是和用户代码解耦的，它独立可复用的，用户类通过我们之前介绍过的CRTP技术和它进行组合。
通过例子可以看到，TransitionTable的描述已经非常接近手工描述一张状态表了，我们基本没有给用户带来太多偶发复杂度，更重要的是我们完全通过编译时代码生成技术来实现，没有为用户带来任何运行时效率损失。
接下来我们具体看看StateMachine的实现。
template<typename Derived>
struct StateMachine
{
template<typename Event>
int processEvent(const Event& e)
{
using Dispatcher = typename details::DispatcherGenerator<typename Derived::TransitionTable, Event>::Result;
this->state = Dispatcher::dispatch(*static_cast<Derived*>(this), this->state, e);
return this->state;
}
template<typename Event>
int onUndefined(int state, const Event& e)
{
std::cout << "Error: no transition on state(" << state
<< ") handle event( " << typeid(e).name()
<< " )" << std::endl;
return state;
}
protected:
template< int CurrentState,
typename EventType,
int NextState,
void (Derived::*action)(const EventType&) >
struct Row
{
enum
{
current = CurrentState,
next = NextState
};
using Fsm = Derived;
using Event = EventType;
static void execute(Fsm& fsm, const Event& e)
{
(fsm.*action)(e);
}
};
protected:
StateMachine() : state(Derived::initial)
{
}
private:
int state;
};
上面是StateMachine的代码实现，不要被这么一大坨代码吓住，我们一步步分析它的实现。
先来看它的构造函数：
StateMachine() : state(Derived::initial)
{
}
int state;
它的内部有一个私有成员state，用来存储当前的状态。它的构造函数把state初始化为Derived::initial。得益于CRTP模式，我们在父类模板中可以使用子类中的定义。StateMachine要求其子类中必须定义initial，用来指明初始状态值。
接来下`onUndefined函数定义了当收到未定义的消息时的默认处理方式。可以在子类中重定义这个方法，如果子类中没有重定义则采用此默认版本。
template<typename Event>
int onUndefined(int state, const Event& e)
{
std::cout << "Error: no transition on state(" << state
<< ") handle event( " << typeid(e).name()
<< " )" << std::endl;
return state;
}
接下来内部的嵌套模板Row用于子类在表中定义一行transition。它的四个模板参数分别代表当前状态、事件类型、目标状态以及对应action的函数指针。注意由于采用了CRTP模式，这里我们直接使用了子类的类型Derived来声明函数指针类型void (Derived::*action)(const EventType&)。
template< int CurrentState,
typename EventType,
int NextState,
void (Derived::*action)(const EventType&) >
struct Row
{
enum
{
current = CurrentState,
next = NextState
};
using Fsm = Derived;
using Event = EventType;
static void execute(Fsm& fsm, const Event& e)
{
(fsm.*action)(e);
}
};
上面在Row中通过定义execute方法，对action的调用进行了封装，统一了所有action的调用形式。原有的每个action名称不同，例如sayReady、sayStoped...，后续可以统一通过调用Row::execute的方式进行使用了。借助封装层来统一不同方法的调用形式是一种非常有用的设计技巧。
最后我们来看StateMachine的processEvent函数实现。
template<typename Event>
int processEvent(const Event& e)
{
using Dispatcher = typename DispatcherGenerator<typename Derived::TransitionTable, Event>::Result;
this->state = Dispatcher::dispatch(*static_cast<Derived*>(this), this->state, e);
return this->state;
}
该函数是一个模板方法，它的入参是待处理的消息，为了支持每种消息，将消息的类型定义为泛型。为了方便客户获取转换后的目标状态，函数结束时返回最新的状态。我们期望它对于任一种合法的入参消息类型，可以自动生成它的处理逻辑。
例如对于DanceRobot的Close消息，我们希望它可以自动生成如下代码：
int processEvent(const Close& event)
{
if(state == opened)
{
sayClosed(event);
state = closed;
}
else if(state == dancing)
{
sayClosed(event);
state = closed;
}
else
{
reportError(event);
}
return this->state;
}
而这所有神奇的事情，都是通过如下两句代码完成的：
using Dispatcher = typename DispatcherGenerator<typename Derived::TransitionTable, Event>::Result;
this->state = Dispatcher::dispatch(*static_cast<Derived*>(this), this->state, e);
上面第一句，我们通过把状态表Derived::TransitionTable和当前事件类型交给DispatcherGenerator，通过它得到了Dispatcher类型。从第二句中我们知道Dispatcher类型必须有一个静态方法dispatch，它接收当前状态和事件对象，然后完成所有的处理逻辑。
所以一切的关键都在于DispatcherGenerator<typename Derived::TransitionTable, Event>::Result所做的类型生成。它能够根据状态转化表以及当前类型，生成正确的处理逻辑。那么DispatcherGenerator怎么实现呢？
我们再来看看如下DanceRobot的Close消息处理函数的实现：
if(state == opened)
{
sayClosed(event);
state = closed;
}
else if(state == dancing)
{
sayClosed(event);
state = closed;
}
else
{
reportError(event);
}
我们发现，它的实现是形式化的。就是根据当前消息类型Close，在状态转换表Derived::TransitionTable中找到所有可以处理它的行：
// +----------+----------+----------+----------------+
// | current | event | target | action |
// +----------+----------+----------+----------------+
Row < opened , Close , closed , &R::sayClosed >,
Row < dancing , Close , closed , &R::sayClosed >
TypeList已经有__filter元函数，它根据一个指定的规则，将TypeList中所有满足条件的元素过滤出来，返回由所有满足条件的元素组成的TypeList。接下来要做的是用过滤出来的行，递归地完成如下模式的if-else结构：
template<typename Transition, typename Next>
struct EventDispatcher
{
using Fsm = typename Transition::Fsm;
using Event = typename Transition::Event;
static int dispatch(Fsm& fsm, int state, const Event& e)
{
if(state == Transition::current)
{
Transition::execute(fsm, e);
return Transition::next;
}
else
{
return Next::dispatch(fsm, state, e);
}
}
};
最后的一个else中调用未定义消息的处理函数：
struct DefaultDispatcher
{
template<typename Fsm, typename Event>
static int dispatch(Fsm& fsm, int state, const Event& e)
{
return fsm.onUndefined(state, e);
}
};
到此，基本的思路清楚了，我们把上述生成processEvent函数的这一切串起来。
template<typename Event, typename Transition>
struct EventMatcher
{
using Result = __is_eq(Event, typename Transition::Event);
};
template<typename Table, typename Event>
struct DispatcherGenerator
{
private:
template<typename Transition>
using TransitionMatcher = typename EventMatcher<Event, Transition>::Result;
using MatchedTransitions = __filter(Table, TransitionMatcher);
public:
using Result = __fold(MatchedTransitions, DefaultDispatcher, EventDispatcher);
};
上面我们首先使用__filter(Table, TransitionMatcher)在表中过滤出满足条件的所有transition，将过滤出来的TypeList交给MatchedTransitions保存。TransitionMatcher是过滤条件，它调用了EventMatcher去匹配和DispatcherGenerator入参中Event相同的Transition::Event。
最后，我们对过滤出来的列表MatchedTransitions调用__fold元函数，将其中每个transition按照EventDispatcher的模式去递归折叠，折叠的默认参数为DefaultDispatcher。如此我们按照过滤出来的表行，自动生成了递归的if-else结构，该结构存在于返回值类型的静态函数dispatch中。
这就是整个DSL背后的代码，该代码的核心在于利用模板元编程递归地生成了每种消息处理函数中形式化的if-else嵌套代码结构。由于模板元编程的所有计算在编译期，模板中出现的封装函数在编译期都可以被内联，所以最终生成的二进制代码和最开始我们手写的是基本一致的。
如果对本例的完整代码该兴趣，可以查看TLP库中的源码，位置在"tlp/sample/fsm"中。
网友评论