练习

这些练习按“语言语义 → AST/parser → 解释器 → IR → 汇编 → 实现边界”逐层推进。先构建第五章快照：

1
2

cd code/05_recursion
make

需要自行输入的程序可以保存到 practice.lang。每题先在纸上写下预测，再用 mini 检查；递归程序只看最终数字，很容易漏掉调用展开和返回回卷这两个不同阶段。

1
2
3

基础：练习 1—3，理解 sub1、letrec 语义与 AST
核心：练习 4—7，贯通调用环境、IR 和递归栈帧
进阶：练习 8—11，检查尾位置、尝试受限优化、函数逃逸与边界

练习 1：sub1 只做一件事

预测下面三个程序的结果：

1

(sub1 43)

1

(sub1 (sub1 5))

1

(sub1 -2)

依次用 ./mini run practice.lang 检查。预期结果是 42、3 和 -3。

再回答：为什么 sub1 本身不会保证递归结束？它只把当前数字减一。若参数从负数开始，而基例是 (eq? n 0)，每次 sub1 反而让参数离零更远。

最后在 interpreter.cpp 和 assembly.cpp 中分别找到它的实现，确认两条路径做的是同一件事：解释器返回 value - 1，汇编生成器发出 subq $1, %rax。

练习 2：手动展开并回卷 sum 3

把贯穿示例的入口从 5 改成 3：

1
2
3
4
5

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

不要先运行。分别写出调用展开：

1

sum 3 -> sum 2 -> sum 1 -> sum 0

再从基例开始写返回回卷：

1
2
3
4

sum 0 = 0
sum 1 = 1 + 0 = 1
sum 2 = 2 + 1 = 3
sum 3 = 3 + 3 = 6

运行检查：

1

./mini run practice.lang

预期输出 6。指出哪一段是基例，哪一个表达式让参数靠近基例，以及为什么每一层都必须保留自己的 n，直到更深一层返回。

练习 3：从 letrec 语法还原 AST

先给 examples/recursive_sum.lang 手画 AST。最外层应该是一个 LetRecExpr，它有四项有效信息：

1
2
3
4

name            sum
param           n
function_body   if 表达式
body            (sum 5) 调用

运行：

1

./mini ast examples/recursive_sum.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)))

沿着这一行找出两个 Var(sum) 分别属于哪棵子树：一个在 function body 的递归调用中，一个在 letrec body 的首次调用中。它们都由同一个 LetRecExpr::name 引入，却会在不同环境中被解析。

接着检查三种错误输入：

1

(sub1 1 2)

1

(letrec sum n 0)

1

(letrec sum n n (sum))

分别保存到 practice.lang 并运行 ./mini ast practice.lang。它们依次多了 sub1 操作数、缺少 letrec body、缺少调用实参。第三个应明确报告：

1

error: expected function argument

在 parse_expr() 中说明为什么 head 为 sub1 或 letrec 时先进入固定特殊形式，而 head 为普通名字 sum 时才落入 call 分支。

练习 4：追踪一次递归调用环境

仍以 sum 3 为例。写出进入四层函数体时的初始环境：

1
2
3
4

sum 3 的 call_env   sum -> 当前函数，n -> 3
sum 2 的 call_env   sum -> 当前函数，n -> 2
sum 1 的 call_env   sum -> 当前函数，n -> 1
sum 0 的 call_env   sum -> 当前函数，n -> 0

每一行都是一份新的 Env，不是在同一份环境里反复改写 n。找到解释器的 call 分支，标出以下四步：

1
2
3
4

求值 callee
求值 argument
加入 self_name -> callee
加入 parameter -> argument 并求函数体

再解释为什么绑定 self 时使用“这次实际调用得到的 callee”，而不是让 Function 在创建时持有一个指向自己的 shared_ptr。前者既能让函数调用自己，也不会形成永远无法归零的强引用环。

练习 5：让递归函数作为值离开

运行已经准备好的例子：

1
2

./mini run examples/recursive_function_value.lang
./mini ir examples/recursive_function_value.lang

解释器输出应为 15。这个程序在 letrec 的 body 中没有立即调用 sum，而是直接返回函数值；外层把它改名为 f 后才调用。

回答两个问题：

1. 调用位置只知道名字 f，函数体为什么仍然能用原来的 self name sum？
2. 编译结果为什么不需要复制函数代码，只需要复制指向同一 label 的地址？

再尝试把函数作为参数传递：

1
2
3
4

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

预期结果仍然是 15。这说明“函数是一等值”和“函数能自调用”可以同时成立；它并不意味着函数已经能捕获任意外层变量。

练习 6：逐行解释递归 IR

先不看输出，手写 recursive_sum.lang 的 IR 形状。要求分成主程序和 lambda0(n) 两部分，并包含：

1
2
3
4
5

主程序取得函数地址并调用 sum 5
函数体重新取得自己的函数地址
eq?、branch、then/else/end
sub1、递归 call、返回后的 add
主程序和函数体各自的 return

再运行：

1

./mini ir examples/recursive_sum.lang

当前输出是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

f.0 = function lambda0
t.5 = call f.0 5
return t.5
lambda0(n):
  sum0 = function lambda0
  t.0 = eq? n 0
  if t.0 goto then0 else else0
  then0:
  t.1 = 0
  goto end0
  else0:
  t.2 = sub1 n
  t.3 = call sum0 t.2
  t.4 = n + t.3
  t.1 = t.4
  end0:
  return t.1
end lambda0

逐项回答：

1. 为什么主程序的 f.0 不能直接供 .Llambda0 的栈帧读取？
2. f.0 和 sum0 为什么可以有不同名字却表示同一个函数值？
3. 为什么 t.2 = sub1 n 必须出现在递归 call 之前？
4. 为什么 t.4 = n + t.3 必须出现在递归 call 之后？
5. IR 中的 then 是 branch 的目标；为什么汇编物理布局可以让 then label 紧跟条件跳转，并只对 else 发出 je？

最后在 lowerer 中确认：function_env 是新环境，先加入 sum -> sum0，再加入 n -> n；它没有复制外层 main 的环境。

练习 7：画出七个同时存在的栈帧

生成汇编：

1

./mini compile examples/recursive_sum.lang -o out.s

在 out.s 中找出：

1
2
3
4
5
6

main 的 16 字节局部区
.Llambda0 的 64 字节局部区
subq $1, %rax
call *%rcx
递归返回后的 addq
函数结尾的 retq

想象 sum 0 刚进入、还没有返回的时刻，画出同时存在的七个 frame：main，以及 sum 5、sum 4、sum 3、sum 2、sum 1、sum 0 中的六个递归函数 frame。不要被“入口调用一次”骗过。

对每个函数 frame 至少标出：

1
2
3
4
5

当前 n 的栈槽
当前 self 地址的栈槽
call 压入的返回地址
上一层保存的 %rbp
递归结果与本层加法结果的槽

然后从 sum 0 向上画箭头，说明 %rax 怎样依次携带 0、1、3、6、10、15 返回。关键点是：更深一层返回时，当前层的 frame 仍然存在，所以 addq 还能读到本层保存的 n。

最后在当前平台链接并检查：

1
2
3

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

Apple Silicon Mac 改用：

1
2
3

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

退出状态应为 15。

练习 8：尾位置不等于尾调用优化

查看 examples/countdown.lang：

1
2
3

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

递归分支把 (down ...) 的结果直接作为分支结果，没有再做加法，所以调用处于尾位置。运行：

1
2
3

./mini run examples/countdown.lang
./mini ir examples/countdown.lang
./mini compile examples/countdown.lang -o countdown.s

结果应为 42。在 IR 中仍能看到普通 call down0，在汇编中仍能看到 call *%rcx；每次调用仍会创建新 frame，返回时仍逐层经过 retq。

回答：如果真的做尾调用优化，哪一种资源增长应该消失？本章不要求实现优化，只需说明“语法上位于尾位置”和“后端已经复用当前 frame”是两件事。

练习 9（进阶选做）：把直接自尾调用变成跳转

这一题不改变第五章标准代码快照，而是在自己的练习副本中实现一个严格受限的优化。只处理同时满足以下条件的调用：

1
2
3

调用位于当前递归函数的尾位置
callee 经过词法名字解析后，正是当前 letrec 的 self binding
只处理直接自调用，不处理普通 lambda、函数别名、相互递归或任意尾调用

先让 lowering 携带“当前表达式是否位于尾位置”的信息，并按下面的规则向下传递：

1
2
3
4
5
6
7

每个 function body                              从自己的尾位置上下文开始
尾位置 letrec 的 body                           是尾位置
尾位置 if 的 then branch 和 else branch         是尾位置
if 的 condition                                 不是尾位置
尾位置 let 的 body                              是尾位置
let 的 value                                    不是尾位置
+、sub1、eq? 的操作数以及 call 的 callee/argument 都不是尾位置

call 表达式本身可以是候选者，但求 callee 和 argument 的过程都不是尾位置。遇到嵌套 letrec 时，内层 function body 还要切换到内层函数自己的 self binding，不能继续沿用外层函数身份。

不要只比较源码名字是否等于 letrec 的函数名。下面的调用虽然位于尾位置，但 loop 已被内层 let 遮蔽，因此不能优化成外层函数的自跳转：

1
2
3
4

(letrec loop n
    (let loop (lambda x x)
        (loop n))
    (loop 3))

可以在名字解析后比较 callee 对应的唯一 self operand，或者显式保存 binding identity。这个程序应得到 3；若只比较字符串，很可能错误地不断跳回外层 loop。

接着在结构化 IR 中加入明确的 tail_self_call op，保存已经求值完成的新参数和当前函数体入口。不要扫描 IR 文本或汇编字符串猜测 call 后面是否紧跟 return。函数汇编需要两个入口位置：

tail_self_call 是终结当前控制流路径的 op，不会产生供后续表达式使用的结果。现有 lower_expr() 总是假设表达式会返回一个 Operand，因此不要为它捏造一个假临时值。可以增加一个只处理尾位置的 lower_tail_expr()：普通表达式仍委托给 lower_expr() 并写入函数结果；尾位置的 if 递归处理两个分支；直接自尾调用则在参数求值后发出 tail_self_call，到这里结束该分支。

1
2

.Llambda0         执行一次 prologue，并把 %rdi 保存到参数槽
.Llambda0_body    当前 frame 内重新开始执行函数体

tail_self_call 可以生成类似下面的代码：

1
2
3

movq new_argument, %rax
movq %rax, parameter_slot
jmp .Llambda0_body

先求值并保存 new_argument，再覆盖旧参数槽，因为参数表达式可能仍要读取旧参数。跳转目标必须是 prologue 之后的 body label；若跳回 .Llambda0，就会再次执行 pushq %rbp，不但没有复用 frame，还会破坏栈布局。

完成后做三组检查：

1. countdown.lang 的 main 仍用一次普通 call 进入函数，但递归分支改用 jmp .Llambda0_body。
2. recursive_sum.lang 中的递归调用后面还要做加法，必须继续生成普通 call。
3. 上面的 shadowing 程序继续返回 3，不能被误判为直接自调用。

最后把 countdown.lang 的初始参数暂时改成一个较大的数，确认编译后的程序仍返回 42，并说明为什么递归深度不再带来线性增长的机器栈。这个练习只建立“直接自尾调用”这一种最小优化；不要继续扩展到通用尾调用约定。

练习 10：比较外层名字和 self name

先运行不受支持的捕获例子：

1
2

./mini run examples/recursive_capture_error.lang
./mini ir examples/recursive_capture_error.lang

两条命令都会报告 undefined variable: base。按名字来源分类：

1
2
3

adddown   self name，受支持
n         parameter，受支持
base      创建位置的外层变量，不支持

再把程序改成一个从未调用的递归函数：

1
2

(let base 10
    (letrec unused n base 42))

预测并检查：

1
2

./mini run practice.lang
./mini ir practice.lang

run 输出 42，因为函数体没有执行；ir 仍在 lowering 函数体时报告 undefined variable: base。解释为什么这只是报错阶段不同，而不是解释器已经支持闭包。

练习 11：做一次完整回归

依次运行：

1
2
3
4
5
6
7
8
9

./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/sub1.lang
./mini run examples/recursive_sum.lang
./mini run examples/recursive_function_value.lang

除了最后两个递归求和例子输出 15，前七个都应输出 42。这一步验证第五章没有为了加入递归而丢掉前几章的主线能力。

最后任选一个结果在 0 到 255 之间的示例，完成：

1
2

source -> ast -> run
source -> ir -> compile -> cc -> executable

逐层写下“输入是什么、输出是什么”。如果两条路线产生同一整数，并且你能解释 self binding 在解释器、IR 和汇编中的对应位置，第五章的核心就已经走通了。