返回学习路线

从源字符到显式求值次序：保住同一个计数器 ​

这份任务把三个前端接口走完：字符切成 token、名字指向声明身份、有副作用的表达式拆成 ANF。最后交回已有闭包转换，验证同一组读写事件。解析理论、SSA、类型推导和运行时 GC 各保留原有课程责任，不为了接线重写一遍。

固定输入、模型与交付物 ​

先做三个入口自测：为什么 letx 不应被切成 let 和 x？为什么非递归 let 的右侧不能看到自己的新声明？为什么一个未被使用的函数返回值不意味着调用可以删掉？答案分别是先比较匹配长度、非递归绑定的作用域仅覆盖体、调用仍可能产生副作用。

若入口三问尚不熟，先回到DFA理路确定性有限自动机Deterministic finite automaton · DFA以有限状态和总转移函数为每个输入字规定唯一运行的识别模型。、抽象语法树理路抽象语法树Abstract syntax tree · AST把抽象语法构造表示为有根有序树的常见编译器数据结构。、变量绑定理路变量绑定Variable binding · Binding occurrence把变量的使用出现关联到作用域内声明，并区分自由出现、绑定出现与遮蔽。及传值调用理路传值调用Call by value · CBV仅当实参先求值为值后才进行函数体替换的求值策略。与可变状态语义理路可变状态语义Semantics of mutable state · Store semantics把位置到值的存储纳入配置并随求值更新的语义。补齐接口，再开始下面的同程序任务。

源语言采用左到右传值，整数按数学整数，显式引用单元可读写，词法绑定本身不可变，没有并发、异常、递归、if 或资源失败。源码如下，含两个同名 x、返回的两个闭包，以及一份共享单元：

let x = ref 4 in
let make = fun u -> (fun d -> (x := !x + d; !x), fun v -> !x) in
let p = make(0) in
let f = fst p in
let g = snd p in
let x = 100 in
(f((f(1); 2)), (g(0), x))

交付四项：完整 token 序列和源区间；使用到声明 ID 的映射；满足目标文法的 ANF；四个执行阶段的结果、堆和读写事件相同的证据。四阶段为源名字 AST、解析身份 AST、ANF、显式代码标签加环境字段的闭包表示。阶段一致只检验这些输入，不代替机制页的一般证明。

下载标准库检查器；下载完整输入与输出证据。本地用 Python 3.10 或更高版本运行：

python foundations-cs03b-checker.py --trace --out result.json
python -O foundations-cs03b-checker.py --out result-no-trace.json

第一条保存逐事件证据，第二条关闭事件记录并验证测试不依赖会被优化模式移除的 assert。程序只使用标准库，不联网，不生成真实 ELF，不调用 LLVM，也不测主机机器码的性能。

字符、语法与声明身份 ​

词法规格中的关键字为 let、in、fun、ref、fst、snd，优先于 ID；ID 为 ASCII 字母或下划线起始、后接字母数字下划线；INT 为非空十进制数字；其余 token 为 -> := + ! ( ) , ; =。空白消耗但不发出，EOF 单独发出。完整 token 的 lexeme 序列为：

let x = ref 4 in
let make = fun u -> ( fun d -> ( x := ! x + d ; ! x ) , fun v -> ! x ) in
let p = make ( 0 ) in
let f = fst p in
let g = snd p in
let x = 100 in
( f ( ( f ( 1 ) ; 2 ) ) , ( g ( 0 ) , x ) ) EOF

共82个非空白 token，加EOF共83项；文件中的完整证据逐项给 (类别,文本,start,end)。例如第一个 x 在 [4,5)；inc 体的赋值左侧 x 在 [48,49)、第一次读 x 在 [54,55)、返回读 x 在 [62,63)；peek 的 x 在 [76,77)。区间按源串字符而非字节计算。检查器的源文本固定为上述换行形式，改变空白会改变 span，但不应改变绑定或结果。

解析器只是复用具体语法理路语法树Parse tree · Derivation tree用有序树记录产生式层次，以完整例子区分推导顺序、文法歧义、优先级及抽象语法树。到AST理路抽象语法树Abstract syntax tree · AST把抽象语法构造表示为有根有序树的常见编译器数据结构。的适配器。函数应用写成 e(e)，绑定最紧；前缀 !、ref、fst、snd 其次；加法左结合；赋值 := 右结合；序列 ; 再次；let 与 fun 的体是完整表达式。括号中一个逗号构成二元组，额外元组须嵌套。关键字 in、逗号和右括号终止相应子表达式。没有容错恢复，也没有类型推导阶段：类型不合的程序可能解析、解析名字成功，却在教学求值器报错。

按声明先序编号如下。提前分配 ID 不代表提前扩展作用域：let 的右侧仍在旧作用域解析。

两个函数体里每个 x 都指向1，最后结果中的 x 指向9；f、g 的调用分别指向7、8。resolved AST 保留每次变量使用的源 span，未绑定诊断含该区间；声明表只列身份和原名，检查器没有另外导出声明 span 表。两次函数捕获的外部 ID 集合都是 {1}，make 自己也需要1。

对 let x=x in x，空环境中的右侧必须拒绝；对 (let x=1 in x,x)，第二分量必须拒绝。检查器在退出解析体时用 finally 恢复名字栈，失败不会把内层声明留给后一次解析。

完整 ANF 与显式环境答案 ​

下面用 v1…v9 写源声明，用 t1…t15 写新鲜临时量。花括号仅用于展示函数体边界，不属于源语言语法。每个操作的参数都是原子；函数创建不执行其体。

let t1 = ref(4)
let v1 = t1
let v2 = fun v3 -> {
  let t7 = pair(
    fun v4 -> {
      let t2 = load(v1)
      let t3 = add(t2,v4)
      let t4 = store(v1,t3)
      let t5 = load(v1)
      return t5
    },
    fun v5 -> {
      let t6 = load(v1)
      return t6
    })
  return t7
}
let t8 = call(v2,0)
let v6 = t8
let t9 = fst(v6)
let v7 = t9
let t10 = snd(v6)
let v8 = t10
let v9 = 100
let t11 = call(v7,1)
let t12 = call(v7,2)
let t13 = call(v8,0)
let t14 = pair(t13,v9)
let t15 = pair(t12,t14)
return t15

t11 的值被序列丢弃，但其调用保留。t4 的值是 unit，写单元的操作同样不能删掉。没有任何函数体读写被提升到函数创建点，且 pair 的第一个元素先求完，才计算第二个元素。

交给已有闭包转换理路闭包转换Closure conversion · 闭包变换把词法捕获改写为显式环境参数，同时保留遮蔽、求值顺序与共享可变单元。后，make、inc、peek 分别成为代码 L1、L2、L3。三份代码的捕获身份列表均为 [1]；L1 的普通形参为3，L2为4，L3为5。每份环境第0字段保存同一单元位置 ℓ。L1 运行时创建 Closure(L2,[ℓ])、Closure(L3,[ℓ]) 并返回其二元组，后续调用把环境字段与普通实参交给相应代码。代码表与全部转换树在下载证据中逐项展开。

该接线复用了旧转换的显式环境契约，未新增另一套 closure 定义。检查器用 Python tuple 表示环境字段，整数 ID 表示绑定，用独立 code 表解释标签；它没有继续生成寄存器或机器指令，栈帧与移动 GC 的旧终点保持独立。

执行、错误变体与成本 ​

四阶段都得到 (7,(7,100))，最终唯一单元为7。全部八个存储事件必须按下表保持：

若删除 t11 绑定，则第一次增量1没有发生，得到 (6,(6,100))。若把 inc、peek 的捕获各改成 ref(!ℓ) 私有单元，inc 能升到7而 peek 仍读4，得到 (7,(4,100))。若名字解析改成调用点动态查找，f 里的 x 会误读整数100，不再是合法单元；检查器应报错，而不是假定还能继续做引用写入。

固定运行的 AST 求值节点计数依次为53、53、90、93，复制的环境条目数依次为27、27、175、145。它们是这个树解释器的真实工作，不能拿90对53推导机器码变慢比例；特别是复制整个 Python 字典的工作，和真实编译器的寄存器临时量不同。四个阶段存储事件数都为8，开 trace 时保留各自事件列表；打印完整 token、树和代码表还要按输出字符数收费。

扫描器报告307次字符转移尝试、2626次规则状态尝试、175次成功推进尝试。这里同时模拟固定数量规则的组合状态，未生成缓存DFA转移表；它仍实现最长匹配规格，但不能把 rule_attempts 当成“一次机器指令”。a | a*b 在输入 aⁿ 上另测到成功推进次数 n(n+1)/2，n=4时为10。

迁移任务与验收边界 ​

把最终表达式改为 (f(1),f(2))，答案 (5,7)、最终单元7；两次结果要在各自返回时保存。将外层 x=100 改名 z，并同步最后那次使用，结果不变，其他函数的捕获仍只有ID1。将任一函数里的 x 同时改成 z，则定义点没有 z，应在那个 span 报未绑定。

再把返回闭包换成提升页理路Lambda 提升与传递环境参数Lambda lifting · 函数提升对只直接调用的局部函数组闭合传递需求，把自由变量变为普通参数，并说明返回函数仍为何需要闭包。给定的同作用域 f/g/h 直接调用环，得到三份 Need={x}；h(3)返回1、h(2)返回外层x。这是提升的独立短任务，当前 make 返回函数值不在其受限输入域内。尾调用页理路尾调用与栈帧复用Tail-call frame reuse · Proper tail calls · 尾递归实现从尾上下文识别相同续延，用受限教学 ABI 复用当前帧，精算参数搬移和活动栈深度，并指出资源边界。另给 sum(3,0) 的四次参数状态和一帧48字节证明；检查器同时执行正确平行赋值与错误逐次赋值，实际得到(9,2)与(9,9)，sum状态机也调用该平行赋值接口；它并未声称本前端自动插入尾调用指令。

验收包括结果、别名、事件顺序、ANF构造元参数个数、名字作用域和失败位置。有限测试不能证明任意程序正确，求值 fuel 耗尽也只代表检查器预算耗尽，不能判定源程序发散。模型扩展到if、异常、无限递归、Unicode、资源失败或真实ABI时，需要增加语义与测试接口。