计算机程序的构造和解释
这门课学什么
这门课把编程当成控制复杂度的方法，用 Scheme 语言讲。内容包括高阶函数、数据抽象、状态与赋值、流、元语言抽象，以及自己写解释器和编译器。1986 年录像按 SICP 教材顺序讲。
内容摘要
这门课用 Lisp 的方言 Scheme 教编程，但它真正讲的是怎样控制复杂度。录像拍于 1986 年，教材《计算机程序的构造和解释》（SICP）的两位作者艾贝尔森（Harold Abelson）和萨斯曼（Gerald Jay Sussman）轮流主讲。讲座顺序和教材章节一一对应。
课程分 5 个阶段。第 1 阶段（1A–2A）讲过程、过程产生的计算过程和高阶过程。第 2 阶段（2B–4B）讲数据抽象和符号数据，用 Escher 图形语言、符号求导和模式匹配做例子。第 3 阶段（5A–6B）讲赋值、状态和流，比较两种给时间建模的方法。第 4 阶段（7A–8B）讲元循环求值器和逻辑编程，演示一门语言怎样用它自己实现。第 5 阶段（9A–10B）下到机器层，讲寄存器机器、显式控制求值器、编译和垃圾回收。
录像本身不带作业。OCW 的 Spring 2005 页面提供习题集、编程项目和测验，可以配合录像使用。SICP 全文免费公开，书中练习是主要的动手材料。
学完以后，你会把程序看成描述计算过程的语言，而不只是一串指令。你能写高阶函数，能设计抽象层，能读懂解释器和编译器的骨架。这些想法今天仍出现在函数式编程、领域专用语言和语言实现中。
两位讲者风格不同。艾贝尔森讲得稳，重视概念的来龙去脉。萨斯曼讲得快，常在黑板上即兴推演。录像画质老，但信息密度高，建议边看边读书。
为什么值得学
SICP 是最有影响力的计算机教材之一。原作者亲自讲课，几十年后程序员还在学。
课程信息
- 学校
- 麻省理工（MIT）
- 课程号
- 6.001
- 讲师
- 哈罗德·艾贝尔森（Harold Abelson）、杰拉尔德·杰伊·萨斯曼（Gerald Jay Sussman）
- 学期
- 1986 录像（OCW Spring 2005）
- 平台
- MIT OpenCourseWare
- 费用
- 免费
- 难度
- 入门
- 学时
- 20 讲（YouTube 上拆成 40 段）
- 先修
- 无（有编程经验更好）。
- 材料
- 视频、讲义、考试、教材
- 许可证
- CC BY-NC-SA 4.0
课程大纲 · 共 20 节
大纲依据：OCW Spring 2005 收录的 1986 年讲座录像列表（20 讲，编号 1A–10B）（查看原始页面 ↗）
- 1A概述与 Lisp 入门Overview and Introduction to Lisp
说明计算机科学研究的是“怎么做”的知识，介绍 Lisp 的基本元素、组合手段和抽象手段。
- 1B过程与计算过程；代换模型Procedures and Processes; Substitution Model
用代换模型解释过程怎样求值，比较递归和迭代两种计算过程。
- 2A高阶过程Higher-order Procedures
把过程当作参数和返回值，用求和、不动点和牛顿法做例子。
- 2B复合数据Compound Data
用有理数算术说明数据抽象，引入序对和抽象屏障。
- 3AHenderson 的 Escher 图形语言Henderson Escher Example
用一门画图小语言演示怎样设计嵌入式语言的基本元素和组合手段。
- 3B符号求导与引用Symbolic Differentiation; Quotation
用符号求导程序引入引用和符号数据，讨论表达式的表示和化简。
- 4A模式匹配与基于规则的代换Pattern Matching and Rule-based Substitution
把求导规则写成数据，构造一个通用的模式匹配和代换系统。
- 4B通用操作Generic Operators
用复数的多种表示讨论数据导向编程和通用操作的分派。
- 5A赋值、状态与副作用Assignment, State, and Side-effects
引入赋值以后代换模型不再适用，改用环境模型解释求值。
- 5B计算对象Computational Objects
用数字电路模拟器演示带状态的对象怎样组合，并引入可变数据结构。
- 6A流（上）Streams, Part 1
用流把序列操作组合起来，介绍延迟求值的实现方法。
- 6B流（下）Streams, Part 2
构造无穷流，讨论用流代替状态给时间建模的利弊。
- 7A元循环求值器（上）Metacircular Evaluator, Part 1
用 Lisp 写出 Lisp 的 eval 和 apply，展示解释器的核心循环。
- 7B元循环求值器（下）Metacircular Evaluator, Part 2
在求值器上修改和扩展语言特性，讨论不同设计选择的后果。
- 8A逻辑编程（上）Logic Programming, Part 1
介绍查询语言，用事实和规则描述关系，而不是描述步骤。
- 8B逻辑编程（下）Logic Programming, Part 2
讲查询系统的实现：模式匹配、合一（unification）和基于流的搜索。
- 9A寄存器机器Register Machines
把 Lisp 过程翻译成寄存器机器的数据通路和控制器，并用栈实现递归。
- 9B显式控制求值器Explicit-control Evaluator
用寄存器机器实现完整的 Lisp 求值器，说明尾递归为什么不占用栈空间。
- 10A编译Compilation
把解释器改造成编译器，比较两者的效率差异。
- 10B存储分配与垃圾回收Storage Allocation and Garbage Collection
讲表结构在内存中的表示，以及垃圾回收的基本算法。