上一篇文章把 lambda 演算拆成三种表达式：变量、函数、调用。示例只做了最小的一步替换，用来说明函数应用可以变成表达式重写。

本文把这件事补成一个规约器：给定一个 lambda 表达式，持续执行 beta 规约，打印每一步轨迹，并处理替换过程中最容易出错的变量捕获问题。这个规约器仍然很小，但已经具备解释器和 AST 重写器的基本骨架。

规约器要解决什么

lambda 演算的核心计算规则是 beta 规约：

1
2
(x -> body) argument
  -> body 中的自由 x 替换成 argument

例如：

1
2
(x -> x) a
  -> a

更复杂一点的例子：

1
2
3
(((x -> (y -> x)) a) b)
  -> ((y -> a) b)
  -> a

规约器需要完成三件事：

职责 作用
找到可规约位置 判断哪一个调用先执行
做安全替换 只替换自由变量，避免误改绑定变量
重复执行 直到表达式无法继续变化

这和解释器很接近。区别在于解释器通常维护环境和值，lambda 规约器直接改写表达式树。

表达式结构

沿用前一篇的三种节点：变量、函数、调用。

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
31
from __future__ import annotations
from dataclasses import dataclass


@dataclass(frozen=True)
class Variable:
    name: str

    def __str__(self) -> str:
        return self.name


@dataclass(frozen=True)
class Function:
    parameter: str
    body: Expression

    def __str__(self) -> str:
        return f"({self.parameter} -> {self.body})"


@dataclass(frozen=True)
class Call:
    function: Expression
    argument: Expression

    def __str__(self) -> str:
        return f"({self.function} {self.argument})"


Expression = Variable | Function | Call

节点本身只保存结构。自由变量分析、替换、规约都放在独立函数里。这样更接近 Java 里的 AST 处理：节点是数据结构，重写器是访问逻辑。

自由变量

变量是否自由，取决于它有没有被外层函数参数绑定。

1
2
3
4
x                  自由变量：x
x -> x             自由变量：无
x -> (x y)         自由变量：y
x -> (z x)         自由变量：z

Python 实现如下。

1
2
3
4
5
6
7
8
9
10
11
def free_variables(expression: Expression) -> set[str]:
    if isinstance(expression, Variable):
        return {expression.name}

    if isinstance(expression, Function):
        return free_variables(expression.body) - {expression.parameter}

    if isinstance(expression, Call):
        return free_variables(expression.function) | free_variables(expression.argument)

    raise TypeError(f"unknown expression: {expression!r}")

Function 节点会把自己的参数名从函数体自由变量集合里删掉。Call 节点则合并左右两侧的自由变量。

捕获问题

替换不能只做字符串替换。看这个表达式：

1
((x -> (y -> x)) y)

外层函数把 x 替换成实参 y。如果直接把函数体里的 x 改成 y，会得到：

1
y -> y

这个结果改变了含义。实参里的自由变量 y 被内层函数参数 y 捕获了。安全结果应该先把内层参数改名：

1
y_1 -> y

这个改名过程通常叫 alpha conversion。它不改变表达式含义，只为替换腾出一个不会冲突的新名字。

生成新名字和改名

安全改名需要先知道哪些名字已经被使用。free_variables 只关心自由变量，生成新参数名时还要避开内层绑定名，否则 trace 里容易出现新的遮蔽关系。

1
2
3
4
5
6
7
8
9
10
11
def all_names(expression: Expression) -> set[str]:
    if isinstance(expression, Variable):
        return {expression.name}

    if isinstance(expression, Function):
        return {expression.parameter} | all_names(expression.body)

    if isinstance(expression, Call):
        return all_names(expression.function) | all_names(expression.argument)

    raise TypeError(f"unknown expression: {expression!r}")

再写一个新名字生成器。

1
2
3
4
5
6
7
8
9
def fresh_name(base: str, used_names: set[str]) -> str:
    index = 1
    candidate = f"{base}_{index}"

    while candidate in used_names:
        index += 1
        candidate = f"{base}_{index}"

    return candidate

再写一个只改当前绑定范围的 rename_bound。如果遇到同名的内层函数参数，说明那里已经进入新的绑定范围，不能继续改进去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def rename_bound(expression: Expression, old: str, new: str) -> Expression:
    if isinstance(expression, Variable):
        if expression.name == old:
            return Variable(new)
        return expression

    if isinstance(expression, Function):
        if expression.parameter == old:
            return expression
        return Function(expression.parameter, rename_bound(expression.body, old, new))

    if isinstance(expression, Call):
        return Call(
            rename_bound(expression.function, old, new),
            rename_bound(expression.argument, old, new),
        )

    raise TypeError(f"unknown expression: {expression!r}")

这段逻辑看起来像细节，但它是表达式重写器的核心风险控制。AST 里所有“按名字替换”的操作都会遇到类似问题，例如变量内联、宏展开、SQL alias 改写。

安全替换

substitute(expression, name, replacement) 的目标是把表达式中自由出现的 name 替换成 replacement。

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
31
32
33
34
def substitute(expression: Expression, name: str, replacement: Expression) -> Expression:
    if isinstance(expression, Variable):
        if expression.name == name:
            return replacement
        return expression

    if isinstance(expression, Call):
        return Call(
            substitute(expression.function, name, replacement),
            substitute(expression.argument, name, replacement),
        )

    if isinstance(expression, Function):
        if expression.parameter == name:
            return expression

        if name not in free_variables(expression.body):
            return expression

        if expression.parameter not in free_variables(replacement):
            return Function(
                expression.parameter,
                substitute(expression.body, name, replacement),
            )

        used_names = all_names(expression.body) | free_variables(replacement) | {
            name,
            expression.parameter,
        }
        new_parameter = fresh_name(expression.parameter, used_names)
        renamed_body = rename_bound(expression.body, expression.parameter, new_parameter)
        return Function(new_parameter, substitute(renamed_body, name, replacement))

    raise TypeError(f"unknown expression: {expression!r}")

Function 分支最重要。若函数参数等于要替换的名字，说明这个名字在函数体里已经被重新绑定，替换停止。若函数体里根本没有自由出现的 name，也直接返回原函数，避免做无意义的 alpha conversion。只有当 name 确实需要进入函数体，且函数参数可能捕获 replacement 里的自由变量时，才先改名，再继续替换。

单步规约和多步 trace

规约器采用左侧优先的策略：先尝试规约最外层调用；如果左侧还没变成函数，就先规约左侧；左侧稳定后再规约参数；函数体也可以继续规约到正常形。

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
def reduce_once(expression: Expression) -> Expression:
    if isinstance(expression, Call):
        if isinstance(expression.function, Function):
            return substitute(
                expression.function.body,
                expression.function.parameter,
                expression.argument,
            )

        reduced_function = reduce_once(expression.function)
        if reduced_function != expression.function:
            return Call(reduced_function, expression.argument)

        reduced_argument = reduce_once(expression.argument)
        if reduced_argument != expression.argument:
            return Call(expression.function, reduced_argument)

        return expression

    if isinstance(expression, Function):
        reduced_body = reduce_once(expression.body)
        if reduced_body != expression.body:
            return Function(expression.parameter, reduced_body)

    return expression

trace 负责持续调用 reduce_once，直到表达式不再变化。

1
2
3
4
5
6
7
8
9
10
def trace(expression: Expression) -> Expression:
    current = expression
    print(current)

    while True:
        next_expression = reduce_once(current)
        if next_expression == current:
            return current
        print(next_expression)
        current = next_expression

这里依赖 dataclass(frozen=True) 提供的结构相等判断。新表达式和旧表达式相等，说明已经到达正常形。

完整示例

完整代码如下。

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
from __future__ import annotations
from dataclasses import dataclass


@dataclass(frozen=True)
class Variable:
    name: str

    def __str__(self) -> str:
        return self.name


@dataclass(frozen=True)
class Function:
    parameter: str
    body: Expression

    def __str__(self) -> str:
        return f"({self.parameter} -> {self.body})"


@dataclass(frozen=True)
class Call:
    function: Expression
    argument: Expression

    def __str__(self) -> str:
        return f"({self.function} {self.argument})"


Expression = Variable | Function | Call


def free_variables(expression: Expression) -> set[str]:
    if isinstance(expression, Variable):
        return {expression.name}

    if isinstance(expression, Function):
        return free_variables(expression.body) - {expression.parameter}

    if isinstance(expression, Call):
        return free_variables(expression.function) | free_variables(expression.argument)

    raise TypeError(f"unknown expression: {expression!r}")


def all_names(expression: Expression) -> set[str]:
    if isinstance(expression, Variable):
        return {expression.name}

    if isinstance(expression, Function):
        return {expression.parameter} | all_names(expression.body)

    if isinstance(expression, Call):
        return all_names(expression.function) | all_names(expression.argument)

    raise TypeError(f"unknown expression: {expression!r}")


def fresh_name(base: str, used_names: set[str]) -> str:
    index = 1
    candidate = f"{base}_{index}"

    while candidate in used_names:
        index += 1
        candidate = f"{base}_{index}"

    return candidate


def rename_bound(expression: Expression, old: str, new: str) -> Expression:
    if isinstance(expression, Variable):
        if expression.name == old:
            return Variable(new)
        return expression

    if isinstance(expression, Function):
        if expression.parameter == old:
            return expression
        return Function(expression.parameter, rename_bound(expression.body, old, new))

    if isinstance(expression, Call):
        return Call(
            rename_bound(expression.function, old, new),
            rename_bound(expression.argument, old, new),
        )

    raise TypeError(f"unknown expression: {expression!r}")


def substitute(expression: Expression, name: str, replacement: Expression) -> Expression:
    if isinstance(expression, Variable):
        if expression.name == name:
            return replacement
        return expression

    if isinstance(expression, Call):
        return Call(
            substitute(expression.function, name, replacement),
            substitute(expression.argument, name, replacement),
        )

    if isinstance(expression, Function):
        if expression.parameter == name:
            return expression

        if name not in free_variables(expression.body):
            return expression

        if expression.parameter not in free_variables(replacement):
            return Function(
                expression.parameter,
                substitute(expression.body, name, replacement),
            )

        used_names = all_names(expression.body) | free_variables(replacement) | {
            name,
            expression.parameter,
        }
        new_parameter = fresh_name(expression.parameter, used_names)
        renamed_body = rename_bound(expression.body, expression.parameter, new_parameter)
        return Function(new_parameter, substitute(renamed_body, name, replacement))

    raise TypeError(f"unknown expression: {expression!r}")


def reduce_once(expression: Expression) -> Expression:
    if isinstance(expression, Call):
        if isinstance(expression.function, Function):
            return substitute(
                expression.function.body,
                expression.function.parameter,
                expression.argument,
            )

        reduced_function = reduce_once(expression.function)
        if reduced_function != expression.function:
            return Call(reduced_function, expression.argument)

        reduced_argument = reduce_once(expression.argument)
        if reduced_argument != expression.argument:
            return Call(expression.function, reduced_argument)

        return expression

    if isinstance(expression, Function):
        reduced_body = reduce_once(expression.body)
        if reduced_body != expression.body:
            return Function(expression.parameter, reduced_body)

    return expression


def trace(expression: Expression) -> Expression:
    current = expression
    print(current)

    while True:
        next_expression = reduce_once(current)
        if next_expression == current:
            return current
        print(next_expression)
        current = next_expression


constant = Function("x", Function("y", Variable("x")))
expression = Call(Call(constant, Variable("a")), Variable("b"))

print("normal-order trace:")
result = trace(expression)
print("result:", result)

capture_case = Call(Function("x", Function("y", Variable("x"))), Variable("y"))
print("capture-safe:")
print(capture_case)
print(reduce_once(capture_case))

nested_case = Call(
    Function("x", Function("y", Function("y_1", Variable("x")))),
    Variable("y"),
)
print("nested-scope-safe:")
print(nested_case)
print(reduce_once(nested_case))

no_rewrite_case = Call(
    Function("x", Function("y", Function("y_1", Variable("y")))),
    Variable("y"),
)
print("no-rewrite-needed:")
print(no_rewrite_case)
print(reduce_once(no_rewrite_case))

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
normal-order trace:
(((x -> (y -> x)) a) b)
((y -> a) b)
a
result: a
capture-safe:
((x -> (y -> x)) y)
(y_1 -> y)
nested-scope-safe:
((x -> (y -> (y_1 -> x))) y)
(y_2 -> (y_1 -> y))
no-rewrite-needed:
((x -> (y -> (y_1 -> y))) y)
(y -> (y_1 -> y))

读取执行轨迹

第一段 trace 对应常量函数。

1
2
3
(((x -> (y -> x)) a) b)
((y -> a) b)
a

第一步把 a 代入 x -> (y -> x) 的函数体，得到 y -> a。第二步把 b 代入 y -> a，函数体里没有 y，所以结果仍然是 a。

后面三段分别检查捕获规避的边界。

1
2
((x -> (y -> x)) y)
(y_1 -> y)

实参 y 必须保持自由。规约器发现内层函数参数也叫 y，于是先把内层参数改成 y_1，再执行替换。

1
2
((x -> (y -> (y_1 -> x))) y)
(y_2 -> (y_1 -> y))

这个例子多了一层已经存在的 y_1 绑定。新名字不能再选 y_1，否则会制造新的遮蔽关系；所以规约器选择 y_2。

1
2
((x -> (y -> (y_1 -> y))) y)
(y -> (y_1 -> y))

第三个例子里，外层函数体中没有自由出现的 x。即使实参也叫 y，替换并不会进入函数体，所以不需要改名。这个分支能防止规约器为了“看起来安全”而改变一个本来无需改写的作用域。

Java 程序员的迁移表

Python 组件 Java 对照 工程含义
Variable / Function / Call sealed interface Expr + record AST 节点
free_variables 作用域分析 visitor 收集名字依赖
all_names 符号收集 visitor 为安全改名避开已有名字
rename_bound 符号改名 pass 避免命名冲突
substitute AST rewrite visitor 安全替换子树
reduce_once 单步优化 / 求值 pass 一次局部改写
trace debug log / explain plan 展示每次改写

在 Java 里实现同一套逻辑，通常会把节点定义为 sealed hierarchy，把分析和重写写成 visitor。编译器优化、模板展开、SQL planner、规则引擎都依赖类似的“分析信息 + 安全重写”组合。

模式提炼：替换必须尊重作用域

表达式重写最危险的部分不是遍历树，而是保持名字含义不变。只要系统里存在“名字绑定”，替换就必须知道作用域。

1
name binding + tree rewrite -> scope-aware rewrite

这个模式在工程里反复出现。

场景 绑定 风险
lambda 规约 函数参数 自由变量被捕获
Java 重构 局部变量、字段、方法参数 rename 改错作用域
SQL 改写 表别名、列别名 alias 冲突
模板展开 模板变量 外层变量误覆盖
宏系统 宏参数 展开后名字污染

规约器的小例子提供了一个简化版经验：任何自动改代码、改查询、改模板的系统，都需要先做作用域分析，再做替换。

下一步

lambda 规约器已经能把函数调用规约到正常形。下一篇进入 Church 编码：在没有内置数字和布尔值的前提下，用函数表示 true、false、0、1、2、加法和条件选择。

这一步会把“函数足够表达计算”从语法层推进到数据层。数字不再是语言原语，而是一组可调用的函数结构。

练习

第一，给 trace 增加最大步数限制，避免规约发散时无限循环。

第二，构造 (x -> (x -> x)) y，观察外层替换为什么不能进入内层同名参数。

第三，把 reduce_once 改成只规约最外层，不进入函数体，比较 trace 差异。

第四，给表达式节点增加 to_tree() 方法，用缩进格式打印 AST。

系列导航

参考资料