Skip to content

最弱自由前置条件

Weakest liberal precondition · WLP

刻画所有终止结果都满足后置条件的最大初始状态集,同时不把发散本身视为部分正确性失败。

条目类型
定义

形式陈述

设命令 C 从状态 s 出发可以有多个执行。对状态谓词 Q,最弱自由前置条件定义为

swlp(C,Q)s.C,sssQ.

量词只约束终止结果:如果某条执行永不终止,它不会单独使公式为假。在 demonic 非确定语义下,“所有终止结果”覆盖每个可能分支;若还要求所有最大执行都终止,才得到 最弱前置条件 的总正确性口径。令 Term(C) 表示从当前状态出发每条允许执行都终止,则在这一固定语义下

wp(C,Q)Term(C)wlp(C,Q),

因而总有 wp(C,Q)wlp(C,Q)

赋值、顺序和条件的逆向方程与总正确性变换器表面相同,例如

wlp(x:=E,Q)=Q[E/x],wlp(C;D,Q)=wlp(C,wlp(D,Q)).

差别在循环固定点。令

F(X)=(¬BQ)(Bwlp(C,X)).

把谓词视为状态集合并按包含排序时,while B do C 的 wlp 是单调算子 F 的最大不动点;无限留在循环中的状态因此可以被纳入。

直觉

“liberal”不是降低后置条件,而是拒绝在同一个判断里承诺终止。它问的是:如果程序有一天返回,返回状态会不会违反 Q?这使安全性证明可以先独立于终止性开展。随后若另有排名函数、结构递归或其他终止证书,二者合在一起才成为总正确性。

最大不动点给出一个可靠的方向检查。对 while true do skip,无论后置条件是什么都没有终止结果,所以每个初态都满足 wlp;全集正是相应循环方程的最大解。若误取最小解,会把这个程序的 wlp 算成空集,悄悄把终止要求塞回部分正确性。

例子与边界

考虑整数程序

text
if x = 0 then
    while true do skip
else
    y := x

后置条件为 y0。当 x0 时,赋值终止且建立后置;当 x=0 时,唯一分支发散,没有违反后置的终止结果。因此

wlp(C,y0)true,wp(C,y0)x0.

这两个结果的差异完全来自终止量词,而不是赋值规则。

对 demonic 选择 skip [] diverge,若当前状态满足 Q,wlp 为真,因为唯一终止结果仍满足 Q;wp 却为假,因为调度可以选择发散分支。若使用 angelic 选择,终止量词会变成“存在成功选择”,得到另一种变换器,不能沿用上述公式。

异常和 stuck 也必须分类。若除零被定义为错误终态,它应由单独的异常后置或安全条件约束;若把它误当作非终止,wlp 会平白放过内存错误。文献有时用 wp 记部分正确性变换器,因此引用结论时必须同时核对语义定义,不能只看符号名称。

推论与应用

Hoare 部分正确性目标可改写为

Pwlp(C,Q).

对无循环命令,这给出最精确的安全入口条件;对带不变式的循环,验证器通常计算一个可证明的充分条件,而不是自动获得最大固定点的闭式表示。由此产生的初始化、保持与退出义务适合交给逻辑求解器检查。

wlp 也说明安全与活性为何必须分层:它对“坏结果永不出现”很自然,却无法区分正常完成与永远沉默。精化演算、程序验证器和异常逻辑若要组合这些结论,必须公开采用的是 liberal 还是 total 变换器,以及非确定选择由程序还是环境控制。

参考资料
  • Edsger W. Dijkstra, “Guarded Commands, Nondeterminacy and Formal Derivation of Programs,” Communications of the ACM 18(8), 1975, pp. 453–457。
  • Edsger W. Dijkstra, A Discipline of Programming, Prentice Hall, 1976, Chs. 1–4。
  • Ralph-Johan Back and Joakim von Wright, Refinement Calculus: A Systematic Introduction, Springer, 1998, Chs. 2–4。
  • Glynn Winskel, The Formal Semantics of Programming Languages, MIT Press, 1993, Chs. 6–7。
关系图谱5 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

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