Notebook

有限状态机¶

有限状态机（finite state machine，简称 FSM），有时也被称为 finite state automation，有时就简单地叫 state machine，不属于一看就知道大概是什么的概念（这一点和前面我们讲过的都不一样）。有限状态机有相当深刻的理论背景，算是比较高级的东西了，很多程序员别说学校里，工作十年可能都没碰过这东西，但其实真的不难理解，而且学会了就爱不释手，因为它解决某些问题真是太好用了。

什么是有限状态机¶

其实我们身边到处都是“有限状态机”的例子，最简单的一个是灯：灯有两种状态：“亮”和“熄”，灯可以从一种状态变成另一种，“亮”的状态下接收到“关”的指令就会变成“熄”，“熄”的状态下接收到“开”的指令就会变成“亮”，就像下图这样：

在这个图里，圆圈表示“状态（state）”，箭头代表状态间可以发生的“转换（transition）”，而箭头上标注的文字代表触发状态转换的“输入（input）”。这基本上就是状态机的三大要件了。

灯只有两个状态，不算很有意思，我们可以再看一个常见的例子：红绿灯，我们熟知的红绿灯的颜色按照“绿 -> 黄 -> 红 -> 绿”这样的顺序循环变化——嗯，我知道有的还有“绿灯闪烁”之类的状态，不过我们这里简化一下，用有限状态机来描述大致如下图：

这里：

有三种状态：绿，黄，红；
状态转换是受限的，绿只能转黄，黄只能转红，红只能转绿；诸如黄转绿这样的状态转换是不允许的；
状态转换的输入条件很简单，接收到 1 就转换到下一个状态。

所以简单来说，有限状态机就是一台包含了预先定义好的一组状态的机器，当机器接收到一个指令，就根据指令内容查一张预先定义好的表：

检查当前状态是否接受这个指令；
如果不接受，那就当无事发生；
如果接受，再检查表中“当前状态x该指令”对应的目标状态是什么，然后把机器状态转换为目标状态。

至于何时发送指令给状态机，是由外部系统决定的，比如红绿灯的例子里，外部系统是几个定时器，时间到了就发信号给有限状态机切换状态。

有了现实生活中的例子打底，我们现在可以来看看抽象的“有限状态机（FSM）”是怎么定义的了。

如上图所示，每一个 FSM 都包含五个要素：

Q 包含了有限个状态（states）的集合；
Σ 包含了有限个、非空的有效输入（input）的集合；
δ 一系列转换函数（transition functions），定义了什么样的当前状态结合什么输入可以变成什么目标状态，通常可以定义为一张二维表（见上图）；
q₀ 起始状态，并不是所有 FSM 都关心起始状态，比如红绿灯就无所谓起始状态；
F 包含了所有“结束状态（final states）”的集合，这个名字容易误解，它的作用和有限状态机的具体类型及面对的问题有关，我们可以简单理解为“标记出来有特别含义的状态的集合”就可以了，注意这个集合可以是空的。

以上图所示的 FSM 为例，

这个 FSM 有四个有效状态，Q = { A, B C, D}；
这个 FSM 只接受两个合法输入，Σ = { 0, 1 }；
当这个 FSM 接收到输入时，不在 Σ = { 0, 1 } 中的输入会被丢弃；如果输入在 Σ 中（是 0 或者 1），就查 δ 表，看看当前状态对应行和输入对应列的交叉点是什么状态，比如当前状态是 A，输入是 1，那么对应状态为 C，也就是说应该转换到状态 C。
起始状态 q₀ = A 和结束状态集 F = { D } 这两个对某些 FSM 来说很重要，比如正则表达式。

正则表达式对应一大类有限状态机，主要用来解决“在一系列输入之后是什么状态”的问题，通过回答这个问题来判断输入序列是不是我们想要的，或者输入序列属于什么分类，这种状态机有很深刻的理论背景，有兴趣的话可以读一下计算理论（computation theory）的经典教材，比如这本；这类状态机还被广泛应用于人工智能（比如图像识别算法）中。

在计算机编程领域 FSM 最广泛的应用之一是流程和行为控制（flow and behavior control），简单说就是管理：

在某个状态下什么能做什么不能做；
做了什么会变成另外的什么状态。

游戏里玩家行为控制、NPC（non-player character，非玩家角色）的 AI、剧情任务流程等都是用 FSM 来实现的；所有的工作流系统都包含 FSM；还有电商核心系统之一的“订单系统”（order system）。

我们用过淘宝都知道，一个订单从创建开始要经历好几个状态，中间也有不同的操作可以进行，下面是一个比较典型的流程设计，经过一定简化，并以“状态”的主视角来描绘：

图中圆边的矩形代表状态，最上面一排是“正常”的状态和流程；第二排的矩形则表示一些“逆向”子流程，通常是由用户或客户发起的特殊操作，这些操作会带来其他一些订单状态，为了简单起见没有在这里展开。

流程说明：

当买家点击下单时订单生成，处于“已创建”状态；
这个状态下的正常操作是“支付”，如果输入“支付成功”会进入下一个状态“已支付”，“支付失败”或者没有任何操作则停在本状态；
这个状态下其他可选操作包括“修改”、“取消”等，分别会去到订单修改和订单取消子流程（这里略去细节）；
支付成功后进入处于“已支付”状态；
这个状态下需要等待商家发货，商家输入“已发货”会进入下一个状态“配送中”；
这个状态下不能修改订单了，但仍然可以取消订单；
商家发货后进入“配送中”状态；
当配送到货，买家签收成功输入则进入下一个状态“已签收”；如果配送失败（买家不在家之类的情况）则留在“配送中”状态（另外择时重新送货）；
这个状态下已不能修改和取消订单，但是可以发起退货申请，进入退货子流程（这里略去细节）；
买家签收后进入“已签收”状态；
买家满意，确认订单完成则进入最后状态“已完成”，订单生命周期结束；
否则买家可以发起退货进入退货子流程（略）。

从这里我们可以看到，实际业务系统中状态和转换的规则相当复杂（我们这还是大大简化的版本），每个状态下允许的操作和可能转换的下一个状态都是严格受控的，现在我们思考一下，我们可以如何用程序来实现这样的流程呢？

利用有限状态机编写易于维护的代码¶

回忆我们之前提到的，流程和行为控制（flow and behavior control）的关键是管理：

在某个状态下什么能做什么不能做；
做了什么会变成另外的什么状态。

最简单直接的办法就是书写一堆 if...else 的判断规则，大致会是这个样子：

In [1]:

class Order:
    STATES = {'created', 'paid', 'delivering', 'received', 'done', 'cancelling', 'returning', 'closed'}
    state = 'created'
    
    def can_pay(self):
        return state == 'created'
    
    def can_deliver(self):
        return state == 'paid'
    
    def can_cancel(self):
        return state == 'created' or state == 'paid'
    
    def can_receive(self):
        return state == 'delivering'
    
    # 还有一大堆类似这样的规则，不写了
    
    def payment_service(self):
        # 调用远程接口完成实际支付
        pass
    
    # 然后是关键操作的实现，比如支付
    def pay(self):
        if self.can_pay(self):
            result = payment_service(self)
            if result.succeeded:
                state = 'paid'
                return True
            else:
                return False
        else:
            raise ValueError()
    
    def cancel(self):
        if self.can_cancel(self):
            self.state = 'cancelling'
            # 取消订单，申请审批和清理数据，如果顺利成功再——
            self.state = 'closed'
        else:
            raise ValueError()
    
    # 还有一大堆操作的函数，每一个里面都要判断状态是不是可以做想做操作
    # 然后根据执行的情况修改 self.state 为对应的新状态

这样的代码非常冗长和重复，难以维护且难以修改，设想一下，假设在上面的基础上再增加一个状态，要连带修改不确定几处地方，做完这样的修改还需要相应修改所有的测试用例，累就不说了，关键是容易出错。

有限状态机实际上是这些“八股”的通用实现，然后提供一个非常简洁的接口供我们使用。有兴趣的话可以自己尝试用 Python 写一个 FSM 的实现出来，只做最基本功能的话也不是很难，但我们实际上没必要自己写，Python 有不少 FSM 的第三方实现，比如 transitions 这个库，我们下面就用它来演示一下上面的流程如何用 FSM 实现。

运行下面的例子之前需要在命令行界面运行 pip install transitions 来安装这个库。也可以在 notebook 里打开一个新的 cell 直接输入 !pip install transitions，和在命令行运行的效果是一样的。

In [2]:

# 引入 transitions 库里的核心类
from transitions import Machine

class Order:
    # 定义状态集
    states = ['created', 'paid', 'delivering', 'received', 'done', 'cancelling', 'returning', 'closed']
    
    def __init__(self, order_id):
        self.order_id = order_id
        
        # 创建 FSM
        self.machine = Machine(model=self, states=Order.states, initial='created')
        
        # 定义状态转换函数
        # 基本的语法很好懂，trigger 参数是输入函数名，source 和 dest 分别是当前和转换后的状态
        # before 参数表示进行这个状态转换之前要调用的函数，如果该函数运行时出现异常，状态转换会中止
        self.machine.add_transition(trigger='t_pay', source='created', dest='paid', before='payment_service')
        # after 参数表示当这个状态转换完成后调用的函数，我们用这个函数来通知用户已经发货在途了
        self.machine.add_transition(trigger='t_deliver', source='paid', dest='delivering', after='notify_delivering')
        self.machine.add_transition(trigger='t_receive', source='delivering', dest='received')
        self.machine.add_transition(trigger='t_confirm', source='received', dest='done')
        # 可以一次定义多个状态向同一个状态的装换
        self.machine.add_transition(trigger='t_cancel', source=['created', 'paid'], dest='cancelling')
        self.machine.add_transition(trigger='t_return', source=['delivering', 'received'], dest='returning')
        self.machine.add_transition(trigger='t_close', source=['cancelling', 'returning'], dest='closed')
        
    def payment_service(self):
        print('支付服务申请中……')
        # 调用远程接口完成实际支付，如果失败可抛出异常，对应的状态转换会中止（即，不会转换到 'paid' 状态）
        return
    
    def notify_delivering(self):
        # 通知用户已发货在途
        print('已通知用户：商品配送中')
        return

# 然后就可以测试一下了
order1 = Order(1)
order1.state # => 'created'
# order1.t_receive() # => 如果运行这一句会抛出 MachineError 异常，因为当前状态与此 trigger（输入）不匹配，转换不被允许
order1.t_pay() # => 会先调用 payment_service()，成功的话返回 True
order1.state # => 'paid'
order1.t_deliver() # => 成功后调用 notify_delivering() 通知用户
order1.t_receive()
order1.t_confirm()
order1.state # => 'done'

支付服务申请中……
已通知用户：商品配送中

Out[2]:

'done'

除了具体业务执行的代码，上面基本上完整实现了流程控制的部分，值得注意的是，借助 FSM 的实现，不仅简洁易懂，而且易于维护，假定我们需要对流程规则进行修改，或者在某些状态转换的前后添加一些操作，我们通常都只需要修改一处代码，而不用到处找哪里还要改。

顺便说一下， transitions 这个库还有不少强大的功能，有兴趣可以自行发掘下。

小结¶

本章介绍了重要的数据模型“有限状态机（FSM）”，需要理解其背后的现实世界模型、具体应用及其带来的好处。

FSM 是对程序中一组的状态进行管理的工具；
FSM 能够精简程序里的逻辑判断，我们只需要陈述规则，FSM 自动管理什么可以什么不可以；
尝试体会和理解 FSM 背后的抽象思维方式，如何从特定问题中抽象出可以普遍应用的通用工具。