[]
回头看与延伸阅读
[] 回头看与延伸阅读
全文走过的路,可以按“用了什么前文”串成一条线:
- 自然语言在结构、完备、量词、自指、可检查性上的五个弊端( [例] 结构歧义 至 [例] 贝里悖论 ),引出对象语言与元语言的分层( [定义] 对象语言与元语言 )。
- 用“满足封闭条件的最小集合”定义项( [定义] 项的集合 ),“最小”直接给出结构归纳( [定理] 结构归纳原理(structural induction) )。
- 用同样的“最小”定义求值关系( [定义] 一步归约 ),得到对推导归纳( [定理] 对推导归纳 ),再证明确定性( [定理] 确定性 )。
- 用推导规则定义类型( [定义] 类型与类型判断 )。语法导向给出反演( [引理] 反演 ),反演给出类型唯一和典范形式。
- 进展与保型合起来得到类型安全( [推论] 类型安全 )。
- 证明检查器相对规则可靠且完备,把“检查器接受”与“运行不受阻”接上( [推论] 检查器接受的程序不会受阻 )。
贯穿始终的方法只有一个:先把东西定义成满足某些规则的最小对象,再沿着这些规则归纳。语言变大以后,规则会变多,证明会变长,但这个方法不变。它在数学和逻辑史上的来历,见 [注记] “最小 + 归纳”的历史 。
2 延伸阅读
- Benjamin C. Pierce. Types and Programming Languages。第 2 章讲归纳定义与归纳法,第 3、8 章就是本文这门语言,规则名沿用了它的写法。
- Software Foundations。在 Coq 里从零开始讲归纳证明,第二卷的
TypesTypes一章把本文的定理全部机械化证明了一遍。 - Andrew K. Wright, Matthias Felleisen. A Syntactic Approach to Type Soundness. Information and Computation, 1994。进展 + 保型这种证明方式的出处。
- Robert Harper. Practical Foundations for Programming Languages。第 1、2 章对“抽象语法”和“归纳定义”的处理比 TAPL 更细致。
References
References
[定理] 结构归纳原理(structural induction) [structural-induction]
[定义] 一步归约 [one-step-reduction]
[定义] 类型与类型判断 [types-and-typing-judgments]
[推论] 检查器接受的程序不会受阻 [accepted-programs-do-not-get-stuck]
[注记] “最小 + 归纳”的历史 [history-of-least-sets-and-induction]
[定义] 对象语言与元语言 [object-language-and-metalanguage]
[例] 结构歧义 [structural-ambiguity]