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

第五章在已有语言上增加两个表达式：

1
2

(sub1 expr)
(letrec function-name parameter function-body body)

sub1 完成一次数字减一。letrec 创建并绑定一个递归函数，是本章真正的语义重点。

sub1 让参数靠近停止条件

最小例子是：

1

(sub1 5)

结果为 4。它的求值顺序只有两步：

1
2

1. 先求值内部的 expr
2. 确认结果是数字，再减一

所以嵌套表达式也可以作为操作数：

1
2

(sub1 (+ 2 3))
(sub1 (sub1 5))

它们的结果依次是 4 和 3。

sub1 并不保证结果非负：(sub1 0) 是 -1，(sub1 -2) 是 -3。本章的递归示例使用非负参数，是因为它们只用 0 作为停止条件；如果从负数开始不断执行 sub1，参数会离 0 越来越远。

sub1 只接受数字。解释器执行下面的程序时会报告类型错误：

1

(sub1 (lambda x x))

1

error: sub1 expected a number

和第四章一样，当前编译器还没有完整的运行时类型检查。编译路径仍只用值种类正确的程序进行验证。

为什么普通 let 不能完成这件事

先回顾普通 let 的作用域：

1

(let name value body)

它会先在旧环境中求值 value，再把 name 绑定到结果，最后在扩展后的环境中求值 body。因此 name 只在 body 中可见，不在自己的 value 中可见：

1
2
3

(let sum (lambda n ...sum...) (sum 5))
     └──────── value ───────┘ └ body ┘
              看不到 sum       看得到 sum

第四章的普通函数调用又只给函数体提供参数和函数体内部的绑定。于是下面的 sum 在真正执行函数体时没有来源：

1
2
3
4
5
6

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

外层 (sum 5) 可以找到 let 绑定的函数值，第一次调用能够发生；进入函数体后，递归位置的 sum 却查找失败。let 的规则不能仅靠改变求值先后顺序随意修补，因为普通 let 还要保持“右边不在新绑定作用域内”的既有语义。

因此，本章使用一个形状和边界都更明确的新构造 letrec。

letrec 的四个部分

贯穿示例是：

1
2
3
4
5

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

去掉排版后，letrec 的结构始终是：

1
2
3
4
5
6

(letrec function-name parameter function-body body)
        ─────┬──── ────┬──── ─────┬───── ──┬─
             │          │           │        └─ 使用递归函数的表达式
             │          │           └────────── 每次调用时执行的函数体
             │          └────────────────────── 接收实参的参数名
             └───────────────────────────────── 递归函数自己的名字

在示例中：

这里不再额外写 (lambda n ...)。letrec 本身已经表示“创建一个参数为 n、函数体为 function-body 的函数，并把它递归绑定到 function-name”。

letrec 是一个表达式，不是顶层声明。它的结果就是最后那个 body 的求值结果。在贯穿示例里，body 是 (sum 5)，所以整个 letrec 的结果是 15。

精确的求值顺序

求值一个 letrec 时，可以按下面四步理解：

1
2
3
4

1. 创建记录 parameter、function-body 和 function-name 的函数值；暂不执行 function-body
2. 在当前环境中加入 function-name -> 这个函数值
3. 在扩展后的当前环境中求值 letrec 的 body
4. body 结束后移除当前环境中的 function-name，返回 body 的结果

第一步记录的 function-name 会在每次调用时用来建立 function-name -> 当前 callee，第二步则让 letrec 的 body 能发起第一次调用。两处最终都指向同一个函数值，但函数值不会通过一份环境强引用自己。

函数体不会在创建时执行。下面的程序会直接得到 42，不会陷入循环：

1
2
3

(letrec loop n
    (loop n)
    42)

(loop n) 属于 function-body；由于 letrec 的 body 只是整数 42，函数从未被调用。

当一次调用真的发生时，第四章的调用顺序仍然有效：先求值 callee，再求值 argument，然后建立调用环境并执行函数体。区别是调用 letrec 函数时，会根据它记录的递归名字多建立一条自绑定：

1
2

sum -> 当前递归函数
n   -> 本次调用的实参

下一次 (sum (sub1 n)) 会取得同一个函数值，但用更小的实参建立一份新的调用环境。

函数名和参数各自在哪里可见

letrec 的作用域可以用一张表固定下来：

最后一行是第五章的重要边界。例如：

1
2
3
4
5
6

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

letrec 的 body 可以处在 base 的作用域里，但递归函数体不能捕获 base。支持这种写法需要函数保存定义位置的任意外层变量，也就是第七章的闭包。

函数体内部新建的普通 let 仍然可用：

1
2
3
4
5

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

这里的 next 只属于当前这一层调用。每次递归调用都会得到自己的参数环境和内部 let 绑定。

同名时仍然遵守 shadowing

当前 parser 允许函数名和参数名使用相同拼写：

1
2
3

(letrec f f
    f
    (f 1))

调用时参数绑定后加入环境，因此函数体中的参数 f 会遮蔽递归函数名 f。上面函数体的结果是实参 1，不是函数值。为了让代码含义清楚，并确保递归位置能找到函数自己，本章示例始终使用不同的函数名和参数名。

普通 let 也可以在更小的作用域里暂时遮蔽递归函数名。这与第二章的 shadowing 规则相同，不是递归的特殊规则。

递归函数仍然是一等值

letrec 的 body 不一定立刻调用函数，也可以直接返回函数值：

1
2
3
4
5

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

内部 letrec 的结果是函数 down。即使求值已经离开 letrec 的 body，这个函数值仍然记录着递归名字 down；外层用名字 saved 调用它时，解释器会重新建立 down -> 当前 callee，所以递归仍能继续。整个程序的结果是 42。

这说明 letrec 没有加入一种只能在声明位置使用的特殊函数。它创建的仍然是第四章已经认识的一等函数值，只是这个函数值额外记住了调用时要使用的 self name。

停止条件决定递归是否结束

以 (sum 3) 为例，每次调用都有两个可能的分支：

1
2
3

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

1
2

n == 0    停止递归，直接返回 0
n != 0    用 n - 1 再次调用 sum，等待结果后完成加法

只有被选中的 if 分支会执行，所以到 n == 0 时，递归分支不会再求值。若忘记停止条件，或者参数始终无法到达停止条件，程序会不断建立新的调用栈帧，最终耗尽栈空间。本章没有尾调用优化，也没有为无限递归提供额外保护。

主线语法

在第四章主线语法上加入 sub1 和 letrec：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

expr := integer
      | identifier
      | (+ expr expr)
      | (sub1 expr)
      | (let identifier expr expr)
      | (letrec identifier identifier expr expr)
      | (eq? expr expr)
      | (if expr expr expr)
      | (lambda identifier expr)
      | (expr expr)

两个连续的 identifier 分别是递归函数名和参数名。普通 identifier 仍然只能由一个或多个英文字母组成。sub1 中含有数字，只作为括号 head 位置的固定特殊形式识别，不会扩大普通变量名规则。

第五章只支持一个函数的单参数自递归，不支持：

• 一次绑定多个相互递归的函数。
• 把普通值递归绑定给自己。
• 捕获函数定义位置的任意外层变量。
• 尾调用优化。

这些边界让本章只回答一个问题：已有的一等函数值，怎样获得一条稳定的自引用。