“在带原始布尔发散常量的弱传名语言中,形式近似的基本引理逐项证明变量、常量、抽象、应用和条件式的归纳分支;条件式守卫为底而结果为函数时,要用“各类型底元近似任意项”的辅助引理。完全抽象反例还展…”
形式陈述
一个模型能够正确解释每次程序执行,是否就精确刻画了程序之间的可观察差异?完全抽象要求:对任意同型闭项
左边是数学模型中的相等,右边是固定语言和观察下的上下文等价。正方向是上下文可靠性;反方向要求模型不把上下文无法区分的程序再分开。在已经证明正方向的文献中,常仅把反方向写作 full abstraction 条件;本文始终明确保留两个方向。
以下先固定该单元的
直觉
函数域中可能存在某个数学输入,而源语言没有程序能实现它。模型可以用这个额外输入区分两个高阶程序;实际客户端却只能编写语言允许的输入,因而可能永远看不见差别。
仅说“存在不可定义函数”还不够:必须找到两个源程序,证明所有源上下文都无法区分它们,再用那个数学输入算出不同结果。下面分三步完成这三个量词不同的任务。
例子与边界
两个只在通过全部探针后才不同的程序
令
T_b = λf:H.
if f true Omega then
if f Omega true then
if f false false then Omega else b
else Omega
else Omega
代码中的 Omega 就是
某个守卫发散,计算就停留在那里;得到与要求相反的布尔值,则走向显式
三元关系证明没有源程序通过探针
在
递归定义
现在证明
- 变量直接取环境分量;true、false 的对角三元组满足基关系;
的三元组为 。 - 应用把相关函数三元组作用在相关实参三元组上,结论正是箭头关系的定义。
- 抽象任取相关实参三元组,分别扩展三个环境,在函数体上使用归纳假设,得到箭头关系。
- 条件式的三个守卫相关。若第一或第二守卫为底,则同一分量的整个条件解释为结果类型的底,前述底元事实给出结果相关;否则基关系强迫三个守卫为同一个布尔值,于是三个解释选择同一侧分支,分支归纳假设给出结果相关。这里覆盖了结果为函数的条件式,不能只核查 Bool 结果。
这些正是基本定理的全部构造义务。取空环境,任何闭项
连续应用两次箭头关系得到
可是
从所有实参提升到所有程序上下文
接下来把调用结果的结论传到任意程序位置,包括 λ 体和高阶参数。为此定义闭项上的二元传名关系
这里两边输入可以不同,也可以不是值。先记两条按类型归纳的闭包。其一,对任意一侧作有限弱求值,不改变
证明环境版本:若
最后,对任意上下文
对我们的一对
模型中的九格输入却能区分它们
模型允许如下柯里化函数
其规则是:只要任一参数为
依次查表可得
代入
两指称是函数,在同一输入上结果不同,故不相等。结合 (2),得到一个计算充分、上下文可靠、但不完全抽象的模型。三元关系还已经证明 por 不可由
把数学 por 加入目标语言后,翻译保持什么
现在区分两门语言:源语言仍为前面完整定义的
这里没有加入一般 fix;递归充分性中的
目标求值与观察契约
为表达两侧均可提供 true 结果,目标使用有限大步推导
规则不要求实参
它们与文献的布尔 por 求值规则一致。[1] 按有限推导归纳,原构造保持指称,新增三条规则则分别查九格表,故
定义目标观察为:有 true 推导时为
所有完整源程序的观察都保持
先对不含 por 的闭项建立
左侧可使用与原弱小步等价的大步规则:常量/λ 零步到自身;应用先有限步把函数位置化为 λ,再 β 收缩并计算函数体;条件式同样先求守卫再进入选中分支。对大步推导归纳能拼出这些小步;反方向按有限小步长度拆开第一次函数/守卫求值及根步,得到大步推导。
从源到目标,所有源大步规则都仍被允许,直接按推导归纳。从目标到源,加强归纳命题为:“输入不含 por,则返回值也不含 por,并且同一推导可在源语言重建。”值规则立即成立;条件式的子项仍不含 por,使用守卫和分支归纳假设。应用时先由函数位置归纳假设知道返回的 λ 连同其函数体不含 por,再用源项在避免捕获替换下的封闭性,知道
因此两个布尔结果的存在性完全相同;都没有有限结果时,两边观察也同为
本例没有错误、外部事件或 UB,所以这也是所声明观察下完整程序的行为保持。证明覆盖全部源程序,不靠有限测试推出普遍结论。
新目标客户端能区分源端等价的部件
目标中可定义
两次传名 β 调用后,前三条规则分别给出
因此
前面已经用三元、二元关系证明
反射方向仍成立:若
推论与应用
本单元可以用三个问题验收。第一,常返回 true 的函数与严格读取布尔参数后返回 true 的函数,被
编译阶段的语义保持还有另一种完全抽象问题。若翻译
两边分别量化源语言与目标语言的全部允许上下文,并使用各自声明的观察。完整闭程序运行结果保持,只涉及已经链接好的程序;翻译的完全抽象还要求分析任意目标客户端能否区分源语言中等价的部件。前者比较完整执行,后者比较两种语言中的部件等价,而指称模型的完全抽象比较程序等价与数学对象相等。
参考资料
[1] A. M. Pitts、G. Winskel、M. Fiore、M. Lennon-Bertrand,Denotational Semantics,2024-12-05 版,§8.1,Definition 31、Theorems 40–41;经典并行或与测试项来源。讲义未给 Theorem 40 的证明。本文为较小语言