上一篇把《计算的本质》的主线压成了一句话：计算就是用有限规则描述可以机械执行的状态变化过程。从这一篇开始，系列进入代码实验。后面的解释器、自动机、图灵机、lambda 演算、抽象解释都需要一套很小的实验语言。

本文选择 Python。它在这里承担两个角色：一方面，代码足够短，方便把注意力留给计算模型；另一方面，Python 和 Java 的距离刚好合适，读者可以看清哪些部分属于模型本身，哪些部分只是语言样板。

本文按 Python 3.12 写代码。大部分示例在 Python 3.10 及以上也能运行，因为结构化模式匹配从 Python 3.10 开始可用。

只需要一只小工具箱

后续文章不会用到完整 Python 知识。实验语言只需要七件工具。

工具 用途 后续出现位置 Java 对照
dataclass 定义不可变语法节点 AST、图灵机配置、lambda 项 record
match 按节点类型分派 解释器、规约器 switch + 模式匹配
函数对象 把规则当值传递 指称语义、lambda 演算 Function<T, R>
闭包 保存环境和值 变量绑定、Church 编码 捕获变量的 lambda
tuple / frozenset 表示不可变结构 状态集合、纸带片段 不可变集合
dict / set 表示查表和状态集 自动机、环境、转移函数 Map / Set
类型标注 帮读者看结构 文章代码说明 泛型和接口

这些工具有一个共同点：它们都服务于“把规则写成数据，再让函数解释数据”。后续所有模型都可以拆成两层：一层是结构，另一层是解释结构的规则。

用 dataclass 写语法树

第一个实验对象是表达式语言。它只有两种表达式：数字和加法。

1
2
3
4
5
6
7
8
9
10
11
12
from dataclasses import dataclass


@dataclass(frozen=True)
class Number:
    value: int


@dataclass(frozen=True)
class Add:
    left: object
    right: object

@dataclass 自动生成构造方法、相等性比较和调试输出。frozen=True 让对象创建后不能再改。这个约束对后面的计算模型很重要：语法树一旦创建，它就像数学对象一样稳定；求值过程产生新值或新状态，原节点不被偷偷改写。

同样结构放到 Java 里，会接近这段代码：

1
2
3
4
sealed interface Expr permits Num, Add {}

record Num(int value) implements Expr {}
record Add(Expr left, Expr right) implements Expr {}

Java 版本更强调类型边界。Python 版本省掉接口和文件组织后，读者会更快看见这件事：程序可以先表示为一组普通对象。

模式提炼：先把文本变成结构

source text -> structured nodes -> interpreter

编译器、解释器、规则引擎、模板引擎都遵循这个模式。文本进入系统后，第一步通常是变成结构化节点。只有结构稳定下来，后面的求值、优化、检查、转换才有对象可操作。

场景 结构节点 后续规则
表达式语言 Number / Add 求值规则
SQL 查询计划节点 优化与执行
模板语言 文本节点 / 占位符节点 渲染规则
自动机 状态和转移表 接受规则

用 match 写解释器

语法树本身不会计算。计算发生在解释器里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from dataclasses import dataclass


@dataclass(frozen=True)
class Number:
    value: int


@dataclass(frozen=True)
class Add:
    left: object
    right: object


def evaluate(expression):
    match expression:
        case Number(value):
            return value
        case Add(left, right):
            return evaluate(left) + evaluate(right)
        case _:
            raise TypeError(f"unknown expression: {expression!r}")


program = Add(Number(1), Add(Number(2), Number(3)))
print(evaluate(program))

运行结果是：

1
6

match 在这里承担分派工作。解释器看到 Number，直接取出值；看到 Add，递归解释左右两边，再把结果相加。

这段代码很短，却已经具备解释器的基本形状：

1
2
3
4
interpret(node):
    按节点类型选择规则
    递归解释子节点
    合成当前节点结果

Java 里的对应写法可以用 sealed class 和 switch：

1
2
3
4
5
6
static int evaluate(Expr expr) {
    return switch (expr) {
        case Num n -> n.value();
        case Add a -> evaluate(a.left()) + evaluate(a.right());
    };
}

Java 的优势是编译器能检查分支覆盖；Python 的优势是实验速度快。后续文章用 Python 展开模型，再在关键位置补 Java 对照。

函数对象让规则可以传递

在《计算的本质》里，函数不只用来组织代码。函数本身也会成为被研究的对象。lambda 演算、指称语义、Church 编码都依赖这种视角。

Python 函数可以赋值、传参、返回。

1
2
3
4
5
6
7
8
9
def double(value):
    return value * 2


def apply_twice(function, value):
    return function(function(value))


print(apply_twice(double, 3))

运行结果：

1
12

function 在 apply_twice 里只是一个值。后面讲指称语义时，表达式会被翻译成 Python 函数；讲 lambda 演算时，函数会成为唯一的计算材料。

Java 也能表达同样结构：

1
2
3
Function<Integer, Integer> doubleValue = value -> value * 2;
Function<Function<Integer, Integer>, Function<Integer, Integer>> twice =
    function -> value -> function.apply(function.apply(value));

Java 写起来更重，因为类型信息显式出现。这个重量并非坏事；它能帮助读者看清函数值的输入输出形状。文章里的 Python 示例会用短代码建立直觉，Java 对照负责把形状钉牢。

闭包保存环境

闭包是后面理解变量绑定的关键。一个函数可以带着创建它时的外部值一起返回。

1
2
3
4
5
6
7
8
9
def make_adder(amount):
    def add(value):
        return value + amount

    return add


add_ten = make_adder(10)
print(add_ten(5))

运行结果：

1
15

add 使用了外层函数里的 amount。make_adder 返回以后，amount 仍然被 add_ten 带着走。

这个机制和解释器里的“环境”很接近。变量求值时，解释器需要知道变量名绑定到哪个值；函数创建时，也需要保存当时能看到的变量。Java lambda 捕获外部变量时，也在做类似的事，只是 Java 要求被捕获的局部变量保持 effectively final。

模式提炼：规则加环境

rule + environment -> executable behavior

很多程序行为都来自“规则”和“环境”的组合。规则本身可能很小，环境决定它在当前时刻如何运行。

场景 规则 环境
表达式求值 节点解释规则 变量表
闭包调用 函数体 捕获变量
模板渲染 占位符替换规则 渲染上下文
自动机运行 转移函数 当前状态

看到“同一段逻辑在不同上下文下行为不同”时，可以先找这两个东西：规则在哪里，环境在哪里。

不可变数据减少干扰

计算模型的代码最怕隐藏副作用。表达式节点、自动机状态、图灵机纸带配置都适合写成不可变数据。不可变数据让每一步变化都显式出现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from dataclasses import dataclass


@dataclass(frozen=True)
class Configuration:
    state: str
    tape: tuple[str, ...]
    head: int


start = Configuration(
    state="scan",
    tape=("1", "1", "0"),
    head=0,
)

next_step = Configuration(
    state="scan",
    tape=("x", "1", "0"),
    head=1,
)

print(start)
print(next_step)

运行结果会显示两个不同的配置。start 没有被修改，next_step 是新的对象。

这种写法和 Java 里的 record 很像。业务系统里经常为了性能或便利使用可变对象；教学模型里，优先使用不可变对象。原因很简单：每一步变化都能被打印、比较、回放。

dict 和 set 适合写自动机

自动机本质上是一张转移表。Python 的 dict 很适合表达“在某个状态读到某个符号以后去哪”。

下面这台有限自动机识别偶数个 a 组成的字符串。输入只允许出现 a。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
transitions = {
    ("even", "a"): "odd",
    ("odd", "a"): "even",
}

accepting_states = {"even"}


def accepts(text):
    state = "even"

    for symbol in text:
        state = transitions[(state, symbol)]

    return state in accepting_states


print(accepts(""))
print(accepts("a"))
print(accepts("aa"))
print(accepts("aaa"))

运行结果：

1
2
3
4
True
False
True
False

dict 存转移函数，set 存接受状态。这个模型会在自动机章节继续扩展：NFA 需要把一个输入映射到多个状态，PDA 还要把栈顶符号放进 key 里，图灵机则会把转移结果扩展为“写符号、移动方向、新状态”。

Java 也能写同样模型，只是需要为 key 定义一个 record：

1
2
3
4
5
6
record Transition(String state, String symbol) {}

Map<Transition, String> transitions = Map.of(
    new Transition("even", "a"), "odd",
    new Transition("odd", "a"), "even"
);

Python 的短处是少了一层类型保护。文章中的代码会用小规模示例控制风险；复杂起来以后，再通过类型标注和测试补约束。

类型标注只做路标

Python 类型标注在这个系列里只承担路标作用。它帮助读者看懂函数期望什么、返回什么，不会成为主要内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from dataclasses import dataclass


@dataclass(frozen=True)
class Number:
    value: int


@dataclass(frozen=True)
class Add:
    left: "Expression"
    right: "Expression"


Expression = Number | Add


def evaluate(expression: Expression) -> int:
    match expression:
        case Number(value):
            return value
        case Add(left, right):
            return evaluate(left) + evaluate(right)

Expression = Number | Add 表示表达式只能是这两种节点。它类似 Java 里的 sealed interface，但 Python 运行时不会自动限制调用方只传这两类对象。类型标注更像注释和工具协议，严密性弱于 Java 类型系统。

这个弱点在实验文章里反而有用。它提醒读者：模型本身的规则要写清楚，不能把所有安全感都交给语言。

一个最小实验文件

把上面的内容合成一个文件，可以得到后续系列的起点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from dataclasses import dataclass


@dataclass(frozen=True)
class Number:
    value: int


@dataclass(frozen=True)
class Add:
    left: "Expression"
    right: "Expression"


Expression = Number | Add


def evaluate(expression: Expression) -> int:
    match expression:
        case Number(value):
            return value
        case Add(left, right):
            return evaluate(left) + evaluate(right)
        case _:
            raise TypeError(f"unknown expression: {expression!r}")


if __name__ == "__main__":
    program = Add(Number(1), Add(Number(2), Number(3)))
    print(evaluate(program))

保存为 simple_expression.py，执行：

1
python simple_expression.py

输出：

1
6

下一篇会从这个文件继续往前走：先解释“语法树”这个词，然后把表达式语言扩展到乘法、小于、布尔值和变量。第 2 章的核心问题会逐渐显形：程序的含义到底由谁决定。

Java 程序员的迁移表

Python 写法 Java 对照 迁移理解
@dataclass(frozen=True) record 用值对象表达语法节点
match expression switch 模式匹配 按节点类型选择规则
函数对象 Function<T, R> 规则可以作为值传递
闭包 捕获 effectively final 变量的 lambda 函数可以带着环境运行
dict[(state, symbol)] Map<Transition, State> 转移函数就是查表
set / frozenset Set / 不可变集合 状态集合和接受集合
类型标注 接口、泛型、sealed class 给模型边界加说明

练习

第一，把表达式语言加上乘法节点 Multiply，让 Multiply(Number(2), Add(Number(3), Number(4))) 输出 14。

第二，把自动机示例改成识别奇数个 a。只改接受状态，不改转移表。

第三，给 evaluate 增加一个 Variable 节点，并传入环境：

1
2
environment = {"x": 10}
program = Add(Variable("x"), Number(5))

预期输出是 15。这个练习会直接连到后面的变量、赋值和环境。

参考资料