边界：会调用自己，还不是闭包

本节阅读量:

letrec 只比第四章多解决一个名字问题：函数体能够通过固定名字再次取得自己。

1
2


第四章的函数环境       parameter + 函数体内部的 let
第五章的递归函数环境   self name + parameter + 函数体内部的 let

这个变化足以写出递归，却没有让函数自动看到创建位置的全部环境。本节把这条界线说清楚，也区分“语言不支持什么”和“本章暂时怎样观察结果”。

自绑定不等于捕获外层环境

下面的程序属于第五章：

1
2
3
4
5


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

sum 的函数体只使用两类名字：自己的名字 sum 和参数 n。调用环境可以明确地建立这两个绑定。

下面的程序则越过了本章边界：

1
2
3
4
5
6


(let base 10
    (letrec adddown n
        (if (eq? n 0)
            base
            (+ 1 (adddown (sub1 n))))
        (adddown 5)))

它保存在 examples/recursive_capture_error.lang。base 既不是递归函数名，也不是参数或函数体内部的 let 名字；它来自创建 adddown 时的外层环境。

1
2


cd code/05_recursion
./mini run examples/recursive_capture_error.lang

解释器会报告：

1

error: undefined variable: base

IR lowering 也使用一份只含 self 和 parameter 的新环境，因此同样拒绝它：

1

./mini ir examples/recursive_capture_error.lang

1

error: undefined variable: base

要让 adddown 记住 base，函数值必须同时携带创建时需要的外层值。第七章会把函数值从单独的代码入口扩展成闭包；第五章不提前实现这件事。

“不捕获外层环境”并不表示递归函数只能在 letrec 的 body 里立即调用。下面的程序先让 sum 作为 letrec 的结果离开，再把它绑定到 f：

1
2
3
4
5
6
7


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

它保存在 examples/recursive_function_value.lang：

1

./mini run examples/recursive_function_value.lang

输出仍是：

1

15

原因不是函数偷偷保存了整个外层环境，而是递归函数值自身记录了 self_name = "sum"。无论它后来通过 sum、f，还是另一个函数的参数到达调用点，解释器都会在调用时把当前 callee 重新绑定给 sum。编译器中的函数地址也仍然指向同一个 .Llambda0。

因此本章支持的是：

1
2
3


递归函数作为值流动     支持
递归函数调用自己       支持
函数读取任意外层名字   不支持

本章语法是：

1

(letrec name parameter function-body body)

它一次只创建一个函数，所以没有同时声明多个函数的语法，也不支持 even 与 odd 互相调用这样的相互递归。

普通 let 的 value 也仍然看不到它刚要绑定的名字：

1
2


(let loop (lambda n (loop n))
    (loop 1))

这里函数体中的 loop 不是 lambda 的参数或内部名字，因此仍然未定义。需要自绑定时，应明确使用 letrec，不要把普通 let 当成递归声明。

嵌套 letrec 当然可以存在，但内层函数不会因此自动捕获外层递归函数。每个递归函数都只有自己的 self、parameter 和内部绑定。

建议始终给函数名和参数使用不同名字：

1

(letrec sum n ...)

当前语法并未额外禁止 (letrec f f ...)。调用环境先放入 self 绑定，再放入参数绑定，所以同名参数会遮蔽函数名；函数体里的 f 将得到实参，而不是递归函数值。这个结果遵守项目一直使用的“后加入的同名绑定优先”规则，但几乎不会是递归程序想表达的意思。

解释器和生成代码都不会证明递归一定结束。一个正常的递归通常需要三部分：

1
2
3


基例       例如 n 等于 0 时直接返回
递归步     例如用 sub1 让 n 减少
递归调用   用更接近基例的参数再次调用自己

examples/recursive_sum.lang 对非负整数满足这个结构。若把入口参数换成负数，sub1 会让它继续远离零；若完全忘记基例，程序也会一直递归：

1

(letrec loop n (loop n) (loop 1))

不要实际用很深的输入反复试这个程序。本章没有递归深度限制，也没有把递归改写成循环；每次调用都会再占用一个机器栈帧，最终可能因栈耗尽而异常结束。

countdown.lang 的递归分支没有在调用结果上继续做加法：

1
2
3
4
5


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

递归调用处在函数体的尾位置，但第五章仍然为它生成普通 call *%rcx。因此 down 3、down 2、down 1 和 down 0 的栈帧会同时存在，等基例返回后再逐层 retq。

尾调用优化会改变这种栈行为，不属于本章标准实现。这里用 countdown 先帮助你认出“尾位置”与“已经做了尾调用优化”不是一回事；章末进阶选做练习再把范围严格限制为直接自尾调用，尝试把它变成当前 frame 内的跳转。

源语言仍然是动态类型。解释器会在运行时检查：

1
2
3


sub1 的操作数     必须是 number
+ 和 eq? 的操作数 必须是 number
call 的 callee    必须是 function

例如把一个普通函数值交给 sub1，mini run 会报告 sub1 expected a number。但是本章编译器仍用一个裸机器字同时表示整数和函数地址，没有加入运行时 tag，也没有在汇编里复制这些检查。

所以编译路径继续只承诺这样的程序：名字符合本章作用域；实际执行到的算术收到整数；实际执行到的 call 收到函数；递归能够在机器栈耗尽前结束。第六章引入统一的 tagged value 和堆对象后，机器层才开始具备区分值种类的表示基础。

解释器在函数真正被调用时才执行函数体；编译器则必须在生成代码时 lowering 函数体。于是一个从未调用的越界函数会表现出不同的报错时机：

1
2


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

mini run 会输出 42，因为 unused 的函数体没有执行。mini ir 和 mini compile 会在 lowering base 时报告未定义变量。两条路径没有给这个程序不同的闭包语义，只是在不同阶段遇到了同一个不受支持的自由变量。

第四章末尾的 (cin)、(cout expr) 和 C++ runtime 链接只是一次独立的 ABI 实验。第五章回到语言主线，代码快照不再包含这两个 primitive；递归示例继续使用 mini run 或链接后的小整数退出状态观察结果。

这不是功能回退：整数、负整数、加法、变量、let、条件、函数值和调用都继续保留；只有明确约定为第四章专属的 I/O 实验没有继承。

5.6 汇编：调用向下展开，结果逐层返回

5.8 本章总结与验收清单

本节目录