乐趣区

关于c++17:谈-C17-里的-State-模式之一

jiezi

回顾状态模式，思考实作它的各种问题——特地是无关如何实现一个状态机的问题。同时，这一篇呢，可能不得不分几篇，因为写的时候脑壳在发散嘛，于是就关联失去的、能想起来的都提了一嘴，就多了。然而最初还是会给出代码的，我喜爱写代码的。

注：

文中不会做固定式实践介绍（像通常的 Design Patterns 书籍那样的固定版式），你须要相干背景常识的初步理解；有深刻理解更好，有助于互相印证。

然而你也能够全无理解，藉此入门后再进入教科书。为此我也致力束缚术语的准确应用，尽力不带来误会。

本文应该是无趣的，我只是在整顿。

Prologue

状态模式，是指一个对象 A 领有多种不同的状态，当特定条件满足时，对象 A 由一种状态切换到另一种，且在不同状态时（可能）具备不同的外在体现。据此，对象 A 将总是有一个开始状态 S，当状态正在产生转换时，咱们说前一状态为以后状态 C，而将要转换到的状态为下一状态 N。而当状态转换实现时，以后状态也就切换到了下一状态。

如果有必要，状态模式可能存在着一个终止状态 T。对于一段输出序列来说，如果输出完毕，可能会触发到迁徙到终止状态；或者特定的标记（Token）会做出这样的触发，例如 Pascal 语言翻译机在遇到 END. 标记时就完结一个编译单元的编译解决。

从狭义上讲，状态模式和状态机、编译器有着亲密乃至于等价的关系。你能够把状态模式视为简版的编译器，这算是一种约定俗成的习语。而少数语境里，大家对状态模式和状态机不作辨别，但有的时候，如果咱们的探讨语境较为学术性时，那么多半会采纳状态机这一术语。

2021-09-07 23:35

State Pattern

实践

状态模式是一种结构型的设计模式，它往往和状态机、无限状态机、自动机、编译原理、UML 状态图等近似或关联性概念一起被混用以及同时提起。

一般来说，咱们认为状态模式就是状态机的一种实现范式。因而本文中会将状态模式与 如何实现一个状态机 等同起来。

提到状态机，它首先示意的是一个对象领有一系列状态，并且可能在状态之间互相状态，而当产生转换时则会触发特定的动作 Action（分为进入动作 Entry Action 和退出动作 Exit Action，以及输出动作 Input Action，有时候也包含转移动作 Transition Action），并体现出不同的外在形象。

分类

状态机 / 自动机（Automaton）能够被分为多种类别：

  1. 接受器 / 识别器 / 序列检测器，Acceptors – 例如 gcc 这样的编译器承受一个正规文法序列，正确实现编译的序列则被认为是 可承受的。
  2. 变换器，Transducers – 重点在于给定输出能够引发动作，生成输入。这一类状态机还能够细分为两个小类：Moore Machine 和 Mealy Machine。

除了上述的次要划分之外，还有其它分类形式。

例如分类器 Classfiers 和序列（时序 / 音序等）测定器 / 生成器 Sequencers。将多个接受器依照确定性与否，则可划分为 DFA 与 NFA 等。在确定型自动机（DFA）中，每个状态对每个可能输出只有准确的一个转移。在非确定型自动机（NFA）中，给定状态对给定可能输出能够没有或有多于一个转移。

等等。

Moore Machine

Moore Machine 的特点是只应用进入动作，就是说输入只依赖于以后状态，与输出信号（如果有）无关。

例如电梯门的运行到站和超时时开闭的状态图：

图示中，从状态 Opened 只能迁徙到 Closed，当进入到 Opened 时其进入动作 open door 会导致电机启动并开门，而从状态 Closed 也只能迁徙到 Opened，其进入动作 close door 导致电机反向启动并关门。

图示中没有绘制的是外界反馈或者外部反馈，例如开门工夫超时状态机推动到关门状态、或者电梯运行到楼层导致推动到开门状态，但咱们考查的只是一个子系统，从而得以演示出摩尔机的概念。如果咱们用不同的其它尺度来察看电梯门零碎，则可能产生其余后果。

由上例可见，Moore 机的状态转换只依赖于以后状态，只应用进入动作，相对来说是很简略的。

对于 Moore 机来说，状态转换须要一个推动力，这是通常的状态机教材没有显示提及的。通常状态机不可能自行驱动本身从一个状态变迁到另一状态，所以它须要一个驱动力。在上例电梯门的 Moore 机中，Somebody 按下开门关门钮就是这个驱动信号。

Mealy Machine

Mealy Machine 的状态切换依赖于输出动作以及以后状态，它比摩尔机更简单一点，但同时也经常因而而使得其状态图更简略简洁。例如电梯门被开闭的状态图：

图示中，因为开门按钮按下（sensor opened）导致电梯门从 closed 状态切换到 opened，因为关门按钮按下（sensor closed）导致反向转换。

和摩尔机的示例有所不同，这个例子中视角聚焦在电梯门是如何受到传感器信号的触发而扭转的。

同样的情理，这个例子也有驱动信号的存在：只管同样是开门关门按钮按下导致门开门关，但驱动信号在这个例子中是门开门关传感器所产生的信号，传感器检测到门开门关动作后发出信号，以标示电梯门进入到新的状态（门已开，门已关）。所以同一个事件，精密考查不同的部分，会失去不同的论断。

TCP 的状态跃迁图

TCP 的状态跃迁图可能很好地展现状态的切换：

FROM: PDF – TCP/IP State Transition Diagram (RFC793)

为了帮忙不相熟的敌人多角度观察，这里也提供另一张图可供互相佐证：

FROM: The TCP/IP Guide – TCP Operational Overview and the TCP Finite State Machine (FSM)

实现办法介绍

能够有几种形式来实现一个状态机 / 状态模式（能够被称作自动机编程范式）：

  1. 齐全手写条件和转换
  2. 查表法
  3. DFA 技术

实现状态模式最直觉的办法，是采纳一系列的 if..else 或者 switch 语句，但这种形式在状态较多，转换门路简单时将会很被动。一个简短的例子如下：

#include <stdio.h>
enum states {before, inside, after};
void step(enum states *state, int c) {if(c == '\n') {putchar('\n');
    *state = before;
  } else
    switch(*state) {
      case before:
        if(c != ' ') {putchar(c);
          *state = inside;
        }
        break;
      case inside:
        if(c == ' ') {*state = after;} else {putchar(c);
        }
        break;
      case after:
        break;
    }
}

int main(void) {
  int c;
  enum states state = before;
  while((c = getchar()) != EOF) {step(&state, c);
  }
  return 0;
}

所以一般来说的正确实现形式是利用一张二维的转换表，通过查表的形式求得下一状态从而实现转换。而开发者首先要做的就是剖析需要并编制出这么一张转换表再说。

另外，在 C++ metaprogramming 世界里，通常就不会应用一张明确的转换表了，代替这张表的伎俩是利用 hash_map 的形式建设从状态 from 到 to 的转换关系。这种形式在咱们后边的具体实现中会有一个展现。然而它依然是一种查表法。

稍后再粗略议论 FSM（编译原理中的 FSM）和 DFA 技术的实现概要。

查表法

状态机的转换规则能够示意为一张二维的状态转移表，像这样：

在理论场景中，这张表往往是比拟稠密的，很多交叉点是没有到下一状态的跃迁可能性的，所以这张表所映射到的二维数组通常都能够采取肯定的措施以将其压缩下来，压缩的后果除了能显著升高表的存储空间之外，也有可能显著地升高扫描这张表的速度。

对于无需参考输出条件的 Moore 机来说，没有纵向的条件表，代替它的是一个枯燥的信号，该信号促使状态机产生步进动作，因而条件表仍然是无效的。

FSM，NFA 和 DFA

真正实用的状态模式实现伎俩，都是采纳查表法的。

如果不是，那么它们采纳的是查表法的某种模式的变体。

在将实践进一步深刻之后，状态模式能够回升到无限状态机（FSM，Finite-State Machine）的高度，在这一档次钻研雷同的状态机问题时，咱们将会采纳在编译原理中必备的根底钻研形式。

面对一台 FSM，咱们首先是列举并绘制出状态变迁图，而后通过技术手段（典型地如 Thompsion 结构法）将文法形容转换为 NFA（Nondeterministic Finite Automaton，非确定性无限状态机），而后借助于通过了严格证实的实践将 NFA 转换为 DFA（Deterministic Finite Automaton，确定性无限状态机）。值得一提的是，NFA 到 DFA 的转换也是个刻板无趣的过程，并且往往会导致新增大量的中间性过渡型状态，所以 DFA 可能比 NFA 大很多倍。一个 DFA 的数据结构示意，通常是一张微小的、通过了规约之后的二维数组（等效于后面所形容的二维的转换表），面对输出的字符集，在这个转换表中可能间接求得下一状态。同时，这张表中的空洞也很多，这是因为从一个状态到另一个状态的变迁关系当然不会是笛卡尔积的，所以说它总是会是一张稠密的二维数组。

言归正传，通过一系列的正规文法上的束缚和求解之后，咱们总是可能从正规文法的形容上取得对应的转换表，这是经由了数学证实后的论断。最终，咱们（通常、常常）须要压缩规范的 DFA，将其所占据的宏大的空间进行膨胀，但功能不变，就造成了最初的 FSM 工作机。

上述的过程能够提炼为：

  1. 绘制状态变迁图
  2. 计算 NFA
  3. 转换为 DFA
  4. 压缩 DFA
  5. 配套一个查表算法的代码

个别地，在编译器畛域，实现下面一系列操作的货色叫做编译器的编译器，这会应用术语 LEX 来简称，因为近代以来基本上是 Flexible LEX 一家独大，所以咱们经常也称之为 FLEX（这是 Unix/Linux 零碎上的一个软件，事实上的编译器畛域的准则和规范）。而由 LEX 所创立进去的则是编译器（等效于 gcc），而编译器则被看作是可能吃进一段合乎某种文法的源代码的机器，这台机器解释源代码的词法和语法为机器码，每当吃进一个 token 时，编译器就推动外部状态从前一状态迁徙到下一状态，同时做出肯定的反馈（解决某些 action）。

当然，实用的少数编译器的 FSM 局部，也即编程语言的文法翻译局部，除了实践钻研时采纳 Flex & Bison（也即 LEX & YACC）之外，事实实现中往往采纳手写来实现，起因在于手写版本能够糅合编码人的脑力规约，经常在特定状态的翻译时显著地缩减编译的资源需要，这是面对现实世界时的一种斗争与抉择，不提。

如果对无限状态机以及 NFA -> DFA 感兴趣，请浏览编译原理的经典教材。

所谓非确定性无限状态机 NFA/NDFA，是指给定状态对于给定输出能够有任意多个转移（0..N）。此时若要想正确实现转换，可能须要向后持续预观察和预匹配能力一次性地间断转进多个状态。

而确定性无限状态机 DFA 的每个状态对于每个可能的输出有且只有一个准确的转移。

可见对于 CPU 运算来讲咱们最终须要一个 DFA 模型能力无效运行，而 NFA 则会导致咱们的解决逻辑过分简单（look-ahead）甚至于齐全无奈实现。学术研究在上世纪 5、60 年代就曾经确定了任何正规文法的 NFA 均可能被转换为等价的 DFA（代价是更多更简单的中间状态，参考 Kleene 闭包）。

因而才会有 LEX（一种 Unix 软件）工具的呈现。

这种实现形式十分正统与学院派，然而因为它与编译原理的分割如此严密，因而通常在非编译器实现的其它畛域中，咱们总是称说自动机为状态机，并且实现形式更多地偏向于不采纳 DFA 手法。

这只是通常状况，没有人能阻止你用牛刀杀鸡。

另外转头思考，DFA 技法实际上隐含着一个前提，它的事件激励是通过流式输出的元素序列来达到的，所以对于编译器来说吃进字符序列是个牵强附会的机制，而在这个畛域中也倒退了正规文法以及正则式等一系列关联性实践，它们之间都是相辅相成的。而 DFA 技法被利用在其它场合中时就有点麻烦、或者说不合理了。只管咱们还是能够将事件信号采纳某种形式流化（例如一连串的鼠标事件以及键盘事件被串行化后通过音讯泵传送到散发器时，散发器也能够结构一个 DFA 模式的表格来实现状态迁徙、顺便再触发相干的 action，也没什么不能够），但这就不肯定是实作时的最佳抉择了：所以 UI 音讯散发器通常还是采纳动作函数的到事件发生器（sender）的绑定形式，这样做有利于代码保护和相干逻辑的保护，若是用一张 DFA 表呢，这个保护就很艰巨了。

OK，在本文中，咱们采纳 FSM 术语来暗指 FSM 以及 NFA 以及 DFA 等一系列特有的技术概念与实现，并隐含着它们将在编译原理的上下文中被提及。此外咱们将其它状况中的状态模式称为实现一个状态机。

然而在其它文章中，FSM 可能仅仅只是蕴含状态机而不用回升到 DFA 计算档次。

进一步的分类

在经典的状态机实践之上，UML 标准提供了加强的状态机算法模型。相比较而言，UML 状态机（绘制成 UML 图时就叫做 state chart）的加强之处在于：

  1. HFSM，Hierarchy FSM，即所谓层级状态机、分层状态机、嵌套状态机。中文叫法多样，但却是同一个货色，也就是说在大的状态机里某个状态蕴含了一组成系列的子级状态机。

    举个例子，计算器具备开、关状态，而开机后的计算机又有输出状态、求值状态、间断求值状态等等一系列子状态。

    https://en.wikipedia.org/wiki…

  2. 正交区域 Orthogonal regions
  3. 等等

HFSM 在游戏开发畛域中、芯片设计、FPGA 设计、PLC 设计等场合里十分常见。

有时候咱们也能够将一般的状态机进行形象后形成更细腻的分区，从而失去 HFSM 的状态，例如编译器在解释可嵌套的正文块时，实际上就进入了子状态机的工作模态，但有别于正规的 HFSM 解决流程的是，编译器对于子状态往往是直白地用额定的代码（action）对其予以解决，并不将其流程化、或者表格化。

谈到 HFSM 时经常又会同时提到另一个概念：行为树（Behavior Tree）。行为树这种货色并不是一个 良好 的算法表述（在一棵树上遍历节点时、节点的个性齐全不同），它实际上是给人看的，是一种 HFSM 的图解形式。换句话说，行为树的随意性较高，没有良好的约束条件，所以须要管理者付出额定力量来保障不会产生抵触和竞争（例如在不同节点层次结构中的 actions 中）。

如果想更多理解 HFSM 以及 BT，能够看看：

PDF – HFSM & BT – stanford cs123

游戏业中喜爱讲行为树我的实现如许有特点，如许 AI，是的，从不同的角度实现 FSM 是十分有价值的，它使得状态迁徙的规定更易于被治理，不过这玩意和 AI 还是搭不上界的。

小小结

一般来说，咱们认为状态模式就是状态机的一种实现范式。因而本文中会将状态模式与如何实现一个状态机等同起来。

因为在计算机科学中咱们总是钻研状态数规模具备下限的状态机，所以咱们所实现的状态机也将总会是一种无限状态机（FSM）。FSM 通常与编译原理紧密结合。

无论如何，还是要总结一下：

状态模式通常能够被看作为 FSM 的轻量级版本。这是因为经常咱们会认为大量状态的变迁能够间接手写（包含手工结构状态转换表），不用引入严格的实践求证作为根据。而一旦状态变迁规模变大，或者工程需要提出了严格的指标要求时，那么咱们就应该采纳 FSM 形式（DFA 形式）来确保编码实现的冥等性。

像 TCP 的状态变迁，规模不大，齐全能够手写，除非你心愿做严格的实践推导或者学术研究，否则泰半无需调兵遣将。然而对于现代化的 RegExp 进行翻译和解释，手写通常行不通（也不相对，的确曾有团队是硬撸的），只能借助于 Kleene 闭包的伎俩实现到 DFA 的翻译后实现结构，而那是十分省力的。

下一部分

只能留待下一篇再来议论具体的实现案例了。

Epilogue

未完待续。

退出移动版