状态机：从循环到图（解释版）

每隔几个月，智能体构建领域就会采用一种新的抽象，从链到循环，再到现在的图，而这些其实都是同一个底层思想的不同名字。

这个思想就是有限状态机，一种自20世纪50年代就出现在教科书中的形式化方法，它规范了TCP和CPU的控制单元，并且已经以意外形式存在于大多数代码库中——由布尔标志和散落的条件语句构建而成。

由于有意识地实现一个状态机几乎不增加额外成本，并且能提供强大的保证，因此值得正确理解这种模式。本文涵盖理论、实现，以及为何智能体框架正趋同于它却不承认。

核心

状态机回答一个简单问题：给定当前状态，当事件发生时，下一个状态是什么？写成函数就像这样：

每个程序实际上都已经这样运行了，因为React组件、请求处理器、游戏循环和LLM智能体都持有某种状态，接收某个事件，并因此迁移到新状态。

由于这种结构存在于每个程序中，无论是否有人规划过它，开发者唯一真正的决定是迁移逻辑放在哪里——通常它最终分散在事件处理器和条件语句中，没人能看到全貌。

将其写成一个显式函数，就能将系统的完整行为集中到一处。本文后续描述的所有好处都源于这个简单的举动。

正式定义

有限状态机在形式上是五元组：

M = (S, Σ, δ, s0, F)

其中：

• S 是有限的状态集合
• Σ 是有限的事件集合，称为输入字母表
• δ : S × Σ → S 是迁移函数
• s0 ∈ S 是初始状态
• F ⊆ S 是最终状态集合

因为S是有限的，δ可以写成一张表，系统的完整行为可以被枚举——这意味着每个可达状态和每个可能的迁移序列都能被列出和检查。

任意代码缺乏这种性质，因为其状态空间是无界的，控制流依赖于运行时值。正是这种差异使得协议、正则引擎和硬件被指定为状态机——因为有限的规格可以被穷举检查，并在安全关键场景中被证明正确。

一个理论上的区别在实践中经常出现，值得了解。如果δ(状态, 事件)恰好产生一个下一个状态，则该机器称为确定性有限自动机（DFA）；如果可能产生一组下一个状态，则称为非确定性有限自动机（NFA）。

非确定性听起来抽象，但正则引擎将每个模式编译成NFA，然后要么直接模拟它，要么通过子集构造将其转换为DFA。这意味着写一个像 a+b*c 这样的表达式相当于编程一个状态机，然后让编译器为你构造它。

本文后面讨论的每个框架，包括智能体编排库，都是这个δ函数的包装器。记住这一点，评估新工具时会容易得多。

它解决的问题：不可能状态

考虑数据获取通常如何建模：

三个布尔值产生 2³ = 8 种组合，其中可能只有三种是有意义的。像 isLoading && isError 这样的组合描述的是不连贯的情况，但类型系统允许它，最终竞争条件会构造出它，产生一个覆盖在错误信息上的旋转器，再覆盖在过时数据上。

问题呈指数增长，因为每个额外的标志会使状态空间翻倍，而有效状态的数量增长却慢得多。因此一个有五个标志的组件有32种可能组合，其中可能只有五种是合法的。

通常的应对方法是编写防御性条件，如 if (isLoading && !isError && ...)，试图手动圈出合法区域。在增长的代码库中，总会有某个情况被遗漏。

将同样的特性建模为状态机，首先用枚举替换标志：

在这种表示下，loading 和 error 的组合甚至无法写出来。因此，矛盾标志这类bug在类型层面就消失了，而不是在测试中被捕获。

函数式程序员将这种做法描述为“使非法状态不可表示”。状态机将同样的原则应用于系统随时间的演变，而不是单个数据结构。

从这种结构立即得出两个保证：

• 系统始终处于恰好一个状态。
• 移动只能沿着你定义的迁移进行。

第二个保证的实际分量容易被低估。在基于标志的代码中，任何处理器都可以随时触发并改变任何东西；而在状态机中，一个事件如果没有从当前状态定义的迁移，就什么也不做。

当用户双击提交按钮时，第二个 SUBMIT 事件在机器处于 loading 状态时到达。由于 loading 没有定义 SUBMIT 迁移，机器忽略它。这意味着重复提交的bug从未存在过，也从未需要防抖、锁或禁用按钮标志来防止它。

实现

迁移函数是数据。最干净的实现将其视为数据，在大多数语言中就是一张简单的查找表：

这一个函数就是完整的状态机解释器。表格形式带来了几个实际后果。

功能的完整行为可以放在一个屏幕上；代码评审中对此对象的 diff 直接显示行为变化，而不需要评审者模拟控制流；该对象可以被序列化、存储在数据库中、通过网络发送或自动渲染成图。

测试也改变了性质。因为状态乘以事件构成一张有限表，测试套件可以遍历整张表，而不是采样代码路径并希望覆盖了重要的那些。

同样的机器也可以写成 switch 语句：

这个版本更冗长，但在 TypeScript 或 Rust 中，编译器会强制执行穷尽性——因此添加新状态而忘记处理它会导致构建失败，而不是在生产中失败。

Rust 通过类型状态模式将这一思想推向极致：每个状态成为不同的类型，无效迁移根本编译不过。

任何写过 Redux reducer 或使用过 useReducer 的人都已经写过 (state, action) => nextState 形式的函数。所以这种模式比听起来更熟悉。

区别在于，大多数 reducer 允许任何 action 从任何状态修改任何东西——这以更好的语法悄悄重新引入了布尔标志问题。而一旦 reducer 在考虑事件之前检查当前状态，它就变成了真正的状态机。这个排序上的单一改变承载了上面描述的所有保证。

有限状态 vs. 上下文

此时一个合理的反对意见是：实际应用状态包括表单输入、数组和时间戳，这些都无法枚举。因此有限性要求似乎排除了真实程序。

标准答案是将状态分成两部分，它们扮演不同角色。有限状态捕获系统所处的模式，使用如 idle、loading、editing 或 disconnected 等值。这部分保持定性、小型和可枚举。

上下文（也称为扩展状态）包含所有定量内容，如表单值、重试次数和获取的数据。这部分可以是无界的，因为机器从不枚举它。

机器管理模式，上下文伴随它一起。这样扩展的机器在形式上称为扩展状态机，其迁移函数返回更多信息：

下面的示例实现了最多三次尝试的重试：

这段代码中出现了三个标准概念，值得命名。守卫（guard）是附加在迁移上的条件，这里的检查 ctx.retries < 3 就是一个守卫——它允许同样的 RETRY 事件在尝试次数未用完时导向 loading，在次数用完后导向 gaveUp。

动作（action）是迁移触发的副作用，返回的 ['fetch'] 就是一个动作。关键细节是：机器只决定应该发生哪些效果，并返回它们；而机器外部的解释器实际执行它们。这保持了迁移函数的纯性，使得无需任何 mock 即可测试它。

Redux 中间件和 Elm 从其 update 函数返回命令的模式遵循同样的分离。进入和退出动作完善了集合——这些是附加于进入或离开某个状态的效果，而不是附加于任何特定边。因此，进入 loading 会启动旋转器和超时，而退出 loading 会取消两者，无论经由四条可能边中的哪一条进入或退出。

退出动作特别消除了围绕泄漏定时器、悬挂订阅和忘记清理的一系列bug。因为当取消附加到 loading 的退出时，每个离开该状态的路径都会运行它，没有代码路径能让定时器继续运行。

用标志达到同样的可靠性需要在每个可能离开 loading 模式的处理器中记住清理，而实践中总有一个处理器忘记。

Mealy 和 Moore 机器

经典文献根据输出附着的位置区分两种变体。在 Moore 机器中，输出仅依赖于当前状态——就像交通灯在机器处于绿灯状态时持续点亮。因此输出实际上位于图的节点上。

在 Mealy 机器中，输出同时依赖于状态和事件——就像自动售货机在 idle 状态收到 COIN 事件时出货。因此输出位于边上。

两种变体在表达能力上等价，可以互相转换。真实系统混合使用两者，因为进入/退出动作是 Moore 风格的，而迁移动作是 Mealy 风格的。

除了帮助理解老旧的论文和硬件文档外，这一区别提供了一个真正有用的设计问题：某个效果应该因为系统处于某个状态而发生，还是因为系统如何到达那里而发生？由于两种答案在边界情况下的行为不同，混淆它们会产生微妙bug。

这已经在运行的地方

几个主要的基础设施被指定为状态机，观察它们可以看出这种模式在当前重新发现之前有多么久远。

TCP 通过其状态图定义每个连接，状态包括 LISTEN、SYN_SENT、ESTABLISHED、FIN_WAIT_1 和 TIME_WAIT。RFC 793 早在1981年就将该协议定义为状态图，因为对于如此关键的东西，文字描述太模糊。直到今天，实现之间的分歧仍通过指向状态图来解决。

正则引擎运行在 DFA 上，每个输入字符以常数时间处理，无需回溯。grep 的速度直接归因于底层模型的这一性质，而非任何实现技巧。

游戏 AI 从街机时代就开始使用这种模式。敌人行为遵循 patrol → chase → search → patrol 等迁移，由看到或丢失玩家等事件驱动。《吃豆人》中的幽灵是四个小状态机，它们著名的不同个性完全来自四个不同的迁移表。

在硬件中，这种模式是基础——CPU 是一个时钟驱动的状态机，Verilog 和 VHDL 都将 FSM 视为主要设计惯用语。交通灯、电梯和自动售货机成为教科书范例，正是因为这些系统的故障会造成物理伤害，所以其逻辑必须建立在可验证的东西上。

UI 代码隐含地包含相同结构：每个表单都经过 pristine、editing、validating、submitting，最后 succeeded 或 failed 等阶段。下拉菜单、媒体播放器和拖拽交互也有相同特征。

一个常见的bug是模态框关闭但深色遮罩层仍停留在屏幕上——这发生在系统占据了设计者从未意图的状态组合时。这正是显式机器使其不可表示的情况。

智能体

智能体图描述了智能体在规划、调用工具、评估结果、重试、询问人类以及最终完成的过程中，如何在步骤之间移动。

该领域始于线性管道；承认智能体会失败和分支后，转向 DAG；然后不得不允许循环，因为承认智能体会重试直到验证，并通过人类反馈循环。这最终形成了一个带标记边的有向循环图、一个起始节点和多个终止节点。

将这些部分映射到五元组：节点是 S，边标签是 Σ，边是 δ，起始节点是 s0，终止节点是 F。因此，智能体图以新名称重建了有限状态机。

一个用显式机器编写的实际智能体如下所示：

使机器显式为智能体带来了几个在生产中重要的性质。

重试逻辑变成了带守卫的边。因为“重试直到验证”的行为简化为从 evaluating 到 planning 的单一迁移，并带有一个守卫要求尝试次数不超过最大值。因此失控循环被结构本身排除，而不是依赖于有人记得在 while 循环中添加计数器。

控制流也脱离了模型的手。这很重要，因为 LLM 输出是非确定性的，让它直接驱动控制流会产生声称自己完成但实际上并未完成的智能体。

在机器中，模型输出首先被分类为事件（如 VERIFIED 或 UNSAFE），然后机器检查该事件是否有一条从当前状态出发的合法迁移。因此模型可以幻觉出一个事件，但一个没有匹配边的事件不会造成任何后果。从 UNSAFE 到 awaitingHuman 的安全关键路径由查找表强制执行，而不是由系统提示中的指令。

长期运行的智能体也变得可持久化，因为当前状态和上下文的组合是一个小的可序列化值。因此，等待三天人类批准的智能体简化为将 (awaitingHuman, ctx) 写入数据库行，终止进程，并在批准 webhook 触发时重新水化。

Temporal 和 AWS Step Functions 等持久化工作流引擎正建立在这个想法上。Step Functions 甚至要求将机器写成 JSON。

调试也因为相同原因变得更简单：智能体在做什么这个问题变成单列查询，它如何到达那里变成事件历史。而回答关于自由形式循环的相同问题则需要从追踪中重建行为。

多智能体系统自然地将状态机与 actor 模型配对——每个智能体是一个持有私有状态、仅通过消息通信的 actor，而每个 actor 的内部行为是一个状态机，其事件是传入的消息。

Erlang 在1980年代就构建了这种精确组合。其 OTP 框架提供了一个名为 gen_statem 的状态机 actor 原语。结果是在电信交换机上以极高正常运行时间运行了数十年。因此，多智能体架构也是一种重新发现，尽管这属于另一篇文章的主题。

状态图

扁平状态机在一种特定方式上无法扩展——当系统有独立关注点时，问题立即显现。

一个文本编辑器，其中加粗、斜