守株阁

上一篇文章把 lambda 演算拆成三种表达式：变量、函数、调用。示例只做了最小的一步替换，用来说明函数应用可以变成表达式重写。 本文把这件事补成一个规约器：给定一个 lambda 表达式，持续执行 beta 规约，打印每一步轨迹，并处理替换过程中最容易出错的变量捕获问题。这个规约器仍然很小，但已经具备解释器和 AST 重写器的基本骨架。 规约器要解决什么 lambda 演算的核心计算规则是 beta 规约： 12(x -> body) argument -> body 中的自由 x 替换成 argument 例如： 12(x -> x) a -> a 更复杂一点的例子： 123(((x -> (y -> x)) a) b) -> ((y -> a) b) -> a 规约器需要完成三件事： 职责 作用 找到可规约位置 判断哪一个调用先执行 做安全替换 只替换自由变量，避免误改绑定变量 重复执行 直到表达式无法继续变化 这和解释器很接近。区别在于解释器通常维护环境和值，lambda 规约器直...

图灵机用纸带、读写头和指令循环描述计算。lambda 演算换了一条路：它不用可变纸带，也不用状态跳转，只保留函数定义、函数调用和变量替换。 这个模型看起来比图灵机更不像机器，却和图灵机有同等表达能力。图灵机强调“有限控制怎样改写存储”，lambda 演算强调“表达式怎样通过函数应用逐步化简”。从工程角度看，它把计算从指令循环翻译成表达式重写。 本文先建立 lambda 演算的最小语法，用 Python 表示变量、函数和调用，再通过一个小例子展示函数怎样返回函数、调用怎样变成替换。 三种表达式 lambda 演算的核心语法只有三种。 形式 示例 含义 变量 x 一个名字 函数 x -> x 接收参数 x，返回表达式 x 调用 (x -> x) a 把函数应用到参数 a 函数也叫抽象，调用也叫应用。为了贴近 Java 程序员熟悉的形式，本文用 x -> x 表示 lambda 表达式，而不用希腊字母写法。 最小模型可以写成一棵表达式树： 1234Expression = Variable(name) | Function(param...

上一篇文章已经写出一台最小 DTM：读取当前格，写入一个符号，移动读写头，然后停机。那台机器能展示图灵机的组成，但还不像一段程序。 本文复用同一套 Python 结构，把图灵机写成一个更接近算法的例子：对纸带上的二进制数加一。输入是 1011，输出是 1100。机器需要先移动到数字右侧的空白格，再从右向左处理进位。这个过程会经过多个状态和多次纸带改写，适合观察“有限控制 + 可变纸带”怎样形成完整计算。 二进制加一的规则 二进制加一可以拆成两个阶段。 第一阶段从最左侧开始，一直向右移动，直到读到数字后面的空白格 _。 第二阶段从空白格左移一格，开始处理进位： 当前符号 写入符号 下一步 1 0 继续向左进位 0 1 进位结束，停机 _ 1 数字整体增长一位，停机 以 1011 为例，最右侧两个 1 都会变成 0，左边的 0 变成 1，结果得到 1100。 11011 + 1 = 1100 这里需要两个控制状态： 状态 含义 seek_right 向右寻找数字末尾 carry 从右向左处理进位 halt 计算完成 图灵机的状...

DFA 只有有限状态。NFA 允许同时保留多个状态。PDA 在有限状态之外加了一只栈，可以处理任意深度的嵌套。图灵机再往前走一步：它把栈换成一条可以读、写、左右移动的纸带。 这个变化很小，却足以把机器能力推到通用计算。图灵机仍然只有有限个控制状态，每一步仍然按规则机械执行；不同的是，机器可以在纸带上写下中间结果，之后再移动回来读取。程序状态和可变存储被明确分开。 本文先写一台最小确定性图灵机（Deterministic Turing Machine，DTM）。示例很小：读写头从第一个字符开始，把当前位置的符号改成 1，向右移动一格，然后停机。下一篇再用同一套结构实现一个稍微有算法味的纸带程序。 图灵机比 PDA 多了什么 PDA 的栈只能操作一端。读写都发生在栈顶，历史只能以后进先出的方式取回。图灵机的纸带更自由：读写头可以向左或向右移动，机器可以反复回到某个位置修改内容。 模型 有限控制 可增长存储 读写位置 典型能力 DFA / NFA 有 无 无 正则语言 PDA 有 栈 栈顶 嵌套结构 图灵机 有 纸带 当前格，可左右移动 通用计算 这个表里...

DFA 和 NFA 都只有有限状态。状态数量再多，也仍然是有限的。它们适合识别固定模式、分支和重复，但面对任意深度的嵌套结构时会遇到硬边界。 括号匹配就是最小例子。()、(())、(()()) 都合法，(()、())、)( 都非法。有限状态机可以识别“最多三层括号”“最多十层括号”，但只要深度没有上限，有限状态就不够用了。机器需要一种能随输入增长的记忆结构。 下推自动机（Pushdown Automaton，PDA）给有限状态机加了一只栈。状态仍然有限，但栈可以随着输入增长。读到左括号就压栈，读到右括号就弹栈；输入结束后，栈如果回到底部符号，括号就匹配完成。 栈解决的是后进先出问题 括号嵌套天然是后进先出结构。最近打开的左括号，必须最先被右括号关闭。 123456789(()())1234561: push (2: push (3: pop (4: push (5: pop (6: pop ( 第 2 个字符打开的括号，要在第 3 个字符关闭；第 4 个字符打开的括号，要在第 5 个字符关闭；第 1 个字符打开的括号最后关闭。这个顺序正好是栈。 有限状态机无法保存任意多个...

DFA 和 NFA 已经把“字符串识别”拆成了状态、输入字符、转移规则和接受状态。正则表达式站在更高一层：开发者写 a(b|c)*，机器负责把它变成可以执行的匹配过程。 这篇文章只处理传统正则表达式的核心结构：字面量、连接、选择和重复。现代正则 API 还包含捕获组、环视、反向引用、贪婪/非贪婪策略等扩展；这些扩展属于工程实现层，不影响本文要展示的主线。 核心链路很短： 1regex text -> regex AST -> NFA design -> accepts(text) 本文不写正则 parser，直接手工构造 AST。前面文章已经展示过“字符串到 AST”的方法，这里把注意力放在第二步：一个正则 AST 节点怎样编译成 NFA。 正则表达式先变成结构 a(b|c)* 不是一串神秘字符。按传统正则语义，它可以拆成四种结构。 正则片段 AST 节点 含义 a Literal("a") 匹配一个字符 bc Concatenate(Literal("b"), Literal("c"...

DFA 每次只处在一个状态里。读取一个字符，规则表给出唯一的下一个状态。这个约束让 DFA 很容易实现，也让它的执行轨迹很干净：current_state + character -> next_state。 非确定性有限自动机（Nondeterministic Finite Automaton，NFA）放宽了这个约束。同一个状态读取同一个字符时，可以走到多个下一状态；机器还可以在不消耗字符的情况下移动到别的状态。NFA 的实现方式并不神秘：把“当前状态”从单个值改成一个集合，一次保留所有可能路径。 这篇文章用 Python 写一个 NFA，识别两个字符串：ab 和 ba。这个示例足够小，但能完整覆盖 NFA 的两个核心机制：分支和空转移。 非确定性不是随机 “非确定性”容易被误解成机器随机选择一条路。NFA 的更好理解是：同一时刻保留多条候选路径，只要其中一条路径最后进入接受状态，整个输入就被接受。 问题 DFA NFA 当前状态 一个状态 一组状态 同一输入的下一状态 唯一 可以有多个 是否允许不读字符就移动 不允许 允许 接受条件 当前状态...

上一篇用指称语义把程序翻译成 Python 函数。程序语义这一段到这里已经形成闭环：AST 给出结构，大步语义、小步语义和指称语义分别给出不同角度的含义。接下来进入自动机。问题从“程序怎样执行”换成“机器怎样根据输入移动到下一个状态”。 确定性有限自动机（Deterministic Finite Automaton，DFA）是自动机部分的起点。它没有变量表，没有栈，没有堆，也没有可写纸带；它只记住一个当前状态，然后逐个读取输入字符。每读一个字符，机器就根据一张规则表换到下一个状态。输入读完后，当前状态如果属于接受状态，字符串就被接受；否则被拒绝。 这个模型很小，却足够解释很多工程直觉：订单状态流转、协议解析、词法分析、简单规则匹配，都可以先压成“当前状态 + 输入 -> 下一个状态”的形式。 从业务状态机收缩到形式模型 Java 程序员对状态机并不陌生。订单可以从 CREATED 变成 PAID，再变成 SHIPPED；审批单可以从 DRAFT 变成 SUBMITTED，再变成 APPROVED 或 REJECTED。这些状态机通常带着业务动作、数据库事务、权限检查、通知...

复旦、北大、上海奇绩智峰联合出的 Agentic Harness Engineering（AHE）做了一件很具体的事：让 GPT-5.4 驱动的 Coding Agent 在 Terminal-Bench 2 上的 pass@1 从 69.7% 涨到 77.0%，绝对 +7.3 个百分点，超过 OpenAI 官方 Codex-CLI 的 71.9%，也超过同期两条主流自演化基线 ACE（68.9%）和 TF-GRPO（72.3%）。换到 GPT-6.0 上，他们的同名 NexAU-AHE 在 Terminal-Bench 2 leaderboard 上跑到 84.7%，全球前三。 值得记下来的不是这几个数字，而是它怎么涨上去的。AHE 没有调模型权重，没有改评估框架，只让一个 Evolve Agent 在一个被严格围出来的工作区里改 Harness 自己。这件事能跑通的关键，是它把"哪些组件可以改、改了之后哪里能看到信号、看到信号之后用什么口径决策"全部当成一等公民设计了出来。 上一篇 把 Harness Engineering 的概念边界讲清楚：人怎么把 A...

很多人都遇到过这种场景：一个 JVM 进程因为 -Xmx 写错了一个字符，启动起来就死掉，控制台一行日志都没有；一个 Node.js CLI 比如 opencode 在前台 hang 住，光标不闪，也不退出；一个 Spring Boot 服务被 systemd 拉起来，systemctl status 显示 running，但端口永远不开。stderr 看不到、源码也没有，只能反复重启。 这类问题的共同点不是程序"出 bug"，而是进程在"出第一行日志"之前就已经失败或卡住。常规的"看日志找异常"那一套这时候没东西可看。需要的是另一类方法论：把进程当黑盒，从外部撬开它的状态。 一、先把"看不到日志"分成四种情况 把"启动期黑盒"展开来看，至少是四种性质完全不同的故障。混在一起调，方向就错了。 类别 特征 进程状态 主要工具方向 A. crash 静默 进程已经退出，但没看到任何 stderr 不存在 找输出去向；看 OS / runtime 留下的尸检文件 B....