State Machines: From Loops to Graphs (Explained)

vixhaℓ 2026-07-21 42.1 KB 81.2K 562 𝕏 文章列表

文章阐述了状态机理论及其在软件开发中的应用。作者指出Agent框架从链条到循环再到图形的演变，本质上是有限状态机（FSM）的体现。通过将分散的逻辑迁移到明确的转换函数中，状态机能消除不可能状态，避免竞态条件，并提供类型级安全保障。文章展示了基于查找表和Switch语句的实现方式，强调了其在代码审查、测试及系统可靠性方面的优势。

# State Machines: From Loops to Graphs (Explained) **作者**: vixhaℓ **日期**: 2026-07-20T18:36:17.000Z **来源**: [https://x.com/TheVixhal/status/2079274210367775052](https://x.com/TheVixhal/status/2079274210367775052) --- ![Image](/doc/3220/image/img_f7034d822435.jpg) Every few months the agent-building world adopts a new abstraction, moving from chains to loops and now to graphs, and each of these turns out to be the same underlying idea with a different name. That idea is the finite state machine, a formalism that has existed in textbooks since the 1950s, that specifies TCP and the control unit of your CPU, and that already exists in most codebases in an accidental form built out of Boolean flags and scattered conditionals. Since implementing one deliberately costs almost nothing extra and comes with strong guarantees, it is worth understanding the pattern properly, so this article covers the theory, the implementation, and the reason agent frameworks are converging on it without acknowledging it. # The core A state machine answers a single question, which is that given the current state, when an event occurs, what is the next state? Written as a function, it looks like this: ``` transition(state, event) -> nextState ``` Every program already behaves this way, because a React component, a request handler, a game loop, and an LLM agent all hold some state, receive some event, and move to a new state as a result. Since this structure is present in every program whether or not anyone planned it, the only real decision a developer makes is where the transition logic lives, and usually it ends up scattered across event handlers and conditionals where nobody can see the complete picture. Writing it as one explicit function gathers the complete behavior of the system into one place, and every benefit described in the rest of this article follows from that single move. # The formal definition A finite state machine is formally a 5-tuple: M = (S, Σ, δ, s₀, F) where: - S is a finite set of states - Σ is a finite set of events, called the input alphabet - δ : S × Σ → S is the transition function - s₀ ∈ S is the initial state - F ⊆ S is the set of final states Because S is finite and δ can be written down as a table, the complete behavior of the system can be enumerated, meaning every reachable state and every possible sequence of transitions can be listed and inspected. Arbitrary code lacks this property because its state space is unbounded and its control flow depends on runtime values, and this difference is exactly why protocols, regex engines, and hardware get specified as state machines, since a finite specification can be checked exhaustively and, in safety-critical settings, proven correct. One distinction from the theory appears often enough in practice to be worth knowing. If δ(state, event) yields exactly one next state, the machine is called a deterministic finite automaton (DFA), and if it can yield a set of possible next states, it is called a nondeterministic finite automaton (NFA). Nondeterminism sounds abstract, but a regex engine compiles every pattern into an NFA and then either simulates it directly or converts it into a DFA through subset construction, which means that writing an expression like a+b*c amounts to programming a state machine and letting a compiler construct it for you. Every framework discussed later in this article, including the agent orchestration libraries, is a wrapper around this δ function, and keeping that in mind makes new tooling much easier to evaluate. # The problem it solves: impossible states Consider how data fetching usually gets modeled: ``` let isLoading = false; let isError = false; let isSuccess = false; let data = null; let error = null; ``` Three booleans produce 2³ = 8 combinations, of which perhaps three are meaningful, and a combination like isLoading && isError describes no coherent situation at all, yet the type system permits it and eventually a race condition will construct it, producing a spinner rendered on top of an error message on top of stale data. The problem grows exponentially because each additional flag doubles the state space while the number of valid states grows much more slowly, so a component with five flags has 32 possible combinations and maybe five legitimate ones. The usual response is to write defensive conditions like if (isLoading && !isError && ...) that try to fence off the valid region by hand, and in a growing codebase some case always gets missed. Modeling the same feature as a state machine begins with replacing the flags with an enumeration: ``` type State = 'idle' | 'loading' | 'success' | 'failure'; ``` Under this representation the combination of loading and error cannot even be written down, so the entire category of contradictory-flag bugs disappears at the type level rather than being caught in tests. Functional programmers describe this as making illegal states unrepresentable, and a state machine applies the same principle to how a system evolves over time rather than to a single data structure. Two guarantees follow immediately from the structure: 1. The system is always in exactly one state. 2. Movement is only possible along transitions you defined. The practical weight of the second guarantee is easy to underestimate. In flag-based code any handler can fire at any moment and mutate anything, while in a state machine an event that has no transition defined from the current state simply does nothing. When a user double-clicks a submit button, the second SUBMIT event arrives while the machine is in loading, and since loading defines no SUBMIT transition, the machine ignores it, which means the duplicate-submission bug never existed and no debounce, lock, or disabled-button flag was ever needed to prevent it. # Implementation The transition function is data, and the cleanest implementations treat it that way, which in most languages means a plain lookup table: ``` const machine = { initial: 'idle', states: { idle: { FETCH: 'loading', }, loading: { RESOLVE: 'success', REJECT: 'failure', CANCEL: 'idle', }, success: { REFETCH: 'loading', }, failure: { RETRY: 'loading', }, }, }; function transition(state, event) { return machine.states[state]?.[event] ?? state; // undefined event: stay put } ``` That one function is a complete state machine interpreter, and the tabular shape carries several practical consequences. The full behavior of a feature fits on one screen, a diff of this object in code review shows behavior changes directly rather than requiring the reviewer to simulate control flow, and the object can be serialized, stored in a database, sent over the network, or rendered into a diagram automatically. Testing also changes character, because states multiplied by events forms a finite table, so a test suite can walk the entire table instead of sampling paths through the code and hoping the important ones were covered. The same machine can also be written as a switch statement: ``` function transition(state: State, event: Event): State { switch (state) { case 'idle': return event.type === 'FETCH' ? 'loading' : state; case 'loading': switch (event.type) { case 'RESOLVE': return 'success'; case 'REJECT': return 'failure'; case 'CANCEL': return 'idle'; default: return state; } case 'success': return event.type === 'REFETCH' ? 'loading' : state; case 'failure': return event.type === 'RETRY' ? 'loading' : state; } } ``` This version is more verbose, but in TypeScript or Rust the compiler enforces exhaustiveness, so adding a new state and forgetting to handle it fails the build instead of failing in production. Rust takes the idea furthest through the typestate pattern, in which each state becomes a distinct type and an invalid transition fails to compile at all. Anyone who has written a Redux reducer or used useReducer has already written a function of the form (state, action) => nextState, so this pattern is more familiar than it might sound. The difference is that most reducers allow any action to modify anything from any state, which quietly reintroduces the boolean-flag problem with better syntax, whereas a reducer becomes a genuine state machine once it checks the current state before considering the event, and that single change in ordering is what carries all of the guarantees described above. # Finite state vs. context A reasonable objection at this point is that real application state includes form inputs, arrays, and timestamps, none of which can be enumerated, so the finiteness requirement appears to rule out real programs. The standard answer is to split state into two parts that play different roles. The finite state captures the mode the system is in, using values like idle, loading, editing, or disconnected, and this part stays qualitative, small, and enumerable. The context, also called extended state, holds everything quantitative, such as form values, retry counts, and fetched data, and this part is allowed to be unbounded because the machine never enumerates it. The machine governs the mode while the context travels alongside it, and a machine extended this way is formally called an extended state machine, with a transition function that returns more information: ``` transition(state, context, event) -> (nextState, nextContext, actions) ``` The following example implements retries with a cap of three attempts: ``` function transition(state, ctx, event) { if (state === 'failure' && event.type === 'RETRY') { if (ctx.retries < 3) { return ['loading', { ...ctx, retries: ctx.retries + 1 }, ['fetch']]; } return ['gaveUp', ctx, ['notifyUser']]; } // ... } ``` Three standard concepts appear in this code and deserve names. A guard is a condition attached to a transition, and the check ctx.retries < 3 is one, allowing the same RETRY event to lead to loading while attempts remain and to gaveUp once they run out. An action is a side effect that a transition triggers, and the returned ['fetch'] is one, with the important detail being that the machine only decides which effects should occur and returns them, while an interpreter outside the function actually executes them, which keeps the transition function pure and makes testing it possible without any mocks. Redux middleware and Elm's pattern of returning commands from its update function follow the same separation. Entry and exit actions round out the set, and these are effects attached to entering or leaving a state rather than to any particular edge, so that entering loading starts a spinner and a timeout while exiting loading cancels both, regardless of which of the four possible edges was taken in or out. Exit actions in particular eliminate the family of bugs around leaked timers, dangling subscriptions, and forgotten cleanup, because when the cancellation is attached to the exit of loading, every path out of that state runs it and no code path can leave the timer running. Achieving the same reliability with flags requires remembering the cleanup in every handler that could leave loading mode, and in practice one handler always forgets. # Mealy and Moore machines The classical literature distinguishes two variants of the machine according to where outputs attach. In a Moore machine the output depends on the current state alone, as in a traffic light that stays lit for as long as the machine remains in the green state, so outputs effectively live on the nodes of the diagram. In a Mealy machine the output depends on the state and the event together, as in a vending machine that dispenses when a COIN event arrives during the idle state, so outputs live on the edges instead. The two variants are equivalent in expressive power and can be converted into each other, and real systems mix both, since entry and exit actions are Moore-flavored while transition actions are Mealy-flavored. Beyond helping with older papers and hardware documentation, the distinction supplies a genuinely useful design question, namely whether a given effect should happen because the system is in a state or because of how it arrived there, and since the two answers behave differently under edge cases, conflating them produces subtle bugs. # Where this already runs Several major pieces of infrastructure are specified as state machines, and looking at them shows how far the pattern predates its current rediscovery. TCP defines every connection through its state diagram, whose states include LISTEN, SYN_SENT, ESTABLISHED, FIN_WAIT_1, and TIME_WAIT. RFC 793 specified the protocol as a state diagram back in 1981 because prose was too ambiguous for something this critical, and to this day disagreements between implementations get settled by pointing at the machine. Regex engines run on DFAs, which process each input character in constant time with no backtracking, and grep owes its speed directly to this property of the underlying model rather than to any implementation cleverness. Game AI has used the pattern since the arcade era, with enemy behavior following transitions such as patrol to chase to search and back to patrol, driven by events like seeing or losing the player. The ghosts in Pac-Man are four small state machines, and their famously distinct personalities come entirely from four different transition tables. In hardware the pattern is foundational, since a CPU is a clocked state machine and both Verilog and VHDL treat FSMs as a primary design idiom. Traffic lights, elevators, and vending machines became the textbook examples precisely because failures in those systems cause physical harm, so their logic had to be built on something checkable. UI code contains the same structure implicitly, because every form passes through stages like pristine, editing, validating, submitting, and finally succeeded or failed, and dropdowns, media players, and drag interactions have the same character. The familiar bug where a modal closes but its dark overlay remains on screen occurs when the system occupies a state combination its designers never intended, which is precisely the situation an explicit machine makes unrepresentable. # Agents An agent graph describes how an agent moves between steps as it plans, calls tools, evaluates results, retries, asks a human, and eventually finishes. The field started with linear pipelines, moved to DAGs after admitting that agents fail and branch, and then had to allow cycles after admitting that agents also retry until verified and loop through rounds of human feedback, which leaves a directed cyclic graph with labeled edges, a start node, and terminal nodes. Mapping those parts onto the 5-tuple, the nodes are S, the edge labels are Σ, the edges are δ, the start node is s₀, and the terminal nodes are F, so the agent graph reconstructs the finite state machine under a new name. A realistic agent written explicitly as a machine looks like this: ``` const agent = { initial: 'planning', states: { planning: { PLAN_READY: 'executing', NEEDS_INFO: 'awaitingHuman', }, executing: { TOOL_RESULT: 'evaluating', TOOL_ERROR: 'executing', // self-loop: retry the tool BUDGET_EXCEEDED: 'failed', }, evaluating: { VERIFIED: 'done', NOT_GOOD_ENOUGH: 'planning', // a cycle, which a DAG cannot express UNSAFE: 'awaitingHuman', }, awaitingHuman: { APPROVED: 'executing', REJECTED: 'failed', CLARIFIED: 'planning', }, done: {}, // final failed: {}, // final }, }; ``` Making the machine explicit gives agents several properties that matter in production. Retry logic becomes a guarded edge, since the behavior of retrying until verified reduces to the single transition from evaluating back to planning with a guard requiring attempts to stay under a maximum, so runaway loops are ruled out by the structure itself instead of by a counter that someone hopefully remembered to add to a while loop. Control flow also stays out of the model's hands, which matters because LLM output is nondeterministic and letting it drive control flow directly produces agents that declare themselves finished when they are not. Under the machine, model output first gets classified into an event such as VERIFIED or UNSAFE, and the machine then checks whether that event has a legal transition from the current state, so a model can hallucinate an event but a hallucinated event with no matching edge goes nowhere, and the safety-critical route from UNSAFE to awaitingHuman ends up enforced by a lookup table rather than by instructions in a system prompt. Long-running agents become persistable as well, because the pair of current state and context is one small serializable value, so an agent waiting three days for human approval reduces to writing the pair ('awaitingHuman', ctx) into a database row, terminating the process, and rehydrating when the approval webhook fires. Durable workflow engines such as Temporal and AWS Step Functions are built on exactly this idea, and Step Functions goes as far as requiring the machine to be written out as JSON. Debugging gets simpler for the same reason, since the question of what the agent is doing becomes a single-column query and the question of how it got there becomes the event history, whereas answering the same questions about a free-form loop requires reconstructing behavior from traces. Multi-agent systems pair the machine naturally with the actor model, in which each agent is an actor holding private state and communicating only through messages, while each actor's internal behavior is a state machine whose events are the incoming messages. Erlang built this exact combination in the 1980s, its OTP framework ships a state-machine actor primitive called gen_statem, and the result has run telecom switches at extreme uptime for decades, which means multi-agent architecture is also a rediscovery, though one that belongs to a separate article. # Statecharts Flat state machines fail to scale in one specific way, which shows up as soon as a system has independent concerns. A text editor where bold, italic, and underline can each be toggled independently needs flat states like bold_italic, bold_underline, and bold_italic_underline to cover the combinations, so the combinatorial explosion from the boolean-flag section returns, now with strings instead of booleans. David Harel addressed this in 1987 with statecharts, introduced in his paper "Statecharts: A Visual Formalism for Complex Systems," which remains genuinely readable today. The formalism adds three constructs to the plain machine: - Hierarchy allows states to contain child states, so if connected contains syncing and idle, a single DISCONNECT transition defined on the parent covers every child and the duplication of shared transitions ends. - Parallel regions let independent concerns run side by side within one machine, so bold, italic, and underline become three parallel two-state regions, giving 2 + 2 + 2 = 6 states instead of 2 × 2 × 2 = 8 combined ones, and the gap widens rapidly as more regions are added. - History states make a parent remember which child was last active, so re-entering the parent resumes there, which is the mechanism behind a pause menu that returns exactly where you left off. Statecharts remain state machines formally and carry the same guarantees, since these constructs only compress the description of large machines rather than changing the model, and the state diagrams in UML are statecharts by another name. # When not to use this Genuinely sequential logic that runs A then B then C with no waiting, no external events, and no failure branches worth modeling belongs in a plain function, because state machines earn their cost only when events and time enter the picture. Truly continuous state, as in a physics simulation or a numerical solver, gains nothing from the framing either, because there are no discrete modes to model, and at the other end of the scale a two-state toggle needs nothing beyond useState(false). A reliable trigger in practice is the moment a second boolean appears that interacts with the first, or the moment a comment appears that reads "but only if we're currently...", because at that point the code has already grown the shape of a machine and would benefit from becoming one explicitly. # Wrapping up Loops and graphs both turned out to be state machines once their states, events, and transitions were named, and whatever abstraction arrives after them can be judged the same way. If it can answer those three questions, it is a state machine that can be reasoned about, and if it cannot, it is scattered control flow with better marketing. ## 相关链接 - [𝙩𝙮≃𝙛{𝕩}^A𝕀²·ℙarad𝕚g𝕞 reposted](https://x.com/TaNGSoFT) - [vixhaℓ](https://x.com/TheVixhal) - [@TheVixhal](https://x.com/TheVixhal) - [15K](https://x.com/TheVixhal/status/2079274210367775052/analytics) - [Upgrade to Premium](https://x.com/i/premium_sign_up) - [2:36 AM · Jul 21, 2026](https://x.com/TheVixhal/status/2079274210367775052) - [15.5K Views](https://x.com/TheVixhal/status/2079274210367775052/analytics) - [View quotes](https://x.com/TheVixhal/status/2079274210367775052/quotes) --- *导出时间: 2026/7/21 09:36:01* --- ## 中文翻译 # 状态机：从循环到图（详解） **作者**: vixhaℓ **日期**: 2026-07-20T18:36:17.000Z **来源**: [https://x.com/TheVixhal/status/2079274210367775052](https://x.com/TheVixhal/status/2079274210367775052) --- ![Image](/doc/3220/image/img_f7034d822435.jpg) 每隔几个月，智能体构建领域就会采用一种新的抽象，从链到循环，再到如今的图，而每一次这些抽象最终都被证明是同一个底层思想换了个名字。这个思想就是有限状态机，这是一种自20世纪50年代起就存在于教科书中的形式化方法，它规范了 TCP 协议和你 CPU 中的控制单元，并且已经以偶然的形式存在于大多数代码库中，由布尔标志和散落的条件语句拼凑而成。既然有意识地实现一个状态机几乎不需要额外成本，而且能带来强有力的保证，那么值得好好理解这个模式，因此本文将涵盖其理论、实现，以及智能体框架为何在未经承认的情况下趋同于它。 # 核心状态机回答一个单一的问题，即：给定当前状态，当一个事件发生时，下一个状态是什么？写成一个函数，就像这样： ``` transition(state, event) -> nextState ``` 每个程序其实都已经以这种方式运作，因为 React 组件、请求处理器、游戏循环和 LLM 智能体都持有某些状态，接收某些事件，并因此转移到一个新的状态。由于这种结构存在于每个程序中，无论是否有人刻意设计过，开发者真正做的唯一决定就是转移逻辑放在哪里，而通常它最终散落在事件处理器和条件语句中，没有人能看到完整的全貌。把它写成一个显式的函数，会将系统的完整行为汇集到一处，本文其余部分描述的每一个好处都源于这一举动。 # 形式化定义有限状态机在形式上是一个五元组： M = (S, Σ, δ, s₀, F) 其中： - S 是状态的有限集合 - Σ 是事件的有限集合，称为输入字母表 - δ : S × Σ → S 是转移函数 - s₀ ∈ S 是初始状态 - F ⊆ S 是终态集合由于 S 是有限的，且 δ 可以写成一个表格，系统的完整行为是可以被枚举的，这意味着每一个可达状态和每一种可能的转移序列都可以被列出来并加以检查。任意编写的代码缺乏这种性质，因为其状态空间是无界的，其控制流依赖于运行时的值，而这种差异正是协议、正则表达式引擎和硬件都以状态机来规范的原因，因为有限的规范可以被穷尽检查，在安全关键的场景中甚至可以被证明是正确的。理论中的一个区别在实践中出现得足够频繁，值得了解。如果 δ(state, event) 恰好产生一个下一个状态，该机器被称为确定性有限自动机（DFA）；如果它可以产生一组可能的下一个状态，则被称为非确定性有限自动机（NFA）。非确定性听起来很抽象，但正则表达式引擎会把每个模式编译成 NFA，然后要么直接模拟它，要么通过子集构造法将其转换为 DFA，这意味着写一个像 a+b*c 这样的表达式，就相当于在编写一个状态机，并让编译器为你构建它。本文后面讨论的每个框架，包括智能体编排库，都是围绕这个 δ 函数的封装，记住这一点会让评估新工具变得容易得多。 # 它解决的问题：不可能的状态想想数据获取通常是如何被建模的： ``` let isLoading = false; let isError = false; let isSuccess = false; let data = null; let error = null; ``` 三个布尔值产生 2³ = 8 种组合，其中也许只有三种是有意义的，而像 isLoading && isError 这样的组合根本不描述任何连贯的情况，但类型系统却允许它存在，最终某个竞态条件会构造出这种组合，导致加载指示器渲染在错误信息之上，而错误信息又叠加在过期数据之上。这个问题呈指数级增长，因为每增加一个标志，状态空间就翻一倍，而有效状态的数量增长却慢得多，所以一个带有五个标志的组件有 32 种可能的组合，而合法的也许只有五种。通常的应对方式是编写防御性条件，如 if (isLoading && !isError && ...)，试图手动圈出有效区域，而在不断增长的代码库中，总会有某种情况被遗漏。将同一个功能建模为状态机，首先要用一个枚举来取代这些标志： ``` type State = 'idle' | 'loading' | 'success' | 'failure'; ``` 在这种表示下，"加载中"和"出错"的组合根本无法被写出来，因此这一整类自相矛盾的标志 bug 在类型层面就消失了，而不是靠测试来捕获。函数式程序员将此描述为"让非法状态不可表示"，而状态机将同一原则应用于系统随时间的演变方式，而非单个数据结构。有两个保证直接源于这种结构： 1. 系统在任何时刻都恰好处于一个状态。 2. 移动只能沿着你定义的转移进行。第二个保证的实际分量很容易被低估。在基于标志的代码中，任何处理器都可以在任何时刻触发并修改任何东西，而在状态机中，一个从当前状态没有定义转移的事件根本不做任何事情。当用户双击提交按钮时，第二个 SUBMIT 事件到达时机器正处于 loading 状态，而由于 loading 没有定义 SUBMIT 转移，机器会忽略它，这意味着重复提交的 bug 从根本上就不存在，也从来不需要防抖、锁或禁用按钮的标志来防止它。 # 实现转移函数就是数据，而最简洁的实现会把它当作数据来对待，这在大多数语言中意味着一个普通的查找表： const machine = { initial: 'idle', states: { idle: { FETCH: 'loading', }, loading: { RESOLVE: 'success', REJECT: 'failure', CANCEL: 'idle', }, success: { REFETCH: 'loading', }, failure: { RETRY: 'loading', }, }, }; function transition(state, event) { return machine.states[state]?.[event] ?? state; // 未定义事件：保持原状态 } ``` 仅仅这一个函数就是一个完整的状态机解释器，而这种表格化的结构带来了几个实际的好处。一个功能的全部行为可以在一屏内展示完毕，在代码评审中，对这个对象的 diff 直接展示行为变更，而不需要评审者去模拟控制流；此外，这个对象可以被序列化、存储在数据库中、通过网络发送，或自动渲染成图表。测试的性质也随之改变，因为状态乘以事件构成一张有限的表格，测试套件可以遍历整张表格，而不是抽样几条代码路径并寄希望于重要路径已被覆盖。同一台机器也可以用 switch 语句来写： ``` function transition(state: State, event: Event): State { switch (state) { case 'idle': return event.type === 'FETCH' ? 'loading' : state; case 'loading': switch (event.type) { case 'RESOLVE': return 'success'; case 'REJECT': return 'failure'; case 'CANCEL': return 'idle'; default: return state; } case 'success': return event.type === 'REFETCH' ? 'loading' : state; case 'failure': return event.type === 'RETRY' ? 'loading' : state; } } ``` 这个版本更冗长，但在 TypeScript 或 Rust 中，编译器会强制穷举检查，因此新增一个状态却忘记处理它时会导致构建失败，而不是在生产环境中出错。 Rust 通过 typestate（类型状态）模式将这一思想发挥到极致：每个状态成为一个独立的类型，无效的状态转换根本无法通过编译。任何写过 Redux reducer 或使用过 useReducer 的人，其实都已经写过形如 (state, action) => nextState 的函数，所以这种模式比听起来要熟悉得多。区别在于，大多数 reducer 允许任何 action 在任何状态下修改任何内容，这实际上以更好的语法悄悄重新引入了布尔标志的问题；而一旦 reducer 在处理事件之前先检查当前状态，它就成为一个真正的状态机——正是这一顺序上的改变，承载了上述所有的保证。 # 有限状态与上下文此时一个合理的质疑是：真实的应用状态包括表单输入、数组和时间戳，这些都无法枚举，因此有限性的要求似乎把真实程序排除在外了。标准的答案是将状态拆分为扮演不同角色的两个部分。有限状态捕获系统所处的模式，使用诸如 idle、loading、editing 或 disconnected 这样的值，这一部分保持定性、小且可枚举。上下文（context），也称为扩展状态（extended state），保存所有定量的内容，例如表单值、重试次数和获取到的数据，这一部分可以是无界的，因为机器从不去枚举它。机器管理模式，而上下文随行陪伴；以这种方式扩展的机器在形式上被称为扩展状态机，其转换函数返回更多的信息： ``` transition(state, context, event) -> (nextState, nextContext, actions) ``` 下面的例子实现了最多重试三次的逻辑： ``` function transition(state, ctx, event) { if (state === 'failure' && event.type === 'RETRY') { if (ctx.retries < 3) { return ['loading', { ...ctx, retries: ctx.retries + 1 }, ['fetch']]; } return ['gaveUp', ctx, ['notifyUser']]; } // ... } ``` 这段代码中出现了三个标准概念，值得为其命名。守卫（guard）是附加在转换上的条件，这里的检查 ctx.retries < 3 就是一个守卫，它使得同一个 RETRY 事件在还有尝试次数时导向 loading，而在次数用尽后导向 gaveUp。动作（action）是转换触发的副作用，返回的 ['fetch'] 就是一个动作，重要的细节在于：机器只决定应该发生哪些副作用并将其返回，而由函数外部的解释器实际执行它们，这使转换函数保持纯粹，并且无需任何 mock 就能对其进行测试。 Redux 中间件以及 Elm 从 update 函数返回命令的模式遵循同样的分离原则。进入和退出动作（entry and exit actions）补全了这一整套概念，它们是附加在进入或离开某个状态时的副作用，而不是附加在任何特定的边上：进入 loading 时启动加载指示器和超时计时器，离开 loading 时取消两者，无论进出该状态的是四条可能的边中的哪一条。退出动作尤其能消除围绕计时器泄漏、悬空订阅和被遗忘的清理工作的一系列 bug，因为当取消操作被附加到 loading 的退出时，每一条离开该状态的路径都会执行它，没有任何代码路径能让计时器继续运行。用标志位实现同样的可靠性，需要在每一个可能离开 loading 模式的处理函数中记住清理操作，而实践中总会有某个处理函数忘记。 # Mealy 机与 Moore 机经典文献根据输出附加的位置区分机器的两种变体。在 Moore 机中，输出仅取决于当前状态，例如交通灯在机器处于绿色状态期间持续亮灯，因此输出实际上存在于图的节点上。在 Mealy 机中，输出取决于状态和事件的组合，例如自动售货机在 idle 状态下收到 COIN 事件时出货，因此输出存在于边上。这两种变体在表达能力上是等价的，并且可以相互转换，实际系统往往混合使用两者，因为入口和出口动作偏向 Moore 风格，而迁移动作则偏向 Mealy 风格。除了帮助理解较早的论文和硬件文档之外，这一区分还提供了一个真正有用的设计问题，即某个给定的效果应该是因为系统处于某个状态而发生，还是因为它到达该状态的方式而发生。由于这两种答案在边缘情况下的行为不同，将二者混淆会产生隐蔽的 bug。 # 这一模式早已在运行的地方若干主要的基础设施都被规定为状态机，观察它们可以看出这一模式远远早于它目前的重新发现。 TCP 通过其状态图定义了每一个连接，其状态包括 LISTEN、SYN_SENT、ESTABLISHED、FIN_WAIT_1 和 TIME_WAIT。早在 1981 年，RFC 793 就以状态图的形式规定了该协议，因为对于如此关键的东西，散文式的描述太模糊了，直到今天，实现之间的分歧仍通过指向这台机器来解决。正则表达式引擎运行在 DFA 上，它以恒定时间处理每个输入字符且无需回溯，grep 的速度直接归功于底层模型的这一特性，而不是任何实现上的巧思。游戏 AI 自街机时代起就使用这一模式，敌人行为遵循诸如巡逻到追击到搜索再回到巡逻的迁移，由看到或失去玩家等事件驱动。《吃豆人》中的幽灵是四个小型状态机，它们出了名的鲜明个性完全来自四张不同的迁移表。在硬件领域，这一模式是基础性的，因为 CPU 就是一个时钟驱动的状态机，Verilog 和 VHDL 都把 FSM 视为主要的设计惯用法。红绿灯、电梯和自动售货机之所以成为教科书式的例子，正是因为这些系统的故障会造成人身伤害，所以它们的逻辑必须建立在可检验的东西之上。 UI 代码中隐含着同样的结构，因为每个表单都会经历诸如初始、编辑中、校验中、提交中，最终成功或失败等阶段，下拉菜单、媒体播放器和拖拽交互也具有相同的性质。那种熟悉的 bug——模态框关闭了但它的深色遮罩仍留在屏幕上——正是发生在系统占据了设计者从未打算让其存在的状态组合时，而这恰恰是显式状态机使其无法表示的情况。 # 智能体智能体图描述了一个智能体在规划、调用工具、评估结果、重试、询问人类并最终完成的过程中如何在各个步骤之间移动。这个领域从线性流水线开始，在承认智能体会失败和分支后转向了 DAG，随后又不得不允许循环，因为承认了智能体还会重试直至验证通过，并在多轮人类反馈中循环，这就形成了一个带有标注边的有向循环图，包含一个起始节点和若干终止节点。把这些部分映射到五元组上，节点是 S，边标签是 Σ，边是 δ，起始节点是 s₀，终止节点是 F，因此智能体图以一个新名字重构了有限状态机。一个以显式机器形式编写的真实智能体如下所示： ``` const agent = { initial: 'planning', states: { planning: { PLAN_READY: 'executing', NEEDS_INFO: 'awaitingHuman', }, executing: { TOOL_RESULT: 'evaluating', TOOL_ERROR: 'executing', // self-loop: retry the tool BUDGET_EXCEEDED: 'failed', }, evaluating: { VERIFIED: 'done', NOT_GOOD_ENOUGH: 'planning', // a cycle, which a DAG cannot express UNSAFE: 'awaitingHuman', }, awaitingHuman: { APPROVED: 'executing', REJECTED: 'failed', CLARIFIED: 'planning', }, done: {}, // final failed: {}, // final }, }; ``` 将机器显式化能为智能体带来若干在生产环境中至关重要的特性。重试逻辑变成了带守卫的边，因为重试直至验证通过的行为可以化简为从 evaluating 迁回 planning 的单一迁移，并附带一个要求尝试次数不超过上限的守卫条件，因此失控循环被结构本身排除，而不是靠某人希望记得在 while 循环中加上的计数器。控制流也不再交由模型掌握，这一点很重要，因为 LLM 的输出是非确定性的，让它直接驱动控制流会产生那些明明没完成却宣称自己已完成的智能体。在机器之下，模型输出首先被分类为一个事件，例如 VERIFIED 或 UNSAFE，然后机器检查该事件从当前状态出发是否具有合法的迁移。因此模型可以幻觉出一个事件，但没有匹配边的幻觉事件不会产生任何效果，而从 UNSAFE 到 awaitingHuman 这条关乎安全的路线最终由查找表来强制执行，而不是靠系统提示词中的指令。长时间运行的智能体也因此变得可持久化，因为当前状态和上下文组成的二元组是一个小的可序列化值，于是一个等待人工审批三天的智能体可以化简为把二元组 ('awaitingHuman', ctx) 写入数据库行、终止进程，并在审批的 webhook 触发时恢复运行。 Temporal 和 AWS Step Functions 这类持久化工作流引擎正是建立在这一理念之上，Step Functions 甚至要求把机器以 JSON 的形式明确写出来。调试也因此变得更简单，因为“智能体在做什么”这个问题变成了一个单列查询，而“它是如何到达这里的”则变成了事件历史；而对于自由形式的循环，回答同样的问题则需要从追踪记录中重建行为。多智能体系统让机器与Actor模型天然契合——每个智能体都是一个持有私有状态的Actor，仅通过消息进行通信，而每个Actor的内部行为是一台状态机，其事件就是接收到的消息。 Erlang在20世纪80年代就构建了这种精确的组合，其OTP框架提供了一个名为gen_statem的状态机Actor原语，其成果已在电信交换机上以极高的运行时间运行了几十年，这意味着多智能体架构同样是一次重新发现，不过这属于另一篇文章的内容了。 # 状态图（Statecharts）扁平状态机在一种特定情况下无法扩展，一旦系统有了相互独立的关注点，这个问题就会显现。一个文本编辑器中，粗体、斜体和下划线各自可以独立切换，就需要像 bold_italic、bold_underline 和 bold_italic_underline 这样的扁平状态来覆盖各种组合，于是布尔标志部分提到的组合爆炸又回来了，只不过这次是字符串而不是布尔值。 David Harel在1987年的论文《Statecharts: A Visual Formalism for Complex Systems》中通过状态图解决了这个问题，这篇论文至今仍然非常易读。该形式化为普通状态机增加了三种构造： - 层次结构允许状态包含子状态，因此如果 connected 包含 syncing 和 idle，在父状态上定义的一个 DISCONNECT 转换即可覆盖所有子状态，共享转换的重复就此终结。 - 并行区域让相互独立的关注点在同一台机器中并行运行，因此粗体、斜体和下划线成为三个并行的双状态区域，得到 2 + 2 + 2 = 6 个状态，而不是 2 × 2 × 2 = 8 个组合状态，并且随着更多区域的加入，差距会迅速扩大。 - 历史状态让父状态记住最后处于活动状态的是哪个子状态，因此重新进入父状态时会从那里恢复，这正是暂停菜单能够准确返回你上次离开位置背后的机制。状态图在形式上仍然是状态机，并具有相同的保证，因为这些构造只是压缩了大型机器的描述，而并未改变模型本身，而UML中的状态图就是换个名字的状态图。 # 何时不应使用它真正顺序执行的逻辑——先运行A再运行B再运行C，没有等待、没有外部事件、没有值得建模的失败分支——应该放在一个普通函数中，因为只有当事件和时间进入画面时，状态机的成本才物有所值。真正的连续状态，比如物理模拟或数值求解器中的状态，也无法从这种框架中获益，因为没有需要建模的离散模式；而在另一个极端，一个双状态切换开关只需要 useState(false) 就足够了。实践中一个可靠的触发信号是：当出现第二个与第一个相互作用的布尔值时，或者当代码中出现"但仅当我们当前处于……"这样的注释时，因为到了那个时刻，代码已经长出了状态机的形状，明确地把它变成状态机将会带来好处。 # 总结循环和图在命名了它们的状态、事件和转换之后，最终都被证明是状态机，而在它们之后出现的任何抽象都可以用同样的方式来评判。如果它能够回答这三个问题，它就是一台可以被推理的状态机；如果不能，它就是包装得更漂亮的散乱控制流。 ## 相关链接 - [𝙩𝙮≃𝙛{𝕩}^A𝕀²·ℙarad𝕚g𝕞 reposted](https://x.com/TaNGSoFT) - [vixhaℓ](https://x.com/TheVixhal) - [@TheVixhal](https://x.com/TheVixhal) - [15K](https://x.com/TheVixhal/status/2079274210367775052/analytics) - [Upgrade to Premium](https://x.com/i/premium_sign_up) - [2:36 AM · Jul 21, 2026](https://x.com/TheVixhal/status/2079274210367775052) - [15.5K Views](https://x.com/TheVixhal/status/2079274210367775052/analytics) - [View quotes](https://x.com/TheVixhal/status/2079274210367775052/quotes) --- *导出时间: 2026/7/21 09:36:01*