如何设计程序？

摘自《How to Design Programs》 BY Matthias Felleisen / Robert Bruce Findler / Matthew Flatt / Shriram Krishnamurthi

刘建文略译（http://blog.csdn.net/keminlau ）

KEY: 程序设计 工作 方法论 科学方法论 职业 创新 基础教育

Preface

It goes against the grain of modern education to teach children to program. What fun is there in making plans, acquiring discipline in organizing thoughts, devoting attention to detail and learning to be self-critical?
-- Alan Perlis, Epigrams in Programming

向儿童传授程序设计知识有悖于现代教育学。制定计划。学习教规。注重细节。严格自律有何乐趣?
--艾伦·佩利(1966年图灵奖获得者)，《编程警句》

Many professions require some form of computer programming. Accountants program spreadsheets and word processors; photographers program photo editors; musicians program synthesizers; and professional programmers instruct plain computers. Programming has become a required skill.

许多职业都需要进行某种形式的计算机“程序设计”。会计师使用电子表格和字处理程序设计，摄影师使用图片编辑程序设计，音乐家使用音响合成程序设计，职业程序员则直接对计算机进行程序设计。“程序设计”已成为一种人人都需要掌握的技能。
KEMIN:著者的意思其实是人人都要工作，只抽象为一个共同的概念--程序设计。

Yet programming is more than just a vocational skill. Indeed, good programming is a fun activity, a creative outlet, and a way to express abstract ideas in a tangible（实体的, 有形的） form. And designing programs teaches a variety of skills that are important in all kinds of professions: critical reading, analytical thinking, creative synthesis, and attention to detail. We therefore believe that the study of program design deserves the same central role in general education as mathematics and English. Or, put more succinctly, everyone should learn how to design programs.

程序设计并不仅仅是一种职业技能。事实上，编程是件有趣的活动，是种施展创造性的手段，也是一种表达抽象概念的用有形方式。通过设计程序，可以磨练人各种职业技能，如阅读能力、分析能力、动手能力以及倾听能力（关注细节）等。所以，在基础教育中，程序设计课程的地位应该和数学、语文一样重要。或者用更简洁的话来说，就是每个人都应该学习如何设计程序。 为什么呢？

On one hand, program design teaches the same analytical skills as mathematics. But, unlike mathematics, working with programs is an active approach to learning. Interacting with software provides immediate feedback and thus leads to exploration, experimentation, and self-evaluation. Furthermore, designing programs produces useful and fun things, which vastly increases the sense of accomplishment when compared to drill exercises in mathematics. On the other hand, program design teaches the same analytical reading and writing skills as English. Even the smallest programming tasks are formulated as word problems. Without critical reading skills, a student cannot design programs that match the specification. Conversely, good program design methods force a student to articulate thoughts about programs in proper English.

一方面，程序设计跟数学一样，可以训练人的分析能力，不同的是，程序设计是一种积极的学习方法。在与软件的互动过程中，学生可以直接得到反馈，进行探索、实验和自我评价。与钻研数学习题相比，程序设计的成果，即计算机软件，更有趣，也更有用，它们能极大地增加学生的成就感。另一方面，程序设计跟语文一样，可以增强学生的阅读和写作能力。即使是最小的编程任务，也是以文字形式表达的，没有良好的判断和阅读技能不可能设计出符合规范的程序，反之，好的程序设计方法会迫使学生用适当的语言清晰地表达他的思考过程。

编程设计处方

Our guidelines are formulated as a number of program design recipes.1 A design recipe guides a beginning programmer through the entire problem-solving process. With design recipes, a beginner almost never again stares at a blank piece of paper or a blank computer screen. Instead, the student will check the design recipe and use the question-and-answer guidelines to make some progress.

本书提出一种称为“编程设计处方”（programming design recipe）的编程指导来引入编程方法论概念。编程设计处方可指导程序设计初学者练习问题求解的全过程。有了设计处方，程序设计的初学者就不用再盯着空白的纸张或计算机屏幕发呆了，他们可以自我检查并核对设计处方，使用“问答”方式进行程序设计并取得进步。

We created the design recipes by identifying categories of problems. The identification of a problem category is based on the classes of data that are used to represent the relevant information. Starting from the structure of this class description students derive the programs with a checklist. Figure 1 shows the basic six steps of a design recipe checklist. Each step produces a well-defined intermediate product:

• 1. the description of the class of problem data;
• 2. the informal specification of a program's behavior;
• 3. the illustration of the behavior with examples;
• 4. the development of a program template or layout;
• 5. the transformation of the template into a complete definition; and
• 6. the discovery of errors through testing.

The major difference concerns the relationship of steps 1 and 4.

我们创立各种设计处方的根据是问题的范畴（categories），而标识问题的范畴是基于用于描述问题的数据及相关信息的型别（class）。从数据型别的结构出发，学生可以通过一个设计处方清单（checklist）半自动地推导出程序。下面给出的设计处方的6个基本步骤，每个步骤都将产生定义明确的中间结果：

• 1. 写下问题数据的型别
• 2. 写下程序行为的非正式规格（specification）
• 3. 举例说明程序的行为
• 4. 开发出程序的模板或整体框架
• 5. 把以上的程序模板转换成完整的定义
• 6. 通过测试发现错误

不同的设计处方主要差异在于第1步和第4步之间。

Design recipes help beginners and teachers alike. Teachers can use the recipes to inspect a beginner's problem-solving skills, to diagnose weaknesses, and to suggest specific remedial steps. After all, each stage of the design recipe yields a well-defined, checkable product. If a beginner is stuck, a teacher can inspect the intermediate products and determine what the problem is. Based on this analysis, the teacher can then provide guidance for a specific step in the recipe, raise appropriate questions, and recommend additional practice exercises.

使用设计处方不仅对初学者有所帮助，对教师教学也很有益。教师可以使用清单检查初学者解决问题的能力，具体诊断出学生能力弱点，从而有针对性强化学生能力。此外，设计处方的每一步都会产生一个定义明确、可检查的结果；如果一个初学者在设计过程被掐住了，教师可以借助清单检查他的中间结果，并判断问题之所在。基于这样的一种有针对性的分析，教师就可以有针对性的对学生提供学习指导，比如提出一些问题，推荐一些额外的练习。

设计处方

Cooking is at once child's play and adult joy. And cooking done with care is an act of love.
-- Craig Claiborne (1920-2000), Food Editor, New York Times

烹饪既是孩童的游戏也是成人的乐事，细心烹饪是爱的举措。
--克雷格·卡莱波恩(1920--2000)，《纽约时报》饮食版编辑

Learning to design programs is like learning to play soccer. A player must learn to trap a ball, to dribble with a ball, to pass, and to shoot a ball. Once the player knows those basic skills, the next goals are to learn to play a position, to play certain strategies, to choose among feasible strategies, and, on occasion, to create variations of a strategy because none of the existing strategies fits.

学习设计程序就像学习踢球一样，必须练习夺球、运球、传球和射门。一旦掌握了这些基本技能，下一个目标就是学习担任某个角色，选择并实施合适的策略,。这样当你遇到没有完全符合战况的策略，能适当调整符合战况的策略。

A programmer is also very much like an architect, a composer, or a writer. They are creative people who start with ideas in their heads and blank pieces of paper. They conceive构思 of an idea, form a mental outline, and refine it on paper until their writings reflect their mental image as much as possible. As they bring their ideas to paper, they employ basic drawing, writing, and instrumental skills to express certain style elements of a building, to describe a person's character, or to formulate portions of a melody. They can practice their trade because they have honed用磨刀石磨 their basic skills for a long time and can use them on an instinctive本能的, 直觉的 level.

程序设计者也和建筑师、作曲家和作家一样，是富有创造性的人。他们的创新起始于脑内的一个构想和手上的一张白纸。他们通过在纸上反复对这个构想进行进一步的构思、描绘和精细，直到尽可能接近构想原型。在这个从构想到实现的过程中，他们会使用一些基本职业技能进行工作（比如绘图、著述等），比如建筑师绘图来表达建筑物风格、作家描述人的特征等。他们能胜任自己的职业，是因为他们长时间的磨练了这些职业基本技能，工作时能本能地使用这些技能。

Programmers also form outlines, translate them into first designs, and iteratively refine them until they truly match the initial idea. Indeed, the best programmers edit and rewrite their programs many times until they meet certain aesthetic美学的 standards. And just like soccer players, architects, composers, or writers, programmers must practice the basic skills of their trade for a long time before they can be truly creative.

程序设计者同样从构想开始，初步翻译为第一个设计版本，尔后反复修订精细，直到与最初的构想相符。事实上，优秀的程序设计者会对自己的作品要求很高，他们会多次编辑和修改自己的程序，以满足某种美学标准。从工作过程这一点上看，程序设计者这和足球运动员、建筑师、作曲家以及作家一样，要开展他们的职业工作，甚至创新的工作，他们必须先长期练习该职业所必需的基本技能。

Design recipes are the equivalent of soccer ball handling techniques, writing techniques, techniques of arrangements, and drawing skills. A single design recipe represents a point of the program design space. We have studied this space and have identified many important categories. This book selects the most fundamental and the most practical recipes and presents them in increasing order of difficulty.2

（KEMIN：本段落非我译）设计处方好比控球技法、写作技法、乐曲编排技法和绘图技巧。通过学习和研究，在程序设计领域，计算机科学家已经积累了许多重要的方法和技巧，本书挑选了其中最重要和最实用的一些，由浅入深，逐一讲解。

About half the design recipes focus on the connection between input data and programs. More specifically, they show how the template of a program is derived from the description of the input data. We call this data-driven program design, and it is the most frequently used form of design. Data-driven designs are easy to create, easy to understand, and easy to extend and modify. Other design recipes introduce the notion of generative recursion, accumulation, and history sensitivity.

（KEMIN：本段落非我译）本书大约有一半的设计诀窍涉及输入数据和程序之间的关系。更准确地说，它们描述了如何从输入数据的描述得出整个程序的模板，这种基于数据驱动的程序设计方式最常见，易于创建。理解。扩展和修改。其他设计诀窍有生成递归(generative recursion)。累积(accumulation)和历史敏感性(history sensitivity)。

The first one produces recursive programs that generate new instances of problems as they recur; accumulator-style programs collect data as they process inputs; and history-sensitive programs remember information between successive applications. Last, but not least, we also introduce a design recipe for abstracting over programs. Abstracting is the act of generalizing two (or more) similar designs into one and of deriving the original instances from it.

（KEMIN：本段落非我译）其中，递归型程序可以被重复调用以处理新的问题，带累积器的程序在处理输入的过程中收集数据，历史敏感性程序可以记住程序被多次调用的信息。最后，但不是最不重要的，是抽象程序的设计诀窍。抽象是把两个 (或更多)相似的设计概括为一个并由它衍生最初示例。

On many occasions, a problem naturally suggests one design recipe. On others, a programmer must choose from among several possibilities; each choice may produce programs with vastly different organizations. Making choices is natural for a creative programmer. But, unless a programmer is thoroughly familiar with the bag of design recipes to choose from and completely understands the consequences of choosing one over the other, the process is necessarily ad hoc and leads to whimsical, bad designs. We hope that by mapping out a collection of design recipes, we can help programmers understand what to choose from and how to choose.

很多时候，一个问题往往只适合套用某个设计处方。而有时候，一个问题可能几个可选的设计处方，不同的设计处方可能会产生完全不同的程序组织。作出抉择是程序员具有创造性的体现（KEMIN：设计处方只是一种半自动辅助设计手段），所以这时候除非程序员十分熟悉所有可选的设计处方，完全理解选择某个处方而不是另一个处方的后果，否则程序员必须对不甚合适的现有处方进行修剪，按需设计，生搬硬套只会得到一个离奇古怪的设计。

Now that we have explained what we mean by ``programming'' and ``program design,'' the reader can see why and how teaching program design instills thinking skills that are important in a variety of professions. To design a program properly, a student must:

• 1. analyze a problem statement, typically stated as a word problem;
• 2. express its essence, abstractly and with examples;
• 3. formulate statements and comments in a precise language;
• 4. evaluate and revise these activities in light of checks and tests; and
• 5. pay attention to details.

All of these are activities that are useful for a businessman, a lawyer, a journalist, a scientist, an engineer, and many others.

现在我想大家应该开始明白我一开始提出所谓“程序设计”的意思了。并且也应该明白为什么“程序设计”有益每一种职业和如何讲授“程序设计”。要正确地设计程序，你必须：

• 1. 分析一个问题的陈述（一般是以文字表达）；
• 2. 撑握问题的实质，能抽象地和具体地表述它；
• 3. 形式化问题的陈述，用精确的语言对模糊的地方进行注释；
• 4. 通过检查和测试对上述活动进行评估和修订；和
• 5. 关注细节。

上述过程几乎接近一般的科学方法论内容，所以对所有的职业，包括商人、律师、记者、科学家和工程师都是有效的。

While traditional programming requires these skills, too, beginners often don't understand this connection. The problem is that traditional programming languages and traditional forms of programming force students to perform a large amount of book-keeping work and to memorize a large number of language-specific facts. In short, menial work drowns the teaching of essential skills. To avoid this problem, teachers must use a programming environment that imposes as little overhead as possible and that accommodates beginners. Because such tools didn't exist when we started, we developed them.

方法论的东西很有价值，但是“百姓日用而不知”，尤其是对初哥来更是如此。一般的程序设计者都会沉没于技术细节（比如语言细节），这对于工作的效率和职业发展是很有害的。但是我们干活也不能光谈方法理论不涉及细节，怎么在两者找到一个很好的折中呢？本书的著者声称开发一项辅助工具，好，我们拭目以待，文哥要开始干活袅……