守株阁

这个系列从《计算的本质》重新出发，用 Python 重写核心实验，再把每个模型映射到 Java 程序员熟悉的工程结构。一路走下来，主题并不是记住更多术语，而是换一种方式观察程序。 程序可以是语法树，执行可以是规约，协议可以是自动机，嵌套可以靠栈，通用计算可以由解释器承载，分析工具也可以承认不精确并保持有用。 本文不再引入新模型，只把前面十几篇文章收束成一张工程地图。 概念地图 先把系列里最重要的模型压成一段可运行的概念地图。 12345678910concept_map = [ ("AST / 语义", "解释器、DSL、规则执行"), ("DFA / NFA / 正则", "协议状态、校验器、词法分析"), ("PDA / 栈", "parser、嵌套结构、调用栈"), ("图灵机 / 通用性", "VM、脚本引擎、程序作为数据"), ("停机问题 / 抽象解释", &...

停机问题说明，对任意程序做完备且正确的停机判断是不可能的。工程分析工具并没有因此失去意义。它们换了目标：不追求精确理解所有程序，而是用可计算的抽象信息给出有用结论。 抽象解释就是这个方向的代表。它把具体值集合映射到抽象域里，用保守规则模拟程序执行。只要抽象规则覆盖了所有可能的具体行为，分析结果就可以用于告警、优化或拒绝高风险程序。 本文用区间分析做一个最小模型：变量不再保存单个整数，而是保存可能取值范围。 从具体值到抽象值 具体执行关心单个值： 123x = 3y = 5z = x + y = 8 抽象执行关心值的集合。若只知道 x 在 0 到 10 之间，y 等于 5，就可以推出： 123x in [0, 10]y in [5, 5]z = x + y => z in [5, 15] 这个结果不精确。z 不一定等于区间里的每个数，但所有可能结果都被包含在 [5, 15] 里。保守性比精确性更重要：不能漏掉可能发生的值。 区间抽象域 区间可以用两个端点表示。 12345678910111213141516from dataclasses import dataclass@...

上一篇文章用寄存器机解释器说明了通用性：程序可以编码成数据，解释器可以读取这份数据并模拟执行。通用性带来强大表达能力，也带来一个边界问题：能不能写一个程序，判断任意程序在任意输入上是否会停机。 答案是否定的。停机问题说明，不存在一个对所有程序和输入都正确的通用停机判定器。工程里可以做超时、步数限制、静态分析和资源预算，但这些方法要么不完整，要么会保守拒绝，要么只覆盖有限范围。 本文先用一个可运行的有界检查器展示工程近似，再用自引用反证解释为什么通用判定器不存在。 问题形式 停机问题可以写成一个理想函数： 1halts(program, input_data) -> True / False 它的承诺是： 返回值 含义 True program(input_data) 最终会停机 False program(input_data) 会一直运行 难点在“任意程序”和“任意输入”。判断某个具体程序很容易；判断所有程序则会遇到自引用。 工程里常见的近似：有界执行 最朴素的方法是只运行有限步。如果步数内停机，就返回 True；如果步数用完还没停，就返回 Fa...

前面的文章已经走过两条计算模型路线。图灵机用纸带和指令循环表达计算，lambda 演算用函数应用和表达式规约表达计算。Church 编码进一步说明，数字和布尔值也可以由函数行为构造出来。 这些模型看起来差异很大，却都能表达同一类可计算过程。通用性的核心在于：一种机器可以把另一种机器的程序和数据编码成自己的数据，然后按规则解释这份编码。 本文用一个小型寄存器机解释器展示“程序作为数据”这件事。示例不会追求指令集完整性，只展示通用解释器的基本形状。 从专用机器到通用机器 DFA、PDA、某个固定规则表的图灵机，都像专用机器。规则写死以后，它只能识别或执行某一类任务。 通用机器多了一层编码： 1encoded_program + input_data + interpreter -> output_data 程序不再只是宿主语言里的代码，也可以是一段数据。解释器读取这段数据，根据其中的指令改变配置。只要编码方式足够表达指令和数据，解释器就能模拟很多不同程序。 这个结构正是虚拟机、脚本引擎和 DSL runtime 的共同骨架。 场景 程序数据 解释器 JVM by...

lambda 演算的基本语法只有变量、函数和调用。前一篇已经写出规约器，说明函数应用可以通过替换一步步化简。 接下来的问题是数据从哪里来。日常编程语言有数字、布尔值、条件表达式和集合；纯 lambda 演算没有这些原语。Church 编码给出一种极端答案：数据可以表示成行为。布尔值是“选择左边还是右边”的函数，数字是“把某个函数重复执行多少次”的函数。 本文用 Python 高阶函数实现 Church boolean 和 Church numeral，再把它们映射回工程直觉。 数据也可以是行为 普通编程里，数字 2 看起来是一块数据。Church 编码换一个定义： 12 = 接收函数 f 和初始值 x，然后执行 f(f(x)) 也就是说，数字不再保存为整数对象，而是保存为“重复应用函数的次数”。 布尔值也类似： 12true = 选择第一个分支false = 选择第二个分支 这个视角把“值是什么”改成“值能做什么”。在 lambda 演算里，只要函数和调用足够表达这些行为，就可以构造出数字、布尔值和条件选择。 Church 布尔值 Church boolean 的定义很短。 ...

上一篇文章把 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 个字符打开的括号最后关闭。这个顺序正好是栈。 有限状态机无法保存任意多个...