“分离逻辑扩展可变状态语义与Hoare 三元组,框架规则是其局部性原则的集中表达。递归谓词可描述链表、树和图的堆布局。”
形式陈述 ​
分离逻辑的框架规则以Hoare 三元组写为
并带有侧条件:命令
对可能分配、释放、并发共享或通过隐藏别名访问资源的语言,侧条件与语义模型必须相应加强,不能只做表面变量名检查。
直觉
框架规则把“这段代码没有碰其余内存”从每个证明中的重复劳动提升为一条通用推理原则。先在最小堆片段上验证命令,再把无关资源同时附加到前后条件;星号保证两部分互不重叠,局部性保证命令不会越界触碰框外。它像在照片上给不相关区域加一个固定边框,但前提是被验证的操作真的只作用于自己的区域。若存在隐藏别名,所谓“框外”其实可能被命令访问,规则便不能应用。
例子与边界
由
可推出
这里分离合取保证
边界是把 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。