HOW TO DESIGN PROGRAMS

http://www.htdp.org

·前言

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