形式陈述
计算充分性检查一个基本问题:模型声称程序有结果时,程序真的会算出这个结果吗?本页固定上下文等价理路上下文等价Contextual equivalence · 程序上下文等价固定类型、语言与观察后,以所有良类型闭合程序上下文能否区分两个部件来定义可替换性。中定义的语言 、弱传名求值和 三种观察,采用指称语义理路指称语义Denotational semantics把程序构造组合地解释为数学对象与函数的语义方法。中的有限域模型:
布尔域只有 、 及自反比较;函数按逐点序排列,其底元是常底函数。本模型的计算充分性是:对任意闭项 和 ,
其中 、。反方向称本页的求值可靠性:。合在一起,恰得
这包括发散:指称为底则不可能求出布尔值;指称非底则充分性保证终止。这里断言的是闭合基类型的结果对应,不是“高阶指称相等会产生同一函数语法”。
例子与边界
形式近似及两个辅助事实
对 与闭项 ,递归定义 :
输入 遍历所有闭项,包含发散项;传名求值把尚未求值的实参代入函数体,因此环境关系也使用闭项替换。
先按类型证明底元近似任意项。Bool 情形来自定义;箭头情形任取 ,有 ,类型归纳假设给出 ,故满足箭头分支。
再证明有限求值不改变近似关系:若 ,则 。Bool 处,确定性说明有限前缀之前与之后能到达的布尔值相同;箭头处,对任何闭实参 ,函数位置规则给出 ,应用结果类型 上的归纳假设即可。这个事实同时允许从 β 收缩后的函数体倒推到应用项,以及从选出的条件分支倒推到整个条件式。
基本引理的完整归纳
设 , 是语义环境, 把每个 替换为闭项 ,并满足 。要证
这是逻辑关系基本定理理路逻辑关系基本定理Fundamental theorem of logical relations · Fundamental lemma良类型项在点对点相关的环境替换下产生逻辑相关结果的核心引理。在本语言里的具体实例。证明按类型推导归纳,各种构造如下。
- 变量。 时,左边为 ,右边为 ,正是环境假设。
- 布尔常量。 true 和 false 均零步求值到自己,满足各自的非底近似条件。
- 发散常量。 ,由底元引理得 。
- 应用。 若 ,归纳假设给出 和 。把后一对输入交给前一箭头关系,得到 ,即所求。
- 抽象。 若 ,为证明箭头分支,任取 。先把绑定变量改名,使它不与替换冲突,再扩展环境为 、替换为 。函数体归纳假设给出 。后者正是 的 β 收缩结果;有限求值闭包把结论搬回应用项,完成箭头条件。
- 条件式。 设 。若 ,严格条件解释给出 ,底元引理立即适用,即使 是函数类型也成立。若守卫指称为 ,守卫的 Bool 近似给出 ;整个条件式因此有限步进入 。分支归纳假设给出 ,有限求值闭包给出所求。 情形同理选择 。
以上覆盖 的全部类型规则。对闭项取空环境和空替换,再在 Bool 处展开 ,便得到计算充分性。后面另给加入fix的完整分支:在这里的有限类型域中,近似链实际稳定;更一般的无限域才需额外的极限闭包论证。
另一方向为什么成立
求值可靠性来自语义替换等式
该式按 的结构归纳:变量分成 与其他变量;应用、条件式把子项等式代入解释式;抽象先改名避免捕获,再对每个语义实参使用函数体归纳假设;常量不依赖替换。于是 β 根步保持指称;两个条件根步由选择语义直接保持; 自环也保持。组合性把根步等式提升到每个 中,有限步到布尔常量便给出可靠性。
例如 的指称为 ,实际一步得到 true; 的指称为 ,实际永远困在守卫。相同的两个分支不足以消除严格守卫。
加入一般不动点构造:有限域上的完整分支
为保持前面语言 的边界明确,另定义 :在相同 Bool/箭头类型和原有项上加入一元构造 ,规则为
这里没有额外的裸函数常量 fix;值仍只有布尔值与 λ 抽象。不动点项直接展开,无须先计算 ,也不添加 求值上下文。展开后的应用按原传名规则计算函数位置。新增根步唯一且保持类型,故原有保持、进展和确定性证明只多出这一分支。
各 仍是原有限域理路指称语义Denotational semantics把程序构造组合地解释为数学对象与函数的语义方法。。对单调 ,令
由底元最小及 单调,。有限性保证某个 满足 ,此后不再改变。对任一不动点 ,从 归纳得 ,所以 是最小不动点。定义
这项解释也关于环境单调。若 ,项 的归纳假设给出 ;再对 归纳,。取超过两条链稳定位置的同一 ,便得到两最小不动点的次序。语义替换引理的新分支也成立:对子项的替换等式使两边的 完全相同,故最小不动点相同。
现在把 中闭项的量词扩充到全部 项。底元引理及有限求值闭包的类型归纳仍成立,因为求值仍确定,函数位置规则未变。基本引理原有六个分支仍用同样的证明,新增分支如下。
设类型推导末步为 ,置
对 的类型推导归纳假设给出 。另对近似序号 作归纳理路数学归纳法Mathematical induction · Weak induction由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。,证明 :
- 时由底元近似任意项成立。
- 若 ,箭头关系给出 。又有 ,有限求值闭包把结论搬回 ,即 。
取稳定位置 ,得到 ,完成所有类型规则的归纳。这里内层按 归纳,外层仍按严格更小的类型推导归纳,没有假设递归程序已经终止。
反方向的求值可靠性也闭合:不动点等式给出
因此新根步保持指称,组合性继续把它提升到求值上下文。对闭合 Bool 项,观察与指称仍完全对应;组合性继而给出 所有新增上下文中的可靠性。它不是仅沿用原 上下文的量词。
一般 PCF 含无限自然数域,证明需要检查近似关系的链极限闭包,再用 Scott 归纳;本节有限类型域中的链已实际稳定,因此上面的有限归纳足以完成这一特例。[1]
两次语义近似怎样产生一个递归函数
令 ,
对应泛函为 。从函数底元开始:
| 近似函数 |
输入 |
输入 |
输入 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
操作上,:第一次展开选择递归调用,第二次展开选择 true 分支。 则困在严格守卫,指称也是 。另取 ,近似链从底开始立即稳定,而程序反复展开和 β 收缩,永不返回。
有限域的稳定序号是语义近似的性质,不是所有程序执行步数的上界,也不声称含 Nat 的完整 PCF 具有有限域。验收本节时,应能补出 fix 分支的双层归纳、重算四行表,并分别解释稳定指称对应终止与发散的两个例子。