形状图理论的定理证明

《形状图理论的定理证明》由会员分享，可在线阅读，更多相关《形状图理论的定理证明（21页珍藏版）》请在金锄头文库上搜索。

1、书书书第 卷第 期 年 月计 算 机 学 报 收 稿 日 期： ；在 线 出 版 日 期： 本 课 题 得 到 国 家“八 六 三”高 技 术 研 究 发 展 计 划 项 目 基 金（ ） 、国 家 自 然科 学 基 金（ ， ）资 助张昱，女， 生，博 士，副 教 授，中 国 计 算 机 学 会（ ）高 级 会 员，主 要 研 究 方 向 为 程 序 设 计 语言 的 理 论 和 实 现 技 术、程 序 验 证、确 定 性 并 行 编 程 模 型 与 运 行 时 系 统 ： 陈 意 云，男， 年 生，教 授，博 士生 导 师，中 国 计 算 机 学 会（ ）高 级 会 员，主 要 研 究 领

2、 域 为 程 序 设 计 语 言 的 理 论 和 实 现 技 术、程 序 验 证、软 件 安 全 等李 兆 鹏，男， 年生，博 士，副 研 究 员，中 国 计 算 机 学 会（ ）会 员，主 要 研 究 方 向 为 程 序 语 言、程 序 验 证、出 具 证 明 的 编 译 器、自 动 定 理 证 明形 状 图 理 论 的 定 理 证 明张昱陈 意 云李 兆 鹏（中 国 科 学 技 术 大 学 计 算 机 科 学 与 技 术 学 院合 肥 ）（中 国 科 学 技 术 大 学 苏 州 研 究 院 软 件 安 全 实 验 室江 苏 苏 州 ）摘要验 证 操 作 易 变 数 据 结 构 的 指 针

3、程 序 仍 面 临 很 多 挑 战数 据 结 构 中 严 重 的 指 针 别 名 显 著 地 复 杂 化 对 操 作 这些 结 构 的 程 序 的 推 理为 分 析 和 验 证 操 作 易 变 数 据 结 构 的 指 针 程 序，文 中 提 出 了 形 状 图 逻 辑形 状 图 是 描 述 程 序 中静 态 声 明 的 堆 指 针 变 量 和 动 态 分 配 的 结 构 体 中 指 针 域 变 量 的 指 向 的 一 种 有 向 图，能 准 确 表 达 指 针 的 有 效 性 和 指 针之 间 的 相 等 性，可 用 于 判 断 两 个 访 问 表 达 式 是 否 是 别 名形 状 图 逻 辑

4、 是 逻 辑 的 一 种 扩 展，是 一 种 直 接 将 形 状图 作 为 程 序 中 指 针 断 言 集 的 程 序 逻 辑该 文 研 究 形 状 图 的 等 价 理 论 和 蕴 含 理 论 以 及 它 们 的 判 定 方 法 和 应 用首 先，把 形 状 图 及 其 等 价 规 则 和 蕴 含 规 则 分 别 类 比 为 代 数 项 及 其 等 式 规 则 和 重 写 规 则，像 研 究 代 数 规 范 的 理 论 那 样 来 研究 形 状 图 理 论该 文 定 义 了 形 状 图 的 语 法 理 论 和 语 义 理 论，定 义 了 形 状 图 重 写 系 统 及 其 终 止 性、局 部

5、合 流 性 和 合 流性，然 后 得 到 基 于 形 状 图 重 写 的 形 状 图 等 价 判 定 和 蕴 含 判 定 的 方 法其 次，提 出 循 环 不 变 形 状 图 和 递 归 函 数 前 后 形状 图 的 自 动 推 断 方 法借 助 形 状 图 理 论 的 判 定 方 法，该 文 把 一 个 基 于 抽 象 解 释 的 推 断 循 环 不 变 式 的 一 般 方 法 改 编成 推 断 循 环 不 变 形 状 图 的 方 法由 于 计 算 终 止 的 递 归 函 数 总 有 非 递 归 的 出 口，可 以 先 通 过 非 递 归 路 径 得 到 函 数 的后 形 状 图 的 初 值

6、，然 后 再 在 递 归 路 径 上 迭 代 求 解从 而，可 以 像 推 断 循 环 不 变 形 状 图 那 样 来 推 断 递 归 函 数 的 前 后 形状 图第 三，参 照 框 架，提 出 形 状 图 理 论 和 整 数 理 论 组 合 的 一 种 判 定 方 法对 易 变 数 据 结 构，除 了 关心 数 据 结 构 各 节 点 是 否 连 成 预 定 的 形 状 外，往 往 还 关 心 数 据 在 这 些 节 点 间 的 排 列 等 特 性，它 们 不 能 脱 离 易 变 数 据结 构 的 形 状 特 征 而 单 独 验 证为 此，所 提 出 的 组 合 判 定 方 法 针 对 这

7、类 程 序 的 验 证 条 件 的 特 点，利 用 程 序 分 析 阶 段 得到 的 形 状 图 对 验 证 条 件 的 前 件 中 的 符 号 断 言 按 形 状 图 的 节 点 分 组；然 后 运 用 整 数 理 论 为 各 节 点 推 导 出 尽 可 能 多 的性 质；最 后 才 交 由 定 理 证 明 器 去 自 动 验 证这 种 方 式 有 效 地 避 免 验 证 条 件 证 明 过 程 的 不 终 止基 于 形 状 图 逻 辑以 及 文 中 的 工 作，我 们 所 开 发 的 程 序 验 证 系 统 原 型 减 轻 了 自 动 定 理 证 明 器 的 负 担，并 且 能 验 证 易

8、 变 数 据 结 构 上 较为 复 杂 的 程 序，如 有 序 循 环 双 向 链 表、二 叉 排 序 树、伸 展 树、树 堆、二 叉 平 衡 树 和 树 的 插 入 和 删 除 函 数关 键 词形 状 图 逻 辑；形 状 分 析；程 序 验 证；自 动 定 理 证 明；循 环 不 变 式 的 推 断中 图 法 分 类 号 犇 犗 犐号 犜 犺 犲 狅 狉 犲 犿 犘 狉 狅 狏犻 狀 犵 犳 狅 狉 犪 犜 犺 犲 狅 狉 狔 狅 犳 犛 犺 犪 狆 犲 犌 狉 犪 狆 犺 狊 （犛 犮 犺 狅 狅 犾 狅 犳 犆 狅 犿 狆 狌 狋犲 狉 犛 犮犻犲 狀 犮 犲 犪 狀 犱 犜 犲 犮 犺

9、 狀 狅 犾 狅 犵 狔，犝 狀 犻 狏 犲 狉 狊犻狋 狔 狅 犳 犛 犮犻犲 狀 犮 犲 犪 狀 犱 犜 犲 犮 犺 狀 狅 犾 狅 犵 狔 狅 犳 犆 犺 犻 狀 犪，犎 犲 犳 犲犻 ）（犛 狅 犳 狋 狑 犪 狉犲 犛 犲犮 狌 狉犻狋 狔 犔 犪 犫 狅 狉 犪狋狅 狉 狔，犛 狌 狕 犺 狅 狌 犐 狀 狊狋犻狋 狌 狋犲 犳 狅 狉 犃 犱 狏 犪 狀 犮犲 犱 犛 狋 狌 犱 狔，犝 狀犻 狏 犲 狉狊犻狋 狔 狅 犳 犛 犮犻犲 狀 犮犲 犪 狀 犱 犜 犲犮 犺 狀 狅犾狅 犵 狔 狅 犳 犆 犺 犻 狀 犪，犛 狌 狕 犺 狅 狌，犑 犻 犪 狀 犵 狊 狌 ）犃 犫

10、狊狋狉 犪 犮狋 ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， ； ； ， ， ， ， ， ， ， 犓 犲 狔 狑 狅 狉 犱 狊 ； ； ； ； 引言形 式 验 证（包 括 抽 象 解 释、模 型 检 测 和 演 绎 验 证等 途 径）是 提 高 软 件 可 信 程 度 的 重 要 方 法，并 在 工 业界 已 经 逐 步 得 到 应 用，尤 其 是 抽 象 解 释 和 模 型 检 测例 如，空 客 公 司 在 军 用 运 输 机 以 及 和 客 机 的 开 发 上，已 经 用 形 式 验 证 取 代 了 部 分 安全 攸 关 嵌 入 式 软 件

11、 的 测 试和 单 元 测 试 相 比，单 元 证明 降 低 了 投 入，主 要 是 因 为 它 方 便 了 维 护演 绎 验证 在 工 业 界 的 应 用 虽 有 限 但 也 在 拓 展，达 索 航 空 公司 在 健 壮 性 的 形 式 验 证 方 面，已 有 约 的 断 言 是用 演 绎 验 证 方 式 证 明 的在 演 绎 验 证 方 法 中，有 关 自 动 程 序 验 证 的 大 部分 研 究 按 这 样 的 途 径 开 展：程 序 员 提 供 函 数 前 后 条件 和 循 环 不 变 式，系 统 对 程 序 采 用 某 种 正 向 或 逆 向 期张昱 等：形 状 图 理 论 的 定

12、理 证 明的 演 算 来 产 生 验 证 条 件（即 把 对 程 序 满 足 某 些 性 质的 证 明 转 化 为 对 一 些 验 证 条 件 的 证 明） ，然 后 用 自 动定 理 证 明 器 来 证 明 验 证 条 件，如 、 和 有 些 研 究 依 靠 符 号 计 算 及 其 过 程 中的 定 理 证 明 来 避 免 验 证 条 件 的 生 成，如 和 无 论 用 哪 种 策 略，演 绎 验 证 方 法 都 使 用严 谨 的 方 式 对 软 件 系 统 进 行 数 学 推 理，并 且 都 借 助定 理 证 明 软 件，如 定 理 证 明 器 、定理 证 明 辅 助 工 具 、 （ ）求

13、 解 器 基 于 演 绎 推 理 的 自 动 形 式 验 证 方 法 对 自 动 定 理证 明 器 的 能 力 有 较 高 期 待首 先，定 理 证 明 器 在 程 序验 证 过 程 中 频 繁 使 用大 到 验 证 条 件 的 证 明 和 循 环不 变 式 的 推 断，小 到 下 标 变 量 的 别 名 判 断 和 数 组 边界 检 查，都 需 要 或 可 以 使 用 定 理 证 明 器其 次，需 要能 够 应 对 各 种 领 域 专 用 逻 辑 的 定 理 证 明应 用 程 序的 代 码 中 可 能 涉 及 多 种 数 据 类 型，操 作 系 统 的 代 码依 赖 于 硬 件 特 性，为

14、完 成 对 这 些 程 序 的 验 证，需 要 定理 证 明 器 能 够 覆 盖 这 些 领 域 专 用 逻 辑 的 定 理 证 明第 三，需 要 定 理 证 明 器 能 处 理 各 种 理 论 的 组 合例 如面 向 数 组 类 型 的 数 组 逻 辑，它 由 下 标 逻 辑 和 元 素 逻辑 组 成对 于 操 作 数 组 的 程 序 的 验 证，定 理 证 明 器 要能 证 明 这 两 种 逻 辑 的 相 应 理 论（可 能 还 包 括 等 式 理论 和 未 解 释 函 数 理 论）组 合 后 形 成 的 组 合 理 论 上 的定 理组 合 理 论 的 问 题 复 杂 性 在 于：即 使

15、两 个 理 论 分别 可 判 定，其 组 合 理 论 未 必 可 判 定数 组 理 论 就 是这 样 的 例 子本 文 研 究 操 作 易 变 数 据 结 构（包 括 单双 向 链表、循 环 单双 向 链 表和 二 叉 链 表 示 的 二 叉 树）的指 针 程 序 的 自 动 验 证 中 的 一 些 定 理 证 明 问 题这 类程 序 的 验 证 非 常 困 难首 先，难 以 给 出 表 达 程 序 性 质的 函 数 前 后 条 件，尤 其 是 循 环 不 变 式因 为 它 们 涉 及所 操 作 的 数 据 结 构 的 结 构 性 质（常 使 用 带 量 词 的 命题 和 可 达 性 谓 词

16、来 表 达）以 及 在 数 据 结 构 中 各 节 点内 的 数 据 的 性 质，而 后 者 的 描 述 可 能 紧 密 依 赖 于 数据 结 构 的 结 构 性 质，例 如 平 衡 二 叉 树 节 点 的 平 衡 因子 和 树 节 点 的 值其 次，难 以 证 明 这 类 程序 的 验 证 条 件，因 为 在 验 证 条 件 中 经 常 出 现 对 数 据结 构 所 有 节 点 的 某 种 全 称 量 化这 导 致 不 能 使 用 像 框 架这 样 仅 适 用 于 无 量 词 理 论 的传 统 的 理 论 组 合 虽 然 通 过 使 用 匹 配 技术 能 够 处 理 量 化 公 式，但 也

17、难 以 适 应 复 杂 的 量 化 公式除 了 要 用 量 词 刻 画 性 质 以 及 涉 及 的 理 论 组 合 之外，验 证 条 件 的 证 明 可 能 还 要 用 到 数 据 结 构 的 归 纳理 论例 如，对 于 用 根 节 点 的 中 序 前 驱（其 左 子 树 中最 右 下 的 节 点）代 替 根 节 点 的、删 除 二 叉 排 序 树 根 节点 的 函 数，若 要 证 明 结 果 仍 然 是 二 叉 排 序 树，则 需 要用 到 二 叉 排 序 树 的 两 个 性 质：左 子 树 中 任 何 节 点 的值 一 定 小 于 右 子 树 中 各 节 点 的 值，左 子 树 中 最 右

18、 下节 点 的 值 大 于 左 子 树 中 其 他 节 点 的 任 何 值它 们 都是 二 叉 排 序 树 的 归 纳 性 质，但 是 基 于 演 绎 推 理 的 自动 定 理 证 明 器 不 可 能 从 二 叉 排 序 树 的 归 纳 定 义 推 导出 这 些 性 质，因 而 无 法 证 明 依 赖 这 些 性 质 的 验 证条 件为 验 证 操 作 易 变 数 据 结 构 的 指 针 程 序，我 们 提出 了 形 状 图 逻 辑 形 状 图 是 描 述 程 序 所 操 作 的 静态 声 明 的 指 针 型 变 量（简 称 声 明 指 针）和 动 态 分 配 的结 构 体 中 指 针 型 域

19、 变 量（简 称 域 指 针）的 指 向 的 一 种有 向 图它 准 确 表 达 了 指 针 的 有 效 性（指 针 有 效 是 说该 指 针 指 向 已 分 配 且 尚 未 释 放 的 内 存 块）和 指 针 的相 等 性，因 而 可 作 为 指 针 程 序 中 指 针 有 效 性 和 相 等性 的 断 言形 状 图 逻 辑 就 是 一 种 直 接 把 形 状 图 作 为程 序 中 指 针 断 言 集 的 程 序 逻 辑它 是 逻 辑 的一 种 扩 展，为 指 针 操 作 语 句 设 计 了 专 门 的 推 理 规 则，这 些 规 则 用 图 形 方 式 描 述 指 针 操 作 语 句 引

20、起 的 形 状图 上 被 关 注 部 分 的 变 化利 用 形 状 图 还 可 以 方 便 地消 除 访 问 路 径 别 名，使 易 变 数 据 结 构 上 数 据 性 质 的验 证 仍 可 用 逻 辑 的 规 则 进 行 推 理本 文 补 足 文 献 所 缺 少 的 部 分 理 论 和 算 法文 献 主 要 围 绕 程 序 逻 辑 层 面，提 出 把 形 状 图 作为 指 针 断 言，并 在 此 基 础 上 设 计 了 推 理 指 针 程 序 的形 状 图 逻 辑 和 检 查 形 状 合 法 性 的 形 状 系 统本 文 围绕 作 为 指 针 断 言 的 形 状 图，研 究 形 状 图 的

21、等 价 理 论和 蕴 涵 理 论 以 及 它 们 的 判 定 方 法 和 应 用本 文 的 贡献 有 如 下点：（）提 出 形 状 图 理 论 的 一 种 判 定 方 法本 文 把 形 状 图 及 其 等 价 规 则 和 蕴 涵 规 则 分 别 类比 为 代 数 项 及 其 等 式 规 则 和 重 写 规 则，像 研 究 代 数规 范 的 理 论 那 样 来 研 究 形 状 图 理 论本 文 类 似 地 定义 形 状 图 的 语 法 理 论 和 语 义 理 论，定 义 形 状 图 重写 系 统 及 其 终 止 性、局 部 合 流 性 和 合 流 性，最 后 得 到基 于 形 状 图 重 写 的

22、 形 状 图 等 价 判 定 和 蕴 涵 判 定 的方 法（）提 出 循 环 不 变 形 状 图 和 递 归 函 数 前 后 形 状计 算 机 学 报 年 （ ） ， ： 本 文 用“单双 向 链 表”表 示 非 循 环 的 单双 向 链 表，用“ （循环）单双 向 链 表”表 示 循 环 和或 非 循 环 的 单双 向 链 表图 的 自 动 推 断 算 法借 助 形 状 图 理 论 的 判 定 方 法，本 文 把 一 个 通 过迭 代 推 断 循 环 不 变 式 的 一 般 方 法 改 编 成 一 个 推断 循 环 不 变 形 状 图 的 方 法；进 一 步 设 计 该 方 法 的 一个 变

23、 种 来 迭 代 推 断 递 归 函 数 的 前 后 形 状 图（）提 出 形 状 图 理 论 和 整 数 理 论 组 合 的 一 种 判定 方 法对 易 变 数 据 结 构，除 了 关 心 数 据 结 构 各 节 点 是否 连 成 预 定 的 形 状 外，往 往 还 关 心 数 据 在 这 些 节 点间 的 排 列 特 性，它 们 不 能 脱 离 易 变 数 据 结 构 的 结 构特 点 而 单 独 验 证于 是 需 要 研 究 形 状 图 理 论 和 整 数上 线 性 算 术 理 论（假 定 节 点 数 据 是 整 型）组 合 的 判 定问 题本 文 针 对 验 证 条 件 的 特 点，利

24、 用 程 序 分 析 阶 段得 到 的 形 状 图，参 照 框 架，提 出 形 状图 理 论 和 整 数 上 线 性 算 术 理 论 组 合 的 一 种 判 定 方 法本 文 第节 简 要 回 顾 文 献 提 出 的 形 状 图、形 状 图 变 换 规 则 和 形 状 图 逻 辑；第节 介 绍 形 状 图理 论 的 判 定 方 法；第节 介 绍 循 环 不 变 形 状 图 的 推断 和 递 归 函 数 前 后 形 状 图 的 推 断；第节 介 绍 形 状图 理 论 和 整 数 理 论 组 合 的 判 定 方 法；第节 是 验 证实 例；第节 是 和 相 关 研 究 工 作 的 比 较；第节 是

25、总 结 形 状 图 和 形 状 图 逻 辑 形 状 图形 状 图 是 描 述 程 序 中 静 态 声 明 指 针 和 动 态 分 配的 结 构 体 中 域 指 针 的 指 向 关 系 的 一 种 有 向 图形 状 图 的 顶 点（也 称 节 点）有种，其 图 形 化 语法 形 式 见 图 其 中 声 明 节 点 和 结 构 节 点 分 别 表 示静 态 声 明 指 针 和 动 态 分 配 的 结 构 体 节 点 和 悬空 节 点 的 用 意 稍 后 会 提 到图 形 状 图 的 各 种 节 点浓 缩 节 点 是 若 干 个 结 构 节 点 和 它 们 之 间 的 有 向边 的 浓 缩 表 示，

26、其 灰 色 矩 形 下 侧 的 表 达 式和 断 言分 别 表 示 被 浓 缩 的 结 构 节 点 的 个 数 以 及 对的 取值 范 围 的 约 束若 灰 色 矩 形 下 无和，称 为 无 约 束浓 缩 节 点，它 表 示 被 浓 缩 的 结 构 节 点 个 数 任 意，可 以是个谓 词 节 点 代 表 满 足 指 定 谓 词 的 若 干 节 点 和 它 们之 间 的 有 向 边，其 矩 形 节 点 下 侧 标 有 谓 词 名 ，还 可 能 有 与 浓 缩 节 点 含 义 一 致 的 表 达 式和 断 言 指 向 谓 词 节 点 的 有 向 边 以 及 该 节 点 下 侧 的和是 该 节 点

27、 所 代 表 的 谓 词 的 变 元，例 如 图给 出 了 几种 用 形 状 图 定 义 的 数 据 结 构，以 单 链 表 为 例，图 中 谓词 节 点 的 变 元 和 左 侧 的 符 号 谓 词 （，）的 变 元是 一 致 的图 形 状 谓 词 定 义 的 一 些 例 子形 状 图 中 的 有 向 边 表 示 声 明 指 针 和 域 指 针 的 指向，指 向 同 一 个 节 点（悬 空 节 点 除 外）的 指 针 相 等有向 边 及 其 连 接 的 节 点 满 足 如 下 语 法 约 束：（）声 明 节 点只 有 唯 一 的 出 边，没 有 入 边，出边 的 标 记 就 是 声 明 指 针

28、 名（）结 构 节 点 和 浓 缩 节 点有 入 边 和 出 边，其 中出 边 的 条 数 与 结 构 节 点 所 代 表 的 结 构 体 的 域 指 针 个数 一 致，各 出 边 的 标 记 分 别 是 各 域 指 针 名（） 节 点、悬 空 节 点 和 谓 词 节 点有 入 边，没有 出 边 节 点 和 悬 空 节 点 分 别 用 来 表 示 指 向 它们 的 有 向 边 代 表 指 针 和 悬 空 指 针形 状 图 的 定 义： （）节 点 和 有 向 边 满 足 上 述 语法 约 束，各 声 明 节 点 出 边 标 记 相 异，且 边 被 视 为 无 向时 则 连 通 的 图 形 是

29、形 状 图； （）若 形 状 图犌，犌， ，犌狀的 声 明 节 点 出 边 标 记 集 两 两 相 交 都 为 空，则 由 逻辑 合 取 符 号连 接 的犌犌犌狀也 是 形 状 图 期张昱 等：形 状 图 理 论 的 定 理 证 明其 中，不 含 符 号的 形 状 图犌被 称 为 形 状 子 图；（）若 形 状 图犌，犌， ，犌狀的 声 明 节 点 出 边 标 记 集都 相 同，则 逻 辑 析 取 符 号连 接 的犌犌犌狀也 是 形 状 图从 文 献 有 关 形 状 图 的 语 义 知 道，一 个 不 含析 取 符 号 并 且 没 有 浓 缩 节 点 和 谓 词 节 点 的 形 状 图 是程

30、序 状 态 中 指 针 型 数 据 的 图 形 表 示，不 含 析 取 符 号的 一 般 形 状 图犌则 是 程 序 状 态 集 的 图 形 表 示犌犌中 的犌和犌各 代 表 程 序 状 态 的 不 同 部 分犌犌中 的犌和犌则 代 表 不 同 的 程 序 状 态 集若 无 特别 说 明，符 号犌仅 表 示 不 含 符 号的 形 状 图图给 出 基 于 形 状 图 定 义 的 单 链 表（域 指 针 是 下 文 或 的 简 称，本 文 不 区 分 这个 名 称） 、双 向 链 表 和 二 叉 链 表 示 的 二 叉 树（系 统 还 支 持 的 循环 单 链 表 和 循 环 双 向 链 表 的

31、定 义 见 文 献 ）在图中，定 义 式 最 左 边 的 （，）等 符 号 表 示 是为 了 便 于 在 文 中 引 用可 以 看 出，把 （，）的个 定 义 中 的和部 分 略 去，再 用 符 号连 接 它们，就 得 到 （）的 定 义若 用 符 号 谓 词 表 示，图的 二 叉 树 定 义 相 当 于 （） ！ （ ） （ ）一 个 形 状 图 的 某 形 状 子 图 中 用 点 划 线 方 框 标 明并 满 足 下 面 条 件 的 部 分 称 为 窗 口，窗 口 描 述 形 状 子图 上 被 关 注 的 那 部 分，形 状 图 的 其 余 部 分 称 为 窗 口的 上 下 文（）形 状

32、图 的 各 节 点 处 于 窗 口 内 或 上 下 文 中，不 得 与 窗 口 的 方 框 边 界 相 交（）窗 口 内 各 节 点 之 间 的 边 都 位 于 窗 口 中（）表 达 窗 口 中 节 点 与 上 下 文 中 节 点 联 系 的、穿 越 方 框 边 界 的 边 属 于 窗 口，这 些 边 的 另 一 份 副 本在 上 下 文 中窗 口犠和 上 下 文犌 的 匹 配 就 是 检 查 穿 越犠边 界 的 边 和犌 中 的 副 本 边 能 否 重 合，重 合 后 得 到的 形 状 图 用犌犠表 示在 形 状 图 变 换 规 则 中 出 现 的 窗 口 有 如 下 的 缩 写约 定：对

33、窗 口 中 的 某 节 点 而 言，若 要 求 从 窗 口 外 指 向该 节 点 至 少 要 有 一 条 边（如 图的狆） ，则 可 能 还 有的、指 向 该 节 点 的 其 他 边（可 以 是条）用 一 条 标 记为狆犽的 边 统 一 表 示 窗 口 用 来 定 义 形 状 图 的 等 价 规 则 和 蕴 涵 规 则（见 文 献 的 节）及 形 状 图 逻 辑 的 推 理 规 则（见 文 献 的 节）图 （循 环）单 链 表 的 等 价 规 则 的个 例 子 形 状 图 的 等 价 和 蕴 涵 规 则等 价 规 则 是 保 持 形 状 图 语 义 等 价 的 变 换 规 则图列 出 了 在

34、文 献 的 节 中 定 义 的（循 环）单链 表 的 部 分 等 价 规 则第节 还 会 列 举 一 些 等 价规 则除 了 等 价 规 则 外，形 状 图 还 有 蕴 涵 规 则，蕴 涵 规则 是 保 持 形 状 图 语 义 蕴 涵 的 变 换 规 则文 献 中 节 定 义 的 形 状 图 蕴 涵 规 则 分 成 三 部 分（）从 等 价 规 则犠犠犠可 得犠犠和犠犠两 条 蕴 涵 规 则例 如，从 图（）的 等 价 规 则可 以 得 到 两 条 蕴 涵 规 则（）若 等 价 规 则犠犠的 副 条 件 是（ （ ） ）（ （ ） ） ，则 有 蕴 涵 规则犠犠和犠犠，其 副 条 件 分 别

35、是（ （ ） ） 和（ （ ） ） 例 如，从 图的 每 条 等 价 规 则 都 可 得 到 两 条 蕴 涵 规 则图 对 浓 缩 节 点 的 约 束 数 据 进 行 变 换 的 部 分 等 价 规 则（）将 等 价 规 则 中 有 约 束 浓 缩 节 点 改 成 无 约 束浓 缩 节 点 而 得 到 蕴 涵 规 则例 如，图中 蕴 涵 规 则计 算 机 学 报 年（）和（）分 别 从 等 价 规 则（）和（）得 到蕴 涵 方 向的 选 择（称 为 定 向）取 决 于 规 则 的 左 右 两 边 谁 蕴 涵谁以 浓 缩 节 点 所 代 表 的 结 构 节 点 的 个 数狀来 直 观解 释， （

36、）和（）的 定 向 分 别 基 于狀 狀 和狀 狀 图 从 等 价 规 则 得 到 的 蕴 涵 规 则 形 状 图 逻 辑 的 推 理 规 则在 形 状 图 逻 辑 中，有 关 指 针 操 作 语 句 的 推 理 规则 都 是 相 应 语 句 操 作 语 义 的 图 形 表 示因 为 推 理 规则 体 现 语 句 执 行 前 后 形 状 图 的 变 化，而 形 状 图 是 程序 状 态 的 图 形 表 示，因 此 形 状 图 的 变 化 自 然 就 是 相应 语 句 引 起 的 程 序 状 态 变 化这 里 以 指 针 赋 值 语 句狌狏的 部 分 推 理 规 则 为例，介 绍 形 状 图 逻

37、 辑 中 指 针 操 作 语 句 的 推 理 规 则其中狌、狏代 表 从 声 明 指 针 名 出 发、经 若 干 条 域 指 针 边组 成 的 访 问 路 径，如狇或狆 图是狌指 向 节 点、狏指 向（循 环）单 链 表结 构 节 点 时 的 推 理 规 则（狏指 向 浓 缩 或 谓 词 节 点 的规 则 类 似）从 赋 值 前 形 状 图犌到 赋 值 后 形 状 图犌 的 变 化 就 是 让狌也 指 向狏原 来 指 向 的 节 点图花括 号 中 的 不 是 形 状 图，而 只 是 其 中 被 所 关 注 的 若 干个 窗 口若 图中 的个 窗 口 自 左 向 右 依 次 用犠 、犠 、犠 和

38、犠 表 示，则 对 任 意 能 够 使犌犠 ，犠 成 为 形 状 图 的 上 下 文犌 ，有 推 理 规 则犌犠 ，犠 狌狏犌犠 ，犠 其 中犌犠 ，犠 上 的 窗 口犠 和犠 无 重 迭 部 分因 此，严 格 说 图只 是 规 则 的 窗 口 而 不 是 规 则，简 单起 见 仍 称 为 规 则图 指 针 赋 值 语 句 的 一 条 规 则 需 要 注 意 的 是，由 于狌、狏代 表 访 问 路 径，为 便 于描 述 推 理 规 则，图采 用 节 中 窗 口 概 念 的 一 种扩 展 表 示：将 标 记狌和狏等 放 在 边 的 下 方，以 表 示狌和狏等 是 访 问 路 径，而 不 是 边

39、的 标 记（边 的 标 记 放 在边 的 上 方） ；它 们 要 求 在 应 用 规 则 到 某 形 状 图 时，形状 图 上 应 有 相 应 的 访 问 路 径例 如，使 用 图的 规 则时，犌犠 ，犠 要 有 从 某 声 明 节 点 到 达犠 中 节 点 的访 问 路 径，访 问 路 径 上 各 边 的 标 记 顺 次 连 接 构 成狌图是狌指 向（循 环）单 链 表 结 构 节 点、狏指 向 节 点 时 的 推 理 规 则（狏指 向 浓 缩 或 谓 词 节 点 的规 则 也 类 似）若 赋 值 前 只 有狌指 向 结 构 节 点，则 报告 内 存 泄 漏图 指 针 赋 值 语 句 的 另

40、 一 条 规 则 图是 两 个 表 示 单 链 表 的 形 状 图假 定 指向 的 单 链 表 至 少 有 一 个 表 元，程 序 片 段 ； ； （ ！ ） ； ；的 循 环 不 变 形 状 图 就 是 图（）当 ！ 为真 进 入 循 环 时，利 用 图（）的 规 则，把 指 向 的 浓 期张昱 等：形 状 图 理 论 的 定 理 证 明缩 节 点 展 开 成 两 种 情 况，其 一 与 ！ 矛盾 被 略 去，另 一 种 情 况 就 是 图（）的 形 状 图把 语句 当 作 语 句 序 列 ； ； ； ，按 图和图的 规 则 逐 步 修 改 图（） ，其 中 是 初 值为 的 虚 拟 局 部

41、 指 针 变 量引 入 主 要是 为 了 避 免 为 某 些 特 殊 的 指 针 赋 值 情 况 设 计 复 杂 的专 用 规 则，见 文 献 的 节对 也 继 续 用 类 似 的 方 法 修 改 形 状 图，再 把 得 到 的 形 状图 用 类 似 图（）的 规 则，把 原 先 指 向 的 结 构 节点 逆 向 折 叠 进 左 边 的 浓 缩 节 点，得 到 图（）图 形 状 图 的 两 个 例 子 形 状 图 理 论 的 判 定 方 法形 状 图 的 等 价 推 理 规 则 集 由 文 献 中 节 的形 状 图 等 价 规 则（不 包 括 那 些 推 导 形 状 图 析 取犌犌的 规 则，

42、例 如 本 文 图（） ）和 任 何 等 价 推 理 系 统 都有 的 自 反、对 称 和 传 递 规 则 组 成该 规 则 集 可 用 来 证明 形 状 图 之 间 的 等 价 性若 等 价 形 状 图 的 集 合犈是 封 闭 于 可 证 明 的，即?犌犌蕴 涵犌犌?，则 把?叫 做 形 状 图 的 一个 语 法 等 价 理 论类 似 地 可 以 定 义 形 状 图 相 应 的 语义 等 价 理 论，即?犌犌蕴 涵犌犌?由 文 献 中 节 关 于 等 价 规 则 的 性 质 定 理，不 难 证 明?犌犌当 且 仅 当?犌犌类 似 地 根 据 形 状 图的 蕴 涵 规 则，可 以 定 义 形

43、状 图 的 语 法 蕴 涵 理 论 和 语 义蕴 涵 理 论 及 证 明?犌犌当 且 仅 当?犌犌本 节 介 绍 形 状 图 的 重 写 系 统 和 这 两 种 理 论 的 判定 方 法 形 状 图 的 等 价 重 写 系 统形 状 图 的 等 价 重 写 系 统 可 比 照 代 数 项 的 重 写 系统 来 讨 论它 用 于 形 状 分 析 和 验 证 过 程 中 对 形 状图 进 行 等 价 化 简形 状 图 等 价 规 则 限 制 为 单 向 后 得 到 的 蕴 涵 规 则就 是 一 条 形 状 图 重 写 规 则一 组 形 状 图 重 写 规 则 构成 一 个 形 状 图 重 写 系

44、统不 能 用 该 系 统 的 规 则 再 进行 归 约 的 形 状 图 称 为 最 简 形 状 图不 存 在 无 穷 归 约序 列 的 系 统 称 为 具 有 终 止 性 的 系 统可 以 参 照 项 重写 系 统 继 续 定 义 系 统 的 临 界 对（ ） 、局 部合 流 性 和 合 流 性仿 照 完 备 化 过 程 ，可 以 把 文献 中 节 的 等 价 规 则 集 变 换 成 一 个 与 之 等 价并 且 终 止 与 合 流 的 形 状 图 重 写 系 统?下 面 先 以 一 个 简 单 的 项 重 写 系 统 为 例 来 熟 悉 项重 写 系 统 的 一 些 概 念，然 后 说 明

45、项 重 写 和 形 状 图 重写 之 间 的 主 要 异 同例 如，代 数 等 式狓 狓，狓（狓） ， （狓狔）狕狓（狔狕）是 属 于 包 含、加 和 一 元 减 的 自 然 数 等 式 系 统 中 的等 式，把 它 们 从 左 到 右 定 向，得 到条 重 写 规 则狓 狓，狓（狓） ， （狓狔）狕狓（狔狕）项狓（狔（狔） ）的 子 项狔（狔）与 第条 规 则的 左 部 匹 配，因 此狓（狔（狔） ）可 用 第条 规 则重 写 成狓 ，再 依 据 第条 规 则 重 写 为狓不 难 证明 这条 规 则 构 成 的 重 写 系 统 是 终 止 的要 证 明 合 流 性，需 要 考 察 临 界 对

46、第条 规 则 左部 的 子 项狓狔和 该 规 则 左 部（狓狔）狕（加 撇 号以 便 区 别）合 一，得 到 临 界 对 （狓狔）（狕狕） ， （狓（狔狕） ）狕该 临 界 对 中 的 两 个 项 都 能 归 约 到狓（狔（狕狕） ）可 以 类 似 地 计 算 该 重 写 系 统 的 其 它 临 界 对 并 证 明 每一 临 界 对 中 的 两 个 项 都 能 归 约 到 同 一 个 项，所 以 该系 统 具 有 局 部 合 流 性再 由 终 止 性 可 得 该 系 统 具 有合 流 性在 上 述 项 重 写 系 统 中，规 则 的 左 部 和 右 部 都 是项，被 重 写 的 也 是 项而

47、形 状 图 系 统 与 项 重 写 系 统 相比，最 大 的 区 别 是：规 则 的 左 部 和 右 部 都 是 窗 口，被重 写 的 是 形 状 图产 生 该 区 别 的 根 源 在 于 形 状 图 是二 维 的基 于 同 样 的 原 因，合 一 和 匹 配 的 描 述 也 有 区别但 是 两 个 系 统 的 本 质 概 念 和 方 法 是 一 致 的下 面 先 给 出 节 点 相 同 和 形 状 图 相 同 的 定 义定 义 节 点狀和狀若 满 足 下 面 两 个 条 件，则称狀和狀相 同：（）狀和狀是 同 类 节 点，并 且 若 都 是 声 明 节 点、结 构 节 点 或 浓 缩 节 点

48、，则 有 同 样 的 出 边 及 其 标 记；若都 是 谓 词 节 点，则 谓 词 名 相 同（）若狀和狀是 同 类 浓 缩 节 点 或 谓 词 节 点，且分 别 带与和与，则 必 须 满 足（ ） 并 且（ ） 其 中，无 约 束 浓 缩计 算 机 学 报 年节 点 在 此 都 被 视 为 带犿与犿 的 浓 缩 节 点下面 讨 论 判 定 方 法 时 也 作 如 此 假 设定 义 形 状 子 图犌和犌若 满 足 下 面 两 个 条件，则 称犌和犌相 同（）犌和犌的 节 点 一 一 对 应（）犌和犌的 对 应 节 点 都 是 相 同 节 点，并 且 若它 们 有 出 边，则 标 记 相 同 的

49、 出 边 所 指 向 的 节 点 是 对应 节 点定 义 形 状 图犌和犌若 满 足 下 面 的 条 件，则 称犌和犌相 同犌和犌的 形 状 子 图 一 一 对 应 并 且 相 同在 从 形 状 图 的 等 价 规 则 构 造 重 写 系 统 时，可 以忽 略 如 图那 样 仅 替 换 浓 缩 节 点 的和的 那 些 等价 规 则，因 为 定 义已 把 替 换 前 后 的 浓 缩 节 点 定 义为 相 同在 完 备 化 过 程 中，文 献 中 节 的（循 环）单 链 表、 （循 环）双 向 链 表 和 二 叉 树 的 等 价 规 则 按 照节 点 数 减 少 的 方 向 定 为 重 写 规 则

50、，例 如 图的 等 价规 则（）和（）定 向 为 从 右 向 左 的 重 写 规 则规 则（）和（）其 实 是 同 一 条 规 则，只 要 把 其 中 一 条 规 则 中 边上 的 标 记和对 调 一 下 就 可 看 出，这 里 写 成 两 条图 等 价 规 则 的 一 些 例 子是 为 了 便 于 下 面 理 解 和 讨 论 临 界 对对 那 些 两 边 节点 数 相 等 的 各 种 等 价 规 则，可 按 下 面 的 方 式 之 一定 向：（）对 于个 结 构 节 点 和等 于的 浓 缩 节 点之 间 的 等 价 规 则，定 向 为 向 浓 缩 节 点 的 重 写，例 如图（）定 向 为

51、从 左 向 右按 这 个 方 向 定 向 是 便 于 若干 个 相 邻 的 结 构 节 点 归 约 成 浓 缩 节 点（）对 于 出 自 链 表 定 义 的 等 价 规 则，定 向 为 向谓 词 节 点 的 重 写，例 如 图的 规 则（）和（）定 向 为从 右 向 左形 状 图 的 归 约 一 定 会 终 止，因 为 每 次 归 约 都 会使 节 点 数 减 少 或 保 持 不 变，而 节 点 数 保 持 不 变 的 重写 情 况 受 上 面 两 条 的 限 定，因 此 归 约 一 定 会 终 止?的 合 流 性 可 以 参 照 项 重 写 系 统 合 流 性 的 证 明方 法 来 证 明首

52、 先 考 虑 临 界 对，例 如，由 图的 等 价规 则（）和（）得 到 两 条 重 写 规 则犚和犚犚和犚的 左 部（对 应 图等 价 规 则（）和（）的 右 部）经 两 种方 式 合 一，得 到个 临 界 对，分 别 是 图 的（）和（）与 图 的（）和（） ，它 们 分 别 都 能 化 简 到 相 同的 窗 口其 余 的 临 界 对 也 都 是 由 于 规 则 的 窗 口 中 有（循 环）单 链 表、 （循 环）双 向 链 表 或 二 叉 树 的 浓 缩 节点 而 产 生 的，例 如 对 应 图（）和（）的 相 应 重 写 规则 也 会 产 生个 临 界 对很 容 易 检 查 它 们 都

53、 可 归 约到 同 样 的 窗 口，因 而 证 明?是 局 部 合 流 的再 根 据?的 局 部 合 流 性 和 终 止 性 可 以 证 明?是 合 流 的图 临 界 对 的 两 个 例 子基 于 形 状 图 等 价 重 写 系 统 以 及 图这 样 的 规则，参 照 代 数 项 上 的 证 明 方 法，不 难 证 明 下 面 的定 理定 理 形 状 图犌和犌等 价，即犌犌，当 且仅 当 它 们 化 简 后 的 最 简 形 状 图犌 和犌 相 同 犌，犌，犿犌，犌，狀的 判 定 方 法抽 象 地 说，判 定犌，犌，犿犌，犌，狀可 以 先 用 节 的 等 价 重 写 系 统 把 两 边 所 有

54、的形 状 图 分 别 化 简，然 后 比 较 两 边 的 各 个 最 简 形 状 图是 否 都 能 在 对 方 找 到 相 同 的 形 状 图但 是 节 的 期张昱 等：形 状 图 理 论 的 定 理 证 明等 价 重 写 系 统 并 未 考 虑 个 数 不 同 的 形 状 图 之 间 的 等价 性，为 此 需 要 利 用 文 献 中 节 里 的犠犠犠等 价 规 则（如 图 ）展 开 形 状 图，以 期 建 立个 数 不 同 的 形 状 图 之 间 的 等 价 性结 合 应 用 场 合 的特 点，本 文 讨 论 的 等 价 式 中 各 形 状 图 的 声 明 变 量 集都 相 同，等 价 式

55、的 判 定 方 法 如 下：图 从 二 叉 树 定 义 得 到 的 等 价 规 则（）若犌，和犌，的 声 明 变 量 集 不 同 则 该 等 价式 不 成 立否 则 继 续 下 面 步 骤（）将 上 式 中 所 有 的 形 状 图，用 节 介 绍 的形 状 图 重 写 系 统 把 它 们 归 约 到 最 简 形 状 图仍 用 原来 的 符 号犌，犻（ 犻犿）或犌，犼（ 犼狀）代 表 各 形状 图 的 最 简 形 状 图（）若 某 个犌，犻（ 犻犿）的 某 条 尽 可 能 长 的 且不 经 过 浓 缩 节 点 的 访 问 路 径 是 某 个犌，犼（ 犼狀）的 某 条 不 经 过 浓 缩 节 点

56、的 访 问 路 径 的 真 前 缀，并 且若犌，犻中 的 这 条 访 问 路 径 指 向 的 节 点 可 以 用犠犠犠的 等 价 规 则 展 开，则 将 其 展 开反 之 亦 然直到 不 存 在 这 样 的 路 径 或 者 虽 存 在 但 不 能 展 开 为 止为 防 止 滥 用犠犠犠这 类 等 价 规 则，需 要从 访 问 路 径 的 比 较 上 加 以 限 制例 如，若犌，犻中 有 不能 再 延 长 的 二 叉 树 访 问 路 径狆 ，犌，犼中 有 访 问 路径狆 ，且 在犌，犻中狆 指 向 谓 词 节 点，则 可 以根 据 图 的 二 叉 树 等 价 规 则 将犌，犻展 开，其 中 等

57、价规 则 中 的是 占 位 符，可 以 通 配 访 问 路 径狆 中 的 该 规 则 由 图的 二 叉 树 定 义 得 到文 献 中 节 里 的 所 有 的犠犠犠都像 图 这 样，右 边犠或犠中 指 向 谓 词 节 点 或 浓 缩节 点 的 访 问 路 径 比犠的 多 一 个 结 构 体 的 指 针 域，因此 不 会 出 现 等 价 式 左 右 两 边 的 形 状 图 不 断 交 替 展 开而 不 终 止 的 情 况经 过 这 样 的 展 开，原 等 价 式 变 换 成犌 ，犌 ，犿 犌 ，犌 ，狀（）对 每 个犌 ，犻（ 犻犿 ） ，若 存 在 某 个犌 ，犼（ 犼狀） ，使 得犌 ，犻和犌

58、 ，犼相 同，并 且 反 之 亦 然，则犌，犌，犿犌，犌，狀，否 则 该 式 不 成 立显 然，若 上 述 方 法 中 涉 及 的 由 整 型 线 性 表 达 式之 间 的 关 系 式 所 构 成 的 断 言 都 可 判 定，则犌，犌，犿犌，犌，狀可 判 定 犌，犌，犿犌，犌，狀的 判 定 方 法该 判 定 方 法 用 于 程 序 分 析 和 验 证 过 程 中 对 形 状图 蕴 涵 关 系 的 判 定，例 如 第节 的 循 环 不 变 形 状 图和 递 归 函 数 前 后 形 状 图 的 推 断 算 法 需 要 用 到 该 方法先 定 义 节 点 相 容 和 形 状 图 相 容定 义 节 点

59、狀和狀若 满 足 下 面 的 条 件，则狀相 容 于狀（与 定 义的 区 别 仅 在 条 件（） ）（）狀和狀是 同 类 节 点并 且 若 都 是 声 明 节 点、结 构 节 点 或 浓 缩 节 点，则 有 同 样 的 出 边 及 其 标 记；若都 是 谓 词 节 点，则 谓 词 名 相 同（）若狀和狀是 同 类 浓 缩 节 点 或 谓 词 节 点，且分 别 带与和与，则 必 须 满 足（ ） 定 义 形 状 子 图犌和犌若 满 足 下 面个 条件，则 称犌相 容 于犌（）犌的 节 点 集犖到犌的 节 点 集犖有 一 对 一的 函 数犳，使 得犖犳（犖）若 非 空，则 其 中 只 有 浓缩 节

60、 点 并 且 每 个 浓 缩 节 点 的（ ） 可 满 足，即 这 些 浓 缩 节 点 可 以 有等 于的 情 况（）对 任 何狀犖，狀相 容 于犳（狀）（）对 任 何狀犖，若狀和犳（狀）的 某 标 记 相同 的 出 边 分 别 指 向 节 点狀和狀，则狀经 过犿个（犿 ）属 于犖犳（犖）的 浓 缩 节 点 后 所 到 达 的狀和狀满 足犳（狀）狀对 于 图 的犌和犌，犌的 那 个 浓 缩 节 点 经犳函 数 映 射 到犌最 右 边 的 那 个 浓 缩 节 点因 为犌左边 两 个 浓 缩 节 点 的犿和犽都 可 以 等 于，所 以犌相容 于犌图 帮 助 理 解 定 义的 两 个 形 状 图定

61、义 形 状 图犌和犌若 满 足 下 面 的 条 件，则 称犌相 容 于犌犌和犌的 形 状 子 图 一 一 对 应 并 且犌的 每 个 形状 子 图 相 容 于犌中 对 应 的 形 状 子 图在 证 明 形 状 图 之 间 的 蕴 涵 时，需 要 考 虑 在 用 等计 算 机 学 报 年价 重 写 系 统 化 简 形 状 图 后，适 当 地 使 用 形 状 图 的 蕴涵 规 则所 使 用 的 蕴 涵 规 则 是 节 中 第（）类 蕴 涵规 则，即 由犠犠犠得 到 的犠犠和犠犠；而 对 于 第（）和（）类 蕴 涵 规 则，由 于 它 们 都 是 针 对浓 缩 节 点 的和的 规 则，其 效 果 已

62、 体 现 在 节 点 相容 的 定 义 中，因 而 不 必 作 为 重 写 规 则犌，犌，犿犌，犌，狀的 判 定 方 法 可通 过 略 微 修 改 节 的 等 价 式 判 断 方 法 中 的（）和（）两 点 即 可 得 到：（）若 某 个犌，犼（ 犼狀）的 某 条 尽 可 能 长 的 且不 经 过 浓 缩 节 点 的 访 问 路 径 是 某 个犌，犻（ 犻犿）的 某 条 不 经 过 浓 缩 节 点 的 访 问 路 径 或 其 真 前 缀，但不 是 指 向 同 类 节 点，则 尝 试 使 用 上 面 提 到 的 蕴 涵 规则 对犌，犻进 行 重 写例 如，若 图 规 则 右 部 两 个 窗 口

63、之 一 和 左 部 窗口 分 别 出 现 在犌，犻和犌，犼中 的 上 述 位 置，则 使 用 相 应蕴 涵 规 则 重 写犌，犻，把 窗 口 中 内 容 归 约 成 谓 词 节 点（）对 每 个犌，犻（ 犻犿） ，若 存 在 某 个犌，犼（ 犼狀） ，使 得犌，犻相 容 于犌，犼，则犌，犌，犿犌，犌，狀，否 则 该 蕴 涵 式 不 成 立 循 环 不 变 形 状 图 和 递 归 函 数 前 后形 状 图 的 推 断 本 节 应 用 第节 的 形 状 图 理 论 判 定 方 法 来 推 断循 环 不 变 形 状 图该 推 断 方 法 的 一 个 变 种 可 用 来 推断 递 归 函 数 的 前

64、后 形 状 图形 状 图 是 指 针 有 效 性 和 指 针 相 等 性 断 言 的 集 合的 图 形 表 示，循 环 不 变 形 状 图 就 是 循 环 不 变 式 中 有关 指 针 断 言 的 那 部 分 不 变 式，函 数 前 后 形 状 图 就 是函 数 前 后 条 件 中 有 关 指 针 的 那 部 分 断 言对 易 变 数 据 结 构 的 处 理，循 环 语 句 通 常 完 成 下面 功 能 之 一：（）寻 找 数 据 结 构 中 的 操 作 位 置 或 依 次 对 各 节点 上 数 据 进 行 操 作这 时，除 了 某 些 声 明 指 针 的 指 向在 节 点 间 移 动 外，形

65、 状 图 没 有 其 他 变 化（）循 环 体 的 每 次 迭 代 都 在 对 数 据 结 构 进 行 节点 插 入 或 删 除循 环 体 执 行 过 程 中 虽 然 破 坏 了 数 据结 构 的 形 状，但 每 次 到 达 循 环 体 结 束 点 时，形 状 得 到恢 复，仅 节 点 个 数 发 生 变 化（）循 环 体 的 每 次 迭 代 都 在 对 数 据 结 构 某 些 节点 的 边 的 指 向 进 行 调 整，并 且 有 可 能 出 现 这 样 的 情况：每 次 迭 代 结 束 时 形 状 并 未 得 到 恢 复，但 在 整 个 循环 执 行 结 束 时 形 状 得 到 恢 复例 如

66、 文 献 中 例使 用 的 双 向 链 表 倒 置 算 法对 于 这 类 循 环，在 循 环 体 的 每 条 执 行 路 径 上，声明 指 针 在 形 状 图 上 的 移 动 引 起 的 形 状 图 变 化 主 要 体现 在 浓 缩 节 点 所 代 表 的 节 点 个 数 的 变 化 上 循 环 不 变 形 状 图 推 断 算 法 的 框 架根 据 基 于 抽 象 解 释 的 循 环 不 变 式 推 断 框 架 ，循 环 不 变 形 状 图 的 推 断 算 法 框 架 如 图 为 表 达 简单 起 见，本 节 用 字 母?表 示 可 以 出 现 形 状 图 析 取 的形 状 图对 于 循 环

67、（犅）犛（）计 算 循 环 前 条 件?狆 狉 犲犻 （）根 据 形 状 图 逻 辑 的 规 则 计 算?犻 ，使 得?犻犅犛?犻 （）应 用 抽 象 规 则 计 算?犻 ，使 得?犻 ?犻 （）若?犻 ?犻，则?犻是 循 环 不 变 形 状图；否 则，犻犻 ，转（）图 循 环 不 变 形 状 图 推 断 的 算 法 框 架下 面 对 图 的 算 法 框 架 做 一 些 解 释：（）算 法 第（）步 根 据 形 状 图 逻 辑 的 规 则 计 算?犻 ，?犻犅代 表 形 状 图?犻和 符 号 断 言犅的 合 取 若 碰 到 引 起 内 存 泄 漏 的 操 作、悬 空 指 针 或 指针 脱 引

68、用（ ）操 作，则 无 规 则 可 用，报 告错 误（）算 法 第（）步 的 抽 象 是 指：对 形 状 图 上 随 循环 迭 代 次 数 变 化 而 变 化 的 浓 缩 节 点（指 其 代 表 的 结构 节 点 数 随 迭 代 次 数 变 化 而 变 化） ，把 其 代 表 结 构 节点 数 的 表 达 式 换 成 能 概 括 多 次（甚 至 全 部）迭 代 情 况的 表 达 式应 用 的 抽 象 规 则 是 采 用 文 献 中 第 节 的 蕴 涵 规 则（）算 法 第（）步?犻 ?犻的 证 明 是 采用 节 的 判 定 方 法以 节 的 那 段 单 链 表 代 码（假 定 至 少 有 一

69、个表 元）的 循 环 不 变 形 状 图（图（） ）的 推 断 为 例各程 序 点 的 形 状 图 见 图 ，图 中犼是 形 状 分 析 系 统 引入 的 虚 拟 变 量第次 迭 代 后犌犌不 成 立，但 第次 迭 代 后 能 证 明犌犌犌，因 此犌犌是 循 环不 变 形 状 图由 于犌犌，因 此犌犌可 简 化 为犌由 于 没 有 程 序 变 量 可 以 替 代犌中 的 虚 拟 变 量犼，则 略 去犼，得 到 结 果 就 是 图（） 算 法 终 止 的 讨 论图 算 法 终 止 取 决 于 下 面点：（）算 法 第（）步 的 抽 象 能 够 成 功（）算 法 第（）步 的 蕴 涵 式 的 证

70、明 因 得 到 结 果而 终 止 或 因 形 状 检 查 发 现 错 误 而 终 止 期张昱 等：形 状 图 理 论 的 定 理 证 明图 推 断 循 环 不 变 式 的 迭 代 过 程（）若 形 状 检 查 没 有 发 现 错 误，算 法 第（）步 的蕴 涵 式 最 终 会 成 立该 算 法 终 止 的 理 由 概 述 如 下：（）本 文 为 循 环 体犛的 每 条 执 行 路 径 都 安 排 累计 该 路 径 执 行 次 数 的 虚 拟 变 量选 择 一 种 合 适 的 虚拟 变 量 命 名 方 式，能 应 对 出 现 并 列 和 嵌 套 循 环 的 情况 以 及 循 环 体 中 出 现

71、并 列 和 嵌 套 条 件 语 句 的 情 况在 增 加 虚 拟 变 量 时，还 要 把 表 达 虚 拟 变 量 之 间 关 系的 等 式 或 不 等 式 加 到 相 关 形 状 图 中通 过 增 设 虚 拟 变 量，结 合 下 面（）有 关 浓 缩 节 点的表 达 式 为 线 性 的 讨 论，算 法 第（）步 的 抽 象 就 能够 成 功，即 可 以 把 浓 缩 节 点 所 概 括 的 节 点 数 抽 象 为用 含 相 应 虚 拟 变 量 的 线 性 表 达 式 来 表 示（）从 第节 知 道，形 状 图 蕴 涵 关 系 判 定 方 法 的终 止 性 依 赖 于 判 断 浓 缩 节 点 之

72、间 蕴 涵 与 否 的（ ） 的 证 明 的 终 止 性下 面 是 相 关 的 分 析对 于 循 环 体犛的 任 意 一 条 执 行 路 径，对 于 除 第次 迭 代 计 算 以 外 的 其 他 各 次 迭 代 计 算 的 结 果 形 状图，若 与 上 次 迭 代 计 算 的 结 果 形 状 图 相 比，某 浓 缩 节点 所 代 表 的 节 点 数 发 生 变 化，则 再 次 迭 代 计 算 引 起的 变 化 与 本 次 迭 代 计 算 的 变 化 相 同若 循 环 前 某 浓缩 节 点 代 表犪 狓犫个 节 点，第次 迭 代 时，个 数 变 化是犱，随 后 各 次 迭 代 的 个 数 变 化

73、 是犮，则 该 路 径 执 行狔（狔 ）次 结 束 时，该 浓 缩 节 点 代 表 的 节 点 数 是（犪 狓犫）（犮 狔犱） ，由 于（犪 狓犫）在 循 环 执 行 过 程 中 不变，因 此 在 图 算 法 中 证 明 形 状 图 之 间 的 蕴 涵 时 可当 成 常 量这 样，在 每 次 迭 代 计 算 过 程 中，浓 缩 节 点所 代 表 节 点 的 个 数 本 质 上 可 用 该 路 径 的 虚 拟 变 量 的线 性 表 达 式 来 表 示，这 就 保 证 了 该 浓 缩 节 点 的 表 达式维 持 为 线 性类 似 的 分 析 可 知中 的 整 型 表 达式 也 是 线 性这 就 保

74、 证（ ） 的 证 明 会 终止图 例 子 的 迭 代 过 程 体 现 了 这 里 所 说 的 对 浓 缩节 点 的 抽 象另 一 方 面，在 有狆狆 这 样 指 针 赋 值 的情 况 下，除 第次 迭 代 计 算 外，若 一 次 迭 代 计 算 的 结果 形 状 图 中 出 现 无 声 明 节 点 指 向 的 结 构 节 点，但 又不 能 折 叠 成（或 并 入 相 邻）浓 缩 节 点则 表 明 该 结 构节 点 的 出 边 的 指 向 不 符 合 数 据 结 构 定 义 的 要 求，先前 关 于 循 环 语 句 的种 用 法 中 不 会 出 现 这 样 的 情况因 此，若 经 抽 象 后，

75、相 邻个 声 明 指 针 所 指 向 的节 点 之 间 的 结 构 和 浓 缩 节 点 的 个 数 大 于（简 称 节点 个 数 约 束） ，则 在 循 环 体 结 束 点 的 形 状 检 查 会报 告 错 误 并 终 止 迭 代例 如，对 于 各 节 点 都 有 指 针 域和的 双 向 非空 链 表，用 循 环 依 次 将 各 节 点 的域 置 为 且域 的 指 向 不 变代 码 如 下：狆 ； （狆 ！ ） 狆狆 ；狆 ；这 相 当 于 废 弃域，用来 构 成 一 个 单 链 表图 （）是 循 环 入 口 的 形 状 图，图 （）是 经 过次 迭 代的 形 状 图本 算 法 无 法 把 已

76、 经 遍 历 过 的 结 构 节 点 折叠 为 浓 缩 节 点，因 为 双 向 链 表 没 有 相 应 的 规 则形 状检 查 会 因 两 个 相 邻 声 明 节 点 超 出 节 点 个 数 约 束 而 报告 错 误计 算 机 学 报 年图 循 环 不 变 形 状 图 推 断 过 程 报 告 错 误 的 例 子（）由 于 声 明 指 针 的 个 数 有 限，再 加 上（）提 到的 节 点 个 数 约 束，在 循 环 体 结 束 点 能 形 成 的 不 等 价形 状 图 有 限若 未 见 报 告 程 序 错 误，则 一 定 存 在犻，使 得?犻 ?犻成 立 递 归 函 数 前 后 形 状 图 的

77、 推 断对 于 非 递 归 函 数，可 以 从 函 数 前 形 状 图 自 动 推断 函 数 后 形 状 图但 该 方 法 难 以 用 到 有 指 针 型 形 参且 返 回 值 是 指 针 的 递 归 函 数，因 为 推 断 递 归 函 数 前后 形 状 图 时 要 用 到 该 函 数 的 前 后 形 状 图若 仅 有 指 针 型 的 形 参，或 仅 有 指 针 型 的 返 回 值，根 据 形 状 系 统 对 函 数 调 用 点 和 返 回 点 的 形 状 约 束，函 数 的 递 归 性 并 没 有 给 形 状 分 析 带 来 困 难倘 若 形参 和 返 回 值 都 是 指 针 型，则 虽 有

78、 形 状 系 统 的 约 束，在函 数 返 回 点 也 不 能 确 定 实 参 指 针 和 返 回 指 针 之 间 的关 系，因 而 不 能 确 定 函 数 后 形 状 图关 注 实 参 指 针 是因 为 它 的 值 在 被 调 用 函 数 中 虽 不 变，但 其 指 向 的 节点 在 数 据 结 构 中 的 位 置 可 能 会 变为 此，函 数 的 前 形状 图 增 设 虚 拟 变 量 来 表 示 实 参 指 针，它 与 形 参 指 针指 向 同 一 个 节 点，并 据 此 来 推 断 函 数 后 形 状 图可 以 像 推 断 循 环 不 变 形 状 图 那 样 迭 代 推 断 函 数后 形

79、 状 图因 为 计 算 会 终 止 的 递 归 函 数 总 有 非 递 归的 出 口，可 以 先 通 过 非 递 归 路 径 得 到 函 数 后 形 状 图的 初 值，然 后 再 在 递 归 路 径 上 迭 代 求 解对 于 直 接 递 归 函 数，若 函 数 体 中 的 循 环 语 句 里面 没 有 递 归 调 用（通 常 如 此） ，则 函 数 前 后 形 状 图 的推 断 方 法 概 述 如 下：（）通 过 程 序 分 析，确 定 函 数 体 中 非 递 归 执 行路 径 和 递 归 执 行 路 径 的 语 句 序 列这 里 所 说 的 执 行路 径 把 无 递 归 调 用 的 循 环

80、语 句 看 成 一 个 语 句，把 两个 分 支 都 有（或 都 无）递 归 调 用 的 条 件 语 句 也 看 成 一个 语 句，以 减 少 要 考 虑 的 路 径 数为 叙 述 方 便，假 定非 递 归 和 递 归 的 执 行 路 径 各 一 条，语 句 序 列 分 别 是犛狀 狅 狀和犛狉 犲 犮（）从 函 数 前 形 状 图?犲 狀 狋狉 狔和犛狀 狅 狀通 过 形 状 图 逻辑 的 规 则 得 到?，使 得?犲 狀 狋狉 狔犛狀 狅 狀?令犻 （）根 据 形 状 图 逻 辑 的 规 则 计 算?犻 ，使 得?犲 狀 狋狉 狔犛狉 犲 犮?犻 其 中?犲 狀 狋狉 狔和?犻作 为犛狉

81、犲 犮中 出 现 的递 归 函 数 调 用 的 前 后 形 状 图（）应 用 抽 象 规 则 计 算?犻 ，使 得?犻 ?犻 （）若?犻 ?犻，则?犻是 函 数后 形 状 图；否 则，犻犻 ，转（）除 了 推 断 递 归 函 数 的 函 数 前 后 条 件 需 先 分 析 函数 的 非 递 归 和 递 归 的 执 行 路 径 外，本 算 法 与 图 算法 没 有 本 质 上 的 区 别，把 本 算 法 的 第（）到（）步 与图 算 法 的 第（）到（）步 比 较 就 可 以 看 出 这 一 点 形 状 图 理 论 和 整 数 理 论 组 合 的判 定 方 法 在 程 序 验 证 器 原 型 中

82、，验 证 条 件 生 成 器 所 产 生的 验 证 条 件 的 一 般 形 式 是：（犌，犙，）（犌，犿犙，犿） （犌，犙，）（犌，狀犙，狀）其 中犙代 表 符 号 断 言 的 合 取，并 且 其 中 没 有 指 针 相等 性 断 言 和 有 效 性 断 言验 证 条 件 的 证 明 是 形 状 图 理 论 和 整 数 线 性 算 术理 论 的 组 合 的 判 定 问 题首 先，形 状 图 之 间 蕴 涵 的 证明 要 根 据 形 状 图 理 论其 次，犙中 像狆犱狇 犱这 样 的 断 言，需 要 根 据 形 状 图 来 判 断狆犱和狇 犱分 别 是 属 于 哪 个 节 点 的 数 据注 意，

83、在 形 状 图 中，浓 缩 节 点 和 谓 词 节 点 可 能 附带和 这 表 明 形 状 图 理 论 内 部 涉 及 线 性 整 数 算术 理 论它 与 本 节 讨 论 的 理 论 组 合 的 判 定 问 题 没 有联 系，因 为 系 统 原 型 限 定和只 依 赖 整 型 声 明 变量，不 依 赖 于 节 点 的 数 据因 为和是 决 定 该 浓 缩节 点 或 谓 词 节 点 所 代 表 的 链 表（段）的 长 度、或 者 所代 表 的 二 叉 树 片 段 的 高 度 的 表 达 式 和 断 言，通 常 在实 际 编 程 中 不 会 把 决 定 某 种 数 据 结 构 的 长 度 或 高

84、度的 信 息 存 放 在 该 数 据 结 构 节 点 的 域 中本 节 讨 论 组 合 理 论 的 两 种 证 明 方 式 易 变 数 据 结 构 上 被 关 注 性 质 的 描 述通 常 关 注 易 变 数 据 结 构个 层 次 的 性 质：（）各 个 节 点 是 否 连 接 成 预 定 的 形 状该 性 质 的 验 证 在 形 状 分 析 阶 段 完 成，程 序 员 只要 像 声 明 类 型 那 样 声 明 形 状 即 可这 仅 是 形 状 图 理论 上 的 问 题 期张昱 等：形 状 图 理 论 的 定 理 证 明（）与 形 状 有 关 的 性 质例 如 链 表 的 长 度、树 的 高

85、度、二 叉 树 的 两 边 是 否平 衡 和 节 点 之 间 的 可 达 性 等这 些 性 质 很 容 易 归 纳定 义，虽 然 循 环 链 表 的 长 度 的 归 纳 定 义 会 略 显 复 杂（）与 各 节 点 上 数 据 排 列 有 关 的 性 质当 数 据 需 按 序 排 列 时，一 个 数 据 存 放 到 哪 个 节点 依 赖 于 对 数 据 结 构 上 节 点 的 定 序线 性 链 表 上 节点 之 间 的 定 序 比 较 简 单，二 叉 树 上 节 点 之 间 有 多 种定 序 方 式这 样，数 据 是 否 有 序 的 比 较 必 定 涉 及 数 据所 属 节 点 在 数 据 结

86、 构 上 的 位 置在 定 义 上 述 性 质 时，比 较 简 单 的 方 式 是 用 以 指针 为 参 数（可 能 还 有 其 他 参 数）的 归 纳 谓 词另 一 种方 式 是 先 定 义 节 点 之 间 的 可 达 关 系，然 后 基 于 此 再 使用 量 词 来 定 义 所 需 的 性 质用 这 两 种 方 式 描 述 性 质 都比 较 有 利 于 对 操 作 易 变 数 据 结 构 的 递 归 程 序 的 验 证本 文 的 系 统 原 型 针 对 形 状 图 上 浓 缩 节 点 的 特点，还 提 供 使 用 量 词 来 概 括 数 据 性 质 的 方 式，以 方 便操 作 易 变 数

87、 据 结 构 的 循 环 程 序 的 验 证例 如 有 序 单链 表 可 定 义 为 （ 狆）犿：? ? ?（狆（ ）犿 犻： 犿 狆（ ）犻 犱 狆（ ）犻犱）其 中 类 型 由 犱； 给 出，其 中狆（ ）犻代 表狆 ，共犻个“ ”在 该 定 义 中，量 词 的 约 束 变元 出 现 在 访 问 路 径 的 上 角 标 中这 种 直 接 基 于 编 程语 言 中 访 问 路 径 语 法 的 定 义 显 得 比 较 直 观 符 号 断 言 语 言为 便 于 下 面 的 讨 论，将 系 统 原 型 所 使 用 的 断 言语 言 的 抽 象 语 法 描 述 在 图 几 点 说 明 如 下： 犻

88、犱犐 犱 犲 狀 狋犻 犳 犻犲 狉（程 序 中 的 标 识 符 集） 狋 狀犛 犻 犱 犲 狀 狋犻 犳 犻犲 狉（程 序 中 结 构 体 类 型 的 名 字 集） 狆 犱 狆 狉 犲 犱 犻犮 犪 狋犲犻 犱（狆 狆， ，狆 狆犽）犪 狆 狆 狋 犻 犱 狋 犻 狀 狋狋 狀 狆 狋 狋 犺 犲 狅 狉 犲 犿犪犪 狋 犺 犲 狅 狉 犲 犿犪犪 （犫 狅 狅 犾犲 狓 狆是 布 尔 表 达 式，其 产 生 式 略 去） 犪 犫 狅 狅 犾犲 狓 狆 犻 犱：犱犪 犻 犱：犱犪（犪） （犻 狀 狋犲 狓 狆是 整 型 表 达 式，其 产 生 式 略 去） 犱 ?犻 狀 狋犲 狓 狆犻 狀

89、狋犲 狓 狆 犾 狏 犾 狏（犻 犱）犻狀 狋犲 狓 狆（左 值犾 狏是 各 类 型犲 狓 狆的 一 种 选 择）图 符 号 断 言 语 言 的 抽 象 语 法 （）图 前 一 部 分 是 自 定 义 谓 词 以 及 这 些 谓词 之 间 性 质 定 理 的 语 法，后 一 部 分 是 断 言 的 语 法谓词 应 用 可 出 现 在 布 尔 表 达 式 中，因 而 可 出 现 在 断言 中（）程 序 员 用 图 的 文 法 编 写 的 断 言 中 出 现的 变 量，若 不 是 程 序 变 量，则 称 之 为 逻 辑 变 量（）量 词 约 束 变 元 的 论 域 只 能 是 整 数 域 或 它

90、的某 个 区 间，因 而 禁 止 使 用 指 针 型 约 束 变 元在 需 要 由存 在 量 词 来 约 束 指 针 型 变 元 的 地 方，可 以 用 指 针 型逻 辑 变 量 来 代 替 下 面 用 有 序 单 链 表 来 解 释 为 什 么 需 要 提 供 性 质定 理有 序 单 链 表 的 归 纳 定 义 如 下： （ 狆）狆 狆 狆犱 狆 犱 （狆 ）在 一 个 子 句 中，若 出 现 以狆为 前 缀 的 访 问 路径，则 默 认 有 断 言狆！ 的 定 义 从表 尾 向 表 头 方 向 归 纳但 是，在 遍 历 有 序 单 链 表 时，例 如 图 单 链 表 插 入 函 数 中 的

91、 循 环 代 码（暂 且 不 关心 图 中 的 断 言） ，其 遍 历 方 向 是 从 表 头 向 表 尾，因此 还 需 要 用 下 述 表 段 谓 词 和 性 质 定 理 （ 狆， 狇）狆 狇狇！ 狆犱 狆 犱 （狆 ，狇）和 （狆，狇）狇犱 狇 犱 （狆，狇 ）这 个 性 质 定 理 保 证 已 扫 描 过 的 表 段 再 加 入 下 一 个 被扫 描 的 节 点，结 果 仍 然 是 表 段 和 两 个 谓 词 之 间 的如 下 性 质 定 理 也 是 验 证 时 不 可 缺 的： （狆，狇） （狇） （狆）上 述个 性 质 定 理 都 需 要 程 序 员 提 供，因 为 它 们 的证 明

92、 需 要 基 于 表 段 的 长 度 进 行 归 纳，基 于 演 绎 推 理的 自 动 定 理 证 明 器 难 以 发 现 这 样 的 性 质 谓 词 出 现 在 函 数 的 前 后 断 言 中，而 谓 词 出 现 在 循 环 不 变 式 中后 者 的 定义 只 要 能 支 持 函 数 前 后 条 件 的 证 明 就 足 矣，没 有 必要 选 择 最 一 般 的 定 义，即 把 被 验 证 函 数 中 不 会 出 现的 情 况 也 囊 括 在 内，以 免 给 验 证 增 添 不 必 要 的 麻 烦在 断 言 文 法 及 其 类 型 系 统 的 基 础 上，还 要 限 制断 言 中 的 整 型

93、表 达 式 必 须 是 线 性 表 达 式计 算 机 学 报 年 ； 犱； ； 犿 （ ， ） 犻： 犿 （ （ ）犻 犱 （ ）犻犱） 是 为 记 住 实 参 指 针 的 值 而 引 入 的 逻 辑 变 量 （ ， ） ； ； 狆； 犼；狆 （ ） ；狆犱 ；狆 ； （ ） 狆； （狆犱 犱） 狆 ； 狆； ； ；犼 ； ！ 犻： 犼 （ （ ）犻 犱 （ ）犻犱） 犱 犱 犱狆犱犼 犻： 犿犼 （ （ ）犻 犱 （ ）犻犱） 犻： 犼 （ （ ）犻 犱 （ ）犻犱） 犱狆犱犼 （ （ ！ ） （ 犱狆犱） ） ； ；犼犼 ； 狆 ； 狆； ； （ ， ） 犿 犻： 犿（ （ ）犻 犱 （

94、）犻犱） 犱 犱 （ ， ） 犿 犻： 犿 （ （ ）犻 犱 （ ）犻犱） （ ， ） 犿 犻： 犿（ （ ）犻 犱 （ ）犻犱） 图 单 链 表 的 插 入 函 数 验 证 条 件 的 证 明 方 法对 于 验 证 条 件（犌，犙，）（犌，犿犙，犿）（犌，犙，）（犌，狀犙，狀） ，在 形 状 分 析 阶 段 已 经 证 明 了犌，犌，犿犌，犌，狀，即 对 每 个犌，犻（ 犻犿） ，存 在犌，犼（ 犼狀） ，使 得犌，犻犌，犼现 在 仅 需 要 证 明：对 每 个犌，犻犙，犻，存 在犌，犼犙，犼（其 中犌，犻犌，犼已 经 证 明） ，使 得犌，犻犙，犻犙，犼可 把犌，犻看 成犙，犻犙，犼的 证

95、 明 环 境，写成犌，犻犙，犻犙，犼实 际 证 明 时，还 有 程 序 员 提 供 的谓 词 定 义 和 性 质 定 理 可 用，用 字 母犜表 示，因 此 下面 仅 关 注犌，犜犙犙 的 证 明 方 法犌，犜犙犙 的 证 明 有 两 种 方 式：第种 是 常规 的 方 式，把 形 状 图 理 论 和 整 数 理 论 组 合 的 判 定 转换 为 整 数 理 论 上 的 判 定它 通 过 引 入 一 些 未 解 释 函数，把犌转 换 成 符 号 断 言犘，然 后 把?（犘犜犙犙 ）交 给 具 体 把 形 状 图 转 换 为 符 号 断 言 的 方 法见 文 献 这 种 方 式 的 缺 点 是，

96、在 推 理犙中 涉 及节 点 数 据 的 断 言 时，指 针 符 号 断 言犘不 能 像 形 状 图犌那 样 提 供 对 形 状 的 全 局 把 握，从 而 某 些 验 证 条 件用 证 不 出举 例 说 明 如 下：例 单 链 表 的 插 入 函 数，代 码 和 断 言 见 图 该 例 的 循 环 不 变 形 状 图 是 根 据 节 的 算 法 自 动推 断 的为 可 读 起 见，断 言 都 出 现 在 注 释 中图 是 语 句 之 前 程 序 点 形 状 图犌，犌，犌，图 语 句 前 形 状 图 的 一 种 情 况犌，（分 别 对 应 只 有 新 插 入 节 点、插 在 表 头、插 在 表

97、中 和 插 在 表 尾种 情 况）中 的犌，其 中 是 为表 示 实 参 指 针 而 增 设 的 虚 拟 变 量，对 应 的犙，是 下述 符 号 断 言，其 中 有 序 性 用 全 称 量 化 断 言 表 示：犻： 犼 （ （ ）犻 犱 （ ）犻犱） 犱狆犱狆犱 犱犼 犻： 犿犼 （ （ ）犻 犱 （ ）犻犱）犌，转 换 成 的 符 号 断 言 如 下： （ ）犼 狆 狆 （ ）犿犼 （ ， ） 犼 犿犼由犌，转 换 得 到 的 断 言 是 一 些 有 关 有 效 指 针 相等、指 针 等 于 和 链 表 长 度 的 断 言，它 们 是 形状 图 所 包 含 信 息 的 符 号 表 示其 他

98、信 息，例 如狆 （ ）犼可 以 从 这 些 断 言 推 导显 然，这 些 断 言和犙，的 合 取 能 蕴 涵 函 数 后 条 件 中 的 第种 情 况（即 图 中 的 最 后 一 行，记 为犙，）把 这 些 符 号 断言 转 换 成 能 接 受 的 形 式 的 转 换 方 法 见 文 献 期张昱 等：形 状 图 理 论 的 定 理 证 明用 证 明 不 了 这 样 的 蕴 涵原 因 是 在 符 号 断言 中， 难 以 发 现犙，中个 断 言 的 前 后 衔 接 次序若 有 图 的 形 状 图，通 过 把 这个 断 言 分 别 标注 到 相 关 节 点 上，则 很 容 易 发 现 它 们 合

99、并 后 就 是犙，中 的 全 称 断 言采 用 第种 方 式 的 另 一 个 问 题 是，若 与 某 个 归纳 谓 词 定 义 相 对 应 的 某 条 展 开 规 则 对 验 证 来 说 是 需要 的，则 容 易 引 起 不 停 地 用 该 展 开 规 则 去 展 开断 言 中 出 现 的 谓 词 应 用，导 致 证 明 不 终 止第种 证 明 方 式 是 把 形 状 图 直 接 用 于犌，犜犙犙 的 证 明参 照 框 架 ，本 文 提出 的犌，犜犙犙 的 证 明 方 法 概 述 为 如 下步：（）将犙（形 式 为犙犙犿）中 所 有 与 节 点 相关 的犙犼（ 犼犿）都 标 注 在犌中 相 关

100、 的 节 点 上相 关 的 节 点 是 指 断 言 中 的 指 针 型 访 问 路 径（包 括 整 型 访 问 路 径 的 最 长 指 针 型 前 缀）所 到 达 的 节点例 如，例中犙，的 断 言 犱 狆犱标 注在 图 中 和狆指 向 的 节 点 上，断 言狆犱 犱标 注 在 图 中狆和 指 向 的 节 点 上全 称 断 言 经 常 标 注 在 某 个 浓 缩 节 点 上若在 一 个 全 称 断 言 中，约 束 变 元 的 取 值 集 合 使 得 该断 言 与 多 个 节 点 相 关，则 把 该 断 言 同 时 标 注 在 这 些节 点 上例中犙，的 全 称 断 言犻： 犿犼 （ （ ）犻

101、犱 （ ）犻犱）标 注 在图 中 指 向 的 节 点 上，断 言犻： 犼 （ （ ）犻 犱 （ ）犻犱）标 注 在 图 中 和 指 向 的 两 个 节 点 上对 于 有 两 个 指针 变 元 的 谓 词 应 用，情 况 与 全 称 断 言 的 类 似（）把 能 推 导 出 的 性 质 继 续 标 注 在犌的 相 关 节点 上，一 直 到犌的 节 点 都 不 会 再 增 加 新 的 性 质为 止新 性 质 的 相 关 节 点 若 都 不 在犌中，则 无 须 标注 这 类 新 性 质，这 有 利 于 保 证 推 导 过 程 的 终 止对 于 标 注 有 全 称 断 言 的 浓 缩 节 点，注 意

102、它 与相 邻 节 点 之 间 是 否 可 以 利 用（ （犻：犿 狀 犘（犻） ）犘（狀） ） 犻：犿 狀犘（犻）等 等 价 性 来 使 得 全 称 断 言的 约 束 变 元 的 取 值 范 围 扩 大（）对犙 （形 式 为犙 犙 犽）中 的 每 个犙 犼（ 犼犽） ，检 查犙犙 犼是 否 成 立若犙 犼是 节 点 相 关 的 断 言不 论 是 谓 词 应 用、全 称 断 言 还 是 整 数 断 言，若犙 犼从 相 关 节 点 的 断 言 以及犙中 与 节 点 无 关 的 断 言 可 推 导，则犙犙 犼成 立，否 则 不 成 立节 点 数 据 之 间 的 关 系 可 能 通 过 与 节 点 无

103、关 的 断 言 来 传 递，因 此 这 里 强 调 包 括犙中 与 节 点 无 关的 断 言例 如，若狆犱 犿且狆 犱 狀且犿狀，则狆犱狆 犱若犙 犼是 节 点 无 关 的 断 言若犙 不 能 从犙推导，则犙犙 犼不 成 立若 对 每 个犙 犼（ 犼犽） ，犙犙 犼都 可 证，则犌，犜犙犙 得 证可 以 证 明，若 整 数 域 上 断 言 的 证 明 都 可 终 止，则该 证 明 过 程 终 止 并 且 可 靠这 个 方 法 专 用 于 面 向 操 作 易 变 数 据 结 构 的 程 序的 验 证与 框 架 不 同 的 是，这 里 没 有交 错 使 用 两 个 理 论 不 断 推 出 新 性

104、质 并 进 行 传 播 的 过程，而 是 在 形 状 分 析 阶 段 先 用 形 状 图 理 论 完 成 形 状图 蕴 涵 关 系 的 证 明这 里 只 是 利 用 形 状 图 来 把 符 号断 言 分 组，一 方 面 便 于 推 导 更 多 对 验 证 有 用 的 性 质，另 一 方 面 防 止 出 现 无 止 尽 地 推 导另 一 个 不 同 是， 框 架 限 定 被 组 合的 理 论 为 无 量 词 的 一 阶 理 论，而 这 里 允 许 量 词 断 言出 现 在 操 作 易 变 数 据 结 构 的 程 序 的 规 范 中 实 例 分 析基 于 形 状 图 逻 辑 所 实 现 的 程 序

105、 验 证 器 原 型（可从 ： 下 载） 的 流程 分 成 下 面个 阶 段（）预 处 理 阶 段该 阶 段 为 源 代 码 生 成 抽 象 语法 树 并 像 编 译 器 那 样 完 成 通 常 的 静 态 检 查；（）形 状 分 析 阶 段生 成 各 程 序 点 的 形 状 图，包括 推 断 循 环 不 变 形 状 图 和 递 归 函 数 的 前 后 形 状 图；（）程 序 验 证 阶 段该 阶 段 通 过 正 向 演 算 生 成验 证 条 件，并 用 证 明 它 们程 序 员 在 编 程 时，需 要 提 供 有 关 节 点 数 据 的 函数 前 后 条 件 和 循 环 不 变 式程 序 员

106、 可 以 定 义 一 些 归纳 谓 词，用 以 描 述 递 归 数 据 结 构 的 数 据 特 点，以 方 便写 函 数 前 后 条 件 和 循 环 不 变 式程 序 员 需 要 提 供 这些 谓 词 之 间 的、与 程 序 有 关 的 归 纳 性 质，供 自 动 定 理证 明 器 使 用因 为 基 于 演 绎 推 理 的 证 明 器 推 导 不 出这 类 性 质该 原 型 可 以 验 证 易 变 数 据 结 构 上 较 为 复 杂 的 程序，如 有 序 循 环 双 向 链 表、二 叉 排 序 树、伸 展 树、树 堆（ ） 、二 叉 平 衡 树 和 树 的 插 入 和 删 除 函 数有 关 这

107、 些 例 子 的 统 计 数 据 见 表 其 中 的 验 证 时 间是 在 ， 和 内 存 的 机 器 上 实 测 获 得这 些 程 序 大计 算 机 学 报 年多 包 括 插 入 和 删 除 函 数，以 及 被 它 们 调 用 的 函 数操作 二 叉 平 衡 树 的 程 序 的 函 数 最 多，因 为 除 了 插 入 和删 除 函 数 外，还 有 左 旋、右 旋、左 平 衡 和 右 平 衡 等函 数表 有 关 形 状 图 和 验 证 条 件 的 统 计 数 据数 据 结 构 与 程 序 功 能函 数个递 归 函 数个 验 证 条 件个循 环个验 证 时 间 有 序 单 链 表：插 入、倒 置

108、、合 并 有 序 双 向 链 表：倒 置 有 序 循 环 双 向 链 表：插 入 二 叉 排 序 树：递 归 和 非 递 归 插 入、删 除 树：插 入 二 叉 平 衡 树：插 入、删 除 树 堆：插 入、删 除 伸 展 树：插 入、删 除 表各 例 的 循 环 不 变 形 状 图 都 是 用 本 文 方 法 自动 推 断 的其 中 有 序 双 向 链 表 的 倒 置 函 数 虽 只 有 两个 循 环，但 验 证 时 间 明 显 高 于 其 他 链 表 程 序这 是 因为 在 用 循 环 代 码 倒 置 双 向 链 表 过 程 中，链 表 被 分 成正 向 和 逆 向 两 部 分，需 要 多

109、次 迭 代 才 能 得 到 循 环 不变 形 状 图，并 且 循 环 不 变 形 状 图 是种 情 况 的 析 取表各 例 的 递 归 函 数 的 前 后 形 状 图 也 都 是 用 本文 方 法 自 动 推 断 的二 叉 排 序 树 插 入 函 数 的 前 后 形状 图 分 别 在 图 的（）和（）中，其 中 函 数 后 形 状 图分 成 插 入 前 实 参 指 向 非 空 表 和 空 表 两 种 情 况从 此例 可 以 看 出 形 状 图 上 出 现 对 应 形 参 指 针狆的 实 参指 针狆 的 必 要 性其 他 二 叉 树 的 插 入 函 数 的 后 形 状图 也 都 这 样图 二 叉

110、 排 序 树 插 入 函 数 的 前 后 形 状 图表中 二 叉 排 序 树 的 验 证 时 间 远 低 于 列 在 其 后的种 二 叉 树，这 是 因 为 二 叉 排 序 树 仅 需 要 验 证 有序 性，而 其 他 几 种 二 叉 树 还 需 要 验 证 平 衡 性 或 类 似平 衡 性 的 性 质伸 展 树 的 代 码 没 有 递 归，函 数 个 数 和验 证 条 件 也 不 算 多，但 验 证 时 间 远 高 于 其 他 二 叉 树这 是 因 为 其 函 数 的 循 环 不 变 形 状 图 是 多种 情 况 的 析 取，形 状 分 析 阶 段 和 程 序 验 证 阶 段 的 耗时 都

111、大 大 增 加下 面 再 介 绍个 规 模 不 大 但 能 帮 助 理 解 本 文 的例 子例 二 叉 排 序 树 的 递 归 插 入 函 数，代 码 和 断言 见 图 ，程 序 断 言 中 的狔和狕是 整 型 逻 辑 变 量本 例 引 入 的 谓 词 定 义 如 下：（） （ 狆）狆 （狆 ） （狆 ） （狆 ，狆 ） （狆 ，狆 ）（） （ 犿， 狆）狆 犿狆犱 （犿，狆 ） （犿，狆 ）（）（ 犿， 狆）狆 犿狆犱 （犿，狆 ） （犿，狆 ）其 中 的 定 义 见 图 在 函 数 前 后 条 件 中 分 别有狔 （狔，狆）和 （狔，狆） ，它 们 是 说：若狔大于 被 插 入 的 数 据

112、 并 大 于 参 数 树 上 的 所 有 数 据，则狔大 于 结 果 树 上 的 所 有 数 据狕的 含 义 与狔类 似 ； ； 犱； ； （狆）狔 （狔，狆）狕 （狕，狆） （ 狆， ） （狆 ） 狆 （ ） ；狆 ； 狆 ；狆 ； （狆 ） 狆 （狆 ， ） ； （狆 ） 狆 （狆 ， ） ； 狆； （狆） （狔，狆） （狕，狆）图 二 叉 排 序 树 的 插 入 函 数引 入 的 性 质 定 理 有：（）狓狔 （狔，狆） （狓，狆）（）狓狔 （狔，狆） （狓，狆）在 函 数 出 口 点 产 生 的 验 证 条 件 包 括 下 述 蕴 涵式，它 表 示 图 中 第个 递 归 调 用 后 的

113、 断 言 蕴 涵 函数 后 条 件： （狆 ） （狆 ，狆 ）狔狆 （狔，狆 ）狕狆 （狕，狆 ） 期张昱 等：形 状 图 理 论 的 定 理 证 明狔 狕 狆 （狆 ） （狔，狆 ） （狕，狆 ） （狆 ，狆 ） （狆） （狔，狆） （狕，狆）其 中 蕴 含 式 的 前 件 中 的 前 三 行 断 言 是 从 调 用 点前 延 续 到 调 用 点 后，后 两 行 断 言 是 从 函 数 后 条 件 得到在 递 归 调 用 结 束 后，能 得 到 第行 （狆 ，狆 ）的 原 因 是：在 递 归 调 用 点 前，有狆 与 （狆 ，狆 ） ，因 此狆 可 与 被 调 用 的 递 归 函 数的 前、

114、后 条 件 中 的 逻 辑 变 量狔匹 配图 （）两 种 情 况 分 别 都 属 于 该 蕴 涵 式 的 证 明环 境按 照 第节 所 提 出 的 直 接 把 形 状 图 用 于 证 明犌，犜犙犙 的 方 法，把 该 蕴 涵 式 前 件 的 断 言 分 别对 图 （）两 种 情 况 的 形 状 图 标 注 如 下：（）根 节 点： （狆 ，狆 ） ，（狆 ，狆 ） ，狔狆 ，狕狆 ，狆 （）左 子 节 点： （狆 ） ， （狆 ，狆 ） ， （狔， ） ，（狕，狆 ）（）右 子 节 点： （狆 ） ，（狆 ，狆 ） ， （狔，狆 ） ，（狕，狆 ）再 把 利 用 谓 词 定 义 和 性 质 定

115、 理 能 推 导 出 的 断 言增 加 到 这 些 节 点 上：（）根 节 点： （狆） ， （狔，狆） ，（狕，狆） ；（）左 子 节 点：无 增 加；（）右 子 节 点：无 增 加该 蕴 涵 式 在 这 两 种 情 况 下 都 得 证，因 为 其 后 件的 断 言 都 已 经 标 注 在 根 节 点 上 了 在 未 能 得 出 待 证 断 言 有 效 或 不 可 满 足 时，总试 图 继 续 推 导 出 更 多 的 性 质一 种 情 况 是 它 不 断 地把 归 纳 谓 词 展 开，导 致 证 明 过 程 不 终 止针 对 操 作 易变 数 据 结 构 的 程 序 的 验 证，直 接 把

116、形 状 图 用 于 验 证条 件 的 证 明 可 以 有 效 地 阻 止 这 种 不 终 止从 例可以 看 出，在 生 成 验 证 条 件 的 演 算 过 程 中，符 号 断 言 中的 谓 词 断 言 的 展 开 和 形 状 图 上 谓 词 节 点 的 展 开 本 质上 是 同 步 的从 例也 可 以 看 出，全 称 断 言 的 展 开（指 从狓：犿狀（狓） （犿 狀）变 换 成（犿） 狓：犿 狀（狓） （犿 狀）等 情 况）和 形 状 图 上 浓 缩 节点 的 展 开 也 是 同 步 的由 此 可 知，在 证 明 验 证 条 件时，在 把 断 言 按 节 点 分 组 和 推 导 新 性 质

117、的 过 程 中，若谓 词 展 开 式 中 与 节 点 有 关 的 断 言 在 形 状 图 上 没 有 可挂 靠 的 节 点，则 该 谓 词 展 开 也 不 会 给 证 明 带 来 什 么帮 助，因 而 不 必 展 开本 文 并 没 有 把 第节 所 提 出 的 形 状 图 理 论 和 整数 理 论 组 合 的 证 明 方 法 实 现 到 中，而 是 在 验 证器 原 型 中 根 据 该 方 法 的 思 想 对 验 证 条 件 进 行 预 处 理后 再 交 给 ，扩 大 了 可 证 的 范 围，并 减 少 了 不 终止 的 情 况 相 关 工 作 比 较分 离 逻 辑 是 验 证 堆 操 作 程

118、 序（操 作 易 变 数 据 结构 的 指 针 操 作 程 序 是 其 重 要 部 分）的 最 流 行 的 手 工或 半 自 动 推 理 的 程 序 逻 辑 除 了 分 离 逻 辑 外，还存 在 一 些 其 它 逻 辑，如 匹 配 逻 辑 ，也 是 用 于 手 工或 半 自 动 的 推 理分 离 逻 辑 引 入 一 种 专 用 的 分 离 符 号（） ，用 它把 不 能 混 淆 到 一 起 推 理 并 且 不 能 被 忽 略 的 断 言 分 离开 来分 离 逻 辑 的 优 点 和 缺 点 都 源 自 其 引 入 的 分 离概 念分 离 的 好 处 之 一 是 避 免 了 访 问 路 径 别 名

119、 给 程序 验 证 带 来 的 困 难；其 缺 点 是 分 离 切 断 了 不 同 堆 块之 间 的 信 息 联 系，给 需 要 全 局 信 息 才 能 推 断 的 程 序性 质 的 验 证 带 来 困 难例 如，分 离 逻 辑 难 以 发 现 对 某堆 块 的 一 个 指 针 域 的 赋 值 引 起 另 一 个 堆 块 的 泄 漏对 于 堆 操 作 程 序 的 验 证，通 常 允 许 用 户 定 义 的 归 纳谓 词在 分 离 逻 辑 的 环 境 下，必 须 另 行 设 计 归 纳 谓 词的 展 开 或 折 叠 策 略，否 则 因 归 纳 谓 词 的 展 开 没 有 控制 而 导 致 验 证

120、 条 件 的 证 明 可 能 不 终 止因 此，分 离 逻辑 的 证 明 辅 助 工 具 经 常 是 启 发 式 且 不 完 备 的 最近 也 出 现 了 一 些 小 的 判 定 片 断 其 中 文 献 提 出 了 一 种 有 效、可 靠 和 完 备 的 自 动 定 理 证 明 器，用于 检 查 带 表 段 谓 词 的 分 离 逻 辑 公 式 之 间 蕴 涵 的 有 效性，但 它 只 能 用 于 操 作 单 链 表 的 程 序文 献 提 出分 离 逻 辑 一 个 较 小 的 可 判 定 片 段 与 其 他 可 判 定 的 一阶 理 论 的 组 合 理 论 的 判 定 方 法形 状 图 逻 辑

121、的 最 大 特 点 是，形 状 图 既 是 机 器 状态 中 有 关 堆 部 分 的 抽 象 表 示，又 是 指 针 相 等 性 断 言和 有 效 性 断 言 等 的 图 形 表 示，它 总 揽 了 分 离 性 和 整体 性 ，至 少 带 来 下 面 的 好 处：（）形 状 图 逻 辑 无 须 使 用 分 离 合 取 算 符，避 免了 引 入 分 离 合 取 算 符 给 定 理 证 明 带 来 的 复 杂 性在形 状 图 上，关 联 到 不 同 节 点 的 断 言，就 是 分 离 逻 辑 中用 分 离 合 取 算 符 隔 开 的 断 言（）形 状 图 提 供 了 全 局 信 息用 形 状 图

122、逻 辑 很 容 易 发 现 对 某 堆 块 的 一 个指 针 域 的 赋 值 引 起 另 一 个 堆 块 的 泄 漏形 状 图 可 用 来 指 导 验 证 条 件 证 明 过 程 中 与易 变 数 据 结 构 有 关 的 归 纳 性 质 的 展 开，以 避 免 证 明过 程 的 不 终 止计 算 机 学 报 年分 离 逻 辑 优 于 形 状 图 逻 辑 的 重 要 一 点 是 它 适 用于 汇 编 语 言 级 的 程 序 推 理 使 用 分 离 逻 辑，但 验 证 条 件 的 证 明 策 略 类 似 本文 方 法 的 是 等 人 的 论 文 他 们 设 计 了 一 个蕴 涵 检 查 过 程，该

123、 过 程 使 用 展 开 和 折 叠 推 理，能 够 处理 可 能 是 归 纳 定 义 的 良 基 谓 词其 中 的 创 新 点 是 他们 找 到 了 一 种 在 有 用 户 定 义 归 纳 谓 词 情 况 下，保 证过 程 可 靠 和 终 止 的 充 分 条 件该 过 程 把 验 证 条 件 简化 到 标 准 的 逻 辑 理 论该 过 程 能 够 处 理 的 易 变 数 据结 构 超 越 了 树用 符 号 堆 也 是 把 握 程 序 状 态 中 的 指 针 信 息以 避 免 使 用 分 离 逻 辑，从 而 可 自 动 推 理 的 办 法 等 人 使 用 节 点 集 合 和 声 明 变 量 集

124、合，还 有 代 表 有 向 边 集、节 点 到 值 的 映 射 和 声 明 变 量到 值 的 映 射 的 若 干 函 数 来 描 述 程 序 状 态该 文 的 内存 印 迹（ ）由 符 号 堆 和 公 式 组 成，它 们 分 别 对 应 到 本 文 的 形 状 图犌和 数 据 结 构 所 需满 足 的 除 了 形 状 以 外 的 性 质犙 是 分 离 逻辑 的 一 种 方 言，本 质 上 是 堆 上 无 量 词 一 阶 逻 辑，并 用多 个 类 型 的 归 纳 定 义 来 增 强，这 些 类 型 是 为 其 下 有树 结 构 的 存 储 单 元 定 义 的它 用 一 个 可 靠 且 终 止 的

125、过 程，来 证 明 用 命 令 式 语 言 编 写 的 树 结 构 上 很 多 递归 算 法 的 功 能 完 全 正 确 性 等 人 使 用 集 合论，把 翻 译 成 带 递 归 的 经 典 逻 辑，并 提 出一 种 自 然 证 明 技 术 来 证 明 验 证 条 件这 种 技 术 提 供在 手 工 证 明 中 常 用 的 证 明 策 略 来 帮 助 验 证，并 把 这些 策 略 自 动 部 署 到 代 码 中 等 人 为 利 用 框 架 ，把 自 然 证 明 策 略 翻 译 成 嵌 在 标 注 中的 幽 灵 代 码，促 成 获 得 采 用 可 判 定 理 论 的 自然 证 明经 过 这 些

126、努 力，他 们 的 工 具 能 够 验 证 多 种 常见 的、包 括 用 递 归 或 迭 代 方 式 实 现 的、操 作 易 变 数 据结 构 的 程 序本 文 与 和 等 方 法 的 主 要 区 别 有点首 先，有 关 易 变 数 据 结 构 的 形 状 的 验 证，本 文 是 基 于形 状 图 蕴 涵 理 论，直 接 在 形 状 图 上 而 不 是 在 符 号 断言 上 验 证其 次，有 关 归 纳 谓 词 的 展 开 策 略，他 们 采用 由 程 序 员 提 供 证 明 策 略 的 方 式，而 本 文 所 设 计 的方 法 是 利 用 已 经 建 立 的 形 状 图 来 指 导 归 纳

127、谓 词 的 展开 和 折 迭最 后，他 们 的 方 法 必 须 由 程 序 员 提 供 完 整的 循 环 不 变 式，而 我 们 的 方 法 自 动 推 断 有 关 形 状 部分 的 循 环 不 变 式研 究 全 自 动 推 理 的 逻 辑 的 目 标 是 研 发 快 速、可靠 和 完 备 的 判 定 过 程为 达 到 该 目 标，这 些 逻 辑 的 表达 力 通 常 受 到 严 重 的 限 制对 于 堆 操 作 程 序 的 验 证逻 辑 来 说，使 用 可 达 性 谓 词 是 一 种 避 开 分 离 逻 辑 的 常用 简 便 方 式，但 表 达 能 力 上 受 到 较 大 限 制具 体 例

128、子有 在 一 阶 逻 辑 上 扩 展 可 达 性 的 若 干 逻 辑、 、 及 组 合 树 逻 辑 和 整 数 逻 辑 的 逻 辑 提 供 一 种 带 受 限 的 可 达 性 谓 词 和 量 化的 推 理这 种 逻 辑 有 完 全 自 动、可 靠、完 备 和 终 止的 判 定 过 程虽 然 这 是 一 个 高 效 的 判 定 过 程，但 是在 描 述 归 纳 数 据 结 构 性 质 时 表 达 力 上 非 常 有 限 也 是 一 种 这 样 的 逻 辑，它 能 够 应 对 某 些数 据 结 构 的 性 质，并 且 通 过 组 合 可 判 定 的 树 理 论 和算 术 理 论，容 许 可 判 定

129、 的 片 断然 而 它 在 表 达 力 上 极其 有 限这 些 逻 辑 都 不 足 以 描 述 诸 如 平 衡 二 叉 树 的平 衡 性 和 堆 中 的 一 组 键 值 在 通 过 一 段 程 序 后 没 有 改变 等 复 杂 性 质在 有 关 指 针 性 质 的 循 环 不 变 式 推 断 上， 等 人 提 出 了 一 种 用 分 离 逻 辑 推 断 单 链 表 操 作 程序 的 循 环 不 变 式 的 方 法他 们 使 用 符 号 执 行 机 制，并且 给 出 一 组 重 写 规 则 来 交 互 地 计 算 不 动 点所 实 现的 原 型 仅 完 成 了 计 算 表 长、求 各 节 点 数

130、 据 的 和、以 及链 表 的 删 除、倒 置、合 并 和 拆 分 这 几 种 简 单 的 单 链 表操 作 函 数 的 循 环 不 变 式 的 推 断 等 人 提 出 了 一 种 类 似 的 基 于 分 离 逻 辑 的 形 状 分 析 方 法和 文 献 一 样，它 使 用 了 专 为 单 链 表 的 展 开 和 折叠 而 设 计 的 单 链 表 谓 词，也 需 要 关 于 易 变 数 据 结 构形 状 的 先 验 知 识，并 且 也 使 用 符 号 执 行 机 制但 是 它的 单 链 表 谓 词 和 文 献 的 不 同，与 文 献 相 比，它 还 能 计 算 循 环 单 链 表 操 作 函

131、数 的 循 环 不 变 式，例如 循 环 单 链 表 的 删 除 函 数 和 过 滤 器 函 数 等人 提 出 了 一 种 基 于 分 离 逻 辑 的 过 程 间 形 状 分 析，它 执 行 归 纳 的 递 归 综 合，以 自 动 推 断 有 类 似 树 骨 架的 任 意 递 归 形 状 不 变 式其 主 要 特 点 是 从 循 环 体 的固 定 迭 代 次 数 的 符 号 执 行 中 抽 取 循 环 不 变 式，但 是只 能 用 于 树 骨 架 的 形 状对 于 单 链 表、循 环 单 链 表 和二 叉 树， 等 人 不 仅 能 推 断 有 关 形 状 的 循 环 不变 式，而 且 能 推

132、断 有 关 相 邻 节 点 数 值 数 据 的 循 环 不变 式，推 进 了 他 们 先 前 的 工 作 ，也 使 得 他 们 的 结果 优 于 其 他 人 的 结 果他 们 也 采 用 符 号 执 行 机 制，对循 环 体 进 行 迭 代 计 算，其 特 点 是 使 用 专 门 设 计 的 最小 上 界 算 子 和 加 宽 算 子 来 保 证 收 敛 到 不 动 点本 文 和 文 献 相 比，两 者 循 环 不 变 式 的 推 断算 法 都 是 基 于 文 献 我 们 的 特 点 是 采 用 本 文 的形 状 图 蕴 涵 理 论，在 形 状 图 上 直 接 推 断 循 环 不 变 形状 图，

133、文 献 的 特 点 是 还 能 推 断 有 关 相 邻 节 点 数值 数 据 的 循 环 不 变 式在 保 证 收 敛 到 不 动 点 上，我 们 期张昱 等：形 状 图 理 论 的 定 理 证 明采 用 形 状 图 上 的 蕴 涵 规 则 ，并 且 用 该 文 的 形 状 系统 来 保 证 算 法 的 终 止就 推 断 有 关 形 状 的 循 环 不 变式 而 言，文 献 能 推 断 操 作 单 链 表、循 环 单 链 表 和二 叉 查 找 树 的 代 码 的 循 环 不 变 式，而 我 们 还 能 推 断操 作 双 向 链 表、循 环 双 向 链 表 和 伸 展 树 的 代 码 的 循环

134、不 变 形 状 图从 第节 及 表可 知，本 文 推 断 循 环 不 变 形 状图 的 能 力 远 胜 于 上 面 几 项 工 作这 是 由 于 本 文 的 推断 得 到 形 状 系 统 的 支 持也 正 是 由 于 形 状 系 统 的 支持，本 文 还 能 推 断 递 归 函 数 的 前 后 形 状 图据 我 们 所知，尚 未 有 这 方 面 论 文 的 发 表图 逻 辑 或 形 状 逻 辑 一 般 是 指 推 导 图（或 有 向 图、形 状 图）性 质 的 空 间 逻 辑 其 中 图 是 用 符 号 公式 来 描 述 而 符 号 公 式 的 语 法 由 简 单 文 法 来 定 义，要推 导

135、 的 图 上 的 性 质 也 用 符 号 公 式 来 表 示，推 导 规 则也 还 是 基 于 符 号 公 式 的超 边 替 换 文 法（ ） 是 一 个 实 例它 用 超 图 为堆 状 态 建 模，把 双 向 的 图 规 则 用 于 超 图 的 变 换但 是该 文 法 只 是 作 为 动 态 数 据 结 构 建 模 的 一 种 直 观 的 形式 方 法，超 图 和 规 则 等 还 是 用 符 号 公 式 来 表 示 的本文 所 用 的 形 状 图 逻 辑 与 它 们 有 根 本 的 区 别：形 状 图直 接 作 为 逻 辑 公 式，出 现 在 程 序 逻 辑 的 推 理 规 则 中，并 且

136、还 可 以 和 符 号 公 式 一 起 演 算从 规 范 语 言 的 综 述 和 工 业 界 的 使 用看，迄今 为 止 尚 无 像 本 文 这 样 采 用 形 状 图 或 采 用 其 他 非 符号 方 式 来 表 达 程 序 的 部 分 性 质，并 与 表 达 程 序 其 余性 质 的 符 号 断 言 一 起 作 为 程 序 的 规 范 并 一 起 演算 的 总结随 着 面 临 越 来 越 复 杂 系 统 的 定 理 证 明，逻 辑 系统 也 面 临 逻 辑 公 式 复 杂、推 理 规 则 复 杂 和 自 动 定 理证 明 困 难 等 问 题为 降 低 难 度，从 本 文 的 经 验 看，把

137、其 中 适 合 于 用 图 形 表 示 的 领 域 专 用 逻 辑 图 形 化，形成 符 号 逻 辑 和 图 形 逻 辑 的 组 合，是 一 条 可 以 尝 试 的途 径下 一 步 将 考 虑 怎 样 在 目 前 基 础 上 设 计 实 用 性 大大 提 高 的 形 状 图 逻 辑 和 形 状 系 统首 先，充 实 基 本 形状 集，并 分 成 单 态 基 本 形 状 和 多 态 基 本 形 状单 态 基本 形 状 的 特 点 是，易 变 数 据 结 构 中 各 节 点 的 类 型 相同，各 节 点 所 含 指 针 数 相 同 并 且 它 们 指 向 的 类 型 都是 节 点 本 身 的 类

138、型本 文 谈 及 的 单 链 表 等种 形 状都 属 于 单 态 基 本 形 状多 态 基 本 形 状 的 特 点 是，易 变数 据 结 构 中 各 节 点 的 类 型 相 同，各 节 点 所 含 指 针 数可 以 不 同 但 它 们 指 向 的 类 型 都 是 节 点 本 身 的 类 型节 点 的 多 态 性 依 靠 节 点 类 型 中 的 共 用 体 域 来 体 现例 如 编 译 器 中 常 用 的 抽 象 语 法 树 就 可 以 设 计 成 多 态基 本 形 状其 次，规 定 复 杂 形 状 的 构 造 方 式，并 相 应 地 修 改形 状 系 统 中 的 形 状 推 断 规 则 和 形

139、 状 检 查 规 则复 杂形 状 至 少 有 嵌 套 形 状、含 内 部 附 加 指 针 的 形 状 和 含外 来 附 加 指 针 的 形 状 这 样 三 类，它 们 在 构 造 方 式 上的 特 点 分 别 是：各 节 点 都 有 指 向 同 种 内 嵌 形 状 的 指针（例 如 双 向 链 表 的 节 点 都 有 指 针 指 向 各 自 的 单 链表） 、各 节 点 都 有 指 向 本 形 状 节 点 的 附 加 指 针（例 如带 父 节 点 指 针 的 二 叉 树） 、来 自 形 状 外 部 的 附 加 指 针（例 如 队 列 可 以 看 成 带 一 个 这 种 附 加 指 针 的 单

140、链 表，附 加 指 针 指 向 链 表 的 最 后 一 个 节 点）用 基 本 形 状 集 加 上 复 杂 形 状 的 几 种 构 造 方 式，可 以 控 制 住 易 变 数 据 结 构 的 复 杂 性，并 满 足 大 部 分应 用 对 易 变 数 据 结 构 的 需 求，同 时 也 使 得 扩 展 形 状图 逻 辑 来 自 动 验 证 操 作 复 杂 易 变 数 据 结 构 的 程 序 成为 可 能致谢感 谢 刘 刚、张 志 天、宋 艳 辉、孟 建 超、韩 亚 慧和 郝 韛 等 研 究 生，他 们 为 实 现 系 统 原 型 做 出 了 贡 献！参考文献 ， ， ， ： ， ， （） ： ，

141、 ， ， ： ， ， ： ， ， ： ， ， ， ， ： ， ， ， ， ， ： ， ， ： ， ， ： 计 算 机 学 报 年 ， ： ， ， ： ： ， ： ， ， ： ， ， ： ， ， ，： ， ， ， ， （ ） ： ， ： ， ： ， ： ， ， ： ， ： ， ， ， ： ， ， （） ： （ ）（张 志 天，李 兆 鹏，陈 意 云，刘 刚一 个 程 序 验 证 器 的 设 计 和实 现计 算 机 研 究 与 发 展， ， （） ： ） ： ， ， ： ， ， ： ， ， ： ， ， ， ， ： ， ， ， ： ， ， ， ： ， ， ： ， ， ， ： ， ， ， ， ： ，

142、， ， ， ： ， ， ， ， ： ， ， ， （） ： ， ， ， ， ： ， ， ， ， ， ， ， ： ， ， ， ， ： ， ， ， ： ， ， ： ， ： ， ， ： ， ， ， ， ， ： ， ， ， ， ： ， ， ， ， 期张昱 等：形 状 图 理 论 的 定 理 证 明 ， ， ， ， ， ， ， ： ， ， ， ， ： ， ， ， ， ， ： ， ， ， ， ， ： ， ， ： ， ， ， ： ， ， ， ， ， （） ： 犣 犎 犃 犖 犌 犢 狌， ， ， ， ， 犆 犎 犈 犖 犢 犻 犢 狌 狀， ， ， ， ， 犔 犐 犣 犺 犪 狅 犘 犲 狀 犵， ， ， ， ， 犅 犪 犮 犽 犵 狉 狅 狌 狀 犱 （ ） ， ， ， ， ， ， ， ， ， ， ： ， ， ， ， ， ， ， ， ， ， ， 犃 犛 犺 犪 狆 犲 犌 狉 犪 狆 犺犔 狅 犵 犻犮 犪 狀 犱 犪 犛 犺 犪 狆 犲 犛 狔 狊狋犲 犿 犑 狅 狌 狉 狀 犪 犾 狅 犳 犆 狅 犿 狆 狌 狋犲 狉犛 犮犻犲 狀 犮 犲 犪 狀 犱 犜 犲 犮 犺 狀 狅 犾 狅 犵 狔， （） ， ， （ ） ， ， 计 算 机 学 报 年