练习 30：有限状态机

原文：Exercise 30: Finite State Machines

译者：飞龙

协议：CC BY-NC-SA 4.0

自豪地采用谷歌翻译

每当你阅读一本关于解析的书，都有一个可怕的章节，关于有限状态机（FSM）。他们对“边”和“节点”进行了详细的分析，每个可能的“自动机”的组合被转换成其他自动机，坦率地说，它有点多了。FSM 有一个更简单的解释，使得它们实用并且可理解，而不会违背相同主题的纯理论版本。当然你不会向 ACM 提交论文，因为你不知道 FSM 背后的所有数学知识，但如果你只想在应用程序中使用它们，那么它们就足够简单了。

FSM 是组织事件一种方式，事件发生在一系列状态上。定义事件的另一种方法是“输入触发器”，类似于if语句中的布尔表达式，但通常不太复杂。事件可以是按钮点击，从流中接收字符，更改日期或时间，以及几乎任何用于声明事件的东西。状态就是你的 FSM 停止的任何“位置”，同时它等待更多的事件，并且你定义的每个状态都允许事件（输入）。事件往往是暂时的，而状态通常是固定的，而且二者都是可以存储的数据。最后，你可以将代码附加到事件或状态，甚至决定在进入状态时，状态中或退出状态时是否应运行代码。

FSM 只是一种方法，在执行中不同位置发生不同事件时，使用白名单列出可能运行的代码。在 FSM 中，当你收到意外事件时，你会发生故障，因为你必须明确说明每个状态允许哪些事件（或条件）。if语句也可以处理可能的分支，但它是一个可能性的黑名单。如果你忘记了else子句，那么你的if-elif条件没有覆盖的任何东西都会退回默认。

让我们将其拆解：

• 你拥有状态，这是 FSM 当前所在位置的存储指示器。状态可以是“开始”，“按下某键”，“中止”或类似的方式，描述执行的可能位置中的 FSM 的位置。每个状态都意味着正在等待某事发生，在决定下一步做什么之前。
• 你拥有事件，可以将 FSM 从一个状态移动到另一个状态。事件可以是“按下某键”，“套接字连接失败”，“文件保存”，并表示 FSM 接收到一些外部刺激，因此必须决定要做什么，以及下一个状态是什么。一个事件甚至可以回到同一个状态，这是你循环的方式。
• 根据发生的事件，FSM 从一个状态转换到另一个状态，并且仅仅由于为状态提供的确切事件（尽管其中一个事件可以定义为“任何事件”）。他们不会“意外”转移状态，你可以通过查看收到的事件和访问的状态，精确地跟踪他们从一个状态转移到另一个状态。这使得它们非常容易调试。
• 在状态转换之前，之后和期间，你可以在每个事件上运行代码。这意味着你可以在收到事件时运行一些代码，然后决定在该状态下基于该事件做什么，然后在离开该状态之前再次运行代码。这种执行代码的功能使得 FSM 非常强大。
• 有时候“没有”也是一个事件。这很好很强大，因为这意味着即使没有发生任何事情，你也可以将 FSM 转换到新的状态。然而，实际上，“没有”往往是隐含的事件“再来一次”或“醒来”。在其他情况下，这个状态的意思是，“不确定，也许下一个事件会告诉我是什么状态。”

FSM 的力量是能够明确地说明每个事件，事件只是正在接收的数据。这使得它们非常容易进行调试，测试和正确实现，因为你确切地知道每个状态的可能性，以及在每个状态中，对于每个事件可能发生的情况。在本练习中，你将要研究 FSM 库和使用它的 FSM 实现，来了解它们如何工作。

挑战练习

我创建了一个 FSM 模块，处理一些简单的事件来处理 Web 服务器的连接。这是一个虚构的 FSM，为你提供一个在 Python 中快速编写 FSM 的例子。它只是处理连接的基本框架，连接从套接字读取和写入，并且它缺少一些重要的东西，但这只是供你使用的一个很小的例子。

def START():
    return LISTENING

def LISTENING(event):
    if event == "connect":
        return CONNECTED
    elif event == "error":
        return LISTENING
    else:
        return ERROR

def CONNECTED(event):
    if event == "accept":
        return ACCEPTED
    elif event == "close":
        return CLOSED
    else:
        return ERROR

def ACCEPTED(event):
    if event == "close":
        return CLOSED
    elif event == "read":
        return READING(event)
    elif event == "write":
        return WRITING(event)
    else:
        return ERROR

def READING(event):
    if event == "read":
        return READING
    elif event == "write":
        return WRITING(event)
    elif event == "close":
        return CLOSED
    else:
        return ERROR

def WRITING(event):
    if event == "read":
        return READING(event)
    elif event == "write":
        return WRITING
    elif event == "close":
        return CLOSED
    else:
        return ERROR

def CLOSED(event):
    return LISTENING(event)

def ERROR(event):
    return ERROR

也有一个小测试，向你展示如何运行这个 FSM：

import fsm

def test_basic_connection():
    state = fsm.START()
    script = ["connect", "accept", "read", "read", "write", "close", "connect"]

    for event in script:
        print(event, ">>>", state)
        state = state(event)

你在本练习中的挑战是，将此示例模块变成一个更强大和通用的 FSM Python 类。你应该使用它作为一系列线索，来了解如何处理进入的事件，状态如何作为 Python 函数，以及如何进行隐式的转换。看看我有时候为下一个状态返回函数，但其​​他时候我会返回一个状态函数的调用？试着弄清楚为什么我会这样做，因为它在 FSM 中非常重要。

为了完成这个挑战，你需要学习 Python inspect模块，看看你可以用 Python 对象和类来做什么。有一些特殊的变量，如__dict__以及inspect中的函数，可帮助你窥探类或对象并查找函数。

你也可以决定要反转此设计。你可以将事件作为子类中的函数，并在事件函数内检查当前的self.state，来确定接下来要执行的操作。这完全都取决于你正在处理什么，你是否拥有更多的事件还是状态，当时什么有意义。

最后，你可以使用一个设计，其中有一个FSMRunner类，它只知道如何运行这样设计的模块。这比一个知道如何运行自身实例的单一类有一些优点，但也有一些问题。例如，FSMRunner如何跟踪当前状态？它放在模块中还是在FSMRunner的实例中？

研究性学习

• 使你的测试更加泛用，并为你熟悉的完全不同的领域做一个FSM。
• 添加一个功能，启动在你的实现中运行的事件的日志。使用 FSM 处理事件的最大优点之一是，可以存储和记录 FSM 收到的所有事件和状态。这可以让你调试，为什么它达到你不需要的状态。

深入学习

你应该仔细研究 FSM 背后的数学。我这里的小例子不是完全形式化的概念版本，以便你能理解它。