Microsoft PowerPoint - plan06.ppt

Transcription

1 程 序 设 计 语 言 原 理 Principle of Programming Languages 裘 宗 燕 北 京 大 学 数 学 学 院 ~ 基 本 控 制 抽 象 子 程 序 抽 象 子 程 序 活 动 和 局 部 环 境 静 态 实 现 模 型 一 般 实 现 模 型 调 用 序 列 和 在 线 展 开 参 数 机 制 泛 型 子 程 序 异 常 处 理 其 他 子 程 序 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 2

2 机 器 模 型 寄 存 器 组 代 码 区 数 据 区 栈 程 序 指 针 静 态 数 据 区 堆 环 境 指 针 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 3 控 制 抽 象 和 子 程 序 抽 象 是 一 种 手 段, 用 于 建 立 一 个 名 字 与 一 段 可 能 复 杂 的 程 序 片 段 的 关 联, 而 后 可 以 只 考 虑 名 字 功 能 使 用 方 式 和 使 用, 无 须 再 考 虑 其 实 现 细 节 通 常 需 要 区 分 控 制 抽 象 : 抽 象 的 对 象 是 实 现 某 种 功 能 的 可 能 复 杂 的 操 作 数 据 抽 象 : 抽 象 的 对 象 是 被 操 作 数 据 概 念 和 相 关 功 能 本 章 讨 论 控 制 抽 象, 控 制 抽 象 的 主 要 目 的 是 定 义 和 实 现 能 良 好 执 行 的 操 作 有 关 数 据 抽 象 的 问 题 是 下 面 两 章 的 内 容 子 程 序 是 最 主 要 的 计 算 过 程 抽 象 机 制 ( 子 程 序 抽 象 ) 一 个 子 程 序 封 装 一 段 程 序 代 码 并 给 以 命 名, 可 通 过 子 程 序 名 引 用 这 段 代 码, 启 动 其 执 行, 完 成 代 码 所 描 述 的 计 算 建 立 好 的 一 个 子 程 序 可 能 多 次 执 行, 甚 至 可 能 同 时 存 在 多 个 不 同 的 执 行, 甚 至 可 能 存 在 多 个 同 时 处 于 活 动 状 态 的 执 行 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 4

3 子 程 序 抽 象 广 义 的 子 程 序 就 是 指 一 段 代 码, 可 以 独 立 地 启 动 和 运 行, 是 最 一 般 的 概 念, 常 见 的 具 体 子 程 序 概 念 包 括 : 过 程 : 完 成 一 系 列 动 作 的 顺 序 子 程 序, 具 有 典 型 的 后 进 先 出 性 质 函 数 : 一 类 过 程, 其 执 行 的 基 本 目 的 是 算 出 一 个 值 ( 可 用 在 表 达 式 里 ) OO 语 言 里 类 的 方 法, 是 附 着 在 类 的 实 例 对 象 上 的 子 程 序 协 作 子 程 序 : 允 许 同 时 存 在 多 个 正 在 执 行 中 的 协 程, 协 程 之 间 采 用 显 式 的 挂 起 / 唤 醒 方 式 转 移 控 制 权, 每 个 时 刻 只 有 一 个 协 程 处 于 活 动 状 态 并 行 子 程 序 : 可 同 时 存 在 多 个 执 行, 由 基 础 支 持 系 统 ( 调 度 器 等 ) 确 定 控 制 转 移, 一 个 时 刻 可 能 有 多 个 并 行 的 活 动 ( 进 程 ) 子 程 序 通 常 专 指 过 程 和 函 数 其 他 子 程 序 在 很 多 基 本 问 题 上 与 之 类 似 子 程 序 可 以 看 成 一 种 操 作 扩 充 机 制, 用 于 扩 充 语 言 里 描 述 计 算 的 基 本 词 汇 表, 从 而 建 立 起 新 的 描 述 层 次 这 是 最 基 本 的 扩 充 需 要 定 义 好 的 子 程 序 就 像 基 本 操 作, 通 过 这 种 方 式 可 以 分 层 建 立 复 杂 的 计 算 抽 象 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 5 子 程 序 抽 象 子 程 序 的 其 他 重 要 作 用 : 子 程 序 实 现 一 个 局 部 的 计 算 环 境, 是 一 种 控 制 的 封 装 和 屏 蔽 机 制 局 部 环 境 具 有 私 密 性, 与 外 围 环 境 之 间 有 清 晰 的 划 分 与 外 围 环 境 之 间 有 清 晰 的 接 口, 可 通 过 接 口 单 向 或 双 向 传 递 信 息 子 程 序 定 义 一 种 作 用 域, 通 常 是 单 向 透 明 的 ( 开 作 用 域 ) 外 部 定 义 在 其 内 部 可 见, 内 部 定 义 在 子 程 序 外 不 可 见 子 程 序 是 一 种 决 定 对 象 生 存 期 的 程 序 单 元, 子 程 序 里 定 义 的 对 象 在 子 程 序 的 运 行 开 始 时 创 建, 其 生 存 期 在 子 程 序 的 执 行 结 束 时 都 结 束 过 程 和 函 数 的 后 进 先 出 性 质, 可 以 利 用 栈 结 构 方 便 地 管 理 子 程 序 调 用 所 需 的 内 存, 管 理 方 便, 效 率 高 其 他 子 程 序 需 要 更 复 杂 的 运 行 支 持, 子 程 序 间 控 制 转 移 的 代 价 可 能 更 高, 资 源 消 耗 更 大 所 以 : 只 要 可 能, 最 好 是 用 常 规 的 函 数 / 过 程 描 述 计 算, 不 使 用 更 复 杂 的 子 程 序 ( 如 协 作 子 程 序, 并 发 子 程 序 等 ) 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 6

4 子 程 序 : 参 数 化 子 程 序 的 最 直 接 发 展 是 参 数 化 想 法 来 源 于 汇 编 语 言 的 宏 参 数 化 使 子 程 序 更 加 通 用 实 现 参 数 化 的 方 式 就 是 把 子 程 序 性 质 中 的 某 个 部 分 抽 取 出 来, 建 立 反 映 了 这 一 部 分 的 变 化 的 参 数 参 数 化 使 同 一 段 代 码 可 以 作 用 于 不 同 的 实 际 参 数 集 合 实 际 程 序 设 计 对 参 数 有 许 多 不 同 的 需 要 人 们 针 对 不 同 需 要 提 出 了 许 多 不 同 的 参 数 机 制 参 数 机 制 的 设 计 集 考 虑 编 程 需 要, 也 考 虑 实 现 的 方 便 性 和 效 率 子 程 序 的 定 义 调 用 参 数 化, 局 部 环 境 的 建 立 和 使 用 等 等, 都 引 起 复 杂 的 语 义 问 题 和 实 现 技 术 问 题 理 解 子 程 序 带 来 的 这 些 问 题, 是 理 解 程 序 语 言 的 最 关 键 问 题 之 一 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 7 语 言 的 子 程 序 结 构 不 同 程 序 设 计 语 言 可 能 采 用 不 同 的 子 程 序 结 构 常 见 的 : 单 层 结 构 : 一 个 主 程 序 和 位 于 同 一 个 层 次 的 一 组 子 程 序 不 允 许 在 子 程 序 里 嵌 套 定 义 子 程 序 这 种 结 构 最 简 单 如 Fortran C 语 言 的 情 况 类 似, 但 它 没 有 真 正 的 主 程 序, 只 有 一 个 预 先 定 义 的 执 行 入 口 子 程 序 ( 通 常 以 main 作 为 它 的 名 字 ) 嵌 套 结 构 : 一 个 主 程 序 和 在 它 内 部 嵌 套 定 义 的 一 些 子 程 序 允 许 任 意 深 层 的 嵌 套 (Algol 60/Pascal 等 等 ) 更 复 杂 的 嵌 套 结 构 如 Ada, 允 一 组 最 外 层 程 序 单 元, 可 以 是 子 程 序, 也 可 以 是 另 外 几 种 结 构, 包 括 : 包 作 业 等 可 指 定 其 中 任 何 一 个 作 为 执 行 入 口 面 向 对 象 语 言 允 许 在 数 据 描 述 里 嵌 套 定 义 子 程 序 许 多 语 言 允 许 子 程 序 内 嵌 套 分 程 序 ( 复 合 语 句 ) 局 部 环 境 分 程 序 建 立 起 子 程 序 内 部 的 局 部 定 义 环 境 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 8

5 子 程 序 的 定 义 与 执 行 理 解 子 程 序 行 为 的 第 一 步 是 分 清 子 程 序 的 定 义 和 执 行 子 程 序 定 义 是 一 种 语 言 结 构, 其 最 基 本 的 部 分 是 一 个 代 码 体, 其 中 描 述 该 子 程 序 需 要 执 行 的 动 作 子 程 序 有 一 个 接 口 描 述, 说 明 它 的 使 用 形 式, 对 这 个 子 程 序 的 所 有 使 用 都 必 须 符 合 这 个 描 述 的 要 求 接 口 描 述 通 常 包 括 : 子 程 序 名 和 参 数 / 返 回 值 描 述 可 能 包 括 有 关 数 据 传 递 的 约 定 ( 类 型, 采 用 什 么 参 数 模 式 等 ) 要 求 子 程 序 执 行 的 语 法 形 式 称 为 子 程 序 调 用 执 行 子 程 序 的 调 用, 将 导 致 子 程 序 代 码 体 的 实 际 执 行 一 个 子 程 序 应 该 有 且 只 有 一 个 定 义, 可 以 有 0 个 或 多 个 调 用 需 要 分 清 : 定 义 时 环 境 : 定 义 所 在 的 上 下 文 环 境 执 行 时 环 境 : 调 用 所 在 的 上 下 文 环 境 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 9 子 程 序 的 定 义 和 执 行 子 程 序 描 述 的 主 要 部 分 是 其 代 码 体 ( 子 程 序 体 ), 子 程 序 实 现 的 主 要 部 分 就 是 由 其 代 码 体 生 成 的 目 标 代 码 子 程 序 的 接 口 描 述 通 常 只 是 为 编 译 器 阅 读 者 提 供 信 息, 支 持 其 工 作 子 程 序 接 口 本 身 通 常 并 不 生 成 代 码 为 实 现 子 程 序 功 能, 主 要 就 是 实 现 子 程 序 的 调 用 和 正 确 执 行, 还 需 要 生 成 一 些 辅 助 性 代 码, 主 要 是 两 段 代 码 : 前 序 代 码 : 在 子 程 序 本 身 的 代 码 执 行 前 完 成 一 些 准 备 工 作 后 序 代 码 : 结 束 前 的 清 扫, 为 正 确 返 回 调 用 方 而 做 一 些 的 恢 复 工 作 理 解 子 程 序 执 行 的 意 义, 需 要 : 为 执 行 中 的 子 程 序 建 立 一 个 清 晰 模 型 理 解 子 程 序 执 行 时 的 引 用 环 境 ( 包 括 局 部 环 境 ) 的 建 立 使 用 和 撤 销 理 解 参 数 的 传 递 机 制 和 返 回 值 机 制 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 10

6 子 程 序 定 义 : 界 面 与 实 现 子 程 序 的 定 义 分 为 两 个 部 分 : 描 述 子 程 序 与 外 界 关 系 的 界 面 定 义 部 分 子 程 序 名 字 子 程 序 的 参 数 o 各 个 参 数 的 类 型 o 信 息 传 递 方 式 ( 参 数 模 式, 下 面 有 详 细 讨 论 ) o 参 数 名 ( 以 便 在 子 程 序 体 里 使 用 外 界 传 来 的 信 息 ) 返 回 值 ( 是 否 有, 如 何 返 回 等 ) 描 述 子 程 序 执 行 时 的 局 部 环 境 和 动 作 的 实 现 部 分 局 部 定 义, 定 义 局 部 环 境 里 的 变 量 等 成 分 代 码 体, 定 义 子 程 序 调 用 时 的 动 作 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 11 子 程 序 活 动 当 子 程 序 P 被 调 用 时, 需 要 为 它 建 立 一 个 活 动, 其 中 包 括 P 的 代 码 体 ( 或 当 时 代 码 执 行 情 况 的 记 录, 即 当 前 的 代 码 执 行 位 置 ) 一 个 表 征 P 的 局 部 状 态 的 数 据 结 构, 称 为 活 动 记 录 (activity record) 活 动 记 录 是 根 据 P 的 局 部 数 据 做 出 的 安 排 ( 布 局 ), 其 中 包 括 : P 的 所 有 参 数 和 局 部 变 量 为 支 持 子 程 序 启 动 执 行 和 结 束 所 需 的 各 种 辅 助 性 数 据 结 构 P 的 每 个 调 用 启 动 时 将 建 立 一 个 新 活 动 记 录, 该 活 动 结 束 时 销 毁 这 个 记 录 这 种 活 动 记 录 也 是 数 据 对 象 ( 内 部 数 据 对 象 ), 因 此 有 创 建 和 销 毁 在 子 程 序 运 行 过 程 中 被 使 用 和 修 改 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 12

7 子 程 序 活 动 执 行 中 可 能 同 时 存 在 P 的 多 个 不 同 活 动 ( 如 有 递 归 调 用 的 过 程 ): 每 个 活 动 需 要 有 一 个 独 立 的 活 动 记 录 多 个 活 动 可 以 共 享 P 的 同 一 代 码 段 ( 在 常 规 语 言 里, 代 码 是 静 态 的, 不 必 建 立 多 个 副 本 ) 不 应 该 说 在 子 程 序 P 里 执 行 语 句 S, 严 格 说 法 应 该 是 在 子 程 序 P 的 某 个 具 体 活 动 R 里 执 行 语 句 S 应 区 分 子 程 序 P 和 子 程 序 P 的 一 个 具 体 活 动 子 程 序 P 的 一 个 具 体 活 动 的 执 行 状 态 由 以 下 几 部 分 组 成, 其 中 最 主 要 的 部 分 就 是 P 的 这 个 活 动 的 局 部 引 用 环 境 : 代 码 体 的 当 前 执 行 位 置 ( 确 定 下 一 条 要 执 行 的 指 令 ) 当 时 活 动 记 录 的 状 态, 主 要 是 P 的 所 有 局 部 变 量 的 取 值 情 况 可 能 存 在 的 尚 未 记 录 到 内 存 ( 活 动 记 录 ) 里 的 寄 存 器 状 态 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 13 子 程 序 执 行 为 了 支 持 程 序 的 执 行, 需 要 两 个 指 针 : IP( 指 令 指 针 ) 它 总 指 向 当 前 活 动 子 程 序 的 代 码 体 里 的 一 个 位 置 ( 指 向 将 要 执 行 的 那 条 指 令 ), 并 随 着 指 令 的 执 行 而 更 新 EP( 环 境 指 针,fp, 帧 指 针 ) 它 指 向 当 前 子 程 序 的 当 前 活 动 记 录 由 它 出 发 可 以 确 定 当 前 子 程 序 里 的 所 有 数 据 引 用 子 程 序 代 码 体 里 的 大 部 分 数 据 引 用 都 是 基 于 这 个 指 针 得 到 o 局 部 数 据 ( 变 量 / 参 数 ) 通 过 这 个 指 针 加 上 静 态 确 定 的 偏 移 量 o 对 静 态 环 境 中 的 变 量, 代 码 中 可 以 直 接 引 用 o 其 他 非 局 部 引 用 需 要 专 门 支 持 ( 后 面 讨 论 ) 随 着 指 令 的 执 行,IP 自 动 更 新 到 新 确 定 的 指 令 位 置 ( 下 一 条 / 其 他 位 置 ) 代 码 中 的 指 令 基 于 环 境 指 针 更 新 当 前 活 动 记 录 中 的 某 些 数 据 项 ( 还 可 能 修 改 静 态 环 境 和 外 围 环 境 ), 从 而 实 现 程 序 执 行 中 的 状 态 改 变 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 14

8 子 程 序 执 行 程 序 开 始 执 行 前 建 立 主 程 序 的 活 动 记 录 ( 静 态 创 建, 如 有 主 程 序 ), 令 EP 指 向 该 记 录,IP 指 向 主 程 序 代 码 段 的 起 始 位 置, 程 序 开 始 执 行 在 启 动 ( 调 用 ) 一 个 子 程 序 时, 需 要 保 存 当 前 子 程 序 活 动 记 录 和 IP/EP, 还 需 保 存 一 些 有 用 的 寄 存 器 值 ( 子 程 序 恢 复 执 行 时 还 需 要 恢 复 和 使 用 的 值 ) 为 被 调 用 的 子 程 序 创 建 一 个 新 活 动 记 录, 设 置 IP/EP 指 针 ( 转 换 环 境, 转 换 执 行 点 ), 而 后 令 控 制 转 入 被 调 用 的 子 程 序 ( 按 设 置 好 的 新 IP 执 行 ), 实 现 执 行 现 场 的 转 移 当 需 要 转 到 一 个 以 前 暂 停 的 子 程 序 时, 需 要 恢 复 原 来 保 存 的 现 场 保 存 当 前 子 程 序 的 状 态 ( 活 动 记 录, 有 用 的 寄 存 器 和 IP/EP 指 针 ) 恢 复 以 前 保 存 的 寄 存 器 值 和 IP/EP 值 按 恢 复 后 的 IP 值 继 续 执 行 这 是 最 一 般 的 子 程 序 间 控 制 转 移 和 执 行 模 型 过 程 / 函 数 调 用 的 实 现 等 都 是 它 的 特 例 下 面 将 讨 论 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 15 函 数 / 过 程 的 抽 象 执 行 模 型 子 程 序 之 间 控 制 转 移 的 最 简 单 情 况 是 过 程 / 函 数 的 调 用 / 返 回 ( 下 面 讨 论 中 的 子 程 序 专 指 它 们 ) 这 种 情 况 下 子 程 序 之 间 的 控 制 转 移 有 层 次 性 : 调 用 时, 控 制 转 到 被 调 子 程 序 被 调 子 程 序 结 束 时, 控 制 转 回 调 用 ( 主 调 ) 子 程 序 ( 后 进 先 出 ) 处 于 活 动 状 态 ( 执 行 中, 尚 未 结 束 ) 的 子 程 序 可 能 有 许 多, 在 调 用 一 个 新 子 程 序 时, 当 时 的 IP/EP 值 保 存 在 哪 里? 对 函 数 和 过 程, 由 于 后 进 先 出 性 质, 合 适 的 方 式 是 将 它 们 保 存 在 被 调 子 程 序 活 动 记 录 里 的 某 个 固 定 位 置, 子 程 序 返 回 时 可 以 方 便 地 取 出 使 用 为 了 恢 复 子 程 序 执 行 的 现 场, 可 能 需 要 同 时 保 存 另 外 一 些 信 息 采 用 活 动 记 录 和 IP/EP 指 针 对, 可 很 好 解 决 子 程 序 调 用 中 的 基 本 问 题 这 是 抽 象 的 过 程 / 函 数 调 用 模 型, 可 以 ( 根 据 情 况 ) 派 生 出 多 种 具 体 实 现 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 16

9 函 数 过 程 的 局 部 数 据 布 局 函 数 / 过 程 的 定 义 中 描 述 了 它 执 行 时 的 局 部 环 境 : 函 数 / 过 程 内 部 各 变 量 的 类 型 数 组 的 形 状 等 编 译 时 为 子 程 序 p 里 的 局 部 定 义 做 出 某 种 安 排, 确 定 局 部 环 境 的 布 局 int p (int n) { int a[10];... if (...) { int m;... } else { int b[2];... }... return a[0]; } p 的 相 关 数 据 布 局 a n 返 回 地 址 临 时 量 局 部 变 量 簿 记 信 息 等 参 数, 返 回 值 局 部 数 据 基 址 局 部 数 据 所 需 的 存 储 量 应 能 静 态 计 算, 位 置 可 任 意 安 排 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 17 静 态 模 型 早 期 的 Fortran(90 之 前 )/Cobol 等 可 以 采 用 静 态 模 型 实 现 子 程 序 : 运 行 中 任 何 时 刻 每 个 子 程 序 ( 至 多 ) 只 有 一 个 活 动 记 录, 因 此 可 以 在 执 行 前 静 态 建 立 所 有 子 程 序 的 活 动 记 录 ( 都 在 静 态 区 分 配 ) 子 程 序 代 码 中 都 能 直 接 访 问 活 动 记 录 里 的 对 象 ( 不 需 要 EP), 效 率 高 程 序 执 行 时 装 入 代 码, 将 IP 设 置 到 主 程 序 代 码 的 开 始 后 启 动 执 行 调 用 子 程 序 时, 将 当 时 的 IP 存 入 被 调 子 程 序 的 活 动 记 录 里 的 固 定 位 置, 将 IP 设 置 到 被 调 子 程 序 代 码 第 一 条 指 令, 使 控 制 转 入 子 程 序 代 码 返 回 时, 由 当 前 子 程 序 活 动 记 录 取 出 保 存 的 IP 值, 转 入 调 用 程 序 执 行 由 于 Fortran/Cobol 语 言 不 允 许 子 程 序 的 递 归 调 用, 因 此 每 个 子 程 序 至 多 只 存 在 一 个 活 动, 因 此 才 能 采 用 简 单 的 静 态 实 现 模 型 静 态 模 型 下 的 局 部 和 全 局 数 据 都 可 以 直 接 寻 址, 调 用 的 辅 助 工 作 较 少 ( 可 能 需 要 保 存 一 些 寄 存 器, 也 可 存 入 被 调 子 程 序 的 活 动 记 录 ), 实 现 效 率 高 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 18

10 静 态 模 型 对 这 类 语 言, 也 可 以 考 虑 采 用 后 面 介 绍 的 技 术, 动 态 创 建 活 动 记 录 如 果 程 序 实 际 执 行 的 子 程 序 比 程 序 里 定 义 的 子 程 序 少 得 多, 采 用 动 态 建 立 活 动 记 录 的 技 术 可 以 节 约 存 储 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 19 调 用 返 回 的 一 般 模 型 递 归 是 很 有 用 的 编 程 技 术 如 果 语 言 支 持 递 归, 程 序 运 行 中, 就 可 能 同 时 存 在 一 个 子 程 序 的 多 个 活 动, 需 要 用 多 个 活 动 记 录 表 示 它 们 这 时 就 必 须 采 用 IP/EP 对 的 技 术, 在 调 用 子 程 序 时 动 态 地 为 其 创 建 新 的 活 动 记 录 如 果 调 用 后 进 先 出, 活 动 记 录 可 用 栈 分 配, 称 为 栈 帧, 用 帧 指 针 fp 作 为 EP 程 序 运 行 中 栈 里 保 存 着 一 些 帧 ( 子 程 序 活 动 记 录 ), 每 个 帧 里 保 存 的 ep 是 栈 里 下 一 个 子 程 序 帧 的 地 址, 形 成 一 条 链 ( 称 为 动 态 调 用 链 ) 帧 的 分 配 释 放 表 现 为 栈 的 压 入 和 弹 出 计 算 机 硬 件 为 这 种 模 型 提 供 了 支 持 许 多 机 器 提 供 了 专 用 的 栈 寄 存 器 ( 或 者 允 许 用 任 何 寄 存 器 作 为 栈 指 针 ) 和 专 门 的 栈 指 令 Fortran 90 里 定 义 可 能 递 归 的 子 程 序 需 加 关 键 字 RECURSIVE( 借 自 PL/I), 要 求 这 些 子 程 序 的 活 动 记 录 必 须 实 现 为 动 态 创 建 的 栈 帧, 其 余 子 程 序 的 活 动 记 录 可 以 不 入 栈 ( 常 见 语 言 里, 如 Pascal/C 等, 所 有 活 动 记 录 都 入 栈 ) Fortran 90 方 式 可 能 提 高 效 率, 但 有 危 险 ( 递 归 子 程 序 忘 记 加 关 键 字 ) 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 20

11 调 用 返 回 的 一 般 模 型 寄 存 器 动 态 链 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 21 子 程 序 : 引 用 环 境 子 程 序 运 行 时 的 完 整 引 用 环 境 包 括 : 静 态 环 境 ( 可 能 没 有 ) 全 局 和 静 态 变 量 在 静 态 区 分 配, 子 程 序 代 码 里 的 全 局 数 据 访 问 都 编 译 为 绝 对 地 址 寻 址, 或 者 相 对 于 静 态 区 基 址 的 偏 移 量 寻 址 局 部 环 境 按 编 译 时 确 定 的 局 部 环 境 布 局 创 建 栈 帧, 其 中 的 每 个 量 都 在 编 译 时 确 定 在 帧 里 的 位 置, 是 基 于 帧 指 针 (fp) 值 的 相 对 位 置 子 程 序 代 码 里 的 局 部 数 据 访 问, 都 编 译 为 相 对 于 fp 的 偏 移 量 寻 址 非 全 局 外 围 环 境 ( 可 能 没 有, 如 Fortran C 等 ) 外 围 子 程 序 形 成 的 引 用 环 境, 需 要 用 更 复 杂 的 寻 址 方 式 ( 后 面 讨 论 ) OO 语 言 方 法 的 调 用 对 象 形 成 的 外 围 环 境, 通 过 自 动 产 生 的 特 殊 指 针 参 数 this 和 偏 移 量 访 问 年 4 月 程 序 设 计 语 言 原 理 第 6 章 22

12 全 局 环 境 和 静 态 区 一 些 语 言 提 供 了 全 局 环 境, 作 为 所 有 子 程 序 的 环 境 的 一 部 分 全 局 环 境 在 程 序 运 行 前 静 态 建 立, 在 程 序 执 行 期 间 始 终 存 在 用 一 块 静 态 存 储 区 实 现 全 局 环 境 分 配 所 有 全 局 变 量, 确 定 位 置 和 大 小 其 他 静 态 对 象 也 在 静 态 区 分 配 :C 局 部 静 态 变 量,C++/Java 类 静 态 成 员 全 局 对 象 的 初 始 化 在 程 序 运 行 前 完 成 一 般 不 允 许 在 这 种 初 始 化 描 述 里 包 含 源 程 序 代 码, 只 允 许 写 能 静 态 计 算 的 表 达 式 有 些 语 言 允 许 在 初 始 化 中 执 行 代 码 ( 例 如 C++), 模 糊 了 静 态 / 动 态 的 界 线 其 他 静 态 变 量 的 初 始 化 与 此 类 似, 有 些 语 言 有 特 殊 规 定 静 态 环 境 建 立 后, 程 序 就 可 开 始 执 行 各 种 语 言 都 规 定 了 程 序 的 执 行 入 口 ( 主 程 序, 或 默 认 / 指 定 的 子 程 序 ) Java 没 有 全 局 环 境, 对 象 都 是 局 部 的, 但 有 静 态 数 据 对 象 ( 类 的 静 态 成 员 ) 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 23 局 部 环 境 的 栈 实 现 子 程 序 P 的 运 行 环 境 主 要 通 过 P 的 栈 帧 实 现, 多 数 局 部 对 象 在 P 的 帧 里 有 一 个 存 储 位 置 ( 相 对 于 帧 指 针 的 特 定 偏 移 量 ); 也 可 能 有 些 变 量 不 分 配 内 存, 始 终 放 在 寄 存 器, 特 别 是 使 用 频 繁 且 定 义 域 局 部 的 变 量 当 P 的 某 个 活 动 是 当 前 活 动 时, 指 针 fp 指 向 P 当 时 活 动 的 帧, 在 P 的 代 码 执 行 中, 所 有 ( 分 配 了 存 储 的 ) 局 部 变 量 访 问 都 相 对 于 指 针 fp 进 行 子 程 序 里 的 局 部 分 程 序 ( 复 合 语 句 ) 环 境 也 在 活 动 记 录 里 分 配 位 置 如 果 有 可 能 只 使 用 寄 存 器, 就 可 以 不 在 栈 帧 里 为 它 们 分 配 存 储 位 置 如 果 分 配 的 位 置, 运 行 中 同 样 通 过 EP 间 接 访 问 互 不 相 交 的 分 程 序 可 以 共 享 活 动 记 录 里 的 位 置, 以 节 约 存 储 这 种 局 部 分 程 序 没 有 独 立 的 活 动, 因 此 比 较 容 易 处 理 对 于 像 C 语 言 一 样 采 用 平 坦 子 程 序 结 构 的 语 言, 引 用 环 境 只 有 两 层, 所 有 全 局 和 局 部 的 访 问 问 题 都 已 经 解 决 了 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 24

13 调 用 序 列 调 用 序 列 是 编 译 器 生 成 的 代 码 段, 完 成 子 程 序 调 用 和 退 出 时 的 运 行 栈 维 护 不 同 机 器 上 的 不 同 语 言 系 统 ( 对 不 同 语 言 ) 可 能 采 用 不 同 调 用 序 列 子 程 序 调 用 时, 从 原 程 序 暂 停 执 行 到 子 程 序 开 始 执 行 之 间 执 行 的 代 码 段 称 为 子 程 序 的 前 序 代 码 子 程 序 完 成 到 原 程 序 恢 复 执 行 间 执 行 的 代 码 段 称 为 子 程 序 的 后 序 代 码 前 序 代 码 和 后 序 代 码 都 可 能 分 为 两 部 分, 由 调 用 方 和 被 调 方 分 段 完 成 调 用 方 执 行 子 程 序 前 序 代 码 段 1( 保 存 调 用 方 状 态 的 主 要 部 分, 进 入 ) 被 调 方 执 行 子 程 序 前 序 代 码 段 2( 保 存 调 用 方 的 必 要 信 息 ) 执 行 被 调 子 程 序 的 代 码 被 调 方 执 行 后 序 代 码 段 1( 恢 复 调 用 方 的 必 要 信 息, 转 回 ) 调 用 方 执 行 后 续 代 码 段 2( 恢 复 调 用 方 状 态 后 继 续 执 行 ) 具 体 实 现 需 要 精 心 设 计 ( 栈 帧 的 设 计 前 后 序 代 码 设 计 和 功 能 分 配 ) 相 关 代 码 分 别 放 在 调 用 放 代 码 中, 被 调 用 方 代 码 的 前 后 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 25 调 用 序 列 : 平 坦 结 构 ( 例 如 C 语 言 ) 为 返 回 值 分 配 空 间 ( 移 sp) 计 算 并 压 入 各 个 实 参 值 压 入 返 回 地 址 分 配 帧, 保 存 原 fp 设 新 fp 保 存 必 要 的 寄 存 器 前 序 代 码 sp 新 fp 下 一 帧 参 数 返 回 值 临 时 量 局 部 变 量 被 调 方 负 责 执 行 子 程 序 基 本 代 码 计 算 并 存 入 返 回 值 恢 复 保 存 的 寄 存 器 恢 复 sp( 根 据 fp) 弹 出 子 程 序 帧, 恢 复 fp 调 用 方 继 续 后 序 代 码 当 前 帧 原 fp 保 存 状 态 返 回 地 址 参 数 返 回 值 调 用 方 负 责 2012 年 4 月 程 序 设 计 语 言 原 理 第 6 章 26