自己写一个解释器：大步语义与递归求值

上一篇已经把字符串解析成 AST。程序结构稳定以后，下一步是给它一套求值规则。最直接的规则叫大步语义（big-step semantics）：给定一个表达式和环境，直接得到最终值；给定一个语句和环境，直接得到新的环境。

大步语义适合写成递归解释器。表达式节点递归求值，语句节点递归改变环境。它不会展示每一个中间状态，只关心完整运行后的结果。

本文会实现一个小语言。它支持数字、布尔值、变量、加法、乘法、小于、赋值、顺序执行、条件分支和 while 循环。

大步语义关心最终关系

大步语义可以先记成两条关系：

1 2	`expression + environment => value statement + environment => new_environment`

表达式会产生值，语句会改变环境。环境是变量名到值的映射。

例如：

1	`x + 1, {x = 2} => 3`

赋值语句会得到一个新环境：

1	`x = x + 1, {x = 2} => {x = 3}`

这套写法和 Java 程序员熟悉的递归下降解释器很接近。AST 节点决定规则，环境提供变量绑定，解释器负责把二者合在一起。

表达式节点

先定义表达式。

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
Expression = Number | Boolean | Variable | Add | Multiply | LessThan
Environment = dict[str, Value]

Number 和 Boolean 是字面量。Variable 从环境里取值。Add、Multiply、LessThan 都需要先求出左右两边，再组合结果。

这已经足够写表达式解释器。

def evaluate_expression(expression: Expression, environment: Environment) -> Value:
    match expression:
        case Number(value):
            return value
        case Boolean(value):
            return value
        case Variable(name):
            return environment[name]
        case Add(left, right):
            return (
                evaluate_expression(left, environment)
                + evaluate_expression(right, environment)
            )
        case Multiply(left, right):
            return (
                evaluate_expression(left, environment)
                * evaluate_expression(right, environment)
            )
        case LessThan(left, right):
            return (
                evaluate_expression(left, environment)
                < evaluate_expression(right, environment)
            )
        case _:
            raise TypeError(f"unknown expression: {expression!r}")

可以先跑一个表达式：

environment = {"x": 3}
expression = LessThan(Add(Variable("x"), Number(1)), Number(5))

print(evaluate_expression(expression, environment))

输出：

True

解释器没有维护求值过程的每一步。它直接递归到叶子节点，再一层层返回最终值。这就是“大步”的味道。

模式提炼：递归解释树

evaluate(node, environment) -> value

树形结构天然适合递归解释。每个节点只需要知道三件事：它是哪种节点，它的子节点在哪里，怎样把子节点结果合成当前结果。

节点	子问题	合成规则
`Number`	无	返回数字
`Variable`	查环境	返回绑定值
`Add`	求左右表达式	相加
`LessThan`	求左右表达式	比较大小

同一模式会出现在模板渲染、SQL 执行计划、规则引擎和编译器优化里。树上的每个节点都把大问题拆成子问题，再把子结果合成当前结果。

语句节点

表达式有值，语句改变环境。下面定义五种语句。

@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

这些节点接近原书里的 SIMPLE 语言：

DoNothing：空语句。
Assign：把表达式结果绑定到变量名。
If：按条件选择分支。
Sequence：先执行第一条语句，再执行第二条。
While：条件成立时反复执行 body。

语句解释器的返回值是新环境。

def evaluate_statement(statement: Statement, environment: Environment) -> Environment:
    match statement:
        case DoNothing():
            return environment

        case Assign(name, expression):
            return environment | {
                name: evaluate_expression(expression, environment)
            }

        case If(condition, consequence, alternative):
            if evaluate_expression(condition, environment):
                return evaluate_statement(consequence, environment)
            return evaluate_statement(alternative, environment)

        case Sequence(first, second):
            return evaluate_statement(
                second,
                evaluate_statement(first, environment),
            )

        case While(condition, body):
            if evaluate_expression(condition, environment):
                return evaluate_statement(
                    statement,
                    evaluate_statement(body, environment),
                )
            return environment

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

environment | {...} 会创建一个新字典，保留旧环境里的变量，再覆盖当前赋值的变量。教学模型里这样写更清楚：执行语句得到新环境，旧环境不被原地修改。

赋值和顺序执行

先看最简单的程序。

statement = Sequence(
    Assign("x", Number(1)),
    Assign("y", Add(Variable("x"), Number(2))),
)

print(evaluate_statement(statement, {}))

输出：

1	`{'x': 1, 'y': 3}`

Sequence 的规则很重要：

1	`evaluate_statement(second, evaluate_statement(first, environment))`

它先让 first 在旧环境里运行，得到中间环境；再让 second 在中间环境里运行。顺序执行的含义就藏在这行代码里。

Java 里写解释器时，经常会把 Environment 做成一个可变对象，然后 execute() 直接修改它。那样更接近业务代码习惯。本文用不可变风格，是为了让每一次环境变化都能从函数返回值里看见。

条件分支

条件分支先求 condition，再选择 consequence 或 alternative。

statement = If(
    LessThan(Variable("x"), Number(10)),
    Assign("result", Number(1)),
    Assign("result", Number(0)),
)

print(evaluate_statement(statement, {"x": 3}))
print(evaluate_statement(statement, {"x": 12}))

输出：

1 2	`{'x': 3, 'result': 1} {'x': 12, 'result': 0}`

这里有两个层次。LessThan(...) 是表达式，它返回布尔值；If(...) 是语句，它返回新环境。表达式和语句的返回类型分开，解释器结构会清楚很多。

模式提炼：表达式产生值，语句产生状态

expression -> value
statement -> state

很多语言都会区分表达式和语句。表达式回答“值是多少”，语句回答“状态怎样变化”。有些语言会让两者边界变模糊，但解释器内部仍然要处理这两个问题。

结构	输入	输出	例子
表达式	环境	值	`x + 1`
语句	环境	新环境	`x = x + 1`
条件语句	环境	新环境	`if x < 10 ...`
循环语句	环境	新环境	`while x < 5 ...`

写解释器时，先明确每个节点的输出类型。输出类型清楚了，递归结构就稳了。

while 循环

循环最能体现大步语义的特点。它不会暴露每一次循环的中间状态，只给出循环完成后的环境。

下面的程序计算 x = 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))),
            ),
        ),
    ),
)

print(evaluate_statement(program, {}))

输出：

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

While 的实现只有几行：

case While(condition, body):
    if evaluate_expression(condition, environment):
        return evaluate_statement(
            statement,
            evaluate_statement(body, environment),
        )
    return environment

条件成立时，先执行 body 得到新环境，再用同一条 While 语句继续解释。条件失败时，返回当前环境。

这段递归实现表达的是语义，不是工程上最稳的循环写法。Python 没有尾递归优化，循环次数很大时会触发递归深度限制。后面写小步语义时，会用“机器配置一步步推进”的方式避开这个问题。

完整代码

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

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
Expression = Number | Boolean | Variable | Add | Multiply | LessThan
Environment = dict[str, 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


def evaluate_expression(expression: Expression, environment: Environment) -> Value:
    match expression:
        case Number(value):
            return value
        case Boolean(value):
            return value
        case Variable(name):
            return environment[name]
        case Add(left, right):
            return (
                evaluate_expression(left, environment)
                + evaluate_expression(right, environment)
            )
        case Multiply(left, right):
            return (
                evaluate_expression(left, environment)
                * evaluate_expression(right, environment)
            )
        case LessThan(left, right):
            return (
                evaluate_expression(left, environment)
                < evaluate_expression(right, environment)
            )
        case _:
            raise TypeError(f"unknown expression: {expression!r}")


def evaluate_statement(statement: Statement, environment: Environment) -> Environment:
    match statement:
        case DoNothing():
            return environment

        case Assign(name, expression):
            return environment | {
                name: evaluate_expression(expression, environment)
            }

        case If(condition, consequence, alternative):
            if evaluate_expression(condition, environment):
                return evaluate_statement(consequence, environment)
            return evaluate_statement(alternative, environment)

        case Sequence(first, second):
            return evaluate_statement(
                second,
                evaluate_statement(first, environment),
            )

        case While(condition, body):
            if evaluate_expression(condition, environment):
                return evaluate_statement(
                    statement,
                    evaluate_statement(body, environment),
                )
            return environment

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


if __name__ == "__main__":
    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(evaluate_statement(program, {}))

运行：

1	`python big_step.py`

输出：

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

Java 程序员的迁移表

Python 组件	Java 对照	作用
`Expression` 联合类型	sealed interface `Expr`	表达式节点族
`Statement` 联合类型	sealed interface `Stmt`	语句节点族
`evaluate_expression`	`eval(Expr, Env)`	表达式求值
`evaluate_statement`	`exec(Stmt, Env)`	语句执行
`Environment`	`Map<String, Value>`	变量绑定
`environment	{…}`	创建新 `Map`
`match`	`switch` 模式匹配	按节点类型分派

如果用 Java 写这套解释器，常见结构会是：

sealed interface Expr permits Num, Bool, Var, Add, Multiply, LessThan {}
sealed interface Stmt permits DoNothing, Assign, If, Sequence, While {}

Map<String, Value> exec(Stmt stmt, Map<String, Value> env) {
    return switch (stmt) {
        case DoNothing ignored -> env;
        case Assign assign -> put(env, assign.name(), eval(assign.expr(), env));
        case If branch -> eval(branch.condition(), env).asBoolean()
            ? exec(branch.consequence(), env)
            : exec(branch.alternative(), env);
        case Sequence sequence -> exec(sequence.second(), exec(sequence.first(), env));
        case While loop -> eval(loop.condition(), env).asBoolean()
            ? exec(loop, exec(loop.body(), env))
            : env;
    };
}

Java 版本类型更严谨，也更适合长期维护。Python 版本更适合学习语义，因为样板少，递归关系一眼能看见。

大步语义的边界

大步语义很适合回答“运行完以后得到什么”。它也有明显边界。

第一，它不展示中间过程。while 循环跑了几次，环境每次怎样变化，单看大步求值结果并不直观。

第二，它不容易表达不终止。一个死循环没有最终环境，大步解释器会一直递归下去，直到运行时栈溢出。

第三，它不适合描述并发、调试、单步执行这类需要中间状态的场景。调试器关心“下一步是什么”，大步语义关心“最终结果是什么”。

这些边界会把系列带到下一篇：小步语义。小步语义会把程序看成一个可推进的机器配置，每次只走一步。那时 while 循环不会一次性求出最终环境，而会一步步展开成 if 和 sequence。

练习

第一，给表达式增加 Subtract，并让下面的程序输出 {"x": 7}。

1	`Assign("x", Subtract(Number(10), Number(3)))`

第二，给语句增加 Print，让解释器返回 (environment, output)。这样程序可以积累输出结果。

第三，把 While 的递归实现改成 Python 的 while 循环实现。比较两种写法：哪一种更接近语义定义，哪一种更接近工程实现。

参考资料

Understanding Computation 官方目录

Tom Stuart/computationbook 示例代码仓库

Python 文档：dataclasses

Python 文档：match 语句