Skip to content

框架规则

Frame rule

若命令不修改额外资源,则可把该资源同时附加到前置和后置断言。

条目类型
定理

形式陈述

分离逻辑的框架规则以Hoare 三元组写为

{P} C {Q}{PR} C {QR},

并带有侧条件:命令 C 不修改断言 R 中自由出现的程序变量;在堆语义中,PR 还保证 C 所需资源与框住资源不相交。规则依赖命令具有局部性:在较大堆上执行时,其对额外不相交堆的行为与在最小所需堆上一致。

对可能分配、释放、并发共享或通过隐藏别名访问资源的语言,侧条件与语义模型必须相应加强,不能只做表面变量名检查。

直觉

框架规则把“这段代码没有碰其余内存”从每个证明中的重复劳动提升为一条通用推理原则。先在最小堆片段上验证命令,再把无关资源同时附加到前后条件;星号保证两部分互不重叠,局部性保证命令不会越界触碰框外。它像在照片上给不相关区域加一个固定边框,但前提是被验证的操作真的只作用于自己的区域。若存在隐藏别名,所谓“框外”其实可能被命令访问,规则便不能应用。

例子与边界

{xn} [x]:=n+1 {xn+1}

可推出

{(xn)(ym)} [x]:=n+1 {(xn+1)(ym)}.

这里分离合取保证 xy,所以对 x 的写入不影响 y

边界是把 R 取成另一个关于同一位置的断言,或命令通过别名实际能访问 R 的资源;此时前置条件可能不可满足,或局部性假设被破坏。命令若修改普通变量 z,也不能框入依赖 z 旧值的断言而不检查侧条件。

推论与应用

框架规则是分离逻辑相对传统公理语义的关键增益:函数规格只需写触及的资源,调用点可自动保留更大上下文。它使链表库、内存分配器和模块化数据结构证明能够组合。

并发分离逻辑把同一思想扩展为线程资源拆分与共享不变量;分离逻辑自动化则通过 entailment、frame inference 或 bi-abduction 推断调用前后未显式写出的剩余堆。语义框架规则说明何种资源可可靠保留,推断算法负责寻找具体的 frame;算法返回候选并不免除别名、局部性和侧条件检查。

参考资料
  • John C. Reynolds, Separation Logic: A Logic for Shared Mutable Data Structures, LICS 2002,pp. 55–74。
  • Peter W. O'Hearn, Separation Logic, Communications of the ACM 62(2), 2019,pp. 86–95。
关系图谱8 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

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

被这些条目使用