“无循环片段可沿 最弱自由前置条件 逆向计算。赋值返回 $(Q[E/x],\varnothing)$;顺序 $C 1;C 2$ 先处理 $C 2$,再把得到的入口条件交给 $C 1$;条件分支…”
形式陈述 ​
设命令
量词只约束终止结果:如果某条执行永不终止,它不会单独使公式为假。在 demonic 非确定语义下,“所有终止结果”覆盖每个可能分支;若还要求所有最大执行都终止,才得到 最弱前置条件 的总正确性口径。令
因而总有
赋值、顺序和条件的逆向方程与总正确性变换器表面相同,例如
差别在循环固定点。令
把谓词视为状态集合并按包含排序时,while B do C 的 wlp 是单调算子
直觉
“liberal”不是降低后置条件,而是拒绝在同一个判断里承诺终止。它问的是:如果程序有一天返回,返回状态会不会违反
最大不动点给出一个可靠的方向检查。对 while true do skip,无论后置条件是什么都没有终止结果,所以每个初态都满足 wlp;全集正是相应循环方程的最大解。若误取最小解,会把这个程序的 wlp 算成空集,悄悄把终止要求塞回部分正确性。
例子与边界
考虑整数程序
if x = 0 then
while true do skip
else
y := x
后置条件为
这两个结果的差异完全来自终止量词,而不是赋值规则。
对 demonic 选择 skip [] diverge,若当前状态满足
异常和 stuck 也必须分类。若除零被定义为错误终态,它应由单独的异常后置或安全条件约束;若把它误当作非终止,wlp 会平白放过内存错误。文献有时用
推论与应用
Hoare 部分正确性目标可改写为
对无循环命令,这给出最精确的安全入口条件;对带不变式的循环,验证器通常计算一个可证明的充分条件,而不是自动获得最大固定点的闭式表示。由此产生的初始化、保持与退出义务适合交给逻辑求解器检查。
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。