Skip to content

定理Theorem

计算充分性

施工中 · 内容逐步修订

Computational adequacy · 计算适当性

以形式近似证明布尔指称与求值对应,在有限Bool/箭头域上补齐fix基本引理,并由组合性导出上下文可靠性。

形式陈述 ​

计算充分性检查一个基本问题:模型声称程序有结果时,程序真的会算出这个结果吗?本页固定上下文等价中定义的语言 L、弱传名求值和 T,F,⊥ 三种观察,采用指称语义中的有限域模型:

DBool={⊥,T,F},DA→B=[DA→DB]mon.

布尔域只有 ⊥≤T、⊥≤F 及自反比较;函数按逐点序排列,其底元是常底函数。本模型的计算充分性是:对任意闭项 p:Bool 和 b∈{T,F},

[[p]]=b⟹p⇓b―,

其中 T―=true、F―=false。反方向称本页的求值可靠性:p⇓b―⇒[[p]]=b。合在一起,恰得

Obs(p)=[[p]].

这包括发散:指称为底则不可能求出布尔值;指称非底则充分性保证终止。这里断言的是闭合基类型的结果对应,不是“高阶指称相等会产生同一函数语法”。

直觉

把程序解释成数学函数并不自动保证数学结果可由执行得到。证明需要把两边接起来。形式近似关系让一个语义元素携带一条可执行承诺:布尔非底元素承诺实际得到那个值,函数元素则承诺每个已经符合输入承诺的程序都产生符合输出承诺的应用。

底元容纳所有尚未取得结果的计算。守卫指称为底时,整个条件式的语义也是底;形式近似因此在这个分支直接成立。这正是证明里必须同时处理基类型底元与函数类型底元的原因。

例子与边界

形式近似及两个辅助事实 ​

对 d∈DA 与闭项 e:A,递归定义 d◃Ae:

d◃Boole⟺d=⊥ ∨ (d=T∧e⇓true) ∨ (d=F∧e⇓false),f◃A→Be⟺∀a,u (a◃Au⟹f(a)◃B(eu)).

输入 u 遍历所有闭项,包含发散项;传名求值把尚未求值的实参代入函数体,因此环境关系也使用闭项替换。

先按类型证明底元近似任意项。Bool 情形来自定义;箭头情形任取 a◃Au,有 ⊥A→B(a)=⊥B,类型归纳假设给出 ⊥B◃Beu,故满足箭头分支。

再证明有限求值不改变近似关系:若 e→∗e′,则 d◃Ae⟺d◃Ae′。Bool 处,确定性说明有限前缀之前与之后能到达的布尔值相同;箭头处,对任何闭实参 u,函数位置规则给出 eu→∗e′u,应用结果类型 B 上的归纳假设即可。这个事实同时允许从 β 收缩后的函数体倒推到应用项,以及从选出的条件分支倒推到整个条件式。

基本引理的完整归纳 ​

设 Γ⊢e:A,ρ 是语义环境,σ 把每个 x:B∈Γ 替换为闭项 σ(x):B,并满足 ρ(x)◃Bσ(x)。要证

(*)[[e]]ρ◃Ae[σ].

这是逻辑关系基本定理在本语言里的具体实例。证明按类型推导归纳,各种构造如下。

  1. 变量。 e=x 时,左边为 ρ(x),右边为 σ(x),正是环境假设。
  2. 布尔常量。 true 和 false 均零步求值到自己,满足各自的非底近似条件。
  3. 发散常量。 [[Ω]]=⊥,由底元引理得 ⊥◃BoolΩ。
  4. 应用。 若 e=rs,归纳假设给出 [[r]]ρ◃B→Ar[σ] 和 [[s]]ρ◃Bs[σ]。把后一对输入交给前一箭头关系,得到 [[r]]ρ([[s]]ρ)◃Ar[σ]s[σ],即所求。
  5. 抽象。 若 e=λx:B.r,为证明箭头分支,任取 a◃Bu。先把绑定变量改名,使它不与替换冲突,再扩展环境为 ρ[x↦a]、替换为 σ[x↦u]。函数体归纳假设给出 [[r]](ρ[x↦a])◃Ar[σ[x↦u]]。后者正是 (λx:B.r[σ])u 的 β 收缩结果;有限求值闭包把结论搬回应用项,完成箭头条件。
  6. 条件式。 设 e=if g then r else s:A。若 [[g]]ρ=⊥,严格条件解释给出 [[e]]ρ=⊥A,底元引理立即适用,即使 A 是函数类型也成立。若守卫指称为 T,守卫的 Bool 近似给出 g[σ]⇓true;整个条件式因此有限步进入 r[σ]。分支归纳假设给出 [[r]]ρ◃Ar[σ],有限求值闭包给出所求。F 情形同理选择 s[σ]。

以上覆盖 L 的全部类型规则。对闭项取空环境和空替换,再在 Bool 处展开 ◃,便得到计算充分性。后面另给加入fix的完整分支:在这里的有限类型域中,近似链实际稳定;更一般的无限域才需额外的极限闭包论证。

另一方向为什么成立 ​

求值可靠性来自语义替换等式

[[e[u/x]]]ρ=[[e]](ρ[x↦[[u]]ρ]).

该式按 e 的结构归纳:变量分成 x 与其他变量;应用、条件式把子项等式代入解释式;抽象先改名避免捕获,再对每个语义实参使用函数体归纳假设;常量不依赖替换。于是 β 根步保持指称;两个条件根步由选择语义直接保持;Ω 自环也保持。组合性把根步等式提升到每个 E 中,有限步到布尔常量便给出可靠性。

例如 p=(λx:Bool.true)Ω 的指称为 T,实际一步得到 true;q=if Ω then true else true 的指称为 ⊥,实际永远困在守卫。相同的两个分支不足以消除严格守卫。

加入一般不动点构造:有限域上的完整分支 ​

为保持前面语言 L 的边界明确,另定义 Lfix:在相同 Bool/箭头类型和原有项上加入一元构造 fixA(e),规则为

Γ⊢e:A→AΓ⊢fixA(e):A,fixA(e)⟶e(fixA(e)).

这里没有额外的裸函数常量 fix;值仍只有布尔值与 λ 抽象。不动点项直接展开,无须先计算 e,也不添加 fixA(E) 求值上下文。展开后的应用按原传名规则计算函数位置。新增根步唯一且保持类型,故原有保持、进展和确定性证明只多出这一分支。

各 DA 仍是原有限域。对单调 F:DA→DA,令

d0=⊥A,dn+1=F(dn).

由底元最小及 F 单调,d0≤d1≤⋯。有限性保证某个 N≤|DA|−1 满足 dN=dN+1,此后不再改变。对任一不动点 a,从 d0≤a 归纳得 dn≤a,所以 dN 是最小不动点。定义

[[fixA(e)]]ρ=lfp([[e]]ρ).

这项解释也关于环境单调。若 ρ≤ρ′,项 e 的归纳假设给出 Fρ≤Fρ′;再对 n 归纳,Fρn(⊥)≤Fρ′n(⊥)。取超过两条链稳定位置的同一 n,便得到两最小不动点的次序。语义替换引理的新分支也成立:对子项的替换等式使两边的 F 完全相同,故最小不动点相同。

现在把 ◃A 中闭项的量词扩充到全部 Lfix 项。底元引理及有限求值闭包的类型归纳仍成立,因为求值仍确定,函数位置规则未变。基本引理原有六个分支仍用同样的证明,新增分支如下。

设类型推导末步为 fixA(e),置

F=[[e]]ρ,q=fixA(e[σ]).

对 e:A→A 的类型推导归纳假设给出 F◃A→Ae[σ]。另对近似序号 n 作归纳,证明 dn◃Aq:

  • n=0 时由底元近似任意项成立。
  • 若 dn◃Aq,箭头关系给出 F(dn)◃Ae[σ]q。又有 q→e[σ]q,有限求值闭包把结论搬回 q,即 dn+1◃Aq。

取稳定位置 N,得到 [[fixA(e)]]ρ=dN◃Aq,完成所有类型规则的归纳。这里内层按 n 归纳,外层仍按严格更小的类型推导归纳,没有假设递归程序已经终止。

反方向的求值可靠性也闭合:不动点等式给出

[[fixA(e)]]ρ=F([[fixA(e)]]ρ)=[[e(fixA(e))]]ρ.

因此新根步保持指称,组合性继续把它提升到求值上下文。对闭合 Bool 项,观察与指称仍完全对应;组合性继而给出 Lfix 所有新增上下文中的可靠性。它不是仅沿用原 L 上下文的量词。

一般 PCF 含无限自然数域,证明需要检查近似关系的链极限闭包,再用 Scott 归纳;本节有限类型域中的链已实际稳定,因此上面的有限归纳足以完成这一特例。[1]

两次语义近似怎样产生一个递归函数 ​

令 A=Bool→Bool,

r=λf:A.λb:Bool.if b then true else ftrue,q=fixA(r).

对应泛函为 F(f)(b)=if b then T else f(T)。从函数底元开始:

近似函数 输入 ⊥ 输入 T 输入 F
f0=⊥A ⊥ ⊥ ⊥
f1=F(f0) ⊥ T ⊥
f2=F(f1) ⊥ T T
f3=F(f2)=f2 ⊥ T T

操作上,qfalse→∗qtrue→∗true:第一次展开选择递归调用,第二次展开选择 true 分支。qΩ 则困在严格守卫,指称也是 f2(⊥)=⊥。另取 fixBool(λx:Bool.x),近似链从底开始立即稳定,而程序反复展开和 β 收缩,永不返回。

有限域的稳定序号是语义近似的性质,不是所有程序执行步数的上界,也不声称含 Nat 的完整 PCF 具有有限域。验收本节时,应能补出 fix 分支的双层归纳、重算四行表,并分别解释稳定指称对应终止与发散的两个例子。

推论与应用

设同型闭项 e,e′ 指称相等。对任意闭合 Bool 程序上下文 C,组合性先给出 [[C[e]]]=[[C[e′]]],本页的观察对应再给出 Obs(C[e])=Obs(C[e′])。因此

[[e]]=[[e′]]⟹e≃ctxe′.

这是模型的上下文可靠性,与前面的“有限求值保持指称”是不同陈述。组合性负责把部件相等传到完整程序,求值可靠性与计算充分性再把完整程序的指称翻译成实际观察。

验收时应能亲手补出应用、抽象和函数结果条件式的三段归纳,并指出最后推论用了哪条组合等式。反方向 e≃ctxe′⇒[[e]]=[[e′]] 仍可能失败;完全抽象给出同一语言、同一模型中的明确反例。

参考资料

[1] A. M. Pitts、G. Winskel、M. Fiore、M. Lennon-Bertrand,Denotational Semantics,2024-12-05 版,§7,Theorem 30、Theorem 31 与 Lemma 32。讲义讨论含一般递归的 PCF;本文先为语言 L 给出完整归纳,再将第60页的fix证明专门化到有限Bool/箭头域;有限稳定论证及四行算例由正文展开。

关系图谱14 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系