章节目录

自由变量：只带走以后真正需要的名字

本节阅读量:

解释器和编译器创建闭包前，都要回答同一个问题：函数体以后还会读取哪些外层绑定？

这些名字叫自由变量。第七章把自由变量分析放在 front/free_vars.*，让解释器和 IR lowering 共享同一条判断规则。

自由总是相对于某个函数而言

考虑：

1

(lambda y (+ x y))

相对于这个 lambda：

1
2

y  由参数绑定，不自由
x  在函数体中使用，但没有在函数内绑定，自由

所以结果是：

1

[x]

分析不是给整个程序贴一份永久标签。同一个名字在不同 lambda 中可能扮演不同角色。

算法携带两份有序列表

collect 沿 AST 递归时维护：

1
2

bound   当前表达式已经能在内部找到的源码名字
result  已发现的自由变量，按首次出现顺序保存

遇到变量节点时：

1
2
3
4
5
6
7

case ExprKind::variable: {
    const auto& var = static_cast<const VarExpr&>(expr);
    if (!contains(bound, var.name)) {
        add_unique(result, var.name);
    }
    return;
}

add_unique 不使用无序集合，因为捕获顺序最后会变成对象槽位顺序：

1
2
3
4
5
6

void add_unique(std::vector<std::string>& names,
                const std::string& name) {
    if (!contains(names, name)) {
        names.push_back(name);
    }
}

同一个名字只出现一次，但第一次遇到的位置不会丢失。

每种 AST 节点都必须有规则

分析 pass 使用显式 ExprKind + switch。第七章完整表达式集合的递归规则是：

表达式 怎样分析
integer 不产生自由变量
variable 不在 bound 时加入 result
+、eq? 按源码顺序分析左右 operand
sub1 分析子表达式
if 依次分析 condition、then、else
call 先分析 callee，再分析 argument
let value 使用旧 bound；body 临时加入绑定名
letrec 按递归绑定规则分别分析 function body 和 body
lambda 分析 body 时临时加入参数名
record 从左到右分析所有字段
record? 分析唯一子表达式
size 分析 record 表达式
get 分析 record 表达式；index 是字面量元数据

把第六章节点列全很重要，但不需要重讲 record 的语义。自由变量分析只关心哪些子树可能出现变量。

let 的名字只绑定 body

看这个函数：

1
2
3

(lambda x
  (let y 1
    (+ x y)))

分析 let 的 value 时，y 还没有进入作用域；分析 body 时才加入 y：

1
2
3
4

collect(*let.value, bound, result);
bound.push_back(let.name);
collect(*let.body, bound, result);
bound.pop_back();

参数 x 和局部变量 y 都能在函数内部找到，因此捕获列表为空。

这个规则也能正确处理 value 中引用外层同名变量的情况：

1
2
3
4
5

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

内层 let 的 value 里的 y 仍指向外层 y，因此该 lambda 要捕获它。进入 inner body 后，新 y 才遮蔽旧绑定。程序结果是 42。

shadowing 不能靠字符串猜

自由变量分析使用源码名字判断作用域，lowering 随后通过当前环境把名字解析成唯一 operand。

例如：

1
2
3
4

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

分析 lambda 得到源码名字 [x]。创建 closure 时，lowering 所在环境把它解析成外层的 x0：

1
2

x0 = 40
f.0 = closure lambda0 [x0]

后面值为 100 的另一个 x 会得到不同 IR 名字，不可能替换已经写进 closure op 的 x0。

嵌套 lambda 必须让需要的名字向外传播

下面的程序是理解自由变量分析最容易遗漏的一步：

1
2
3
4
5

(let x 40
  (((lambda y
      (lambda z (+ x (+ y z))))
    1)
   1))

对内层 lambda 来说，自由变量是 [x, y]。

对外层 lambda 来说，y 是自己的参数，不自由；但 x 仍然来自外层，因此外层也必须捕获 [x]。原因不是外层函数立即计算 x，而是它以后创建内层 closure 时需要拿到 x 的 Value。

IR 把这条传递关系写得很清楚：

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

x0 = 40
f.0 = closure lambda0 [x0]
check-closure f.0
t.2 = call f.0 1
check-closure t.2
t.3 = call t.2 1
return t.3
lambda1(z5, self: -, captures: [x3, y4]):
  t.0 = y4 + z5
  t.1 = x3 + t.0
  return t.1
end lambda1
lambda0(y2, self: -, captures: [x1]):
  f.1 = closure lambda1 [x1, y2]
  return f.1
end lambda0

若分析嵌套 lambda 时简单停止递归，外层的捕获列表会错误地变成空，运行到 closure lambda1 [x1, y2] 时也就找不到 x1。

多次使用只捕获一次

下面的函数两次读取 x：

1
2

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

第一次遇到 x 时把它加入结果，第二次由 add_unique 去重，所以捕获列表是 [x]，不是 [x, x]。两个变量引用在函数体里都会读取同一个捕获槽。

首次出现顺序是一份内部契约

运行：

1
2

cd code/07_closures
./mini ir examples/multiple_captures.lang

会看到：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

x0 = 10
y1 = 20
f.0 = closure lambda0 [x0, y1]
check-closure f.0
t.2 = call f.0 12
return t.2
lambda0(z4, self: -, captures: [x2, y3]):
  t.0 = y3 + z4
  t.1 = x2 + t.0
  return t.1
end lambda0

创建位置的 [x0, y1] 与函数体声明的 [x2, y3] 一一对应：

1
2

capture 0  x0 -> x2
capture 1  y1 -> y3

以后汇编 emitter 会把它们放在 offset 16、24。只要分析结果、closure op 和 IrFunction::captures 使用同一顺序，源码名字怎样 alpha-rename 都不会造成混淆。

letrec 的 self 不是自由变量

对于：

1
2
3
4
5
6

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

分析递归函数体时，从这两个名字已经绑定开始：

1
2

adddown  self name
n        parameter

因此结果只有 [base]。接口直接把这条规则写出来：

1
2
3
4
5
6

std::vector<std::string> free_vars(const LetRecExpr& letrec) {
    std::vector<std::string> bound{letrec.name, letrec.param};
    std::vector<std::string> result;
    collect(*letrec.function_body, bound, result);
    return result;
}

self 不进入 payload 捕获列表。IR 用单独的 IrFunction::self 保存函数体里的递归局部名；机器调用时再把 %rdi 中的实际 closure Value 写入这个局部槽。

这比“让 closure 捕获自己”更直接，也避免创建自引用 payload。

letrec 出现在其他函数内部时

通用 collect 还要处理一个 letrec 作为普通子表达式的情况。作用域边界是：

  • function body 中，函数名和参数名都已绑定；
  • letrec body 中，只有函数名由这次 letrec 绑定；
  • 参数名不应泄漏到 letrec body。

代码用成对的 push_back 和 pop_back 表达这条边界：

1
2
3
4
5
6

bound.push_back(letrec.name);
bound.push_back(letrec.param);
collect(*letrec.function_body, bound, result);
bound.pop_back();
collect(*letrec.body, bound, result);
bound.pop_back();

这也解释了为什么环境用可保留顺序的列表，而不是只有“存在或不存在”信息的全局集合。

两个消费者使用同一分析结果

自由变量 pass 同时服务两条实现路线：

1
2
3
4
5
6
7

解释器
  free_vars -> 从当前 Env 复制这些名字对应的 Value

编译器
  free_vars -> 从 lowering Env 解析这些名字对应的 Operand
            -> closure.fields
            -> IrFunction.captures

解释器不需要为了教学方便复制整份环境；它也只保存分析选中的名字。于是两条路线都清楚表达“闭包只留住真正需要的外层值”。

本节的验收问题

读到这里，可以先不看答案判断：

1
2
3

(let a 10
  (let b 20
    (lambda x (+ b (+ a (+ b x))))))

捕获列表应为 [b, a]，不是按字母排序的 [a, b]，也不是包含重复项的 [b, a, b]。下一节会把这些名字对应的 Value 真正放进解释器闭包。

7.1 语言：名字由定义位置决定

上一节

7.3 解释器：把自由变量放进函数值

下一节
本节目录