Skip to content

定义Definition

系统精化关系

施工中 · 内容逐步修订

Refinement relation · System refinement · Specification refinement

以行为包含、模拟或表示映射约束实现,使其允许行为不超出规格。

形式陈述 ​

先固定精化方向 ​

设规格 S 允许行为集合 B(S),实现 I 允许行为集合 B(I)。本页采用

I⊑S⟺B(I)⊆B(S),

读作“实现精化规格”。实现可以消除规格中的非确定选择、补充内部细节,却不能增加规格禁止的可观察行为。

有些文献把符号方向反过来,因此任何精化定理都应同时写出集合包含或匹配条件。只说“更精”而不说明哪一边允许行为更少,会在传递证明和接口替换中产生方向错误。

若规格性质 φ 对行为集合按子集封闭,且 S⊨φ,则 I⊑S 推出 I⊨φ。这与语义蕴涵的结构相同:所有实现行为都落在规格模型允许的范围内。

用模拟证明精化 ​

直接比较无限行为集合通常困难。可建立表示关系 R,把每个具体实现状态关联到抽象规格状态,再证明模拟:初始状态被覆盖,每个实现步骤都由规格的一个可见步骤或若干允许的内部步骤匹配。

考虑一个抽象非负整数计数器,动作 inc 使值加一。实现用可扩展的二进制位数组保存值,并用多步 carry 传播完成一次 inc。具体状态还须包含操作阶段和已提交值;只把正在改写的位数组解释为整数,通常不能作为整个操作期间的表示函数。

例如 011 加一时,工作数组可能依次为 010,000,100;若直接读取工作数组,抽象值就经历 3,2,0,4,不符合只允许递增的规格。可把中间写入放在不可观察的工作副本,并令表示函数 r 在提交前始终返回旧值 3,提交后返回 4。这不是仅改证明记号:实现必须确实阻止外部读到工作副本。

把内部 carry 步标作 τ、最终提交步对应抽象 inc 后,证明责任才成为:内部步保持 r;一次提交使 r(c′)=r(c)+1;合法初态映射到规格初态。固定宽度实现还需改成模计数规格或限制输入,否则溢出本身就是精化反例。

仅验证最终几个测试值相等不足以证明精化。还要覆盖溢出、非法位模式、执行中途被观察以及实现非确定调度等边界。

直觉

数据精化与操作责任 ​

状态表示改变时,常用 abstraction function α:C→A 或关系 R⊆C×A。每个具体操作 opC 必须与抽象操作 opA 交换到允许误差内,可写成

R(c,a)∧c→opCc′⟹∃a′,a⇒opAa′∧R(c′,a′).

此外还需 initialization 与 finalization:具体初态对应抽象初态,具体输出经观察函数得到规格允许的结果。忽略输出映射可能让内部状态匹配正确,却向用户返回错误值。

操作前置条件也不能被实现悄悄加强。若规格允许所有非空队列执行 dequeue,实现只能在长度至少二时成功,就减少了调用者受保证的输入范围,通常不构成可替换精化。

系统精化:实现行为包含于规格行为
例子与边界

添加细节不等于添加行为 ​

实现把一个抽象原子动作细分成多个内部步骤,是添加状态和路径细节;只要这些步骤不可观察且不引入新可见结果,仍可能缩小或保持可见行为集合。

相反,给接口增加一个可见错误返回看似“说明得更详细”,却可能增加规格没有允许的 trace。细节多寡是表示层概念,精化方向由可观察行为包含决定。

消除非确定性通常是合法精化。例如规格允许选择红或蓝,实现固定选择红,行为集合变小。对“每条完整执行最终返回结果”这类全称轨迹性质,只要行为集合确实包含无限执行并保持包含关系,删除选择仍会保持性质。对“仍存在一条选择蓝色的路径”则不同:它要求保留某个可能性,单纯行为包含并不保证它。

推论与应用

组合与边界 ​

精化若是预序,应满足自反和传递,使多阶段开发可以串联。要在组件上下文中替换实现,还需 congruence:若 I⊑S,是否对所有环境 E 都有 E[I]⊑E[S]。环境能观察内部时间、故障或资源时,原观察接口可能不够。

只比较有限可见 trace 时,活性或公平性可能丢失。实现可插入无限内部循环,使每个有限可见前缀都合法,却永远不完成规格承诺。若比较对象已经包含完整无限行为,并且性质是逐行为的全称条件,集合包含本身仍保持该性质;失效来自有限观察隐藏了发散,或公平路径的定义没有随精化正确对应。发散敏感的精化要显式处理这一证明义务。

精化证明也不自动连接到机器代码。若只证明高级模型之间的关系,还需编译器正确性、运行时假设或验证提取链才能把结论传到底层实现。

接口版本演进还要固定观察者能力。旧规格若保证调用 read 不改变状态,新实现增加缓存计数器但计数器不可见,仍可能精化;一旦监控接口暴露该计数器,相同内部步成为可见行为,原证明关系便需重做。这不是兼容层问题,而是行为字母表改变后精化命题本身改变。

精化结论因此总是相对于一份明确的观察契约。

参考资料
  • Carroll Morgan, Programming from Specifications, 2nd ed., Prentice Hall, 1994, Chs. 1–5。
  • J. M. Spivey, The Z Notation: A Reference Manual, 2nd ed., Prentice Hall, 1992, Chs. 5, 17。
  • Nancy A. Lynch and Frits W. Vaandrager, “Forward and Backward Simulations,” Information and Computation 121(2), 1995, pp. 214–233。
关系图谱17 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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

使用的工具