Lambda 提升与传递环境参数

闭包理路程序语言闭包Programming-language closure · Function closure · Lexical closure将函数代码与其定义位置的词法环境配对而成的运行时函数值。在函数值里带一个定义环境；闭包转换把它落实为记录，调用时递交那份记录；本页提升让每个已知调用点直接传入所需值。只把函数文本搬到顶层不够：f 虽然自己不读 x，却可能调用读取 x 的 g，于是 f 必须把 x 接进来才能继续传下去。

这里传递的是值。如果值是单元地址，各函数接到的是同一个地址，不是把单元内容复制成多个私有整数。因此该变换与共享状态相容，但不能跳过别名证明。

沿调用链传入未直接读取的变量 ​

outer(x) =
  letrec f(n) = if n==0 then 0 else g(n-1)
         g(n) = if n==0 then x else h(n-1)
         h(n) = if n==0 then 1 else f(n-1)
  in h(3)

x 是唯一外层变量，D(f)=∅, D(g)={x}, D(h)=∅，调用边为 f→g、g→h、h→f。采用同步轮次，第一轮把 x 传给 f，第二轮传给 h，第三轮不再改变，得到三个 Need 集合都为 {x}。

f_lift(xf,n) = if n==0 then 0 else g_lift(xf,n-1)
g_lift(xg,n) = if n==0 then xg else h_lift(xg,n-1)
h_lift(xh,n) = if n==0 then 1 else f_lift(xh,n-1)
outer(x) = h_lift(x,3)

outer(7) 的执行是 h(7,3)→f(7,2)→g(7,1)→h(7,0)→1；outer(7) 若改成入口 h(2)，则 h(7,2)→f(7,1)→g(7,0)→7。两个入口分别经过不读取 x 和确实读取 x 的基例，防止只测输出 1 就误以为可以把全部 x 参数删掉。

如果仅用 D(f) 而没有闭合 Need，f 被提升后没有 xf，生成 g_lift(?,n-1) 时就无值可传。错误不是“性能差一点”，而是输出程序含未解释的自由变量。对循环 f→g→h→f 只扫描一遍，也可能因遍历顺序而漏掉 h 的需求。

返回函数是当前准入边界 ​

make(x)=fun y -> x+y 返回的是携带 x 的函数值。把内层改成 add_lift(x,y) 后，make(4) 不能只返回 add_lift 的代码地址；未来调用者只给 y，代码地址无法区分 make(4) 与 make(9)。可以返回“代码、已供 x”的部分应用记录，但它已经重新承担闭包转换理路闭包转换Closure conversion · 闭包变换把词法捕获改写为显式环境参数，同时保留遮蔽、求值顺序与共享可变单元。的环境责任。本页直接调用算法因此拒绝这个输入，而不是把缺失环境隐藏起来。

另设外层 x=ref(4)，f、g 都需要这个引用。调用 f 写 x=7 后再调用 g 读取，必须得到 7。额外参数传同一位置保持共享；若每个入口以 ref(!x) 重建私有单元，就会破坏源行为。改变函数位置不改变引用身份。

正确性与成本分开核算 ​

闭合算法的不变量是 D(f) 始终包含在 Need(f) 中，Need 中每个变量都沿某条调用路径来自某个函数的直接需求。终点对每条 f→g 都有 Need(g)⊆Need(f)，所以 f 的提升体能提供每次调用所需参数。这既证明输出闭合，也说明得到的是最小需求解：任何满足方程的候选必须包含每轮加入的项。

行为证明令每次提升调用的额外参数与源函数定义环境对应。基例读到相同值；普通实参仍按源顺序求值；递归步把相同额外值传给被调用者，从而保持这一关系。对有限调用推导归纳得到相同结果与存储效果。无穷调用需小步模拟；本变换没有减少或新增源级递归调用，但并不因此承诺空间成本相同。

设 f 个函数、v 个候选外层变量、e 条调用边，若集合为 v 位布尔向量且每轮扫描所有边，每轮还要复制 f 份集合并比较新旧解，因此为 $O((f+e)v)$；至多 fv 次严格增长轮加一次稳定轮，保守上界为 $O((fv+1)(f+e)v)$，空间 $O(fv+e)$，此处 v≥1；v=0 时只须 $O(f+e)$ 做一次空需求检查。这是本页朴素实现的界，不是优化 lambda lifting 的最优复杂度。按变化的变量对使用逆边工作表可改进传播，但输出的额外参数总数和调用处实参总数仍必须计费。

运行时一个调用多传 k 个值，需要 $O(k)$ 参数搬移；闭包转换可能只递交一个环境指针、在体内按需读取。额外实参还可能超出寄存器容量进入栈，提升也可能延长某些值的活动区间。因此“没有环境记录”不推出总内存更小，更不推出总时间更快。[2]

迁移任务：增加 q(n)=f(n)+z，z 是第二个外层变量，且没有函数调用 q。答案为 Need(q)={x,z}，原 f、g、h 仍只需 x。若再加 h→q，则整个强连通分量最终都需要 x、z。按同步轮次写出新增项即可验证传播方向，不能把“调用 q”误解成 q 要继承调用者全部变量。

该页内的函数组与两组输入构成独立短任务；前端返回闭包主例应继续采用旧闭包转换，不强行套本页受限提升。