闭包返回以后：从显式环境到一次移动回收
这份任务只检查一个小程序，但要把它走到底：解释同名变量、翻译两个共享计数器、让创建者返回、暂停另一个调用、搬动对象，最后继续算出结果。只报“GC 后还有四个对象”不够，还要说明哪两个槽被更新、两个环境是否仍指向同一单元。
题目与模型
采用从左到右按值调用，绑定不可变，ref 创建显式可变单元。三元组是嵌套二元组的书写糖；代码地址位于静态区。源程序如下：
make(seed) =
let x = ref seed in
let inc = fun d -> (x := !x + d; !x) in
let peek = fun u -> !x in
(inc, peek)
let p = make(4) in
let a = fst p in
let b = snd p in
let x = 100 in
let unused = ref 999 in
let first = a(3) in
(first, b(0), x)关闭死分配消除，保留 unused 的分配，便于看到一个确定垃圾对象；过最后使用的普通指针可以不作为根。编译器在 inc 写入之后、返回之前插入一次不可观察的 gc_poll。这是唯一一次实际收集，make 的构造阶段有足够空间，且每次对象初始化都在不可收集的短区间完成。
堆字长为 8，对象头占 8 字节；Cell 的整数值不扫描，Env 的单指针扫描，Closure 只扫描 env，不扫描 code，Pair 两字段均扫描。from-space 为 [1000,1512)，to-space 为 [2000,2512)；每半 512 字节。以下地址均为十进制。
| 对象 | 类型 | 起址 | 大小 | 字段（收集前） |
|---|---|---|---|---|
| C | Cell | 1000 | 16 | value=7 |
| Ei | Env | 1016 | 16 | cell=1000 |
| A | Closure | 1032 | 24 | code=inc_code，env=1016 |
| Ep | Env | 1056 | 16 | cell=1000 |
| B | Closure | 1072 | 24 | code=peek_code，env=1056 |
| P | Pair | 1096 | 24 | first=1032，second=1072 |
| U | Cell | 1120 | 16 | value=999 |
调用约定采用教学 ABI：E 为环境参数，A0 为首实参，R 为结果；它们允许被调用改写。栈向低地址增长，call 压返回 PC，序言压旧 FP，再预留 32 字节；FP−8 保存 S，FP−16 是本题根槽。main 的 FP=8192、调用前 SP=8160；inc 的根保存及重载见后面的参考答案。
请先独立完成：
- 给两个 x 不同的绑定身份，列 inc、peek 的捕获项。写出显式环境参数 IR，并指出共享的是记录、地址还是整数副本
- 计算进入 inc 后的 FP、SP、返回地址槽、旧 FP 槽和两个根槽的绝对地址
- 在 inc.poll 找到全部根。解释为什么此时 P、A 可不作为根，而返回后的 b 仍要保留
- 按最外层到当前层的根顺序执行一次 Cheney 收集，列出全部转发及每轮 scan/free。收集后重新读取哪些位置，才能继续得到正确结果
- 删除 main 的根映射项，指出最早会坏在哪次读取。再给一个保留全部对象但破坏共享别名的错误收集变体
- 改用标记清扫时，哪些区间会空闲？若只使用本题已分配区间回收出的空闲块，能否立即容纳连续 48 字节的新对象
参考答案：名字与显式环境
make 内的绑定为 x₁，main 的整数绑定为 x₂。inc 与 peek 都只捕获 x₁ 的值，也就是同一个 Cell 的地址。它们可以有不同 Env，但 Ei.cell=Ep.cell=C。x₂ 不进入捕获集合；错误捕获它会改变词法含义。
make_code(E_unused, seed):
C = alloc Cell(seed)
Ei = alloc Env(C)
A = alloc Closure(inc_code, Ei)
Ep = alloc Env(C)
B = alloc Closure(peek_code, Ep)
return alloc Pair(A, B)
inc_code(E, d):
C_before = load E.cell
old = load C_before.value
store C_before.value = old + d
store [fp-16] = E
// C_before 和旧 E 在此后均不再使用
gc_poll(inc.poll)
E_after = load [fp-16]
C_after = load E_after.cell
return load C_after.value
peek_code(E, u):
return load E.cell.valuemain 调用 inc 前把 B 存在自己的 FP−16；返回后从该槽重载 B_after，再执行 B_after.code(B_after.env,0)。main 的旧 p、a 没有后续使用；执行 inc 需要的是静态代码与 Ei，不要求闭包对象 A 本身继续存活。
如果把 Cell 的整数复制到两个环境并各自更新，结果为 (7,4,100)；正确程序为 (7,7,100)。进一步调用另一组 make(4) 应得到独立单元，不能跨次创建混成同一状态。
参考答案：帧、根与可达对象
main 根槽为 8192−16=8176。call 将返回 PC main.after_inc 放到 8152，序言将旧 FP=8192 放到 8144；inc 新 FP=8144，预留 32 字节后 SP=8112，环境根槽为 8144−16=8128。
当前 inc.poll 映射给出槽 8128。保存的旧 FP 与返回 PC 帮助找到 main 的槽 8176。枚举完整帧链后按最外层到当前层排序，交给收集器的根序列是：
8176: B = 1072
8128: Ei = 1016从 B 到 Ep 再到 C，从 Ei 也到 C，所以存活集合为 {B,Ei,Ep,C}，24+16+16+16=72 字节。全部已分配 136 字节，差额 64。U 只含整数，A 和 P 已过最后使用；死槽中偶然残留的地址不应进入本题精确根表。
参考答案：一次搬家与恢复
根扫描首先将 B 复制到 2000、Ei 复制到 2024；两个根槽同时改写。此时 scan=2000，free=2040。
| 扫描 | 新复制或转发复用 | 扫描后 scan | free |
|---|---|---|---|
| B@2000 | Ep:1056→2040 | 2024 | 2056 |
| Ei@2024 | C:1000→2056 | 2040 | 2072 |
| Ep@2040 | 使用 C 已有转发2056 | 2056 | 2072 |
| C@2056 | 无指针字段 | 2072 | 2072 |
最终根值为 2000、2024；B.env=2040，Ei.cell=Ep.cell=2056，C.value=7。新分配指针 next=2072。旧 from-space 全部失效，而不只是未复制对象失效；旧活对象的旧地址也不能再解引用。
inc 从 8128 重新取得 Ei′，再取 C′，返回 7。恢复旧 FP 与返回 PC 后，main 的 SP 回到 8160；main 从 8176 重载 B′，调用 peek 得到 7，x₂ 保持 100。把初始等式 Ei.cell=Ep.cell 和最终等式一起检查，才验证了共享关系。
两个真正会出错的版本
漏掉 main 根时，收集器只复制 Ei、C。inc 可以正常返回 7；随后 main 从 8176 取出的还是旧 B=1072，读取其 code/env 时访问失效空间。最先成功返回的一次调用不能证明整段程序安全。
若不设置或不查转发头，分别沿 Ei、Ep 复制 C，会得到两个同为 7 的单元。第一次 peek 仍可能读到 7；随后只沿 Ei 把其中一个单元改成 10，沿 Ep 读取仍为 7。这个“后续写入”变体能揭露单纯数值快照比较漏掉的别名错误。
原址清扫与迁移任务
标记清扫保留四个活对象原址不动，释放 A 的 [1032,1056)、P 的 [1096,1120)、U 的 [1120,1136)。后两块相邻，可合并成 [1096,1136)；所得空闲块为24、40字节，单独都放不下48字节。题目限定只使用本次回收块；真实分配器还可使用原来 [1136,1512) 的未用尾区，不能据此断言整个512字节半空间分配失败。
迁移一：增加第三个根槽 alias=B。两槽应同时改到同一 B′，复制量仍为72字节。交换根顺序可改变新地址，但不得改变输出与别名等式。
迁移二：令一对递归闭包与环境形成二环，另做单对象自环；从根可达时各对象只能复制一次，无根时整个环都回收。不得用“入度非零”代替根可达性。
迁移三：在 make 内使用 scratch，只返回整数且不发布闭包。先用逃逸分析判断哪些对象变为栈分配候选，再说明循环多实例、栈容量和堆指针字段扫描仍是额外义务。静态不逃逸不代表可以无条件共用一个栈槽。
完成标准是能独立复算上述地址和状态、解释每个必要假设、让漏根和丢共享的错误版本确实失败。有限测试验证这份模型与这些轨迹，不代替任意编译器或所有 GC 的正确性证明。