程序设计方法（第2版）

本书从系统设计的角度出发介绍计算以及程序设计的方法和过程。全书由6个部分和5个独立章节组成，6个部分侧重于介绍程序设计，分别介绍从数值和图像等原子数据到区间、枚举、条目、结构体及其组合等新方法的基本概念，任意大的复合数据及其用途，用于创建和使用抽象的设计诀窍，迭代改进的思想，生成递归以及关于累积器的用法；5个独立章节引入编程机制和计算的概念，分别介绍教学语言的语法和语义、引用和反引用、作用域和抽象、数值的本质以及计算的成本。
本书强调程序设计的计划和构建、设计诀窍、抽象和迭代改进等思想，逻辑清晰，循序渐进，示例丰富，可以指导有一定编程经验的读者系统地学习程序设计，也可作为高等院校计算机科学与技术专业程序设计导论和计算导论的教材和教学参考书。

作者简介
马蒂亚斯·费雷森（Matthias Felleisen）美国东北大学计算机科学学院Trustee 教授，世界知名的计算机科学家，他最为人知的他是PLT Scheme（Racket）语言的创始人。2009年，他获得Karl V. Karlstrom杰出教育家奖。2010年，他获得了SIGCSE计算机科学教育杰出贡献奖。2012年，他获得了SIGPLAN编程语言成就奖，以表彰他编程语言领域显著和持久的贡献。
罗伯特·布鲁斯·芬德勒（Robert Bruce Findler）美国西北大学计算机科学副教授
马修·弗拉特（Matthew Flatt）美国犹他大学计算机学院教授
施拉姆·克里斯纳默西（Shriram Krishnamurthi）美国布朗大学计算机科学教授
（本书第一作者是其余3 位作者的博士生导师）

译者简介
朱崇恺，美国犹他大学计算机科学硕士，硕士生导师为本书第三作者马修·弗拉特。中文圈内最早的PLT Scheme（Racket 的前身）研究者之一。除了翻译本书，还翻译过Programming Languages: Application and Interpretation （PLAI）和Object-Oriented Programming Languages: Application and Interpretation（OOPLAI）。

1.世界知名的计算机科学家、PLT Scheme（Racket）语言的创始人Matthias Felleisen作品。
2.第2版经过了全面的修订。虽然本书仍然是在教系统化的程序设计方法，但第2版为图形界面的交互式程序和批处理程序提供了不同的设计诀窍。
3.对于函数的设计诀窍，第2版增加了很多新的提示。
4.本书使用的教学语言及其集成开发环境（IDE）现在还可以像支持数值一样支持图像，并支持测试、事件驱动编程，甚至分布式编程。

本书关注程序设计的过程，呈现程序设计的准则，向读者展示如何分析问题陈述，如何编写简明的目的声明，如何列举示例，如何开发解决方案的框架，如何完成程序，以及如何测试程序。因为学习程序设计的重点在于研究原理和获得通用技能，所以本书并没有采用现成的工业用编程语言，而是提供了专门定制的教学用编程语言。出于同样的理由，本书还提供了面向初学者的编程环境——DrRacket，它寓教于乐，注重教学反馈。随着读者逐步熟悉书中的内容，编程环境也会不断完备，直至可以支撑一种适用于所有编程任务的成熟语言。

目 录



开篇：如何编程
算术　3
输入和输出　6
计算的多种方式　10
一个程序，多个定义　13
另一个定义　15
现在你是一名程序员了　17
不！　17
第　一部分 固定大小的数据
第　1章 算术　20
1．1　数值的算术　21
1．2　字符串的算术　22
1．3　二者的混合　23
1．4　图像的算术　24
1．5　布尔值的算术　26
1．6　布尔值的混合　27
1．7　谓词：了解你的数据　29
第　2章 函数和程序　31
2．1　函数　31
2．2　计算　33
2．3　函数的复合　36
2．4　全局常量　38
2．5　程序　39
第3章　程序设计方法　49
3．1　设计函数　50
3．2　熟练习题：函数　54
3．3　领域知识　54
3．4　从函数到程序　54
3．5　关于测试　55
3．6　设计世界程序　56
3．7　虚拟宠物世界　63
第4章　区间、枚举和条目　65
4．1　条件编程　65
4．2　条件计算　67
4．3　枚举　69
4．4　区间　71
4．5　条目　75
4．6　条目的设计　80
4．7　有限状态世界　82
第5章　添加结构体　88
5．1　从位置到posn结构体　88
5．2　posn的计算　88
5．3　posn的编程　89
5．4　定义结构体类型　91
5．5　结构体的计算　94
5．6　结构体的编程　97
5．7　数据的空间　102
5．8　结构体的设计　105
5．9　世界中的结构体　106
5．10　图形编辑器　107
5．11　再探虚拟宠物　109
第6章　条目和结构体　111
6．1　再谈条目的设计　111
6．2　世界的混合　119
6．3　输入错误　121
6．4　世界中的检查　124
6．5　相等谓词　125
第7章　总结　127
独立章节1　初级语言　128
初级语言的词汇　128
初级语言的文法　129
初级语言的含义　131
含义和计算　133
初级语言中的错误　133
布尔表达式　135
常量定义　136
结构体类型定义　137
初级语言中的测试　139
初级语言的错误消息　140
第二部分　任意大的数据
第8章　链表　146
8．1　创建链表　146
8．2　'()是什么，cons又是什么　149
8．3　用链表编程　151
8．4　使用链表进行计算　154
第9章　使用自引用数据定义进行设计　156
9．1　熟练习题：链表　160
9．2　非空链表　161
9．3　自然数　166
9．4　俄罗斯套娃　168
9．5　链表和世界程序　171
9．6　关于链表和集合　174
第　10章 再谈链表　178
10．1　生成链表的函数　178
10．2　链表中的结构体　180
10．3　链表中链表以及文件　183
10．4　再谈图形编辑器　189
第　11章 组合式设计　197
11．1　list函数　197
11．2　函数的组合　199
11．3　递归的辅助函数　200
11．4　一般化的辅助函数　204
第　12章 项目：链表　212
12．1　现实世界中的数据：字典　212
12．2　现实世界中的数据：iTunes　213
12．3　文字游戏—组合的示例　217
12．4　文字游戏—问题的核心　220
12．5　贪吃蛇　221
12．6　简单俄罗斯方块　223
12．7　全面太空战争　225
12．8　有限状态机　226
第　13章 总结　231
独立章节2　Quote和Unquote　232
Quote　232
Quasiquote和Unquote　233
Unquote　Splice　236
第三部分　抽象
第　14章 无处不在的相似性　242
14．1　函数的相似性　242
14．2　不同的相似性　243
14．3　数据定义的相似性　246
14．4　函数是值　248
14．5　函数的计算　249
第　15章 设计抽象　252
15．1　抽象的示例　252
15．2　签名的相似性　255
15．3　单个控制点　259
15．4　模板的抽象　259
第　16章 使用抽象　261
16．1　现有的抽象　261
16．2　局部定义　264
16．3　局部定义增强表达能力　266
16．4　local的计算　268
16．5　使用抽象的示例　271
16．6　用抽象设计　274
16．7　熟悉抽象的习题　275
16．8　项目中的抽象　276
第　17章 匿名函数　278
17．1　lambda函数　278
17．2　lambda的计算　280
17．3　用lambda抽象　282
17．4　用lambda制定规范　284
17．5　用lambda表示　289
第　18章 总结　293
独立章节3　作用域和抽象　294
作用域　294
中级语言的循环　298
模式匹配　304
第四部分　交织的数据
第　19章 S表达式之诗　310
19．1　树　310
19．2　森林　316
19．3　S表达式　317
19．4　对交织数据的设计　321
19．5　项目：二叉查找树　322
19．6　函数的简化　325
第　20章 迭代改进　327
20．1　数据分析　327
20．2　数据定义的改进　328
20．3　函数的改进　330
第　21章 解释器的改进　332
21．1　表达式的解释　332
21．2　变量的解释　335
21．3　函数的解释　336
21．4　解释一切　338
第　22章 项目：XML商业　340
22．1　XML和S表达式　340
22．2　XML枚举的呈现　344
22．3　领域特定语言　348
22．4　读入XML　352
第　23章 同时处理　355
23．1　同时处理两个链表：情况1　355
23．2　同时处理两个链表：情况2　356
23．3　同时处理两个链表：情况3　357
23．4　函数的简化　360
23．5　设计读入两个复杂输入的函数　361
23．6　熟练习题：两个输入　362
23．7　项目：数据库　365
第　24章 总结　374
独立章节4　数值的本质　375
固定大小的数值算术　375
溢出　379
下溢出　379
教学语言中的数值　380
第五部分　生成递归
第　25章 非标准递归　386
25．1　无结构体的递归　386
25．2　忽略结构体的递归　389
第　26章 设计算法　393
26．1　调整设计诀窍　393
26．2　终止　394
26．3　对比结构化递归和生成递归　396
26．4　做出选择　397
第　27章 主题的变化　401
27．1　初试分形　401
27．2　二分查找　403
27．3　初探解析　407
第　28章 数学的例子　411
28．1　牛顿法　411
28．2　数值积分　414
28．3　项目：高斯消元　418
第　29章 回溯的算法　423
29．1　图的遍历　423
29．2　项目：回溯　430
第30章　总结　434
独立章节5　计算的成本　435
具体的时间和抽象的时间　436
“数量级”的定义　440
为何使用谓词和选择函数　442
第六部分　知识的累积
第31章　知识的丢失　446
31．1　结构处理的问题　446
31．2　生成递归的问题　449
第32章　累积器风格函数的设计　453
32．1　认识到需要累积器　453
32．2　添加累积器　454
32．3　将函数转换为累积器风格　455
32．4　带鼠标的图形编辑器　464
第33章　累积的更多用途　466
33．1　累积器和树　466
33．2　带累积器的数据表示　470
33．3　作为结果的累积器　474
第34章　总结　479
尾声：继续前进　481

计算机