指称语义：把程序翻译成 Python 函数

前两篇用操作语义解释程序。大步语义直接给最终结果，小步语义展示每一步规约。第 2 章还有第三种视角：指称语义（denotational semantics）。

指称语义把程序映射到某个更基础的对象。在本文的小语言里，表达式会变成一个 Python 函数，语句也会变成一个 Python 函数。程序的含义从“机器怎样跑”转到“它等价于哪个函数”。

对 Java 程序员来说，可以先把它理解成：

1 2	`Function<Environment, Value> // 表达式的含义 Function<Environment, Environment> // 语句的含义`

本文继续沿用前面的 AST，用 Python 函数重写这套小语言的含义。

三种语义回答三类问题

同一段程序可以从三种角度解释。

语义	关心的问题	本系列里的实现
大步语义	运行完成后得到什么	递归解释器
小步语义	每一步怎样变化	规约机器
指称语义	程序等价于什么对象	函数翻译器

大步和小步都属于操作语义。它们会描述程序在某种抽象机器上怎样执行。指称语义换成另一条路：先给每个 AST 节点分配一个“含义”，再用这些含义组合出整个程序的含义。

本文会把含义落到 Python 函数上：

1 2	`expression -> (environment -> value) statement -> (environment -> environment)`

表达式的含义是一个函数。给它环境，它返回值。

语句的含义也是一个函数。给它旧环境，它返回新环境。

模式提炼：含义变成普通值

syntax -> meaning_object

把程序含义翻译成普通值以后，解释器获得了新的组合方式。函数可以存入变量，可以传递，可以组合，可以测试。

场景	语法	含义对象
表达式引擎	`x + 1`	`env -> env["x"] + 1`
SQL 查询	`select ...`	查询计划或关系代数表达式
模板系统	`{{ user.name }}`	`context -> context["user"].name`
规则 DSL	`age > 18`	`fact -> fact.age > 18`

听到“把 DSL 编译成可复用对象”“把表达式缓存起来”“把规则当数据传递”时，可以回到这个模式。

AST 仍然保持不变

这一点很关键：指称语义不要求改 AST。改的是解释方式。

from collections.abc import Callable
from dataclasses import dataclass


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


@dataclass(frozen=True)
class Boolean:
    value: bool


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


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


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


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


Value = int | bool
Environment = dict[str, Value]
Expression = Number | Boolean | Variable | Add | Multiply | LessThan
ExpressionMeaning = Callable[[Environment], Value]

语句节点也沿用前文。

@dataclass(frozen=True)
class DoNothing:
    pass


@dataclass(frozen=True)
class Assign:
    name: str
    expression: Expression


@dataclass(frozen=True)
class If:
    condition: Expression
    consequence: "Statement"
    alternative: "Statement"


@dataclass(frozen=True)
class Sequence:
    first: "Statement"
    second: "Statement"


@dataclass(frozen=True)
class While:
    condition: Expression
    body: "Statement"


Statement = DoNothing | Assign | If | Sequence | While
StatementMeaning = Callable[[Environment], Environment]

ExpressionMeaning 和 StatementMeaning 是本文新增的两个类型别名。它们把“含义”说清楚了：

表达式含义：环境到值的函数。
语句含义：环境到环境的函数。

表达式翻译成环境函数

先从表达式开始。Number(3) 的含义很简单：无论环境是什么，都返回 3。

def expression_meaning(expression: Expression) -> ExpressionMeaning:
    match expression:
        case Number(value):
            return lambda environment: value

        case Boolean(value):
            return lambda environment: value

        case Variable(name):
            return lambda environment: environment[name]

        case Add(left, right):
            left_meaning = expression_meaning(left)
            right_meaning = expression_meaning(right)
            return lambda environment: (
                left_meaning(environment) + right_meaning(environment)
            )

        case Multiply(left, right):
            left_meaning = expression_meaning(left)
            right_meaning = expression_meaning(right)
            return lambda environment: (
                left_meaning(environment) * right_meaning(environment)
            )

        case LessThan(left, right):
            left_meaning = expression_meaning(left)
            right_meaning = expression_meaning(right)
            return lambda environment: (
                left_meaning(environment) < right_meaning(environment)
            )

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

可以先跑一个表达式。

expression = Add(Variable("x"), Multiply(Number(2), Number(3)))
meaning = expression_meaning(expression)

print(meaning({"x": 4}))
print(meaning({"x": 10}))

输出：

1
2

10
16

这里有一个细节。expression_meaning(expression) 并没有立刻求出值。它返回了一个函数。后面把不同环境传进去，函数才会得到不同结果。

这和 Java 的 Function<Environment, Value> 非常接近：

1	`Function<Environment, Value> meaning = env -> env.get("x").add(Value.of(6));`

AST 先被翻译成函数，环境稍后再传入。这种延迟绑定让含义对象可以复用。

模式提炼：环境延迟绑定

syntax -> (environment -> result)

程序结构和运行环境分开以后，同一份结构可以在多个环境下复用。

场景	被固定的结构	稍后传入的环境
表达式引擎	`x + y`	当前变量表
模板渲染	模板 AST	渲染上下文
SQL 预编译	查询计划	参数绑定
规则系统	规则对象	当前事实集合

这类系统常常先“编译”结构，再多次喂入上下文。指称语义把这个动作写成了函数。

语句翻译成环境变换

语句没有直接的值。它的含义是环境变换。

1	`old_environment -> new_environment`

下面实现语句含义。

def statement_meaning(statement: Statement) -> StatementMeaning:
    match statement:
        case DoNothing():
            return lambda environment: environment

        case Assign(name, expression):
            value_meaning = expression_meaning(expression)
            return lambda environment: environment | {
                name: value_meaning(environment)
            }

        case If(condition, consequence, alternative):
            condition_meaning = expression_meaning(condition)
            consequence_meaning = statement_meaning(consequence)
            alternative_meaning = statement_meaning(alternative)
            return lambda environment: (
                consequence_meaning(environment)
                if condition_meaning(environment)
                else alternative_meaning(environment)
            )

        case Sequence(first, second):
            first_meaning = statement_meaning(first)
            second_meaning = statement_meaning(second)
            return lambda environment: second_meaning(first_meaning(environment))

        case While(condition, body):
            condition_meaning = expression_meaning(condition)
            body_meaning = statement_meaning(body)

            def loop(environment: Environment) -> Environment:
                current = environment

                while condition_meaning(current):
                    current = body_meaning(current)

                return current

            return loop

        case _:
            raise TypeError(f"unknown statement: {statement!r}")

Assign 把表达式含义嵌进去。旧环境进入函数，表达式函数先算出值，再返回带新绑定的环境。

If 把条件、分支都翻译成函数。执行时先用条件函数判断，再调用对应分支。

Sequence 的含义最漂亮：

1	`lambda environment: second_meaning(first_meaning(environment))`

这就是函数组合。先执行第一条语句，把返回的新环境交给第二条语句。

模式提炼：顺序执行就是函数组合

statement_a; statement_b -> meaning_b(meaning_a(environment))

顺序执行常常可以转成函数组合。第一个函数负责把状态从 A 变成 B，第二个函数把状态从 B 变成 C。

场景	第一个函数	第二个函数	组合结果
程序语句	`assign_x`	`assign_y`	新环境
HTTP 中间件	鉴权	业务处理	响应
数据管道	清洗	聚合	报表数据
编译器	解析	类型检查	带类型 AST

看到“先做 A，再做 B，并且 B 依赖 A 的输出”时，函数组合通常比一大段过程代码更清楚。

跑一个完整程序

继续使用前面的大步语义例子：计算 1 * 2 * 3 * 4。

program = Sequence(
    Assign("x", Number(1)),
    Sequence(
        Assign("counter", Number(1)),
        While(
            LessThan(Variable("counter"), Number(5)),
            Sequence(
                Assign("x", Multiply(Variable("x"), Variable("counter"))),
                Assign("counter", Add(Variable("counter"), Number(1))),
            ),
        ),
    ),
)

meaning = statement_meaning(program)
print(meaning({}))

输出：

1	`{'x': 24, 'counter': 5}`

这次没有“规约轨迹”，也没有递归解释器的入口函数。statement_meaning(program) 先把整个程序翻译成一个 Python 函数，meaning({}) 再运行这个函数。

这就是指称语义的味道：程序含义可以被拿出来，作为一个独立对象存在。

while 的特殊之处

While 是本文里最接近形式语义的一块。

case While(condition, body):
    condition_meaning = expression_meaning(condition)
    body_meaning = statement_meaning(body)

    def loop(environment: Environment) -> Environment:
        current = environment

        while condition_meaning(current):
            current = body_meaning(current)

        return current

    return loop

教学代码用 Python 的 while 表达循环含义。严格的数学写法里，循环通常会引出不动点（fixed point）：while 的含义要引用自身，因为循环体执行完以后，还要再次检查同一个条件。

这件事暂时记成一个伏笔即可。后面讲 lambda 演算时，自引用、递归和不动点会重新出现。

模式提炼：递归含义来自自引用

loop = condition ? loop_after_body : identity

循环、递归函数、重试任务都有同一种结构：当前规则会再次调用自己，只到某个条件结束。

场景	自引用对象	结束条件
`while`	循环含义	条件为假
递归函数	函数自身	基线分支
重试任务	任务调度规则	成功或超出次数
消息消费	消费循环	队列为空或进程停止

形式语义用不动点处理这种结构。工程代码通常用循环、递归或调度器表达它。

完整代码

下面是完整文件，可以保存为 denotational_semantics.py 直接运行。

from collections.abc import Callable
from dataclasses import dataclass


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


@dataclass(frozen=True)
class Boolean:
    value: bool


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


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


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


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


Value = int | bool
Environment = dict[str, Value]
Expression = Number | Boolean | Variable | Add | Multiply | LessThan
ExpressionMeaning = Callable[[Environment], Value]


@dataclass(frozen=True)
class DoNothing:
    pass


@dataclass(frozen=True)
class Assign:
    name: str
    expression: Expression


@dataclass(frozen=True)
class If:
    condition: Expression
    consequence: "Statement"
    alternative: "Statement"


@dataclass(frozen=True)
class Sequence:
    first: "Statement"
    second: "Statement"


@dataclass(frozen=True)
class While:
    condition: Expression
    body: "Statement"


Statement = DoNothing | Assign | If | Sequence | While
StatementMeaning = Callable[[Environment], Environment]


def expression_meaning(expression: Expression) -> ExpressionMeaning:
    match expression:
        case Number(value):
            return lambda environment: value

        case Boolean(value):
            return lambda environment: value

        case Variable(name):
            return lambda environment: environment[name]

        case Add(left, right):
            left_meaning = expression_meaning(left)
            right_meaning = expression_meaning(right)
            return lambda environment: (
                left_meaning(environment) + right_meaning(environment)
            )

        case Multiply(left, right):
            left_meaning = expression_meaning(left)
            right_meaning = expression_meaning(right)
            return lambda environment: (
                left_meaning(environment) * right_meaning(environment)
            )

        case LessThan(left, right):
            left_meaning = expression_meaning(left)
            right_meaning = expression_meaning(right)
            return lambda environment: (
                left_meaning(environment) < right_meaning(environment)
            )

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


def statement_meaning(statement: Statement) -> StatementMeaning:
    match statement:
        case DoNothing():
            return lambda environment: environment

        case Assign(name, expression):
            value_meaning = expression_meaning(expression)
            return lambda environment: environment | {
                name: value_meaning(environment)
            }

        case If(condition, consequence, alternative):
            condition_meaning = expression_meaning(condition)
            consequence_meaning = statement_meaning(consequence)
            alternative_meaning = statement_meaning(alternative)
            return lambda environment: (
                consequence_meaning(environment)
                if condition_meaning(environment)
                else alternative_meaning(environment)
            )

        case Sequence(first, second):
            first_meaning = statement_meaning(first)
            second_meaning = statement_meaning(second)
            return lambda environment: second_meaning(first_meaning(environment))

        case While(condition, body):
            condition_meaning = expression_meaning(condition)
            body_meaning = statement_meaning(body)

            def loop(environment: Environment) -> Environment:
                current = environment

                while condition_meaning(current):
                    current = body_meaning(current)

                return current

            return loop

        case _:
            raise TypeError(f"unknown statement: {statement!r}")


if __name__ == "__main__":
    expression = Add(Variable("x"), Multiply(Number(2), Number(3)))
    meaning = expression_meaning(expression)

    print(meaning({"x": 4}))
    print(meaning({"x": 10}))

    program = Sequence(
        Assign("x", Number(1)),
        Sequence(
            Assign("counter", Number(1)),
            While(
                LessThan(Variable("counter"), Number(5)),
                Sequence(
                    Assign("x", Multiply(Variable("x"), Variable("counter"))),
                    Assign("counter", Add(Variable("counter"), Number(1))),
                ),
            ),
        ),
    )

    print(statement_meaning(program)({}))

运行：

1	`python denotational_semantics.py`

输出：

1
2
3

10
16
{'x': 24, 'counter': 5}

和操作语义的对照

三种实现都能跑出同一个程序结果，但它们适合回答不同问题。

问题	大步语义	小步语义	指称语义
最终结果是什么	清楚	需要跑到结束	清楚
中间状态是什么	信息少	清楚	信息少
程序可否作为值传递	不突出	不突出	清楚
顺序执行怎样组合	递归调用	配置转移	函数组合
循环怎样表达	递归解释	展开成 `if`	环境函数自引用

指称语义特别适合讨论程序等价性。两段程序只要翻译成同一个环境函数，就可以说它们有相同含义。编译器优化、查询重写、规则化简、表达式缓存，都离不开这种思想。

Java 程序员的迁移表

Python 写法	Java 对照	作用
`ExpressionMeaning`	`Function<Env, Value>`	表达式含义
`StatementMeaning`	`Function<Env, Env>`	语句含义
`lambda environment: value`	`env -> value`	常量含义
`second(first(env))`	`second.compose(first)`	顺序组合
`environment	{…}`	创建新 `Map`
`While` 的 `loop`	`while` 或递归函数	自引用行为

如果用 Java 表达，核心形状会像这样：

@FunctionalInterface
interface ExprMeaning {
    Value apply(Environment env);
}

@FunctionalInterface
interface StmtMeaning {
    Environment apply(Environment env);
}

StmtMeaning sequence(StmtMeaning first, StmtMeaning second) {
    return env -> second.apply(first.apply(env));
}

这段代码就是指称语义的工程影子。AST 节点先被翻译成函数，函数再彼此组合。

什么时候应该想到指称语义

第一，系统里有一套 DSL。规则、模板、表达式、查询语句都可以先翻译成含义对象，后续反复执行。

第二，需要比较两段程序是否等价。直接比较源码文本很脆弱，比较含义对象或中间表达会稳定很多。

第三，需要做优化。优化的前提是变换前后含义一致。指称语义提供了“含义一致”的表达方式。

第四，需要把复杂执行过程缓存起来。把语法翻译成函数、查询计划或规则对象以后，可以缓存这个对象，避免重复解析。

到这里，第 2 章的核心线索已经齐了：AST 是程序结构，操作语义描述它怎样执行，指称语义描述它等价于什么函数。下一步可以离开通用程序语义，进入自动机：先从确定性有限自动机开始，看“状态 + 输入字符”怎样识别语言。

练习

第一，给表达式增加 Subtract，让 expression_meaning(Subtract(Number(10), Number(3)))({}) 返回 7。

第二，给语句增加 Print。提示：语句含义可以从 Environment -> Environment 扩展成 RuntimeState -> RuntimeState，其中 RuntimeState 同时包含环境和输出列表。

第三，写两个不同的程序，让它们在所有输入环境下都得到同样结果。例如 x = 1 + 2 和 x = 3。思考这种“等价”怎样用测试近似验证。

第四，尝试把 statement_meaning(While(...)) 改成递归函数。观察 Python 的递归深度限制，再对比本文里的 while 写法。

参考资料

Understanding Computation 官方目录

Tom Stuart/computationbook 示例代码仓库

Python 文档：dataclasses

Python 文档：collections.abc.Callable