01 / 导读
导读
引用
Felleisen, M., Findler, R. B., Flatt, M., & Krishnamurthi, S. (2018). How to Design Programs: An Introduction to Programming and Computing (2nd ed.). The MIT Press. Free official edition: https://htdp.org/
章节概要
序幕：如何编程
序幕让读者立即在 DrRacket 中动手编程：对数字、字符串和图像进行运算，然后通过同一程序的几个版本，逐步做出一个火箭着陆的小动画。最后一节（"Not!"）解释为什么这种快速、无计划的编程方式无法扩展，从而引出本书的替代方案——系统化的程序设计。
第1–2章：算术；函数与程序
第一部分"固定大小的数据"从关于数字、字符串、图像和布尔值的表达式讲起，并介绍用于判断值属于哪类数据的谓词。第2章介绍函数定义、用代换进行计算、函数的组合、全局常量，以及本书使用的两类完整程序：批处理程序和用 big-bang 构建的交互式"世界"程序。
第3章：如何设计程序
这是全书的核心章节。它提出函数设计诀窍的六个步骤：数据定义，签名、目的说明与函数头，函数示例，模板，定义，以及测试。随后把这一诀窍推广到完整程序，强调领域知识和用 check-expect 进行测试的作用，并以虚拟宠物为贯穿示例说明如何设计世界程序。
第4–7章：区间、枚举与分项；加入结构；分项与结构；小结
这几章把设计诀窍扩展到更丰富的数据。第4章讲条件表达式及其所对应的数据定义（枚举、区间、分项），最后介绍交通信号灯之类的有限状态世界。第5章从 posn 开始引入结构体，接着讲结构类型定义、"数据的全集"、用结构体进行设计，以及一个图形化文本编辑器。第6章把分项与结构体结合起来，检查输入错误，并讨论相等性谓词。第7章总结这一部分：好的程序员设计程序而不是反复修补，设计诀窍既有过程维度，也有数据维度。
插曲1：初级学生语言
第一个插曲精确描述教学语言 BSL：它的词汇、语法和含义，作为一系列代数步骤的求值过程，错误信息，布尔表达式，常量与结构体定义，以及测试。
第8–10章：列表；用自引用数据定义进行设计；再谈列表
第二部分"任意大的数据"引入由 '() 和 cons 构造的列表，说明自引用的数据定义如何导出递归函数，而函数模板则跟随数据的结构。第9章加入非空列表、作为递归数据的自然数、嵌套的"俄罗斯套娃"结构，以及世界程序中的列表。第10章讨论产生列表的函数、列表中的结构体、列表的列表（从文件读入）以及重新设计的图形化编辑器。
第11–13章：通过组合进行设计；项目：列表；小结
第11章讲授如何把问题分解为辅助函数并加以组合，包括递归的辅助函数和起推广作用的辅助函数。第12章提供较大的项目：词典、iTunes 曲库、文字游戏、贪吃虫游戏、简化版俄罗斯方块、太空大战游戏和有限状态机。小结强调针对自引用改进设计诀窍，并连同所需的数据定义一起写出"愿望清单"。
插曲2：引用与反引用
这个简短的插曲介绍引用（quote）、准引用（quasiquote）、反引用（unquote）和拼接，作为书写大块数据的简洁记法，并介绍符号这种数据。
第14–15章：处处相似；设计抽象
第三部分"抽象"从注意到第二部分中许多函数彼此相似开始。第14章对相似的函数和数据定义进行抽象，并说明函数也是值。第15章给出设计抽象的诀窍：从示例中抽象、推广签名、建立单一控制点，以及从模板中抽象。
第16–18章：使用抽象；匿名函数；小结
第16章讲授如何使用 map、filter、foldr 等现有抽象，引入 local 局部定义及其带来的额外表达能力，并通过示例和项目加以练习。第17章引入用于匿名函数的 lambda，用它来进行抽象、编写规格，甚至表示数据。小结把抽象概括为创建和使用可复用代码两个方面。
插曲3：作用域与抽象
这个插曲定义词法作用域以及变量的绑定出现和被绑定出现，然后介绍另外两种抽象机制：中级学生语言中的 for 循环和模式匹配。
第19–20章：S-表达式之诗；迭代求精
第四部分"交织的数据"处理由多个相互引用的定义所描述的数据：树、森林和 S-表达式，并包括一个二叉搜索树项目和一节关于简化函数的内容。第20章明确引入迭代求精，以一个经过多个版本逐步求精的计算机文件系统模型为例。
第21–22章：求精解释器；项目：XML 的商务应用
第21章用迭代求精的方法，为一门由表达式、变量和函数构成的小语言设计解释器，这正是 DrRacket 交互区的核心。第22章把 XML 表示为 S-表达式，渲染 XML 枚举，讨论领域专用语言，并读取 XML 数据。
第23–24章：同时处理；小结
第23章说明如何设计接受两个复杂输入的函数，区分三种情况（把其中一个输入当作原子数据、以同步方式处理两个输入、用二维表处理所有组合），最后是一个数据库项目。小结指出设计诀窍可以推广到所有形式的结构化数据。
插曲4：数的本质
这个插曲解释定长的数字表示、上溢和下溢，以及教学语言如何区分精确数和非精确数。
第25–26章：非标准递归；设计算法
第五部分"生成式递归"引入不遵循数据结构的递归，例如把问题拆分为新生成的子问题。第26章为这类算法调整设计诀窍：编码步骤增加四个新问题，需要明确的终止性论证，并比较结构递归与生成式递归。
第27–30章：主题的变奏；数学示例；回溯算法；小结
生成式递归的例子包括分形、二分查找和语法分析初探（第27章）；牛顿法、数值积分和高斯消元项目（第28章）；以及图的遍历和关于 n 皇后问题的回溯项目（第29章）。小结指出，大多数计算机科学家把这类函数称为算法，而且它们未必对所有输入都会终止。
插曲5：计算的代价
最后一个插曲解释为什么对特定输入计时说明不了多少问题，引入抽象运行时间和"同阶"的定义，并用它讨论程序为什么依赖谓词和选择器。
第31–34章：知识的丢失；设计累加器风格的函数；累加的更多用途；小结
第六部分"累加器"说明结构递归函数和生成式递归函数在递归过程中会"忘记"知识，从而导致低效或不终止。它给出一套诀窍：识别何时需要累加器、写出累加器陈述、把函数转换为累加器风格，并应用于树、数据表示以及一个用鼠标操作的图形化编辑器。
尾声：继续前行
尾声回顾计算与程序设计，并提出下一步建议：对于未来的开发者和计算机科学家，是学习 Racket 这样的完整语言以及类、对象和类型；对于其他所有人，则是在各自领域中运用这一设计过程。
核心概念
序幕与第1–3章
- 设计诀窍：六个步骤（数据定义；签名、目的与函数头；示例；模板；定义；测试），引导人从问题陈述走到经过测试的函数。
- 数据定义：说明现实世界的信息如何在程序中表示为数据，并附有示例。
- 世界程序：用
big-bang、一个状态、一个渲染函数和若干事件处理函数构建的交互式程序。
第4–7章与插曲1
- 分项：列出若干互不相同情形的数据定义，在模板中对应为每种情形一个子句的
cond。 - 结构类型：程序员定义的复合数据类型，具有构造函数、选择器和谓词。
- 代数式计算模型：用逐步代换来求值 BSL 程序，正如 DrRacket 的单步执行器所展示的那样。
第8–13章
- 自引用数据定义：引用自身的定义（如列表），由此导出递归函数。
- 模板跟随数据：函数代码的形状反映它所处理的数据定义的形状。
- 愿望清单：列出有待日后设计的辅助函数及其签名和目的。
第14–18章与插曲3
- 抽象：把重复出现的代码模式提取为一个函数，并对差异部分进行参数化。
- 函数即值：传递和返回函数，这是
map、filter、foldr和lambda的基础。 - 词法作用域：每个变量出现都对应一个通过阅读程序文本即可找到的定义。
第19–24章
- 相互引用的数据：彼此引用的多个数据定义，需要为每个定义各写一个模板。
- 迭代求精：先解决问题的简化版本，再一步步加入细节。
第25–30章与插曲5
- 生成式递归：基于对问题的洞察、在新生成的子问题上进行的递归，而不是沿着数据的结构递归。
- 终止性论证：说明生成式递归函数为何最终会停止，或对其不会停止的输入给出警告。
- 抽象运行时间：用步数的增长阶来衡量代价，而不是对特定运行计时。
第31–34章
- 累加器：在遍历过程中携带所收集知识的额外参数。
- 累加器陈述：说明累加器代表什么知识，通常是原始参数与当前参数之间的差别。
评析
优点
- 可传授的明确方法。 前言把六步设计诀窍描述为学生可以抄在索引卡上的东西，而每个部分又为每一步补充有针对性的问题。数据定义、示例、模板等中间产物，使卡住的学生或教师能够准确看出问题出在哪里。
- 以数据驱动的递进。 每个部分引入一种新的数据（固定大小、任意大、交织）或一条新的设计原则（抽象、生成式递归、累加器），并相应扩展设计诀窍，因此本书的结构本身就在传授"程序结构跟随数据"的道理。
- 为初学者设计的教学语言和环境。 一系列教学语言（BSL、BSL+、ISL、ISL+）给出与学习者水平相称的错误信息，DrRacket 的单步执行器逐步展示求值过程。带图像的交互式世界程序能提供即时的视觉反馈。
- 大量练习和反复出现的主题。 在线版共有 528 道编号练习，虚拟宠物、文本编辑器和图等主题在多个部分中反复出现；前言称这是"从后门"引入迭代求精。
局限
- 不是主流语言。 本书用基于 Racket 的教学语言讲授设计，而不是 Python、Java 或 C；前言说明这是有意为之，但需要某种工业语言的学生必须在之后自行过渡，尾声把这一步留给其他书籍。
- 篇幅与节奏。 全书有六个部分、五个插曲和五百多道练习，篇幅很长，前言本身也为学季制课程和高中课程提出了删减方案。想快速入门的读者可能会觉得前几章进展缓慢。
- 状态、对象和类型涉及有限。 变量赋值、类与对象以及静态类型大多被推迟，尾声把它们列为后续主题。累加器风格的编程以函数式方式展示，命令式循环被明确说明超出本书范围。
- 规定性强。 即使是很小的函数也坚持走完每一步，这对有编程经验的学生来说可能显得繁重，尽管作者认为这种纪律正是重点所在。
在课程中的定位
在本入门编程书单中，How to Design Programs 是一本入门教材，侧重方法而非某种特定语言。它与 Matthes 的 Python Crash Course 形成对比——后者通常被认为是以项目为导向的 Python 入门书；也与 Downey 的 Think Python 和 Guttag 的 Introduction to Computation and Programming Using Python 不同，后两者用 Python 讲授编程与计算。希望在程序设计、测试和递归方面打下扎实基础的学生，可以先读 HtDP，再按尾声的建议转向某本 Python 教材，把设计诀窍迁移到主流语言中。
Abelson 和 Sussman 的 Structure and Interpretation of Computer Programs 同样源自 Lisp 家族传统，通常被认为对数学的要求更高；HtDP 的前言则把自己定位为只需前代数知识即可阅读，因此是合适的先修读物。Kernighan 和 Ritchie 的 The C Programming Language 面向底层编程，最好在第一门课程之后阅读。
如何使用本书
本书为没有任何编程经验的读者而写；作者认为具备前代数知识就足够了，唯一需要的软件是免费的 DrRacket 环境。前言同时面向自学者和教师。
前言要求自学者从头到尾学完全书，并解出或至少知道如何解出所有练习。前言还给出三条较短的路径：高中课程学习第一、二部分并完成一个小型游戏项目；大学学季制课程学习第一、二、三、五部分以及插曲1和插曲3；大学学期制课程先学第一、二部分，再学第六部分中不依赖生成式递归的内容，然后是插曲5和其余部分。无论哪条路径，第3章（设计诀窍）都是必读的，第8–9章和第14–16章是递归与抽象的基础。
用单步执行器理解求值过程，在写定义之前先写 check-expect 测试，并依照每个数据定义的模板动手，而不是从空白页开始。卡住时，回到设计诀窍中出问题的那一步——正如前言建议教师借助索引卡所做的那样。
版本与来源
本导读依据 https://htdp.org/ 上的免费在线第二版（正文 © 2014 MIT Press，在线版发布日期为 2026 年 5 月 28 日；印刷版由 MIT Press 于 2018 年出版）。内容取材于前言全文（包括设计诀窍、教学语言、各部分安排、建议的课程路径以及与第一版的差异）、完整目录、序幕、六个部分各自的开篇小节与小结章节、全部五个插曲的开头部分、尾声，以及第一、四、五部分中的若干小节。