“计算充分性检查一个基本问题:模型声称程序有结果时,程序真的会算出这个结果吗?本页固定上下文等价中定义的语言 $L$、弱传名求值和 $T,F,\bot$ 三种观察,采用指称语义中的有限域模型:”
形式陈述
先固定语言和观察
两个程序在一次测试中给出相同结果,是否就能在任何客户端中互换?上下文等价把“任何客户端”变成一个明确的量词。本页定义充分性、完全抽象单元共同使用的基线语言
变量、抽象、应用使用通常的简单类型规则;
值为布尔常量和 λ 抽象。根收缩规则是
以及 false 选择
中收缩:
量化全部程序上下文
单洞程序上下文允许洞出现在任意语法位置:
洞恰出现一次;洞外的
程序上下文
直觉
类型规定客户端能怎样使用部件;观察规定使用后什么差异值得区分;上下文量词则覆盖所有满足接口的使用方式。函数本身已经是值,只看它“能否求值到函数”几乎没有区分力。客户端可以调用它、把它传给别的函数、在分支里反复使用它,最后把差异转成布尔结果或发散。
定义不是要求枚举所有客户端。要否定等价,找一个区分上下文即可;要证明等价,则常用组合语义或逻辑关系一次覆盖全部构造。两种证明任务的量词负担不同。
例子与边界
两个对正常布尔输入相同的函数
令
两者类型均为
因此观察分别为
上下文组合给出可替换性
关系的自反、对称、传递性直接来自观察相等。它还对良类型程序上下文封闭:若
空上下文只适用于 Bool 洞;函数洞需要通过调用等操作变成布尔观察。对于本语言的闭合 Bool 项,同一观察确实足以推出上下文等价:由计算充分性取得观察与布尔指称的对应,再用组合性传播相等。高阶接口则还需考察客户端如何使用函数,前面的
推论与应用
程序优化中的“替换部件”自然使用上下文等价,前提是优化承诺的观察与本文相同。例如恒等函数
本单元的入口任务是给
参考资料
- A. M. Pitts、G. Winskel、M. Fiore、M. Lennon-Bertrand,Denotational Semantics,2024-12-05 版,§5.3。该讲义使用更大的 PCF;本文明确限制到 Bool、箭头和原始发散常量的语言
。