这份任务要交付真正能解释执行的残余程序,以及源程序和它之间逐基本块的状态对应。先完成统一绑定时间分析,再运行记忆化流图专门化。把“输入的一部分已知”转成代码,并不意味着生成过程必然结束。
下载标准库参考程序,执行 python foundation-flowchart-specialization-check.py。也运行 python -O foundation-flowchart-specialization-check.py,两次 JSON 应一致;程序使用显式 require,不依赖会被 -O 删除的 assert。脚本仅写标准输出,不写文件。
任务一:先交出分工表
使用六变量 n、x、i、a、b、y 的仿射程序。输入为 n、x,其他变量开始为0。E 依次执行 i:=0、a:=2、b:=1、y:=x;H 判断 i<n;B 依次执行 y:=a*y+b、a:=a+1、b:=b+2、i:=i+1,再回 H;R 返回 y。
先不代入 n=3,只说明 n 已知、x 未知。交出七次赋值依赖出现,标出唯一初始动态种子 x。队列先处理 x 并加入 y,再处理 y 的自环,最终动态集为 {x,y}。解释为什么 a 的自环不迫使 a 动态,以及为什么 H 的比较不产生一条指向某个赋值目标的依赖边。
再把 i:=i+1 改成 i:=i+x,重新求闭包,应得到 {x,y,i}。指出循环条件需要留给残余程序,但这还没有证明有限生成:a、b 仍为静态并持续增长。最后单独主动动态化 a,检查传播方向不能从 y 反推 b 也动态。
任务二:九个版本与两条实际运行
固定 n=3。交出按 n、i、a、b 次序编码的九个键,及其 r0 到 r8 标签:E[3,0,0,0];随后三对 H/B 分别携带 [3,0,2,1]、[3,1,3,3]、[3,2,4,5];最后 H/R 携带 [3,3,5,7]。
残余代码必须保留九块,不能只交一行24x+29作为“生成器输出”。真正留下的赋值为 r0 的 y:=x,以及 r2、r4、r6 的 y:=2y+1、y:=3y+3、y:=4y+5;所有中间跳转都保留,r8 返回 y。
取 x=4,逐块核对证书:每个残余标签对应正确的源标签,证书静态值与源存储相等,残余 x、y 与源动态部分相等。y 的更新是4→9→30→125。再取 x=−2,得到−2→−3→−6→−19。主输出的 main.lockstep 给出 x=4 的整条块边界轨迹,记录入口状态,因此 B 的更新结果出现在下一 H 的记录里。
统计同一次 x=4 运行:源为9块、16赋值、19原语,残余为9块、4赋值、6原语。说明这项比较没有计算生成时间、跳转读取成本或大整数位成本。将 n 改为0,结果是原 x,两边均执行 E、H、R 对应的三块;源仍做一次比较,残余不做。生成器并未为了零次循环提前执行 B 中的动态算术。
需要自定输入时,可用下面的短命令读取同一脚本中的函数,不把 JSON 数组误作它要求的 Python 元组语法:
python -c 'import runpy; m=runpy.run_path("foundation-flowchart-specialization-check.py"); p=m["affine_program"](); q=m["specialize"](p,("x",),{"n":0}); print(m["lockstep"](p,q,{"n":0,"x":7}))'
任务三:错误缓存会在哪一步露馅
换成动态分支例:E 按 p 选 T 或 F,T 设置 k=2,F 设置 k=5,两者进入 J 计算 y=k*x 并返回。p、x 都是未知输入,k、y 初始为0。
交出动态集 {p,x,y} 和五个专门化状态 E[0]、T[0]、F[0]、J[2]、J[5]。x=4 时,p=1 返回8,p=0 返回20。说明 k 为 S 不意味着它在所有真实运行中同值,而意味着每个版本带着自己的已知 k。
参考器的故障实验把 F 到 J[5] 的边重定向到 J[2],实际返回8。把这个错误理解为“仅用源标签缓存”的结果,写出在 J 入口已经失败的静态存储对应,而不要等最终返回不同才发现问题。还要说明:如果缓存键省略一个以后仍会使用的静态变量,类似错误同样可能发生。
将 k 主动动态化后再生成,应只有 E、T、F、J 四个版本;两分支的 k:=2/k:=5 留在运行时。两个结果仍为8和20。对比生成代码数量、运行时赋值数量,解释少生成一个版本为何不是无条件的速度提升。
任务四:三种“停下来”必须分清
第一种是生成成功,但生成物发散。程序只有 L: goto L,参考器生成一个自环。完整运行状态一轮后重复,cycle_start=0、cycle_length=1;确定性与总块执行给出真实无限循环证据。先登记键再处理后继是关键,否则递归展开可能永远等不到结果。
第二种是生成预算失败。令 i 从0开始,在动态 x 下循环判断 i<x,真分支把 i 加一,假分支返回 i。对任意具体整数 x,源程序都在有限步返回 max(0,x);但静态 i 的变体 H[0]、H[1]、……永不穷尽。12个状态预算会在请求 R[i=3] 时失败,不返回残余程序。用任意 i 都能继续产生新 H[i+1] 的论证证明不有限,不能用一次预算失败推断任意程序都会发散。
将 i 主动设为 D 后重试,交付四块完整残余程序和 x=5 的13块运行,返回5。再测 x=−2,三块就返回0。这个修复把变化的 i 放回运行时;它没有证明“只要主动动态化任意一个变量就会终止”。
第三种是运行预算结束但结论未知。解释器若报告 prefix_only,只证明检查了一个有限、未重复的前缀。不能把它当作返回,也不能当作发散。请把这一结果与上面的精确状态重复分开写入验收结论。
最后测试输入接口:回到 n=3 的仿射程序,把 n、i、a、b 都主动动态化。生成器应保留四个源块版本,另加 init 块写入 n=3;残余输入仍只有 x,不能让调用者再提供一个可变 n。x=4 仍返回125。局部变量初始0、已知输入常量初始化和残余动态赋值共同建立第一次块对应,三者都不能漏。
验收材料
提交二分及加入原因、完整残余块表、两条数值轨迹、动态分支错误见证、精确自环证书、无限变体的论证和动态化重试。参考器默认还核对496组仿射输入、600个依赖闭包与慢速算法、3500组无环源—残余运行及101组动态化计数器输入。这些是可重复的找错证据;全输入语义保持来自形式页的表达式引理与逐块对应,不来自有限测试数量。