AST：结构仍是一棵树，递归来自名字
本节阅读量:
语言层新增了两个源码形状：
1
2
|
(sub1 expr)
(letrec name param function-body body)
|
AST 只负责保存它们的结构，不在这一层查找变量，也不会真的调用函数。对应的新节点是：
1
2
|
Sub1(expr)
LetRec(name, param, function_body, body)
|
贯穿示例：
1
2
3
4
5
|
(letrec sum n
(if (eq? n 0)
0
(+ n (sum (sub1 n))))
(sum 5))
|
会得到：
1
2
3
4
5
6
7
8
|
LetRec(
sum,
n,
If(
Eq(Var(n), Int(0)),
Int(0),
Add(Var(n), Call(Var(sum), Sub1(Var(n))))),
Call(Var(sum), Int(5)))
|
最外层的 LetRec 同时拥有递归函数体和使用该函数的 body。两个 Var(sum) 目前都只是保存字符串 "sum" 的普通变量节点；它们究竟指向哪个函数值，要到解释器或 IR lowering 查环境时才确定。
先扩展 ExprKind
代码在 code/05_recursion/src/front/ast.h：
1
2
3
4
5
6
7
8
9
10
11
12
|
enum class ExprKind {
integer,
add,
sub1,
variable,
let,
letrec,
equal,
conditional,
lambda,
call,
};
|
第五章新增的是 sub1 和 letrec。它们被显式列进 kind 后，解释器和 IR lowering 的 switch 都必须决定怎样处理这两种表达式。这样操作种类不会藏在某个类名或列表位置的假设中。
枚举顺序本身不表示求值顺序。真正的求值规则仍由节点字段和后续 pass 决定。
Sub1Expr 拥有一个操作数
sub1 的源码中只有一个子表达式，因此节点也只有一个 expr 字段：
1
2
3
4
5
6
|
struct Sub1Expr final : Expr {
explicit Sub1Expr(std::unique_ptr<Expr> expr);
std::unique_ptr<Expr> expr;
std::string dump() const override;
};
|
构造函数设置正确的 kind，并接过子表达式的所有权：
1
2
3
4
5
6
|
Sub1Expr::Sub1Expr(std::unique_ptr<Expr> expr)
: Expr(ExprKind::sub1), expr(std::move(expr)) {}
std::string Sub1Expr::dump() const {
return "Sub1(" + expr->dump() + ")";
}
|
例如 (sub1 (+ 2 3)) 的结构是：
1
|
Sub1(Add(Int(2), Int(3)))
|
AST 保留了“先算加法，再对结果减一”的嵌套关系；它本身还没有执行任何运算。
LetRecExpr 保存四个位置
LetRecExpr 的字段和源码位置一一对应：
1
2
3
4
5
6
7
8
9
10
11
12
|
struct LetRecExpr final : Expr {
LetRecExpr(std::string name,
std::string param,
std::unique_ptr<Expr> function_body,
std::unique_ptr<Expr> body);
std::string name;
std::string param;
std::unique_ptr<Expr> function_body;
std::unique_ptr<Expr> body;
std::string dump() const override;
};
|
| 源码位置 |
AST 字段 |
保存的内容 |
letrec 后的函数名 |
name |
例如 sum |
| 函数名后的参数名 |
param |
例如 n |
| 第一个表达式 |
function_body |
每次函数调用时执行的表达式 |
| 第二个表达式 |
body |
建好递归绑定后执行的表达式 |
构造函数用 std::move 接收两个子树：
1
2
3
4
5
6
7
8
9
|
LetRecExpr::LetRecExpr(std::string name,
std::string param,
std::unique_ptr<Expr> function_body,
std::unique_ptr<Expr> body)
: Expr(ExprKind::letrec),
name(std::move(name)),
param(std::move(param)),
function_body(std::move(function_body)),
body(std::move(body)) {}
|
调试输出按照同一个字段顺序展开：
1
2
3
4
|
std::string LetRecExpr::dump() const {
return "LetRec(" + name + ", " + param + ", " +
function_body->dump() + ", " + body->dump() + ")";
}
|
字段名 function_body 比含糊的 value 更明确：这个位置不会像普通 let 的 value 那样先求值成一个任意值，它就是即将创建的递归函数的函数体。
为什么不继续组合 LetExpr 和 LambdaExpr
普通写法：
1
|
(let sum (lambda n function-body) body)
|
对应普通 AST：
1
|
Let(sum, Lambda(n, function-body), body)
|
这个结构已经有第二章确定下来的作用域规则：sum 只绑定在 body 中，不绑定在 Lambda 所在的 value 中。若 parser 仍然生成同一个 LetExpr，后续消费者就无法仅从节点种类看出这里需要递归绑定。
专门的节点把差别保留下来：
1
|
LetRec(sum, n, function-body, body)
|
解释器遇到 ExprKind::letrec 时可以建立自绑定；IR lowering 遇到它时可以让函数体引用自己的标签。普通 LetExpr 的旧语义无需改变。
递归不会让 AST 变成环
看到“函数指向自己”时，很容易误以为 AST 里也会出现一根指回祖先节点的指针。实际并不会：
1
2
3
4
5
6
7
8
9
10
11
|
root unique_ptr
└── LetRecExpr
├── function_body unique_ptr
│ └── IfExpr
│ └── ... CallExpr
│ └── callee unique_ptr
│ └── VarExpr("sum")
└── body unique_ptr
└── CallExpr
└── callee unique_ptr
└── VarExpr("sum")
|
VarExpr("sum") 只记录名字，没有直接指向根部的 LetRecExpr。整棵 AST 仍由 std::unique_ptr 单向拥有：父节点拥有子节点，根节点销毁时所有子节点自动销毁。
真正的自引用在 AST 之后才建立：
1
2
|
解释器 环境把名字 sum 映射到函数值
编译器 lowering 环境把名字 sum 映射到函数地址临时值
|
把“源码结构”和“名字指向的运行时值”分开，是理解本章的关键台阶。
AST 消费者仍然使用 kind + switch
新增节点不会改变项目的分派约定：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
switch (expr.kind) {
case ExprKind::sub1: {
const auto& sub1_expr = static_cast<const Sub1Expr&>(expr);
// 使用 sub1_expr.expr
break;
}
case ExprKind::letrec: {
const auto& letrec_expr = static_cast<const LetRecExpr&>(expr);
// 使用 name、param、function_body 和 body
break;
}
// 其他 ExprKind 分支……
}
|
static_cast 安全的前提仍来自构造函数：Sub1Expr 总把 kind 设成 sub1，LetRecExpr 总把 kind 设成 letrec。解释器、IR lowering 等每个消费者都用同一组 kind 明确分派，不需要在运行时猜测节点类型。
实际检查 AST
运行：
1
2
3
4
|
cd code/05_recursion
make
./mini ast examples/recursive_sum.lang
./mini ast examples/countdown.lang
|
第一条命令输出：
1
|
LetRec(sum, n, If(Eq(Var(n), Int(0)), Int(0), Add(Var(n), Call(Var(sum), Sub1(Var(n))))), Call(Var(sum), Int(5)))
|
第二条命令输出：
1
|
LetRec(down, n, If(Eq(Var(n), Int(0)), Int(42), Call(Var(down), Sub1(Var(n)))), Call(Var(down), Int(3)))
|
可以逐项核对：
- 两个根节点都是
LetRec。
sum 和 down 同时出现在函数体的递归调用与外层 body 的第一次调用中。- 每个递归实参都包含一个
Sub1(Var(n))。
- AST 只记录这些结构，还没有决定递归会执行多少次。
下一节会让 parser 从 token 构造出这棵所有权清晰的树。
5.3 Parser：在括号 head 位置识别 `sub1` 和 `letrec`
下一节
