练习

这些练习按“语言语义 → AST → 解释器 → IR → 汇编”的顺序推进。先构建第四章代码：

1
2

cd code/04_functions
make

需要自行输入的程序，可以反复保存到 practice.lang。每次都先写下预测，再运行命令检查；只看输出，很容易错过函数创建和函数调用之间的区别。

可以按下面的难度推进：

1
2
3

基础：练习 1—3，确认语法、AST 和调用环境
核心：练习 4—6，贯通高阶函数、IR 和两个栈帧
进阶：练习 7—8，检查实现边界并尝试自由变量分析

练习 1：预测语义

依次判断下面三个程序的结果：

1

(lambda x (+ x 1))

1

((lambda x (+ x 2)) 40)

1

((lambda x (let y 2 (+ x y))) 40)

对每个程序写下：

1
2
3
4

求值 lambda 时是否执行函数体
函数体一共执行几次
调用环境最初包含哪些绑定
整个程序的结果

把程序逐个保存到 practice.lang，然后检查：

1

./mini run practice.lang

预期输出依次是 <function>、42、42。第三个程序进入函数体时先有 x -> 40，执行内部 let 后才增加 y -> 2。

练习 2：从语法还原 AST

把下面程序保存到 practice.lang，先手画它的 AST：

1

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

检查每个节点的角色：

1
2
3

Let      保存函数值
Lambda   创建函数值
Call     取出 inc 并发起调用

再运行：

1

./mini ast practice.lang

当前实现应输出：

1

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

接着分别让 parser 读取两个参数个数错误的程序：

1

(lambda x x x)

1

((lambda x x) 1 2)

再检查缺少实参：

1

(inc)

仍然运行 ./mini ast practice.lang。第一个应在读完一个函数体后期待 )，第二个应在读完一个 argument 后期待 )，第三个应报告 expected function argument。

结合 parse_expr() 回答：为什么 (lambda x x) 会进入特殊形式分支，而 ((lambda x x) 1) 会在外层进入普通调用分支？

练习 3：追踪解释器的两个环境

把下面程序保存到 practice.lang，再分析：

1
2
3

(let seed 99
    (let twice (lambda x (+ x x))
        (twice 21)))

按时间顺序写出：

1
2
3
4
5

求值 lambda 时的外层环境
twice 绑定完成后的外层环境
求值 callee 和 argument 分别得到什么
刚进入函数体时的 call_env
函数体的结果

关键检查点是：调用点的环境里有 seed 和 twice，新建的 call_env 却只有 x -> 21。本章的 Function 不保存前一份环境，函数体也没有理由看到 seed。

运行检查：

1

./mini run practice.lang

预期输出是 42。然后在 eval_expr() 的 ExprKind::call 分支中，找出“检查 callee”“求 argument”“创建 call_env”和“求值 body”对应的代码。

练习 4：让函数真正成为一等值

把下面两个程序依次保存到 practice.lang。第一个程序把函数作为参数传入：

1
2

((lambda apply (apply 41))
    (lambda x (+ x 1)))

第二个程序先返回函数，再调用返回值：

1

(((lambda ignored (lambda x (+ x 1))) 0) 41)

第二个程序的括号较多。运行前先给每一层调用分别标出 callee 和 argument：中间那次调用得到一个函数值，最外层再把 41 交给这个返回值。

分别运行：

1
2

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

两个程序都应得到 42。检查 IR 时，不必先猜 lambda0、lambda1 的编号，但必须找到：

• 两个独立的函数定义；
• 产生两个函数地址的 function 操作；
• 至少一次以另一个函数为 argument，或者以一次调用的结果为 callee；
• 最终产生整数结果的调用。

第二个程序能运行，是因为返回的内层函数只使用自己的参数 x，没有读取 ignored。把内层函数改成 (lambda x (+ ignored x)) 后，就越过了第四章的边界。

练习 5：手写一次 lowering

先不要运行命令，给 examples/function_value.lang 手写 IR。临时变量的数字后缀可以先省略，但要分成主程序和独立函数体两部分，并包含：

1
2
3
4
5

function_ref
let 对应的 copy
call
函数体里的 add
主程序和函数体各自的 return

然后对照实际输出：

1

./mini ir examples/function_value.lang

当前实现输出：

1
2
3
4
5
6
7
8

f.0 = function lambda0
inc0 = f.0
t.1 = call inc0 41
return t.1
lambda0(x):
  t.0 = x + 1
  return t.0
end lambda0

逐项解释下面三个现象：

1. function_ref 在主程序的 ops 中，函数体的 add 却在 IrFunction::ops 中。
2. inc0 保存的是 f.0，调用不需要知道它最初来自哪个 lambda。
3. t.0 在打印结果中位于 t.1 后面，编号却更小。这与 lowerer 先处理 lambda 的函数体、再继续处理外层调用有关。

最后在 ExprKind::lambda 的 lowering 分支里确认：函数体使用新建的 function_env，其中最初只有参数 x。

练习 6：画出两个同时存在的栈帧

生成并运行汇编：

1
2
3
4

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

退出状态应为 42。打开 out.s，依次找出：

1
2
3
4
5
6
7
8

main 的序言和 32 字节局部空间
.Llambda0 的序言和 16 字节局部空间
leaq 取得的函数地址
函数地址从栈槽装入 %rcx
参数 41 放入 %rdi
call *%rcx
返回值从 %rax 保存到 main 的调用结果槽
两个 retq

在 .Llambda0 已经建立栈帧、但尚未执行加法的时刻，画出栈，并至少标出：

1
2
3
4
5

main 的局部槽
call 压入的返回地址
lambda 保存的旧 %rbp
lambda 的参数 x
lambda 的临时结果槽

第一遍可以先不计算 %rsp mod 16，只画清两个 %rbp、返回地址和各自槽位；再回到正文补上 16 字节对齐。

回答两个问题：

1. 此时 main 的栈帧为什么仍然存在？
2. retq 怎样知道要回到 main 的哪条指令？

最后说明为什么调用点必须生成 call *%rcx，而不能一律写成 call .Llambda0：callee 是运行时求值出来的普通值，它可能来自变量、参数，甚至另一次调用的结果。

练习 7：划清一致性边界

先用一个符合本章约束的高阶函数检查解释器和编译器：

1

((lambda f (f 40)) (lambda x (+ x 2)))

运行完整路径：

1
2
3
4
5

./mini run practice.lang
./mini compile practice.lang -o out.s
cc out.s -o out
./out
echo $?

解释器输出和可执行程序退出状态都应是 42。

再把 practice.lang 改成错误程序：

1

(42 1)

只运行下面两条命令，不要再链接、运行生成的 out.s：

1
2

./mini run practice.lang
./mini compile practice.lang -o out.s

解释器应报告：

1

error: function call expected a function

编译器目前会成功生成汇编。在 out.s 中可以看到与下面相同含义的指令：

1
2

movq $42, %rcx
call *%rcx

也就是说，编译器把 42 当成了裸代码地址。它还没有运行时类型标签，因此不能像解释器一样在调用前区分整数与函数。

先写下本章的语义一致性契约：只比较符合本章作用域规则、实际执行路径上值种类使用正确、使用本章示例中的小整数且加法不发生有符号 long 溢出的程序。

再单独写下观察限制：只有为了用 shell 的 $? 检查结果时，才需要让顶层最终返回 0 到 255 的整数。它不是语义一致性的条件；mini run 可以直接显示更一般的合法结果和 <function>。

最后比较作用域错误：

1
2
3

./mini run examples/capture_error.lang
./mini ir examples/capture_error.lang
./mini compile examples/capture_error.lang -o out.s

三条路径都会遇到 undefined variable: x，但时机不同：解释器调用函数并执行 body 时才查找 x，lowering 在建立独立函数体时就会查找 x。支持范围内的结果一致，不代表所有错误都必须在同一阶段发生。

练习 8（进阶，可选）：自由变量分析

这是一道可选扩展，不是完成第四章主线代码的前提。先完成集合推导；愿意继续写代码时，再做后半部分的工程挑战。目标是让不受支持的捕获和真正未定义的名字得到更准确、稳定的错误，而不是实现闭包。

概念部分：计算一个 lambda 需要的外部名字

可以用 std::unordered_set<std::string> 表示名字集合。对某个 lambda，用“只包含它的参数”的 bound 集合遍历函数体：

1
2
3
4
5
6

integer                 没有自由变量
variable                名字不在 bound 中时，加入结果
add、equal、call         合并子表达式的结果
if                      合并 condition 和两个分支
let name value body     value 使用原 bound；body 使用加入 name 后的 bound
lambda param body       body 使用加入 param 后的 bound

特别注意 let 的 value：新名字只在 body 中生效，不能提前加入 bound。

先手算并记录每个例子的期望集合；实现分析后，再把它们逐个保存到 practice.lang，通过接入分析的 CLI 命令验证：

1
2
3
4

(lambda x (+ x 1))                    需要 {}
(lambda x (let y 1 (+ x y)))          需要 {}
(let y 1 (lambda x (+ x y)))          内层 lambda 需要 {y}
(lambda x (lambda y (+ x y)))         外层需要 {}，内层需要 {x}

最后一个例子说明：不能只检查最外层函数。遍历 AST 时，要把每个嵌套 lambda 都单独当作检查目标。

概念部分：区分捕获与未定义名字

检查 AST 时同时维护当前词法位置已经存在的名字集合 outer_names。对一个 lambda 计算出 needed_names 后，分成两类：

1
2

needed_names 与 outer_names 的交集    外层确实有这个名字，本章缺少的是捕获
needed_names 中其余的名字              任何外层都没有定义，是真正的未定义名字

可以分别报告：

1
2

function cannot capture outer variable before closure chapter: x
undefined variable: missing

进入 lambda 的 body 检查嵌套函数时，把当前参数加入词法名字集合；进入 let 的 body 时，再把它的名字加入。若错误信息中可能出现多个名字，先排序再输出，测试会更稳定。

工程挑战：选择接入位置

一种做法是在 eval 和 lower_to_ir 之前共用一次 AST 预检查。这样解释器和编译器会在相同阶段拒绝捕获。也可以只在各自的 ExprKind::lambda 分支接入，但要接受两条路径遇到嵌套 lambda 的时间可能不同。

无论选择哪种方式，都不要给函数值增加外层环境；那是闭包章节的任务。这道练习只改善诊断。

工程挑战：回归测试

修改 C++ 后先重新构建，再确认合法程序没有回退：

1
2
3

make
./mini run examples/function_value.lang
./mini ir examples/function_value.lang

预期仍然得到 42，并正常打印 IR。再检查已有的捕获示例：

1
2
3

./mini run examples/capture_error.lang
./mini ir examples/capture_error.lang
./mini compile examples/capture_error.lang -o out.s

完成扩展后，三条命令都应明确指出需要捕获 x。最后把下面两个程序分别保存到 practice.lang：

1

((lambda x ((lambda y (+ x y)) 2)) 40)

1

(lambda x (+ x missing))

前者应指出内层函数需要捕获 x，后者应指出 missing 从未定义。能区分这两种错误，才说明分析同时理解了嵌套作用域和第四章的能力边界。