.6.2 补充练习：绘制简单图形　36
6.3 结构体定义　38
6.4 数据定义　41
6.5 设计处理复合数据的函数　43
6.6 补充练习：圆和长方形的移动　46
6.7 补充练习：刽子手游戏　49
第7章 数据的多样性　52
7.1 数据混合与区分　52
7.2 设计处理混合数据的函数　55
7.3 再论函数复合　58
7.4 补充练习：图形的移动　60
7.5 输入错误　61
第8章 语法和语义　63
8.1 Scheme的词汇　63
8.2 Scheme的文法　64
8.3 Scheme的含义　65
8.4 错误　68
8.5 布尔值表达式　70
8.6 变量定义　71
8.7 结构体的定义　72
第二部分 任意数目数据的处理
第9章 复合数据类型之二：表　77
9.1 表　77
9.2 任意长的表的数据定义　80
9.3 处理任意长的表　82
9.4 设计自引用数据定义的函数　84
9.5 更多关于简单表的例子　86
第10章 表的进一步处理　90
10.1 返回表的函数　90
10.2 包含结构体的表　93
10.3 补充练习：移动图片　98
第11章 自然数　100
11.1 定义自然数　100
11.2 处理任意大的自然数　101
11.3 补充练习：创建表，测试函数　103
11.4 自然数的另一种数据定义　104
11.5 更多与自然数有关的性质　108
第12章 三论函数复合　110
12.1 设计复杂的程序　110
12.2 递归的辅助函数　111
12.3 问题泛化与函数泛化　114
12.4 补充练习：字母的重新排列　117
第13章 用list构造表　119
第三部分 再论任意大数据的处理
第14章 再论自引用数据定义　125
14.1 结构体中的结构体　125
14.2 补充练习：二叉搜索树　131
14.3 表中的表　135
14.4 补充练习：Scheme求值　137
第15章 相互引用的数据定义　139
15.1 由结构体组成的表与结构体中的表　139
15.2 为相互引用的定义设计函数　144
15.3 补充练习：网页再谈　145
第16章 反复精化设计　147
16.1 数据分析　147
16.2 定义数据类型，再改进它们　148
16.3 改进函数和程序　150
第17章 处理两种复杂数据片段　152
17.1 同时处理两个表：第一种情况　152
17.2 同时处理两个表：第二种情况　154
17.3 同时处理两个表：第三种情况　156
17.4 函数的简化　159
17.5 设计读入两个复杂输入的函数　160
17.6 处理两个复杂输入的练习　161
17.7 补充练习：Scheme求值之二　164
17.8 相等与测试　165
第18章 局部定义和辖域　172
18.1 用local组织程序　172
18.2 辖域和块结构　183
第四部分 抽 象 设 计
第19章 定义的相似性　189
19.1 函数的类似之处　189
19.2 数据定义的类似之处　195
第20章 函数也是值　199
20.1 语法和语义　199
20.2 抽象函数和多态函数的合约　200
第21章 抽象设计的例子　204
21.1 从实例中抽象　204
21.2 抽象表处理函数的练习　208
21.3 抽象与惟一控制点　209
21.4 补充练习：再论图片移动　210
21.5 注意：由模板设计抽象　211
第22章 使用函数进行抽象设计　213
22.1 返回函数的函数　213
22.2 把函数当成值来进行抽象设计　214
22.3 图形用户界面初探　216
第23章 数学方面的例子　223
23.1 数列和级数　223
23.2 等差数列和等差级数　225
23.3 等比数列和等比级数　225
23.4 函数曲线下方的面积　228
23.5 函数的斜率　229
第24章 定义匿名函数　234
24.1 lambda表达式的语法　234
24.2 lambda表达式的辖域和语义　235
24.3 lambda表达式的语用　237
第五部分 生 成 递 归
第25章 一种新的递归形式　241
25.1 为桌上的一个球建立模型　242
25.2 快速排序　244
第26章 设计算法　248
26.1 终止　249

26.2 结构递归与生成递归的比较　251
26.3 做出选择　252
第27章 主题的变更　256
27.1 分形　256
27.2 从文件到行，从表到表的表　260
27.3 二分查找　263
27.4 牛顿法　267
27.5 补充练习：高斯消去法　269
第28章 回溯算法　273
28.1 图的遍历　273
28.2 补充练习：皇后之间的相互攻击　277
第29章 计算的代价和向量　280
29.1 具体的时间和抽象的时间　280
29.2 “阶”的定义　284
29.3 向量初探　286
第六部分 知 识 累 积
第30章 知识的丢失　297
30.1 一个与结构处理相关的问题　297
30.2 一个关于生成递归的问题　300
第31章 设计带累积器的函数　304
31.1 认识累积器的必要性　304
31.2 带累积器的函数　305
31.3 把函数转换成带累积器的变体　306
第32章 使用累积器的更多例子　315
32.1 补充练习：有关树的累积器　315
32.2 补充练习：传教士和食人者问题　319
32.3 补充练习：单人跳棋　321
第33章 非精确数的本质　323
33.1 固定长度的数的算术运算　323
33.2 上溢出　327
33.3 下溢出　328
33.4 DrScheme数　328
第七部分 改变变量的状态
第34章 函数的记忆　333
第35章 对变量赋值　337
35.1 简单的、能工作的赋值　337
35.2 顺序计算表达式　339
35.3 赋值和函数　340
35.4 第一个有用的例子　342
第36章 设计有记忆的函数　346
36.1 对记忆的需求　346
36.2 记忆与状态变量　347
36.3 初始化记忆的函数　348
36.4 改变记忆的函数　349
第37章 使用记忆的例子　354
37.1 状态的初始化　354
37.2 与用户交互并改变状态　356
37.3 在递归中改变状态　362
37.4 状态变量的练习　367
37.5 补充练习：探险　368
第38章 最终的语法和语义　371
38.1 Advanced Scheme的词汇　371
38.2 Advanced Scheme的文法　371
38.3 Advanced Scheme的含义　373
38.4 Advanced Scheme中的错误　383
第八部分 复合值的改变
第39章 封装　389
39.1 状态变量的抽象　389
39.2 封装练习　397
第40章 可改变的结构体　399
40.1 由函数得出结构体　399
40.2 可变的函数结构体　401
40.3 可变的结构体　403
40.4 可变的向量　409
40.5 改变变量与改变结构体　410
第41章 设计改变结构体的函数　414
41.1 为什么改变结构体　414
41.2 结构体的设计诀窍与变化器之一　414
41.3 结构体的设计诀窍与变化器之二　423
41.4 补充练习：最后一次移动图片　431
第42章 相等　433
42.1 外延相等　433
42.2 内涵相等　434
第43章 修改结构体、向量和对象　437
43.1 关于向量的更多练习　437
43.2 带循环的结构体集合　448
43.3 状态的回溯　455
结束语　458
计算　458
程序设计　458
继续学习　459

. 使它们具有如实的形象，空虚的事物也会有了居处和名字。
——莎士比亚， 《仲夏夜之梦V(i)》
目前越来越少的人在编写程序代码，主张每个人都应该学习编程似乎有些奇怪。事实上大多数人是在使用应用程序包开发软件，即使是程序员也使用“程序生成器”由规则(如商业规律)创建程序，看起来他们似乎不需要编写代码。那么，为什么还说每个人都应该学习编程呢?
问题的答案可以从两个方面阐述。第一，传统形式的编程确实仅仅对少数人来说是有用的。但我们这里所讨论的编程模式对每个人，不管是使用电子表格的行政办公室秘书还是高科技公司的程序员，都是有用的。换句话说，这里所讨论的编程概念远比传统的编程观念广泛。第二，本书以最小影响原则来讲授编程思想，着重于分析问题和解决问题的技能，而不是强迫大家掌握传统的编程语言和编程工具。
要想更好地理解现代编程思想，请仔细观察一下目前流行的应用程序包，如电子表格。如果用户先把描述一个单元A和另一个单元B依赖关系的公式输入电子表格，：接着，输入单元B的值，电子表格就会自动计算单元A的值。对于复杂的电子表格，一个单元的值可能依赖多个其他单元，而不仅仅是一个。
其他应用程序包也需要类似的计算。考虑文字处理和样式表软件。样式表说明了如何由待定的词或句建立一个(或一部分)文档。当提供了特定的词句之后，文字处理软件就会把样式表中的名字替换为特定的词句，从而建立文档。类似地，某个进行网页检索的人可能会指定若干个关键字、给定关键字之间的顺序以及哪个关键字不必在网页中出现。在这种情况下，搜索结果将取决于搜索引擎的高速缓存和用户所输入的检索表达式。
最后，使用程序生成器的技巧其实就是使用应用程序包的技巧。程序生成器由高层功能描述生成传统程序设计语言代码，例如由商业规律或科学定律产生C++或Java程序。规律把数量、销量以及库存记录联系起来并说明计算过程。而程序的其余部分，特别是如何与用户交互以及如何将数据存储于计算机磁盘等等，则几乎或完全不需要人的干预。
所有这些活动都是让计算机软件为我们做某些事。其中一些活动使用科学符号，一些使用固定格式的自然语言，另一些则使用具体的编程符号。实际上这些活动都是某种形式的编程，其本质可归结如下：
1．把某个量与另一个量相关联：
2．用值代换名进行关系计算。
事实上，上述两个概念刻划了使用最低级的程序设计语言，如机器语言，和使用最流行的程序设计语言，如Java，进行编程的本质。程序将输出和输入相联系，将程序应用于特定的输入，就是在计算中用具体的值代替相关的名字。
没有人可以预知今后5年或是10年内会出现哪种类型的应用程序包。但是，使用应用程序包仍然需要某种形式的编程。要使学生们掌握编程，学校要么强迫他们学习代数，它是编程的数学基础，要么让他们进行某种形式的程序设计活动。有了现代化的程序设计语言和程序设计环境，选择后者可以更有效地完成任务，还可以使代数学习的过程变得更加有趣。
设计诀窍
烹饪既是孩童的游戏也是成人的乐事，细心烹饪是爱的举措。
——克雷格·卡莱波恩(1920--2000)， 《纽约时报》饮食版编辑
学习设计程序就像学习踢球一样，必须练习断球、运球、传球和射门。一旦掌握了这些基本技术，下一个目标就是学习担任某个角色、选择并实施合适的战略，如果没有现成的，需要创造一种。
程序员和建筑师、作曲家以及作家一样，是富有创造性的人。他们的念头从白纸开始，先构思概括，再把它写到纸上，直到写出的东西能充分反映他们的思想为止。他们使用图形、文字或其他方法来表达建筑物风格、描述人的特征或是谱写音乐旋律。他们能胜任自己的职业，是因为经过长时间的练习”他们能本能地使用这些技能。
程序设计者也是先形成程序框架，然后翻译为最初的程序版本，再反复修改，直到与最初的想法相符。事实上，好的程序员会多次编辑和修改自己的程序，最终达到某种形式的标准。这和足球运动员、建筑师、作曲家以及作家一样，他们必须长期练习行业必需的基本技能。
设计诀窍类似于控球技巧、写作技巧、乐曲编排技巧和绘图技巧。通过学习和研究，在程序设计领域，计算机科学家已经积累了许多重要的方法和技巧，本书挑选了其中最重要和最实用的一些，由浅入深，逐一讲解。
本书大约有一半的设计诀窍涉及输入数据和程序之间的关系。更准确地说，它们描述了如何从输入数据的描述得出整个程序的模板，这种基于数据驱动的程序设计方式最常见，易于创建、理解、扩展和修改。其他设计诀窍有生成递归(generative recursion)、累积(accumulation)和历史敏感性(historysensitivity)。其中，递归型程序可以被重复调用以处理新的问题；带累积器的程序在处理输入的过程中收集数据；历史敏感性程序可以记住程序被多次调用的信息。最后，但不是最不重要的，是抽象程序的设计诀窍。抽象是把两个(或更多)相似的设计概括为一个并由它衍生最初示例。
在许多场合下，往往会由问题联想到设计诀窍。在另外一些场合下，则必须在几种可能性中作出选择，不同的设计决窍可能会导致不同的程序结构，它们之间的差别可能很大。对于一个具有创造性的程序员来说，做出选择是很自然的事情。除非程序员十分熟悉所有可选的设计诀窍，完全理解选择某个诀窍而不是另一个诀窍的后果，否则程序设计过程不可避免按事论事，甚至会导致离奇古怪的结果。我们希望通过制订一系列设计诀窍来帮助程序员理解选择什么以及如何进行选择。
上面解释了“编程”和“程序设计”的含义，读者应该理解到本书所讲授的思想方法和技能对多种职业来说都相当重要。要正确地设计程序，你必须：
1．分析通常使用文字表述的问题；
2．在抽象表达问题实质的同时使用例子进行说明：
3．用精确的语言阐明所表述的语句和注释：
4．通过检查、测试对上述活动进行评价和修改：
5．关注细节。
所有这些行为对商人、律师、记者、科学家、工程师以及其他人来说都是有用的。
尽管传统意义上的编程也需要这些技巧，但初学者往往不理解它们之间的关系。问题是，传统的程序设计语言以及传统形式的编程需要学生完成大量的登记工作并记住许多与特定语言相关的细节。简而言之，琐碎杂事淹没了技术本质。要避免这个问题，教师必须使用一种适合初学者的程序设计环境，它尽可能不增加学生额外的负担。在开始编写本书的时候，这样的工具并不存在，因此我们就自行开发了。
选用Scheme和DrScheme
我们把美归于简单，
不含多余部分，
边界清晰，
与一切相关联，
是中庸之道。
——拉尔夫·沃尔多·爱默生， 《人生苦旅》
本书选择Scheme作为编程语言，辅助程序设计环境为DrScheme，软件可以免费从本书的正式网站下载。
尽管如此，本书并不是一本介绍Scheme程序设计语言的书籍，它仅涉及部分Scheme结构。具体来说，本书仅使用6种Scheme结构(它们是函数定义和调用、条件表达式、结构体定义，局部定义以及赋值等)以及大约12个基本函数，它们就是讲授计算和编程原则所需要的全部东西。希望把Scheme当作一种工具来使用的人则需要阅读其他的材料。
对初学者来说，选用Scheme是很自然的。首先，程序员可以把注意力集中于两个要素，即前面所指出的基本编程原则：程序就是数量之间的关系，对于特定的输入求取结果。使用Scheme语言核心，在教师的指导下，学生在第一堂课就可以开发出完整的程序。
其次，可以方便地将Scheme组织成从简单到复杂的一系列不同级别的语言。这个性质对初学者来说是至关重要的。当初学者犯了简单的符号错误时，一般程序设计语言会给出含糊的、与语言高级特征相关的错误消息。初学者往往浪费很多时间宋查找错误所在，由此产生学习上的挫折感。为了避免这些问题，通过持续对赖斯大学计算机实验室的程序设计初学者的观察，经过谨慎选择，DrScheme实现了若干不同层次的Scheme程序设计环境。按照安排，不同的环境会给出与学生当前知识水平相适应的错误消息。更好的是，分层会避免许多基本错误。当学生学习了足够的编程和语言知识后，教师可以建议他们接触更丰富的语言层次，由此编写更有趣、更简练的程序。
另外，DrScheme提供了一个真正的交互式环境。环境由两个窗口组成：一个是Definitions窗口，在其中可以定义程序，另一个是交互窗口，其行为就像是一个袖珍计算器，你可以在其中输入表达式，由DrScheme求出它们的值。换句话说，计算由袖珍计算器完成，而这是学生们都相当熟悉的。很快，计算形式就从袖珍计算器上的算术运算向前推进，变成对结构体、表和树的计算。使用交互式的计算方式甚至可以鼓励学生们用各种方法进行程序实验，从而激发他们的好奇心。
最后，使用包含丰富数据结构的交互式程序设计环境可以让学生把注意力集中于问题的解决和程序设计活动之上。关键的改进是，交互式求值环境避免了(几乎是)多余的关于输入和输出的讨论。这一点改进带来了几种结果。第一，掌握输入和输出函数需要记忆，学习这些东西单调乏味、令人厌烦，相反，如果使用固定方式的输入和输出，我们就能将精力集中于问题求解技术的学习；第二，良好的面向文字的输入需要深奥的编程技能，最好从问题求解的课程中学习(学生应该从更高级的课程中学习)。教那些糟糕的面向文字的输入，是对老师和学生时间的浪费；第三，现代软件一般采用图形用户界面(GUI)，GUI是程序员使用编辑器和“向导”设计的，不是手工完成的。学生最好学习使用与标尺、按钮、文本框等相关的函数，而不是背诵那些与流行的GUI库相关的特定协议。简而言之，在初次介绍编程时就讨论输入和输出是对宝贵的学习时间的浪费。如果要进一步学习，掌握必需的Scheme输入输出知识也比较方便。
总而言之，只要少量几节课，学生们就可以学会Scheme语言的核心，这种语言和传统的程序设计语言一样强大。这样，学生立即就可以把注意力集中于编程本质，这将极大增强他们解决一般问题的能力。
本书正文部分
本书由8个部分和7个独立的章节(书中第8、13、18、24、29、33、38章)组成。8个部分主要讨论程序设计，独立章节则介绍一些与程序设计和计算相关的话题。图2给出了本书各部分之间的依赖关系，可以看出，你可以按不同的顺序来阅读本书，只阅读部分内容也是可以的。
本书第一至第三部分包括了基于数据驱动的程序设计基础。第四部分介绍了程序设计中的抽象问题。第五部分和第六部分与递归及累积相关。本书前6部分使用了纯函数式(或称代数式)的程序设计风格，即无论计算多少遍，同一个表达式每次计算的结果总是相同。这种特性使程序易于设计，程序性质易于推导。不过，为了处理程序之间的接口和解决其他领域的问题，我们放弃了部分代数性质，引入了赋值语句。本书的最后两部分说明了设计程序的意义，更精确地说，它们阐述了如何应用前6个部分所描述的程序设计诀窍，以及使用赋值语句必须特别小心的一些问题。
独立章节则介绍一般性的、非本质的，对计算和程序本身来说是重要的话题，但并不涉及程序设计有的是在严格的基础上介绍本书所选定的Scheme子集的语法和语义，有的是介绍了另外的程序设计结构。独立章节5(第29章)讨论了抽象的计算开销(包括时间和空间开销)，并介绍了向量的概念。独立章节6(第33章)则比较了两种数值表示技术以及处理它们的方法。
只有某些独立章节的内容的学习可以推后，直到需要时再学习。对于学习与Scheme语法和语义相关的独立章节尤其应该注意。但是，考虑到图2中第18章的重要地位，我们应该及时学习。
程序的逐步求精：系统化程序设计方法对于开发大型项目特别有意义，也特别重要。而开发单一函数到小规模的包括多个函数的项目则需要另外一种设计思想：逐步求精，即先设计程序核心，再增加功能，直至满足整个需求目标为止。
学习完第一节课后同学就应该有了程序逐步求精的初步印象。为了使学生熟悉这种技术，书中给出了许多补充练习，这些使用简短概述引出的练习可以指导学生进行程序逐步求精的训练。第16章将明确阐述这种思想。
另外，本书会重复使用某些练习和例子。例如，第6．6节、第7．4节、第10．3节、第21．4节、第41．4节以及最后2节中的一些练习题都涉及了如何在画布上移动图片的问题。这样，学生就会多次看到同样的问题，而每一次讨论都会增加他们对程序组织的了解。
本书通过逐步把功能加到一个程序体中的方法来示范为什么程序员必须遵循设计诀窍，借助问题的解决方式向学生展示如何在可用的设计诀窍中进行选择。有时候新知识的作用只是帮助学生改进程序的组织结构，换句话说，要让学生了解到在他们初步的工作完成之后，编程过程并没有结束，如撰写论文和书籍一样，程序也需要进一步的编辑和修改。
教学软件包(TeachPack)：完成工程项目的一个要求是程序员必须进行团队合作。在程序设计教学环境下，这意味着一个学生写的程序必须与另一个学生编写的程序相匹配。为了模仿“与另一个程序相配”这一概念，本书提供了DrScheme教学软件包。粗略地说，教学软件包模仿了一个合作者，由此可以避免由于合作者程序存在错误而带来的不便。技术性的说法是，工程总是由视图和程序组件模型两个部分组成(在模型一视图软件体系结构意义上)，在典型的环境下，学生设计模型，教学包则提供视图。通常，教学包以(图形)用户界面的形式提供视图，而不是单调乏味、毫无意义的代码。事实上，这种分离模仿的是真实世界中的工程分工。
为了使模型与视图相符，学生必须注意函数的规范，必须遵循设计诀窍。对程序员来说，使模型与视图相符是一种非常重要的技能，但程序设计的初级课程常常未能给予足够的重视。在第四部分，为了说明创建GUI的过程并不神秘，我们将说明如何建立一些简单的GUI，以及GUI事件是如何触发函数调用的，但我们不会把很多时间花费在一个需要死记硬背，只需很少思考的主题上。
进度：根据需要，每个学校都可以有自己的教学进度表。在赖斯大学，讲授整本教材以及其他一些附加材料通常需要一个学期的时间。一个研究性大学的教师可以使用类似的进度。而高中教师就必须放慢进度。许多尝试使用本教材的高中教师在一个学期内完成了前三个部分的教学；而少数高中只使用本书第一部分，从计算的角度讲授代数问题的求解：另一些高中则用一年的时间教完整本书。要得到有关教学进度表的更多信息，请访问本书的网站。
本书站点：本书有两种版本，除了纸介版本，在网站http://www．htdp．org/可以免费获得电子版本。
网站提供了一些附加材料，包括前面提到过的各种类型的补充练习。目前网站提供有可视化的小球游戏模拟，更多的练习将在不久的将来加入网站。
致谢
我们特别感谢四个人：罗伯特·科克·卡特赖特，他与本书的第一个作者合作开发了赖斯大学此入门性课程的前身；丹尼尔·P·弗里德曼，他在1984年要求本书的第一个作者重写了The Liule LISPer(由麻省理工学院出版社出版)，而这也是本书写作计划的开始：约翰·克莱门特，他负责设计、实现和维护DrScheme软件：还有保罗·斯特克勒，他忠实地支持我们，帮助我们开发所需的程序设计工具组件。
有许多友人和同事帮助我们开发这本教材，他们在自己的课堂上使用本教材，并且对本书的初稿给出具体的评论。我们对他们的帮助和耐心表示感谢，这些人包括伊恩·巴兰德，约翰·克莱门特，布鲁斯·迪拜，迈克·厄恩斯特，凯瑟·菲尔勒，丹尼尔·P·弗里德曼，约翰·格林纳，约翰·斯通，杰拉尔丁·莫林和瓦尔迪马·忒门。
在赖斯大学，本书草稿在课程Comp 210上使用了12次，学生们提出了许多宝贵意见。众多TeachScheme!研讨会的参加者在他们的课堂上使用了本书的最初草稿，他们中的许多人提出了评论和建议。作为其中代表，这里列出一些作出过积极贡献的人，他们是：巴巴拉·阿德勒女士，斯蒂芬·布洛赫博士，杰克·克莱先生，理查德·克莱门斯博士，凯尔·吉列先生，克伦·布拉斯女士，马文·赫男得先生，迈克尔·亨特先生，克伦·诺斯女士，贾明·雷蒙德先生以及罗伯特·里德。克里斯托弗·费雷荪和他的父亲耐心地参与了本书前几个部分的工作，让我们直接了解到了年轻学生的观点。感谢他们中的每一位。
最后，Matthias在这里表达他对海尔格的感激，感谢她多年以来的耐心，感谢她为一个心不在焉的丈夫和父亲建立了一个家庭。Robby要感谢黄馨慧的支持和鼓励，没有她，他不可能完成任何事。Matthew感谢顾文沅给予的忠诚的支持和不停的争论。Shriram感激凯瑟·菲尔勒的支持、忍耐和俏皮语，同时对她参与本书部分工作表示感谢。