{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 有限状态机"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"有限状态机（*finite state machine*，简称 *FSM*），有时也被称为 *finite state automation*，有时就简单地叫 *state machine*，不属于一看就知道大概是什么的概念（这一点和前面我们讲过的都不一样）。有限状态机有相当深刻的理论背景，算是比较高级的东西了，很多程序员别说学校里，工作十年可能都没碰过这东西，但其实真的不难理解，而且学会了就爱不释手，因为它解决某些问题真是太好用了。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 什么是有限状态机"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"其实我们身边到处都是“有限状态机”的例子，最简单的一个是灯：灯有两种状态：“亮”和“熄”，灯可以从一种状态变成另一种，“亮”的状态下接收到“关”的指令就会变成“熄”，“熄”的状态下接收到“开”的指令就会变成“亮”，就像下图这样："
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<img src=\"assets/fsm-1.png\" width=\"360\">"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"在这个图里，圆圈表示“状态（*state*）”，箭头代表状态间可以发生的“转换（*transition*）”，而箭头上标注的文字代表触发状态转换的“输入（*input*）”。这基本上就是状态机的三大要件了。\n",
"\n",
"灯只有两个状态，不算很有意思，我们可以再看一个常见的例子：红绿灯，我们熟知的红绿灯的颜色按照“绿 -> 黄 -> 红 -> 绿”这样的顺序循环变化——嗯，我知道有的还有“绿灯闪烁”之类的状态，不过我们这里简化一下，用有限状态机来描述大致如下图："
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<img src=\"assets/fsm-2.png\" width=\"500\">"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"这里：\n",
"* 有三种状态：绿，黄，红；\n",
"* 状态转换是受限的，绿只能转黄，黄只能转红，红只能转绿；诸如黄转绿这样的状态转换是不允许的；\n",
"* 状态转换的输入条件很简单，接收到 1 就转换到下一个状态。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"所以简单来说，有限状态机就是一台包含了预先定义好的一组状态的机器，当机器接收到一个指令，就根据指令内容查一张预先定义好的表：\n",
"1. 检查当前状态是否接受这个指令；\n",
"2. 如果不接受，那就当无事发生；\n",
"3. 如果接受，再检查表中“当前状态x该指令”对应的目标状态是什么，然后把机器状态转换为目标状态。\n",
"\n",
"至于何时发送指令给状态机，是由外部系统决定的，比如红绿灯的例子里，外部系统是几个定时器，时间到了就发信号给有限状态机切换状态。\n",
"\n",
"有了现实生活中的例子打底，我们现在可以来看看抽象的“有限状态机（*FSM*）”是怎么定义的了。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<img src=\"assets/fsm-3.png\">"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"如上图所示，每一个 *FSM* 都包含五个要素：\n",
"* *Q* 包含了有限个状态（*states*）的集合；\n",
"* *Σ* 包含了有限个、非空的有效输入（*input*）的集合；\n",
"* *δ* 一系列转换函数（*transition functions*），定义了什么样的当前状态结合什么输入可以变成什么目标状态，通常可以定义为一张二维表（见上图）；\n",
"* *q<sub>0</sub>* 起始状态，并不是所有 *FSM* 都关心起始状态，比如红绿灯就无所谓起始状态；\n",
"* *F* 包含了所有“结束状态（*final states*）”的集合，这个名字容易误解，它的作用和有限状态机的具体类型及面对的问题有关，我们可以简单理解为“标记出来有特别含义的状态的集合”就可以了，注意这个集合可以是空的。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"以上图所示的 *FSM* 为例，\n",
"* 这个 *FSM* 有四个有效状态，*Q = { A, B C, D}*；\n",
"* 这个 *FSM* 只接受两个合法输入，*Σ = { 0, 1 }*；\n",
"* 当这个 *FSM* 接收到输入时，不在 *Σ = { 0, 1 }* 中的输入会被丢弃；如果输入在 *Σ* 中（是 *0* 或者 *1*），就查 *δ* 表，看看当前状态对应行和输入对应列的交叉点是什么状态，比如当前状态是 *A*，输入是 *1*，那么对应状态为 *C*，也就是说应该转换到状态 *C*。\n",
"* 起始状态 *q<sub>0</sub> = A* 和结束状态集 *F = { D }* 这两个对某些 *FSM* 来说很重要，比如正则表达式。\n",
"\n",
"> 正则表达式对应一大类有限状态机，主要用来解决“在一系列输入之后是什么状态”的问题，通过回答这个问题来判断输入序列是不是我们想要的，或者输入序列属于什么分类，这种状态机有很深刻的理论背景，有兴趣的话可以读一下计算理论（*computation theory*）的经典教材，比如[这本](https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X)；这类状态机还被广泛应用于人工智能（比如图像识别算法）中。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"在计算机编程领域 *FSM* 最广泛的应用之一是流程和行为控制（*flow and behavior control*），简单说就是管理：\n",
"* 在某个状态下什么能做什么不能做；\n",
"* 做了什么会变成另外的什么状态。\n",
"\n",
"游戏里[玩家行为控制](https://gameprogrammingpatterns.com/state.html)、[NPC（*non-player character*，非玩家角色）的 AI](https://gamedevelopment.tutsplus.com/tutorials/finite-state-machines-theory-and-implementation--gamedev-11867)、剧情任务流程等都是用 *FSM* 来实现的；所有的[工作流系统](http://b.xfreeservice.com/redir/clickGate.php?u=8otB939m&m=12&p=3b121G4eNI&t=33&splash=0&s=&q=state%20machine%20workflow&url=https%3A%2F%2Fdocs.microsoft.com%2Fen-us%2Fdotnet%2Fframework%2Fwindows-workflow-foundation%2Fstate-machine-workflows)都包含 *FSM*；还有电商核心系统之一的“订单系统”（*order system*）。\n",
"\n",
"我们用过淘宝都知道，一个订单从创建开始要经历好几个状态，中间也有不同的操作可以进行，下面是一个比较典型的流程设计，经过一定简化，并以“状态”的主视角来描绘："
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<img src=\"assets/fsm-4.png\">"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"图中圆边的矩形代表状态，最上面一排是“正常”的状态和流程；第二排的矩形则表示一些“逆向”子流程，通常是由用户或客户发起的特殊操作，这些操作会带来其他一些订单状态，为了简单起见没有在这里展开。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"流程说明：\n",
"* 当买家点击下单时订单生成，处于“已创建”状态；\n",
"* 这个状态下的正常操作是“支付”，如果输入“支付成功”会进入下一个状态“已支付”，“支付失败”或者没有任何操作则停在本状态；\n",
"* 这个状态下其他可选操作包括“修改”、“取消”等，分别会去到订单修改和订单取消子流程（这里略去细节）；\n",
"* 支付成功后进入处于“已支付”状态；\n",
"* 这个状态下需要等待商家发货，商家输入“已发货”会进入下一个状态“配送中”；\n",
"* 这个状态下不能修改订单了，但仍然可以取消订单；\n",
"* 商家发货后进入“配送中”状态；\n",
"* 当配送到货，买家签收成功输入则进入下一个状态“已签收”；如果配送失败（买家不在家之类的情况）则留在“配送中”状态（另外择时重新送货）；\n",
"* 这个状态下已不能修改和取消订单，但是可以发起退货申请，进入退货子流程（这里略去细节）；\n",
"* 买家签收后进入“已签收”状态；\n",
"* 买家满意，确认订单完成则进入最后状态“已完成”，订单生命周期结束；\n",
"* 否则买家可以发起退货进入退货子流程（略）。\n",
"\n",
"从这里我们可以看到，实际业务系统中状态和转换的规则相当复杂（我们这还是大大简化的版本），每个状态下允许的操作和可能转换的下一个状态都是严格受控的，现在我们思考一下，我们可以如何用程序来实现这样的流程呢？"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 利用有限状态机编写易于维护的代码"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"回忆我们之前提到的，流程和行为控制（*flow and behavior control*）的关键是管理：\n",
"* 在某个状态下什么能做什么不能做；\n",
"* 做了什么会变成另外的什么状态。\n",
"\n",
"最简单直接的办法就是书写一堆 `if...else` 的判断规则，大致会是这个样子："
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"class Order:\n",
" STATES = {'created', 'paid', 'delivering', 'received', 'done', 'cancelling', 'returning', 'closed'}\n",
" state = 'created'\n",
" \n",
" def can_pay(self):\n",
" return state == 'created'\n",
" \n",
" def can_deliver(self):\n",
" return state == 'paid'\n",
" \n",
" def can_cancel(self):\n",
" return state == 'created' or state == 'paid'\n",
" \n",
" def can_receive(self):\n",
" return state == 'delivering'\n",
" \n",
" # 还有一大堆类似这样的规则，不写了\n",
" \n",
" def payment_service(self):\n",
" # 调用远程接口完成实际支付\n",
" pass\n",
" \n",
" # 然后是关键操作的实现，比如支付\n",
" def pay(self):\n",
" if self.can_pay(self):\n",
" result = payment_service(self)\n",
" if result.succeeded:\n",
" state = 'paid'\n",
" return True\n",
" else:\n",
" return False\n",
" else:\n",
" raise ValueError()\n",
" \n",
" def cancel(self):\n",
" if self.can_cancel(self):\n",
" self.state = 'cancelling'\n",
" # 取消订单，申请审批和清理数据，如果顺利成功再——\n",
" self.state = 'closed'\n",
" else:\n",
" raise ValueError()\n",
" \n",
" # 还有一大堆操作的函数，每一个里面都要判断状态是不是可以做想做操作\n",
" # 然后根据执行的情况修改 self.state 为对应的新状态"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"这样的代码非常冗长和重复，难以维护且难以修改，设想一下，假设在上面的基础上再增加一个状态，要连带修改不确定几处地方，做完这样的修改还需要相应修改所有的测试用例，累就不说了，关键是容易出错。\n",
"\n",
"有限状态机实际上是这些“八股”的通用实现，然后提供一个非常简洁的接口供我们使用。有兴趣的话可以自己尝试用 Python 写一个 *FSM* 的实现出来，只做最基本功能的话也不是很难，但我们实际上没必要自己写，Python 有不少 *FSM* 的第三方实现，比如 [transitions](https://github.com/pytransitions/transitions) 这个库，我们下面就用它来演示一下上面的流程如何用 *FSM* 实现。\n",
"\n",
"运行下面的例子之前需要在命令行界面运行 `pip install transitions` 来安装这个库。也可以在 *notebook* 里打开一个新的 *cell* 直接输入 `!pip install transitions`，和在命令行运行的效果是一样的。"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"支付服务申请中……\n",
"已通知用户：商品配送中\n"
]
},
{
"data": {
"text/plain": [
"'done'"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# 引入 transitions 库里的核心类\n",
"from transitions import Machine\n",
"\n",
"class Order:\n",
" # 定义状态集\n",
" states = ['created', 'paid', 'delivering', 'received', 'done', 'cancelling', 'returning', 'closed']\n",
" \n",
" def __init__(self, order_id):\n",
" self.order_id = order_id\n",
" \n",
" # 创建 FSM\n",
" self.machine = Machine(model=self, states=Order.states, initial='created')\n",
" \n",
" # 定义状态转换函数\n",
" # 基本的语法很好懂，trigger 参数是输入函数名，source 和 dest 分别是当前和转换后的状态\n",
" # before 参数表示进行这个状态转换之前要调用的函数，如果该函数运行时出现异常，状态转换会中止\n",
" self.machine.add_transition(trigger='t_pay', source='created', dest='paid', before='payment_service')\n",
" # after 参数表示当这个状态转换完成后调用的函数，我们用这个函数来通知用户已经发货在途了\n",
" self.machine.add_transition(trigger='t_deliver', source='paid', dest='delivering', after='notify_delivering')\n",
" self.machine.add_transition(trigger='t_receive', source='delivering', dest='received')\n",
" self.machine.add_transition(trigger='t_confirm', source='received', dest='done')\n",
" # 可以一次定义多个状态向同一个状态的装换\n",
" self.machine.add_transition(trigger='t_cancel', source=['created', 'paid'], dest='cancelling')\n",
" self.machine.add_transition(trigger='t_return', source=['delivering', 'received'], dest='returning')\n",
" self.machine.add_transition(trigger='t_close', source=['cancelling', 'returning'], dest='closed')\n",
" \n",
" def payment_service(self):\n",
" print('支付服务申请中……')\n",
" # 调用远程接口完成实际支付，如果失败可抛出异常，对应的状态转换会中止（即，不会转换到 'paid' 状态）\n",
" return\n",
" \n",
" def notify_delivering(self):\n",
" # 通知用户已发货在途\n",
" print('已通知用户：商品配送中')\n",
" return\n",
"\n",
"# 然后就可以测试一下了\n",
"order1 = Order(1)\n",
"order1.state # => 'created'\n",
"# order1.t_receive() # => 如果运行这一句会抛出 MachineError 异常，因为当前状态与此 trigger（输入）不匹配，转换不被允许\n",
"order1.t_pay() # => 会先调用 payment_service()，成功的话返回 True\n",
"order1.state # => 'paid'\n",
"order1.t_deliver() # => 成功后调用 notify_delivering() 通知用户\n",
"order1.t_receive()\n",
"order1.t_confirm()\n",
"order1.state # => 'done'"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"除了具体业务执行的代码，上面基本上完整实现了流程控制的部分，值得注意的是，借助 *FSM* 的实现，不仅简洁易懂，而且易于维护，假定我们需要对流程规则进行修改，或者在某些状态转换的前后添加一些操作，我们通常都只需要修改一处代码，而不用到处找哪里还要改。\n",
"\n",
"顺便说一下， [transitions](https://github.com/pytransitions/transitions) 这个库还有不少强大的功能，有兴趣可以自行发掘下。"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 小结"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"本章介绍了重要的数据模型“有限状态机（*FSM*）”，需要理解其背后的现实世界模型、具体应用及其带来的好处。\n",
"* *FSM* 是对程序中一组的状态进行管理的工具；\n",
"* *FSM* 能够精简程序里的逻辑判断，我们只需要陈述规则，*FSM* 自动管理什么可以什么不可以；\n",
"* 尝试体会和理解 *FSM* 背后的抽象思维方式，如何从特定问题中抽象出可以普遍应用的通用工具。"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.4"
}
},
"nbformat": 4,
"nbformat_minor": 4
}