练习 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 的例子。它只是处理连接的基本框架,连接从套接字读取和写入,并且它缺少一些重要的东西,但这只是供你使用的一个很小的例子。

  1. def START():
  2. return LISTENING
  3. def LISTENING(event):
  4. if event == "connect":
  5. return CONNECTED
  6. elif event == "error":
  7. return LISTENING
  8. else:
  9. return ERROR
  10. def CONNECTED(event):
  11. if event == "accept":
  12. return ACCEPTED
  13. elif event == "close":
  14. return CLOSED
  15. else:
  16. return ERROR
  17. def ACCEPTED(event):
  18. if event == "close":
  19. return CLOSED
  20. elif event == "read":
  21. return READING(event)
  22. elif event == "write":
  23. return WRITING(event)
  24. else:
  25. return ERROR
  26. def READING(event):
  27. if event == "read":
  28. return READING
  29. elif event == "write":
  30. return WRITING(event)
  31. elif event == "close":
  32. return CLOSED
  33. else:
  34. return ERROR
  35. def WRITING(event):
  36. if event == "read":
  37. return READING(event)
  38. elif event == "write":
  39. return WRITING
  40. elif event == "close":
  41. return CLOSED
  42. else:
  43. return ERROR
  44. def CLOSED(event):
  45. return LISTENING(event)
  46. def ERROR(event):
  47. return ERROR

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

  1. import fsm
  2. def test_basic_connection():
  3. state = fsm.START()
  4. script = ["connect", "accept", "read", "read", "write", "close", "connect"]
  5. for event in script:
  6. print(event, ">>>", state)
  7. state = state(event)

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

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

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

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

研究性学习

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

深入学习

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