解释器：每次调用都把函数自己带进去

本节阅读量:

前一章的普通函数在调用时只需要一个参数绑定：

1

x -> argument

递归函数还要多一个绑定。以 sum 为例，每次进入函数体时都必须同时看见：

1
2


sum -> 当前正在调用的函数值
n   -> 本次调用的参数值

第二行让函数处理这一次的参数，第一行让函数体里的 (sum ...) 能再次找到同一个函数。第五章解释器真正增加的，就是这条受限制的自绑定。

先运行贯穿示例

本节继续使用：

1
2
3
4
5


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

运行解释器：

1
2
3


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

结果是：

1

15

求值过程可以先压缩成：

1
2
3
4
5
6
7
8


sum(5)
5 + sum(4)
5 + 4 + sum(3)
5 + 4 + 3 + sum(2)
5 + 4 + 3 + 2 + sum(1)
5 + 4 + 3 + 2 + 1 + sum(0)
5 + 4 + 3 + 2 + 1 + 0
15

递归调用不断建立新的调用环境；到达 n == 0 后，结果才沿调用链逐层返回。

`sub1` 仍然先求值子表达式

sub1 只是本章用来让参数逐步靠近 0 的辅助操作。它与加法一样，先递归求出子表达式，再检查结果是不是数字：

1
2
3
4
5


case ExprKind::sub1: {
    const auto& sub1_expr = static_cast<const Sub1Expr&>(expr);
    long value = expect_number(eval_expr(*sub1_expr.expr, env), "sub1");
    return Value::make_number(value - 1);
}

因此：

1

(sub1 43)

得到 42，而把函数值交给 sub1 会由解释器报告 sub1 expected a number。可以单独验证：

1

./mini run examples/sub1.lang

函数值只多记一个递归名字

第四章的 Function 保存参数名和函数体。第五章在此基础上增加 self_name：

1
2
3
4
5


struct Function {
    std::string param;
    const Expr* body;
    std::string self_name;
};

三个字段的含义分别是：

字段	保存的内容	什么时候使用
`param`	参数名，例如 `n`	调用时绑定 argument
`body`	函数体 AST 的借用指针	调用时求值函数体
`self_name`	递归名字，例如 `sum`	调用递归函数时建立自绑定

普通 (lambda x body) 的 self_name 保持为空，所以普通函数的行为没有改变。letrec 创建的函数才会填写这个字段。

这里没有保存定义处的整个环境。self_name 只说明“调用时要把当前函数值绑定到哪个名字”，不能让函数读取任意外层变量。这正是第五章与后续闭包能力之间的边界。

body 仍然是不拥有 AST 的裸指针。AST 由 CLI 中解析得到的 std::unique_ptr<Expr> 拥有，并且在整次 eval() 期间一直存在，所以函数调用时这个指针仍然有效。

创建 `letrec` 函数时不执行函数体

解释器的 letrec 分支是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


case ExprKind::letrec: {
    const auto& letrec_expr = static_cast<const LetRecExpr&>(expr);
    auto function = std::make_shared<Function>();
    function->param = letrec_expr.param;
    function->body = letrec_expr.function_body.get();
    function->self_name = letrec_expr.name;
    Value function_value = Value::make_function(function);
    env.push_back({letrec_expr.name, function_value});
    Value result = eval_expr(*letrec_expr.body, env);
    env.pop_back();
    return result;
}

按执行顺序看，它做了四件事：

1
2
3
4


1. 创建一个 Function，记录参数 n、函数体 AST 和递归名字 sum。
2. 把完整的 Function 包装成 Value。
3. 在当前环境中加入 sum -> function_value。
4. 求值 letrec 最后的 body，完成后移除绑定。

第三步让下面最后一行里的 sum 可见：

1
2
3


(letrec sum n
  function-body
  (sum 5))

此时 function-body 还没有执行。它和普通 lambda 的函数体一样，只有真正调用函数时才会求值。

注意，Function 没有保存一个指向自己的 shared_ptr。它只保存字符串 self_name，真正的 sum -> function_value 会在调用时临时建立。这样既能递归，也不会产生“函数值通过环境永久拥有自己”的引用环。

调用时建立全新的自绑定环境

函数调用仍然先求 callee，再求 argument。变化发生在 call_env 的建立过程：

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


case ExprKind::call: {
    const auto& call_expr = static_cast<const CallExpr&>(expr);
    Value callee = eval_expr(*call_expr.callee, env);
    if (callee.kind != Value::Kind::function) {
        throw std::runtime_error("function call expected a function");
    }

    Value argument = eval_expr(*call_expr.argument, env);
    Env call_env;
    if (!callee.function_value->self_name.empty()) {
        call_env.push_back({callee.function_value->self_name, callee});
    }
    call_env.push_back({callee.function_value->param, argument});
    return eval_expr(*callee.function_value->body, call_env);
}

若 callee 是普通 lambda，self_name 为空，call_env 仍然只有参数绑定。若 callee 来自 letrec，解释器先加入自绑定，再加入参数：

1
2


sum -> callee
n   -> argument

环境查找从后往前进行，因此参数是当前函数体中最内层的名字。函数体内部的 let 还可以继续压入更内层的绑定，求值完成后再弹出。

最重要的一行是：

1

Env call_env;

它创建的是全新环境，而不是复制调用点的 env。随后加入的也只有递归函数自身和参数。于是第五章的名字边界可以准确写成：

位置	能看到的名字
`letrec` 的 `body`	原来的外层绑定，加上递归名字
递归函数刚开始执行时	递归名字和本次参数
函数体内部的 `let`	上一行的名字，再加内部绑定
递归函数体	不能直接看到 `letrec` 外面的其他名字

跟踪 `sum(3)` 的四份调用环境

把贯穿示例暂时想成 (sum 3)。第一次调用建立：

1
2
3


call_env A
sum -> <同一个函数值>
n   -> 3

条件为假，求值 (sum (sub1 n))。callee 查到同一个函数值，argument 得到 2，随后建立另一份环境：

1
2
3


call_env B
sum -> <同一个函数值>
n   -> 2

继续调用会得到：

1
2


call_env C: sum -> <同一个函数值>, n -> 1
call_env D: sum -> <同一个函数值>, n -> 0

这四份环境同时处在尚未完成的 C++ 递归求值调用中，但它们彼此独立。call_env D 从基例得到 0 后，结果按相反顺序返回：

返回到哪次调用	当前环境里的 `n`	计算	返回值
`sum(1)`	1	`1 + 0`	1
`sum(2)`	2	`2 + 1`	3
`sum(3)`	3	`3 + 3`	6

每一层都从自己的环境读取 n，所以不会被下一层的参数覆盖。

函数换了变量名，递归能力仍然存在

递归信息属于函数值，而不是调用点使用的变量名。下面的示例让 letrec 返回函数值，再把它绑定为 f：

1
2
3
4
5


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

运行：

1

./mini run examples/recursive_function_value.lang

仍然得到：

1

15

外层调用使用的名字是 f，但函数值中的 self_name 仍是 sum。进入函数体时，解释器因此建立 sum -> callee，递归调用不受函数值被转存或改名影响。

自绑定不是普通环境捕获

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

1
2
3
4
5
6


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

adddown 能看到自己和参数 n，却没有保存外层的 base。运行：

1

./mini run examples/recursive_capture_error.lang

会得到：

1

error: undefined variable: base

这不是递归绑定失效，而是程序要求了另一种能力：保存函数定义位置的普通外层绑定。第五章只解决“函数怎样找到自己”，不会把 call_env 扩大为调用点环境，也不会让 Function 保存任意外层环境。

到这里，解释器侧的变化可以压缩为：

1
2
3


letrec 创建函数值  -> 记录 self_name，并在 letrec body 中绑定函数
调用递归函数       -> 新环境 = self 绑定 + parameter 绑定
执行函数体         -> 递归名字再次得到同一个 callee

5.3 Parser：在括号 head 位置识别 `sub1` 和 `letrec`

5.5 IR：两个函数值临时指向同一个入口

本节目录