本章总结与验收清单

第五章解决的问题可以浓缩成一句话：让函数体里的递归名字稳定地指向同一个函数值。解释器用 self_name 在调用时建立这条绑定；编译器则让函数体内的 function_ref 再次取得同一个函数标签。

有了这条自绑定，下面的程序就能不断进入同一段函数代码，同时让每次调用拥有自己的参数和临时结果：

1
2
3
4
5

(letrec sum n
    (if (eq? n 0)
        0
        (+ n (sum (sub1 n))))
    (sum 5))

它的结果是 15。sub1 只是让参数逐步接近基例；本章真正的新困难是 sum 怎样在自己的函数体里仍然有意义。

从源码到两条执行路线

整章的对应关系如下：

两条路线仍然从同一棵 AST 出发：

1
2

源码 -> AST -> 解释器 -> Value
源码 -> AST -> 结构化 IR -> x86-64 AT&T 汇编

解释器中的多份调用环境，对应编译结果运行时的多层栈帧。它们使用的表示不同，但都保证 sum 5 和 sum 4 中的 n 不会互相覆盖。

语言和 parser 检查

本章完成后，下面三种程序都应被正确识别：

1
2
3
4
5
6
7
8
9

(sub1 5)

(letrec down n
    (if (eq? n 0) 42 (down (sub1 n)))
    (down 3))

(letrec sum n
    (if (eq? n 0) 0 (+ n (sum (sub1 n))))
    (sum 5))

检查点：

• sub1 只有一个子表达式。
• letrec 依次包含 function name、parameter、function body 和 outer body。
• 普通 identifier 仍然是一个或多个英文字母；sub1、eq? 只作为固定 head 识别。
• 特殊形式先于普通调用匹配；(sum 5) 才落入 call 分支。
• 缺少实参的 (sum) 会得到明确的 expected function argument。

AST 和解释器检查

AST 应显式增加 ExprKind::sub1 与 ExprKind::letrec，所有消费方继续通过 kind + switch 分派。LetRecExpr 必须同时拥有两棵子树：递归函数体与 letrec 的 body。

解释器检查点：

• sub1 先求值操作数，再确认它是数字并减一。
• 求值 letrec 时只创建函数值，不执行 function body。
• letrec 的 body 环境包含 name -> function。
• 真正调用递归函数时，新环境先包含 self_name -> callee，再包含 parameter -> argument。
• Function 不保存任意外层环境，也不把自己作为 shared_ptr 放进自己的环境；因此既保持自调用，也不制造自引用环。
• 递归函数作为 letrec 的结果离开后，仍然能通过自己的名字递归。

IR 和汇编检查

lowering 的递归接口继续显式接收当前 ops 与当前 env。IrProgram 是整段输出，可以作为 lowerer 的 pass 状态；主程序和函数体各自拥有不同的操作列表与名字环境。

对 recursive_sum.lang，至少应在 IR 中看到：

1
2
3
4
5
6
7

f.0 = function lambda0
t.5 = call f.0 5
...
lambda0(n):
  sum0 = function lambda0
  ...
  t.3 = call sum0 t.2

这里的关键不是临时编号，而是 f.0 和 sum0 都引用 lambda0。它们属于不同栈帧，不能把 main 的 f.0 当成递归函数体可以直接读取的槽。

汇编检查点：

• function_ref 通过 leaq .Llambda0(%rip), %rax 取得代码地址。
• sub1 生成 subq $1, %rax。
• 参数放进 %rdi，callee 地址放进 %rcx，调用使用 call *%rcx。
• 每次进入 .Llambda0 都建立一份新的、16 字节对齐的栈帧。
• 基例把 0 交给 %rax；非基例在递归返回后，用当前帧保存的 n 继续相加。
• compile 仍然只输出 .s，不替用户调用 cc 或链接可执行文件。

回归检查

第五章是独立代码快照，不应为了增加递归而丢掉前四章的主线能力。进入 code/05_recursion 后，可以运行：

1
2
3
4
5
6
7
8

make
./mini run examples/literal.lang
./mini run examples/negative_add.lang
./mini run examples/nested_let.lang
./mini run examples/if_else.lang
./mini run examples/function_argument.lang
./mini run examples/function_return.lang
./mini run examples/recursive_sum.lang

预期依次得到：

1
2
3
4
5
6
7

42
42
42
42
42
42
15

第四章末尾的 cin/cout 是一次性 C++ runtime 联调，不属于后续主线，因此不在第五章回归范围内。

本章明确不做的事

• 不支持相互递归。
• 不支持普通值的递归绑定。
• 不捕获递归函数创建位置的任意外层变量。
• 标准代码快照不做尾调用优化，也不增加递归深度保护；章末只有一道严格限制为直接自尾调用的进阶选做练习。
• 不增加静态类型标注或静态类型检查。
• 不继承第四章专属的 cin/cout primitive。

最小验收流程

先检查解释器与中间表示：

1
2
3
4
5
6

cd code/05_recursion
make clean
make
./mini ast examples/recursive_sum.lang
./mini run examples/recursive_sum.lang
./mini ir examples/recursive_sum.lang

run 应输出 15。再生成并链接当前平台的汇编：

1
2
3
4

./mini compile examples/recursive_sum.lang -o out.s
cc out.s -o out
./out
echo $?

Linux、WSL 和 Intel Mac 可以直接使用上面的链接命令。Apple Silicon Mac 需要让链接目标也保持 x86-64：

1
2
3

cc -arch x86_64 out.s -o out
./out
echo $?

这里应看到退出状态 15。退出状态只适合观察 0 到 255 的小整数；完整语言结果仍以 mini run 为准。

如果能独立解释下面四件事，就已经抓住了本章主线：

1. 为什么普通 let + lambda 不能给函数体提供自己的名字。
2. 为什么解释器在调用时建立 self 与 parameter 绑定，而不让函数持有自己。
3. 为什么 IR 中的 f.0 和 sum0 是两个值，却指向同一个函数 label。
4. 为什么递归返回后，还能从当前栈帧取回本层的 n 完成加法。

下一章会引入 record、统一的 tagged value 与堆分配。值的机器表示会变得更丰富，但本章建立的自绑定、调用环境和递归栈帧仍然是后续函数语义的基础。