lambda 演算入门：函数为什么足够表达计算

图灵机用纸带、读写头和指令循环描述计算。lambda 演算换了一条路：它不用可变纸带，也不用状态跳转，只保留函数定义、函数调用和变量替换。

这个模型看起来比图灵机更不像机器，却和图灵机有同等表达能力。图灵机强调“有限控制怎样改写存储”，lambda 演算强调“表达式怎样通过函数应用逐步化简”。从工程角度看，它把计算从指令循环翻译成表达式重写。

本文先建立 lambda 演算的最小语法，用 Python 表示变量、函数和调用，再通过一个小例子展示函数怎样返回函数、调用怎样变成替换。

三种表达式

lambda 演算的核心语法只有三种。

形式	示例	含义
变量	x	一个名字
函数	x -> x	接收参数 x，返回表达式 x
调用	(x -> x) a	把函数应用到参数 a

函数也叫抽象，调用也叫应用。为了贴近 Java 程序员熟悉的形式，本文用 x -> x 表示 lambda 表达式，而不用希腊字母写法。

最小模型可以写成一棵表达式树：

Expression
  = Variable(name)
  | Function(parameter, body)
  | Call(function, argument)

这里没有数字、布尔值、字符串、对象和赋值。后续 Church 编码会展示数字和布尔值怎样由函数构造出来。当前阶段只需要抓住一个事实：表达式可以作为函数体，函数也可以作为表达式继续传递。

从 Java 的 Function 看 lambda 演算

Java 里的 lambda 表达式通常会落到某个函数式接口上。

Function<Integer, Integer> identity = x -> x;

这个写法已经有 lambda 演算的影子：参数名 x、函数体 x、调用时把实参代入函数体。

lambda 演算	Java 对照	说明
x	变量名	表达式中的名字
x -> x	Function<T, T>	函数值
(x -> x) a	identity.apply(a)	函数调用
替换	参数绑定	把实参带入函数体
函数返回函数	高阶函数	Function<A, Function<B, C>>

Java 的 lambda 运行在类型系统、对象模型和 JVM 之上；lambda 演算故意拿掉这些工程设施，只保留函数应用这条计算规则。

用 Python 表示变量

变量是最小表达式。替换变量时，如果名字命中，就返回替换表达式；否则保留原变量。

from __future__ import annotations
from dataclasses import dataclass


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

    def replace(self, name: str, replacement: Expression) -> Expression:
        if self.name == name:
            return replacement
        return self

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

replace("x", argument) 可以读作“把表达式里的自由变量 x 换成 argument”。自由变量和变量捕获会在下一篇规约器文章里展开，本文只使用不会发生捕获的例子。

用 Python 表示函数

函数包含一个参数名和一个函数体。

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

    def call(self, argument: Expression) -> Expression:
        return self.body.replace(self.parameter, argument)

    def replace(self, name: str, replacement: Expression) -> Expression:
        if self.parameter == name:
            return self
        return Function(self.parameter, self.body.replace(name, replacement))

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

call 是函数应用的核心：把实参替换进函数体。replace 里有一个遮蔽规则：如果函数自己的参数名正好等于要替换的名字，替换不能进入函数体。否则内部绑定会被外部替换误伤。

例如 x -> x 调用 a，结果就是 a。

(x -> x) a
  -> a

用 Python 表示调用

调用包含两个表达式：左边是被调用的函数，右边是传入的参数。

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

    def replace(self, name: str, replacement: Expression) -> Expression:
        return Call(
            self.function.replace(name, replacement),
            self.argument.replace(name, replacement),
        )

    def reduce_once(self) -> Expression:
        if isinstance(self.function, Function):
            return self.function.call(self.argument)

        if isinstance(self.function, Call):
            return Call(self.function.reduce_once(), self.argument)

        return self

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

reduce_once 只做一小步规约。若左侧已经是函数，就直接调用；若左侧本身还是调用，就先规约左侧。这个策略足够支撑当前例子，完整规约器会在下一篇处理更多情况。

三种表达式定义完成后，可以给类型别名补上。

Expression = Variable | Function | Call

完整示例

完整代码如下。

from __future__ import annotations
from dataclasses import dataclass


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

    def replace(self, name: str, replacement: Expression) -> Expression:
        if self.name == name:
            return replacement
        return self

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


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

    def call(self, argument: Expression) -> Expression:
        return self.body.replace(self.parameter, argument)

    def replace(self, name: str, replacement: Expression) -> Expression:
        if self.parameter == name:
            return self
        return Function(self.parameter, self.body.replace(name, replacement))

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


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

    def replace(self, name: str, replacement: Expression) -> Expression:
        return Call(
            self.function.replace(name, replacement),
            self.argument.replace(name, replacement),
        )

    def reduce_once(self) -> Expression:
        if isinstance(self.function, Function):
            return self.function.call(self.argument)

        if isinstance(self.function, Call):
            return Call(self.function.reduce_once(), self.argument)

        return self

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


Expression = Variable | Function | Call

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

print("expression:", expression)
step1 = expression.reduce_once()
print("step 1:", step1)
step2 = step1.reduce_once()
print("step 2:", step2)

运行结果：

expression: (((x -> (y -> x)) a) b)
step 1: ((y -> a) b)
step 2: a

读取这个例子

constant 对应 x -> (y -> x)。它接收 x，返回一个新函数 y -> x。这个新函数再接收 y，但函数体仍然返回外层的 x。

表达式：

(((x -> (y -> x)) a) b)

第一步把 a 代入外层函数体：

((y -> a) b)

第二步把 b 代入 y -> a。函数体里没有 y，所以结果仍然是 a。

a

这就是常量函数的行为：接收两个参数，返回第一个参数。换成 Java 类型，可以粗略写成：

Function<A, Function<B, A>>

这个例子展示了高阶函数的基本形状。函数可以作为值返回，返回的函数可以继续被调用，调用过程可以被表达为表达式替换。

模式提炼：表达式重写

图灵机的执行模式是：

state + tape -> next_state + next_tape

lambda 演算的执行模式是：

expression -> reduced_expression

两者都在做小步计算。区别在于状态存放位置不同。图灵机把状态显式放在机器配置里，lambda 演算把状态隐含在表达式结构里。一次规约会改写表达式树，新的表达式树就是下一步计算配置。

这个视角能迁移到很多工程代码。

工程场景	表达式	规约
AST 优化	语法树	常量折叠、内联
SQL planner	查询树	谓词下推、投影裁剪
模板引擎	模板 AST	变量替换、片段展开
规则系统	条件表达式	匹配后生成新事实

把程序看成表达式重写系统，有助于理解编译器、解释器、优化器和模板引擎的共同骨架。

当前模型的边界

本文代码只处理最小可运行路径。它还缺少三块能力：

第一，没有完整的规约策略。当前代码只优先规约调用左侧。

第二，没有系统处理自由变量。示例避免了变量捕获。

第三，没有数字、布尔值和条件。后续 Church 编码会把这些概念全部还原成函数。

这些边界不是缺陷清单，而是后续文章的路线。下一篇会把替换、自由变量、捕获规避和多步规约写成更完整的 lambda 规约器。

练习

第一，把 constant 改成 identity = Function("x", Variable("x"))，运行 Call(identity, Variable("z"))。

第二，构造 Function("x", Function("y", Variable("y")))，观察它接收两个参数后的结果。

第三，给 Call 增加 reducible() 方法，让代码能判断表达式是否还能继续规约。

第四，尝试构造 Call(Variable("f"), Variable("x"))，观察当前 reduce_once() 为什么不会继续变化。

参考资料

• Understanding Computation 官方目录
• Tom Stuart/computationbook 示例代码仓库
• Python 文档：dataclasses
• Java 文档：Function