search

xuzhengfu / pilot

进入编程世界的第一课
1 stars 0 forks source link

p2-b-fsm 第十一章 有限状态机 #42

Open xuzhengfu opened 4 years ago

xuzhengfu commented 4 years ago

0. 有限状态机简介

有限状态机（finite state machine，简称 FSM），有时也被称为 finite state automation，有时就简单地叫 state machine，不属于一看就知道大概是什么的概念（这一点和前面我们讲过的都不一样）。

有限状态机有相当深刻的理论背景，算是比较高级的东西了，很多程序员别说学校里，工作十年可能都没碰过这东西，但其实真的不难理解，而且学会了就爱不释手，因为它解决某些问题真是太好用了。

1. 什么是有限状态机

1.1 灯

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

fsm-1

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

1.2 红绿灯

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

fsm-2

这里：

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

1.3 有限状态机的定义

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

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

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

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

fsm-3

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

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

以上图所示的 FSM 为例，

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

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

1.4 FSM 在计算机编程领域的应用

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

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

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

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

fsm-4

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

流程说明：

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

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

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

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

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

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

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 实现。

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

结果如下：

xuzhengfu at xuzhengfudeiMac in ~
$ pip3 install transitions
Collecting transitions
  Downloading transitions-0.8.1-py2.py3-none-any.whl (73 kB)
     |████████████████████████████████| 73 kB 9.5 kB/s 
Requirement already satisfied: six in /usr/local/lib/python3.7/site-packages (from transitions) (1.14.0)
Installing collected packages: transitions
Successfully installed transitions-0.8.1
# 引入 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'

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

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

3. 小结

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

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

Logging

2020-04-09 18:50:42 initialize