程序设计方法.PDF

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