第五章：函数怎样调用自己

本节阅读量:

第四章已经让函数可以作为值创建、保存和调用。不过，下面这个看起来很自然的写法仍然不能工作：

1
2
3
4
5
6


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

问题不在 call，而在名字 sum 的作用域。普通 let 会先求值右边的 lambda，然后才把结果绑定到 sum。因此，lambda 的函数体并不处在 sum 的绑定范围内。真正调用函数并执行到 (sum ...) 时，解释器只能报告：

1

error: undefined variable: sum

这正是本章要解决的核心困难：怎样让一个函数在自己的函数体里找到自己？

用 `letrec` 建立自引用

第五章加入专门的递归函数绑定 letrec：

1
2
3
4
5


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

这段程序保存在 examples/recursive_sum.lang。letrec 创建一个参数为 n 的函数，把它绑定到 sum，并且让这个绑定同时出现在两个地方：

1
2


递归函数的函数体里    (sum (sub1 n)) 可以再次找到同一个函数
letrec 的 body 里     (sum 5) 可以发起第一次调用

sub1 是本章同时加入的一个小型辅助表达式。它把一个整数减一，让递归参数逐步靠近停止条件 n == 0：

1
2
3
4
5
6


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

这里真正的新概念是递归绑定；sub1 只是让示例不必提前加入一整套减法语法。

两条路线仍然一起前进

本章继续维护解释器和编译器两条路线：

1
2


源码 -> AST -> 解释器 -> 值
源码 -> AST -> IR -> x86-64 AT&T 汇编

同一个 letrec 在不同层次有不同的落点：

1
2
3
4


源语言       函数名在函数体里指向函数自己
解释器       函数值记录 self name，调用时建立 name -> callee
IR           函数体取得指向自身函数标签的值
汇编         call 再次进入同一个函数标签，并建立新栈帧

递归不是一种新的机器指令。机器仍然只会执行第四章已经见过的 call 和 ret；变化在于，被调用的地址又指回当前这段函数代码。

先运行贯穿示例

进入第五章代码快照：

1
2
3
4


cd code/05_recursion
make
./mini run examples/recursive_sum.lang
./mini run examples/countdown.lang

两条命令依次输出：

再观察 recursive_sum.lang 的 AST：

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)))

这一行虽然长，但最外层只有一个新的 LetRec 节点。它依次保存函数名 sum、参数名 n、递归函数体和使用该函数的 body。

最后先看一眼 IR：

1

./mini ir examples/recursive_sum.lang

此时不必理解所有临时变量，只观察下面的骨架：

1
2
3
4
5
6
7
8
9


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

主程序中的 f.0 和函数体中的 sum0 都指向 lambda0。前者发起第一次调用，后者让已经进入 lambda0 的函数再次调用自己。IR 一节会完整解释为什么需要这两个名字。

建议的学习顺序

这一章可以分成两个阶段：

1
2
3


00—04    先理解普通 let 为什么不够、letrec 的作用域和解释器自绑定
05—06    再跟踪自引用怎样变成函数标签、call 和一层层栈帧
07—09    明确与闭包和尾调用优化的边界，并用练习完成自检

第一遍阅读时，先抓住“函数体得到自己的名字”即可。栈帧大小、临时变量编号和具体寄存器可以留到后半章。

本章改动落在哪里

1
2
3
4
5


src/front/ast.h/.cpp          Sub1Expr 和 LetRecExpr
src/front/parser.cpp          sub1 与 letrec 的特殊形式分支
src/interp/interpreter.cpp    数字减一和递归函数的自绑定环境
src/compile/ir.h/.cpp         sub1 操作和递归函数 lowering
src/compile/assembly.cpp      subq 与已有间接 call 的递归使用

整数、负整数、加法、变量、let、shadowing、eq?、if、普通函数值和调用都继续保留。第四章末尾的 cin、cout 只是一次独立的 C++ runtime 联调实验，已经完成了它的教学任务；第五章回到课程主线，不继承这两个 primitive。

这一章刻意停在哪里

第五章只实现一个具名、单参数函数的自递归：

1

(letrec name parameter function-body body)

它还不支持相互递归、普通值的递归绑定、尾调用优化，也不能让函数捕获任意外层变量。第六章会先加入 record 和堆对象，第七章再正式解决闭包捕获。

读完本章后，你应该能够说明：

普通 let + lambda 为什么不能直接定义具名递归函数。
letrec 的函数名在哪些表达式中可见。
解释器为什么让函数值记录 self name，再在每次调用时建立自绑定。
IR 为什么在函数体里再次取得同一个函数标签的地址。
一次递归 call 为什么会增加一层栈帧，以及结果怎样逐层返回。

4.10 可选收尾：从 mini 调用 C++ runtime

5.1 语言：给函数一个能看见自己的名字

本节目录