第16章多态类型

推导参数多态、类型推断、重载消解与多态值的IR翻译；用C编译流水线、状态轨迹和端到端验证门交付约束集、合一轨迹、类型方案、实例化与错误证明

学习目标

能说明“第16章多态类型”如何推导参数多态、类型推断、重载消解与多态值的IR翻译，并区分作者C/Java/ML轨道、中文C版与本站重写
能先预测“类型变量、约束、合一和泛化在什么作用域发生？”会改变哪一个C接口、树/图状态、AST/IR、汇编或运行结果，再操作三类交互证据
能只注入“对具有副作用的表达式错误执行一般化，产生不安全多态引用”，定位首个偏离“第16章多态类型的C模块接口、数据结构、状态变换、输出语义与测试始终一致”的状态，并从同一快照完成恢复

为什么从这个问题开始

“第16章多态类型”围绕“类型变量、约束、合一和泛化在什么作用域发生？”建立贯穿任务：在Tiger C实现轨道中复现“第16章多态类型”的输入、状态、变换与验证。先写下哪个C接口、树/图状态、AST/IR、汇编或运行结果会最先变化，再运行参考、故障和恢复路径；运行后补理由不算预测。只有守住“第16章多态类型的C模块接口、数据结构、状态变换、输出语义与测试始终一致”并交付约束集、合一轨迹、类型方案、实例化与错误证明，单模块测试、编译成功或性能变化才构成机制证据。

原版书目、296个正式坐标与C轨道边界

“第16章多态类型”以Andrew W. Appel作者官方目录核对 Modern Compiler Implementation 的C、Java、ML三种实现轨道、2部分、21章和Tiger语言附录；以作者C版页面核对Andrew·W·Appel与Maia Ginsburg、Cambridge University Press、C实现轨道、平装ISBN 0-521-60765-5、软件/练习模块与勘误入口，再以Cambridge C版页面核对原版身份。

“第16章多态类型”以中文版修订版完整目录核对赵克佳、黄春、沈志宇译《现代编译原理：C语言描述（修订版）》，人民邮电出版社，2018年，385页，ISBN 9787115476883。“第16章多态类型”的正式分母为2个部分标题、21个章标题、1个附录标题、251个编号节/小节、附录4节和17个正式“程序设计”项目，合计296个核心层级；每章重复的推荐阅读与习题不另计。

作者页面可访问不等于允许复制书稿，“第16章多态类型”不复制、翻译或改写原文、图表、伪码与习题；所有中文讲解、C接口示意、状态轨迹、反例、交互、练习和答案均为独立教学重写。本页独立核对 1只用于核对本页C实现或现代IR边界，不能混入Java/ML轨道或反向证明原书采用本站表述。

原版目录层级与C项目机制

第16章多态类型

正式坐标 1/15。 原版目录键 第16章多态类型。在“第16章多态类型”的第1个正式坐标中，「第16章多态类型」通过构造带源位置AST并沿作用域环境执行名字绑定和类型检查推进多态类型、合一与值限制；复核者保存CST—AST映射、环境快照、类型推导、错误路径与作用域恢复，出现节点语义、绑定顺序、类型约束或作用域恢复错位就撤回结论。

16·1 参数多态性

正式坐标 2/15。 原版目录键 16.1 参数多态性。围绕“类型变量、约束、合一和泛化在什么作用域发生？”，“第16章多态类型”在坐标2把「16·1 参数多态性」落实为生成约束、执行合一/泛化/实例化并翻译多态值；只有约束集、合一轨迹、类型方案、实例化与错误证明可重放且反例排除不安全一般化、 occurs-check 或重载消解错误，本节点才算掌握。

16·1·1 显式带类型的多态语言

正式坐标 3/15。 原版目录键 16.1.1 显式带类型的多态语言。“第16章多态类型”的目录节点3「16·1·1 显式带类型的多态语言」不能停在术语或伪码：它要构造带源位置AST并沿作用域环境执行名字绑定和类型检查，交付CST—AST映射、环境快照、类型推导、错误路径与作用域恢复，并把节点语义、绑定顺序、类型约束或作用域恢复错位设为单一反事实。

16·1·2 多态类型的检查

正式坐标 4/15。 原版目录键 16.1.2 多态类型的检查。对“第16章多态类型”而言，「16·1·2 多态类型的检查」在第4次检查中改变可观察状态，因为它负责构造带源位置AST并沿作用域环境执行名字绑定和类型检查；CST—AST映射、环境快照、类型推导、错误路径与作用域恢复必须与“第16章多态类型的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受节点语义、绑定顺序、类型约束或作用域恢复错位。

16·2 类型推论

正式坐标 5/15。 原版目录键 16.2 类型推论。在“第16章多态类型”的第5个正式坐标中，「16·2 类型推论」通过构造带源位置AST并沿作用域环境执行名字绑定和类型检查推进多态类型、合一与值限制；复核者保存CST—AST映射、环境快照、类型推导、错误路径与作用域恢复，出现节点语义、绑定顺序、类型约束或作用域恢复错位就撤回结论。

16·2·1 一个隐式类型的多态语言

正式坐标 6/15。 原版目录键 16.2.1 一个隐式类型的多态语言。围绕“类型变量、约束、合一和泛化在什么作用域发生？”，“第16章多态类型”在坐标6把「16·2·1 一个隐式类型的多态语言」落实为构造带源位置AST并沿作用域环境执行名字绑定和类型检查；只有CST—AST映射、环境快照、类型推导、错误路径与作用域恢复可重放且反例排除节点语义、绑定顺序、类型约束或作用域恢复错位，本节点才算掌握。

16·2·2 类型推论算法

正式坐标 7/15。 原版目录键 16.2.2 类型推论算法。“第16章多态类型”的目录节点7「16·2·2 类型推论算法」不能停在术语或伪码：它要构造带源位置AST并沿作用域环境执行名字绑定和类型检查，交付CST—AST映射、环境快照、类型推导、错误路径与作用域恢复，并把节点语义、绑定顺序、类型约束或作用域恢复错位设为单一反事实。

16·2·3 递归的数据类型

正式坐标 8/15。 原版目录键 16.2.3 递归的数据类型。对“第16章多态类型”而言，「16·2·3 递归的数据类型」在第8次检查中改变可观察状态，因为它负责构造带源位置AST并沿作用域环境执行名字绑定和类型检查；CST—AST映射、环境快照、类型推导、错误路径与作用域恢复必须与“第16章多态类型的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受节点语义、绑定顺序、类型约束或作用域恢复错位。

16·2·4 Hindley-Milner类型的能力

正式坐标 9/15。 原版目录键 16.2.4 Hindley-Milner类型的能力。在“第16章多态类型”的第9个正式坐标中，「16·2·4 Hindley-Milner类型的能力」通过构造带源位置AST并沿作用域环境执行名字绑定和类型检查推进多态类型、合一与值限制；复核者保存CST—AST映射、环境快照、类型推导、错误路径与作用域恢复，出现节点语义、绑定顺序、类型约束或作用域恢复错位就撤回结论。

16·3 多态变量的表示

正式坐标 10/15。 原版目录键 16.3 多态变量的表示。围绕“类型变量、约束、合一和泛化在什么作用域发生？”，“第16章多态类型”在坐标10把「16·3 多态变量的表示」落实为生成约束、执行合一/泛化/实例化并翻译多态值；只有约束集、合一轨迹、类型方案、实例化与错误证明可重放且反例排除不安全一般化、 occurs-check 或重载消解错误，本节点才算掌握。

16·3·1 多态函数的扩展

正式坐标 11/15。 原版目录键 16.3.1 多态函数的扩展。“第16章多态类型”的目录节点11「16·3·1 多态函数的扩展」不能停在术语或伪码：它要生成约束、执行合一/泛化/实例化并翻译多态值，交付约束集、合一轨迹、类型方案、实例化与错误证明，并把不安全一般化、 occurs-check 或重载消解错误设为单一反事实。

16·3·2 完全的装箱转换

正式坐标 12/15。 原版目录键 16.3.2 完全的装箱转换。对“第16章多态类型”而言，「16·3·2 完全的装箱转换」在第12次检查中改变可观察状态，因为它负责把“完全的装箱转换”放进多态类型、合一与值限制的C接口—状态—变换—验证链；第16章多态类型的输入角色、中间状态、输出、反例与整合证据必须与“第16章多态类型的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受只复述“完全的装箱转换”名称而没有可观察状态、项目实现和恢复验证。

16·3·3 基于强制的表示分析

正式坐标 13/15。 原版目录键 16.3.3 基于强制的表示分析。在“第16章多态类型”的第13个正式坐标中，「16·3·3 基于强制的表示分析」通过把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹推进多态类型、合一与值限制；复核者保存正则—自动机、token流、项目集、分析表、栈轨迹与冲突，出现最长匹配、展望符、冲突或恢复状态错误就撤回结论。

16·3·4 将类型作为运行时参数传递

正式坐标 14/15。 原版目录键 16.3.4 将类型作为运行时参数传递。围绕“类型变量、约束、合一和泛化在什么作用域发生？”，“第16章多态类型”在坐标14把「16·3·4 将类型作为运行时参数传递」落实为构造带源位置AST并沿作用域环境执行名字绑定和类型检查；只有CST—AST映射、环境快照、类型推导、错误路径与作用域恢复可重放且反例排除节点语义、绑定顺序、类型约束或作用域恢复错位，本节点才算掌握。

16·4 静态重载的解决方法

正式坐标 15/15。 原版目录键 16.4 静态重载的解决方法。“第16章多态类型”的目录节点15「16·4 静态重载的解决方法」不能停在术语或伪码：它要生成约束、执行合一/泛化/实例化并翻译多态值，交付约束集、合一轨迹、类型方案、实例化与错误证明，并把不安全一般化、 occurs-check 或重载消解错误设为单一反事实。

先预测，再操作三个C轨道实验

分步1 / 3

1. C模块、输入与翻译流水线

为“第16章多态类型”选择正式目录坐标，在参考流水线与单一故障间切换，逐阶段核对接口、状态、输出和不变量。

输入—表示—翻译流水线

第16章多态类型

选择正式目录坐标，再比较参考编译合同与单一故障的首个状态分岔。

正式目录坐标

阶段 1/4

第16章多态类型 · C模块与输入

输入: 在Tiger C实现轨道中复现“第16章多态类型”的输入、状态、变换与验证
变换: 冻结多态类型、合一与值限制所需的C接口、源程序、规则、数据结构和版本
输出证据: 第16章多态类型的模块合同、输入快照与所有权表
不变量检查: 第16章多态类型的类型、所有权、源位置、名字和接口布局没有错位

第16章多态类型的可重放协议

阶段	允许动作	必留证据	拒绝条件
第16章多态类型 · C模块与输入	冻结多态类型、合一与值限制所需的C接口、源程序、规则、数据结构和版本	第16章多态类型的模块合同、输入快照与所有权表	未满足“第16章多态类型的类型、所有权、源位置、名字和接口布局没有错位”
第16章多态类型 · 算法与状态	执行推导参数多态、类型推断、重载消解与多态值的IR翻译的最小算法并保存每一步状态	第16章多态类型的参考轨迹、故障轨迹与首个状态分岔	未满足“第16章多态类型每一步可由同一C接口、输入、规则和执行顺序复算”
第16章多态类型 · 输出与整合	比较变换前后AST/IR/汇编/运行时状态和跨模块传递	第16章多态类型的前后差、接口谱系与恢复路径	未满足“第16章多态类型没有把单模块通过或单一样例正确当作端到端正确性”
第16章多态类型 · 独立验证	重放预测、单故障、恢复和不适用边界	第16章多态类型的接受、回退或拒绝理由	未满足“第16章多态类型满足“第16章多态类型的C模块接口、数据结构、状态变换、输出语义与测试始终一致””

unit: "tbc-unit-16"
question: "类型变量、约束、合一和泛化在什么作用域发生？"
scenario: "在Tiger C实现轨道中复现“第16章 多态类型”的输入、状态、变换与验证"
invariant: "第16章 多态类型的C模块接口、数据结构、状态变换、输出语义与测试始终一致"
fault: "对具有副作用的表达式错误执行一般化，产生不安全多态引用"
evidence: "约束集、合一轨迹、类型方案、实例化与错误证明"
reset: restore_concept_mode_stage_trace_step_case_gates_and_artifact

“第16章多态类型”要求从同一C接口、源程序、规则、数据结构、目标机、预算和执行顺序重放参考、故障与恢复路径。重置后若目录选择、模式、阶段、轨迹步骤、案例、证据门或交付包没有回到基线，本次比较已经混入状态泄漏。

本页回顾

掌握“第16章多态类型”不是背术语、表格或伪码，而是围绕“类型变量、约束、合一和泛化在什么作用域发生？”重建C接口、输入、状态变换、输出、整合和端到端验证，并用“第16章多态类型的C模块接口、数据结构、状态变换、输出语义与测试始终一致”拒绝“对具有副作用的表达式错误执行一般化，产生不安全多态引用”。最终交付为约束集、合一轨迹、类型方案、实例化与错误证明。

练习与答案

练习

问题 1：C实现合同。 “第16章多态类型”为什么必须先冻结C接口、源程序、规则、数据结构、目标机和验证口径？

问题 2：目录逐项覆盖。 怎样证明“第16章多态类型”的正式目录坐标已经进入机制、交互和程序设计项目？

“第16章多态类型”的目录项「第16章多态类型」：以“构造带源位置AST并沿作用域环境执行名字绑定和类型检查”解释作用，用“CST—AST映射、环境快照、类型推导、错误路径与作用域恢复”提供复核。
“第16章多态类型”的目录项「16·1 参数多态性」：以“生成约束、执行合一/泛化/实例化并翻译多态值”解释作用，用“约束集、合一轨迹、类型方案、实例化与错误证明”提供复核。
“第16章多态类型”的目录项「16·1·1 显式带类型的多态语言」：以“构造带源位置AST并沿作用域环境执行名字绑定和类型检查”解释作用，用“CST—AST映射、环境快照、类型推导、错误路径与作用域恢复”提供复核。
“第16章多态类型”的目录项「16·1·2 多态类型的检查」：以“构造带源位置AST并沿作用域环境执行名字绑定和类型检查”解释作用，用“CST—AST映射、环境快照、类型推导、错误路径与作用域恢复”提供复核。
“第16章多态类型”的目录项「16·2 类型推论」：以“构造带源位置AST并沿作用域环境执行名字绑定和类型检查”解释作用，用“CST—AST映射、环境快照、类型推导、错误路径与作用域恢复”提供复核。
“第16章多态类型”的目录项「16·2·1 一个隐式类型的多态语言」：以“构造带源位置AST并沿作用域环境执行名字绑定和类型检查”解释作用，用“CST—AST映射、环境快照、类型推导、错误路径与作用域恢复”提供复核。
“第16章多态类型”的目录项「16·2·2 类型推论算法」：以“构造带源位置AST并沿作用域环境执行名字绑定和类型检查”解释作用，用“CST—AST映射、环境快照、类型推导、错误路径与作用域恢复”提供复核。
“第16章多态类型”的目录项「16·2·3 递归的数据类型」：以“构造带源位置AST并沿作用域环境执行名字绑定和类型检查”解释作用，用“CST—AST映射、环境快照、类型推导、错误路径与作用域恢复”提供复核。
“第16章多态类型”的目录项「16·2·4 Hindley-Milner类型的能力」：以“构造带源位置AST并沿作用域环境执行名字绑定和类型检查”解释作用，用“CST—AST映射、环境快照、类型推导、错误路径与作用域恢复”提供复核。
“第16章多态类型”的目录项「16·3 多态变量的表示」：以“生成约束、执行合一/泛化/实例化并翻译多态值”解释作用，用“约束集、合一轨迹、类型方案、实例化与错误证明”提供复核。
“第16章多态类型”的目录项「16·3·1 多态函数的扩展」：以“生成约束、执行合一/泛化/实例化并翻译多态值”解释作用，用“约束集、合一轨迹、类型方案、实例化与错误证明”提供复核。
“第16章多态类型”的目录项「16·3·2 完全的装箱转换」：以“把“完全的装箱转换”放进多态类型、合一与值限制的C接口—状态—变换—验证链”解释作用，用“第16章多态类型的输入角色、中间状态、输出、反例与整合证据”提供复核。 13. “第16章多态类型”的目录项「16·3·3 基于强制的表示分析」：以“把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹”解释作用，用“正则—自动机、token流、项目集、分析表、栈轨迹与冲突”提供复核。
“第16章多态类型”的目录项「16·3·4 将类型作为运行时参数传递」：以“构造带源位置AST并沿作用域环境执行名字绑定和类型检查”解释作用，用“CST—AST映射、环境快照、类型推导、错误路径与作用域恢复”提供复核。
“第16章多态类型”的目录项「16·4 静态重载的解决方法」：以“生成约束、执行合一/泛化/实例化并翻译多态值”解释作用，用“约束集、合一轨迹、类型方案、实例化与错误证明”提供复核。

问题 3：故障恢复。 怎样证明“对具有副作用的表达式错误执行一般化，产生不安全多态引用”已经被修正？

为“第16章多态类型”复用同一C接口、输入、规则、数据结构、目标机、预算和顺序，重放参考路径后只注入该故障；记录首个偏离，撤销故障再运行。只有流水线合同、状态轨迹、端到端验证门和约束集、合一轨迹、类型方案、实例化与错误证明重新满足“第16章多态类型的C模块接口、数据结构、状态变换、输出语义与测试始终一致”，修正才可提交。

名词解释

本章出现的专业名词，用大白话再讲一遍。

多态类型: 检索键 tbc-A 对应正式目录坐标「第16章多态类型」；在“第16章多态类型”中用于构造带源位置AST并沿作用域环境执行名字绑定和类型检查，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
参数多态性: 检索键 tbc-B 对应正式目录坐标「16·1 参数多态性」；在“第16章多态类型”中用于生成约束、执行合一/泛化/实例化并翻译多态值，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
显式带类型的多态语言: 检索键 tbc-C 对应正式目录坐标「16·1·1 显式带类型的多态语言」；在“第16章多态类型”中用于构造带源位置AST并沿作用域环境执行名字绑定和类型检查，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
多态类型的检查: 检索键 tbc-D 对应正式目录坐标「16·1·2 多态类型的检查」；在“第16章多态类型”中用于构造带源位置AST并沿作用域环境执行名字绑定和类型检查，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
类型推论: 检索键 tbc-E 对应正式目录坐标「16·2 类型推论」；在“第16章多态类型”中用于构造带源位置AST并沿作用域环境执行名字绑定和类型检查，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
一个隐式类型的多态语言: 检索键 tbc-F 对应正式目录坐标「16·2·1 一个隐式类型的多态语言」；在“第16章多态类型”中用于构造带源位置AST并沿作用域环境执行名字绑定和类型检查，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
类型推论算法: 检索键 tbc-G 对应正式目录坐标「16·2·2 类型推论算法」；在“第16章多态类型”中用于构造带源位置AST并沿作用域环境执行名字绑定和类型检查，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
递归的数据类型: 检索键 tbc-H 对应正式目录坐标「16·2·3 递归的数据类型」；在“第16章多态类型”中用于构造带源位置AST并沿作用域环境执行名字绑定和类型检查，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
Hindley-Milner类型的能力: 检索键 tbc-I 对应正式目录坐标「16·2·4 Hindley-Milner类型的能力」；在“第16章多态类型”中用于构造带源位置AST并沿作用域环境执行名字绑定和类型检查，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
多态变量的表示: 检索键 tbc-J 对应正式目录坐标「16·3 多态变量的表示」；在“第16章多态类型”中用于生成约束、执行合一/泛化/实例化并翻译多态值，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
多态函数的扩展: 检索键 tbc-K 对应正式目录坐标「16·3·1 多态函数的扩展」；在“第16章多态类型”中用于生成约束、执行合一/泛化/实例化并翻译多态值，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
完全的装箱转换: 检索键 tbc-L 对应正式目录坐标「16·3·2 完全的装箱转换」；在“第16章多态类型”中用于把“完全的装箱转换”放进多态类型、合一与值限制的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
基于强制的表示分析: 检索键 tbc-M 对应正式目录坐标「16·3·3 基于强制的表示分析」；在“第16章多态类型”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
将类型作为运行时参数传递: 检索键 tbc-N 对应正式目录坐标「16·3·4 将类型作为运行时参数传递」；在“第16章多态类型”中用于构造带源位置AST并沿作用域环境执行名字绑定和类型检查，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
静态重载的解决方法: 检索键 tbc-O 对应正式目录坐标「16·4 静态重载的解决方法」；在“第16章多态类型”中用于生成约束、执行合一/泛化/实例化并翻译多态值，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。

第16章 多态类型

学习目标

为什么从这个问题开始

原版书目、296个正式坐标与C轨道边界

原版目录层级与C项目机制

第16章 多态类型

16·1 参数多态性

16·1·1 显式带类型的多态语言

16·1·2 多态类型的检查

16·2 类型推论

16·2·1 一个隐式类型的多态语言

16·2·2 类型推论算法

16·2·3 递归的数据类型

16·2·4 Hindley-Milner类型的能力

16·3 多态变量的表示

16·3·1 多态函数的扩展

16·3·2 完全的装箱转换

16·3·3 基于强制的表示分析

16·3·4 将类型作为运行时参数传递

16·4 静态重载的解决方法

先预测，再操作三个C轨道实验

1. C模块、输入与翻译流水线

第16章 多态类型

第16章 多态类型 · C模块与输入

第16章 多态类型的可重放协议

本页回顾

练习与答案

练习

名词解释

名词解释

讨论

第16章多态类型

第16章多态类型

第16章多态类型

第16章多态类型 · C模块与输入

第16章多态类型的可重放协议