章节目录

AST：保存函数和调用的结构

本节阅读量:

语言层已经确定了两个新形状：

1
2

(lambda parameter body)
(callee argument)

AST 不执行它们，只需要完整保存源码的结构。因此新增两个节点：

1
2

Lambda(param, body)
Call(callee, argument)

源码位置和字段一一对应：

源码 AST 字段
(lambda x body) 中的形参 x LambdaExpr::param
(lambda x body) 中的函数体 LambdaExpr::body
(callee argument) 中的被调用者表达式 CallExpr::callee
(callee argument) 中的实参表达式 CallExpr::argument

贯穿示例：

1
2

(let inc (lambda x (+ x 1))
    (inc 41))

会变成：

1
2
3
4

Let(
  inc,
  Lambda(x, Add(Var(x), Int(1))),
  Call(Var(inc), Int(41)))

外层仍是第二章已有的 LetExpr。新节点只负责其中的函数值和调用部分。

先给 kind 增加两个成员

代码在 code/04_functions/src/front/ast.h：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

enum class ExprKind {
    integer,
    add,
    variable,
    let,
    equal,
    conditional,
    lambda,
    call,
    input,
    output,
};

解释器和 IR lowering 都会对 expr.kind 做 switch。本章函数主线新增的是 lambda 和 call；末尾的可选 C++ runtime 实验还会使用 input、output，完整代码提前把它们列在 kind 末尾，具体节点留到章末再看。显式列出这些成员后，每个 AST 消费者都能明确看到自己必须处理哪些表达式。

LambdaExpr 拥有函数体

1
2
3
4
5
6
7

struct LambdaExpr final : Expr {
    LambdaExpr(std::string param, std::unique_ptr<Expr> body);

    std::string param;
    std::unique_ptr<Expr> body;
    std::string dump() const override;
};

两个字段分别对应源码中的两个位置：

1
2

param   参数名 x
body    表达式 (+ x 1)

构造函数和调试输出写在 code/04_functions/src/front/ast.cpp：

1
2
3
4
5
6

LambdaExpr::LambdaExpr(std::string param, std::unique_ptr<Expr> body)
    : Expr(ExprKind::lambda), param(std::move(param)), body(std::move(body)) {}

std::string LambdaExpr::dump() const {
    return "Lambda(" + param + ", " + body->dump() + ")";
}

这里的 body 使用 std::unique_ptr<Expr>，表示 LambdaExpr 独占并负责销毁自己的函数体。函数体仍然可以是任何表达式，包括 let、if、调用，甚至另一个 lambda。

CallExpr 同时拥有 callee 和 argument

1
2
3
4
5
6
7

struct CallExpr final : Expr {
    CallExpr(std::unique_ptr<Expr> callee, std::unique_ptr<Expr> argument);

    std::unique_ptr<Expr> callee;
    std::unique_ptr<Expr> argument;
    std::string dump() const override;
};

实现仍然只是设置 kind 并接过子节点的所有权：

1
2
3
4
5
6

CallExpr::CallExpr(std::unique_ptr<Expr> callee, std::unique_ptr<Expr> argument)
    : Expr(ExprKind::call), callee(std::move(callee)), argument(std::move(argument)) {}

std::string CallExpr::dump() const {
    return "Call(" + callee->dump() + ", " + argument->dump() + ")";
}

callee 不能只存函数名，因为调用位置并不总是变量。下面三种写法都需要同一个 CallExpr：

1
2
3

(inc 41)
((lambda x (+ x 1)) 41)
((make 0) 41)

它们的 callee 分别是 VarExpr、LambdaExpr 和另一个 CallExpr。把 callee 定义成普通 Expr，parser 就不必提前猜它最终会产生什么值；是不是函数留给解释器运行时判断。

参数同样可能是任意表达式，包括一个函数值：

1

((lambda f (f 41)) (lambda x (+ x 1)))

AST 的所有权是一棵树

解析完整程序后，CLI 持有根节点的 std::unique_ptr<Expr>。每个父节点再用自己的 unique_ptr 持有子节点：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

root unique_ptr
└── LetExpr
    ├── value unique_ptr
    │   └── LambdaExpr
    │       └── body unique_ptr
    │           └── AddExpr
    └── body unique_ptr
        └── CallExpr
            ├── callee unique_ptr
            └── argument unique_ptr

根节点销毁时，所有子节点会沿着这棵树自动销毁，不需要手写 delete，也没有多个节点争夺同一份 AST 所有权。

这是一个 C++ 所有权细节，第一遍可以只记住“根节点活着，整棵 AST 就活着”。parser 会用 std::move 把子表达式交给新节点；解释器创建函数值时只借用 LambdaExpr::body，不会夺走这棵树的所有权。具体生命周期会在解释器一节说明。

消费节点仍然先看 kind

新增节点不会改变项目一直使用的分派方式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

switch (expr.kind) {
case ExprKind::lambda: {
    const auto& lambda_expr = static_cast<const LambdaExpr&>(expr);
    // 使用 lambda_expr.param 和 lambda_expr.body
    break;
}
case ExprKind::call: {
    const auto& call_expr = static_cast<const CallExpr&>(expr);
    // 使用 call_expr.callee 和 call_expr.argument
    break;
}
// 其他 ExprKind 分支……
}

static_cast 安全的前提来自节点构造函数：LambdaExpr 总把 kind 设为 lambda，CallExpr 总把 kind 设为 call。这个约定要在每个节点中保持一致。

检查 AST

1
2
3
4

cd code/04_functions
make
./mini ast examples/function_value.lang
./mini ast examples/call.lang

第一条输出：

1

Let(inc, Lambda(x, Add(Var(x), Int(1))), Call(Var(inc), Int(41)))

第二条输出：

1

Call(Lambda(x, Add(Var(x), Int(1))), Int(41))

这两个结果的区别只在 callee 的形状：一个从变量取函数，另一个直接使用 lambda。

4.1 语言：创建函数，再调用函数

上一节

4.3 Parser：特殊形式之外就是调用

下一节
本节目录