How To Design Programs (2nd Edition)

【实例简介】
现代编程语言的语法大多很繁杂，初学者使用这些语言学习编程会导致花大量的时间在编程语言语法（诸如指针，引用和类型定义）而不是程序设计方法（诸如数据抽象和过程抽象）之上。程序设计方法解决了这个问题——它专注于程序设计方法，使得读者无需把大量时间花在编程语言上。这本书还有一个与之配套的教学开发环境DrRacket，这个环境会根据读者的程度变换编程语言的深度，使得读者可以始终把注意力集中在程序设计方法上。—————http://lucida.me/blog/developer-reading-list/#htdp 这是我从网站上打印下来的，整合成了一个pdf文件，方便离线阅读
2015/119 Preface series of programming languages tailored to the book's design concepts. Initially, the environment roughly corresponds to the world of a so-called pre-algebra course. Both the environment and the language grow with the design concepts. This staging allows the environment to provide tailored feedback in terms of the concepts covered so far-in stark contrast to the usual approach of using professional environments, which only overwhelm ginners Designing programs in this context means that you, the reader, will acquire two kinds of skills. On one hand, program design teaches the same analytical skills as mathematics especially (pre)algebra and geometry. But, unlike mathematics, working with programs is an active approach to learning. Creating software provides immediate feedback and thus programs produces fun and useful things, which vastly increases the sense or in leads to exploration, experimentation, and self-evaluation. Furthermore, designing accomplishment when compared to drill exercises in mathematics texts On the other hand, program design teaches the same analytical reading and writing skills as English Even the smallest design tasks are formulated as word problems Without critical reading skills, you cannot design programs that solve the problem and match its specifications Conversely, program design methods force you to articulate their thoughts in proper and precise English. Indeed, our observations suggests that if you truly absorb the design recipe, you will develop your articulation skills more than anything else Systematic Design A program interacts with people, whom computer scientists call users. Some programs request all their inputs as soon as they are launched and then compute an answer without any further interaction with the user. Others request some input, produce an output, prompt users for more input, and so on. And, different programs use different devices to absorb inputs or deliver outputs Regardless of its mode of interaction, any useful program is likely to consist of many building blocks because it is difficult to construct a reliable artifact in one piece. The key is to discover which building blocks are needed how to connect them, and how to build blocks when needed. We choose to call this activity design because its dictionary meaning matches this description. In support of the design activity this book introduces two kinds of guidelines: recipes and refinement 1. Problem analysis Identify the information that must be represented and how it is represented in the chosen programming language. Formulate data definitions and illustrate them with examples 2. Signature, Purpose Statement, Header State which data the desired function consumes and produces Articulate what the function computes as a concise one-line statement. Define a stub that lives up to the signature 3. Functional Examples Work through examples that illustrate the functions purpose 4. Function Template Translate your data definitions into an outline of the function 5. Function definition http://www.ccs.neu.edu/home/matthias/iitdp2e/Draft/part_preface.html 2/10 2015/119 Preface Fill in the gaps in the function template. Exploit the purpose statement and the examples 6. Testing Articulate the examples as tests and ensure that the function passes all. The tests will hel ur successor ensure that the function works for these examples after future modifications Figure 1: The basic steps of a program design recipe Design recipes come at two levels: for programs and for functions, which in our world are the basic building blocks of programs. Two recipes are about complete programs: one for graphical interactive programs and one for batch programs. All others are about the construction of individual functions with a focus on so-called structural design This latter recipe deals with the design of functions that operate on structured data and whose organization reflects the structure of the data. It is best to think of this recipe as a grid with two dimensions. One dimension lists the steps of the design process; the other "measures increasingly complex forms of data Figure 1 displays the six steps of the structural design process. Each step states the expected outcomes and some activities. Examples play a central role in the process. For the chosen data representation in step 1 writing down examples proves that Instructors Have students copy figure 1 on one you know how real world side of an index card when students are stuck in formation is encoded as data and ask them to prove that they are card-carrying how data is interpreted as members of the design club. Once they information. The request for functional examples in step 3 forces produce the card, point them to the step where they are stuck you to work through concrete scenarios and thus helps you understand what the function is expected to compute. In step 6, you turn examples into tests, which ensures that the function works properly for some cases. While structural design is most of what programmers end up practicing in the real world, they also spend a good amount of time abstracting ("refactoring "in modern parlance code or figuring out how to re-use existing abstractions. Abstracting means unifying simila program fragments into a single element and reusing this element in place of the origin fragments; many languages already come with extremely powerful abstractions so that programmers don't have to re-do basic work over and over again. Hence the book offers design recipes on creating abstractions and using existing abstractions The rest of the book expands and revises the structural design recipes in different directions Even this first look at the design recipes ought to clarify why we claim that design guidelines make sure you never really get stuck. equipped with the design recipes, you don't have to stare at a blank screen and wait for an idea to show up you always have a concrete goal, an intermediate product to create. As a matter of fact, the design recipes provide guidance for each step in the form of pointed questions. The Instructors tell students to write down the answers to these questions help create questions for the creation of structural the intermediate product in an templates and functions on the back of their incremental fashion Our students index card quickly discover that we ask the same questions over and over again, and that they can ask these questions on their own. They thus learn to help themselves. And http://www.ccs.neu.edw/home/matthias/iitdp2e/draft/part_preface.html 3/10 2015/119 Preface you can do so, too. With this explanation of design recipes and design processes, you can also see how the teaching of program design instills skills that are important in a variety of professions. To design a program properly, you must L. analyze a problem statement, typically stated as a word problem 2. extract and express its essence, abstractly and with examples 3. make outlines and plans based on this analysis 4. evaluate results with respect to expected outcomes; and 5. revise the product in light of failed checks and tests Each step requires analysis, precision, description, focus on and attention to specific details. Any experienced businessman, engineer, journalist, lawyer, scientist, or any other professional can tell you how many of these skills are necessary for his or her daily work Practicing program design is one way to prepare yourself for these professions Iterative Refinement addresses the problem of designing complex programs. When a program addresses many concerns and consists of many functions, getting everything right at once is nearly impossible. In response, this book introduces the design concept of iterative refinement, which calls for creating complete programs in discrete layers. Its inner core is the essence of the desired functionality; additional refinement steps improve the functionality of the core and add additional functionality. In this sense a programmer is a mini-scientist who creates approximate models of the desired product, translates them into first designs, evaluates them with users, and iteratively refines them until the product closely matches the initial idea. Indeed, the best programmers rewrite and refine their programs many times until they meet the desired standard Refining and reworking designs is not restricted to computer science and program creation. Architects, composers, writers and all professionals do it, too. They start with ideas in their head and somehow articulate their essence. They refine it on paper until their product reflects their mental image as much as possible. As they bring their ideas to paper, they employ basic skills analogous to fully absorbed design recipes drawing writing, or piano playing to express certain style elements of a building, describe a persons haracter, or formulate portions of a melody. Conversely, they are productive with an iterative development process because they have absorbed basic skills and they have learned which "design recipe"to choose for the situation at hand DrRacket and the Teaching Languages People often tell us that they wish to learn how to program and then they ask which programing language they should learn(first). Given the press that some programming languages get, this question is not surprising. But it is also inappropriate s the preceding sections explain, learning to program well is primarily about studying principles of design. The ideal programming language must support these principles and its mplementation must explain all the mistakes novices make in terms that they understand Our research shows that no off-the-shelf industrial language satisfies the second constraint Their creators expect that the programmers immediately know the entire language because they have professional programmers in mind who roughly understand the fundamental http://www.ccs.neu.edw/home/matthias/iitdp2e/draft/part_preface.html 4/10 2015/119 Preface concepts of languages Our programming language ensures that a reader who works through the first part of this book will also master the concepts of pre-algebra Our solution is to use our own, incredibly small, teaching language, dubbed *SL in this preface. The language includes notation for function definitions, function applications, and nested, potentially conditional expressions. In essence, it is the foreign language that students in pre-algebra courses acquire. The difference is that our language comes with many more kinds of data than algebra-in addition to numbers, its basic data includes images and words. The language also comes with a number of pre-defined functions that make working in "pre-algebra?"fun and entertaining; the very first program is a small animation When it comes to programming environments, we face an equally bad choice. A programming environment for professionals is the rough analogue of the cockpit of a jumbo jet. It has numerous controls and displays, overwhelming anyone who first launches such a software application. Novice programmers need the equivalent of a two-seat, sing. engine propeller aircraft with which they can practice basic skills. We have therefore created Drracket, a programming environment for novice programmers DrRacket consists of two simple panes: a Definitions area, where you define functions, and an Interactions area, where you interact with them. Even when there is nothing in the Definitions area, you can immediately experiment with expressions in the interactions area. Thus, experimenting starts with pocket-calculator arithmetic, and it proceeds from there to calculations with images, words, lists, and other forms of data. This way, learning is closely supported by a highly playful, feedback-oriented support system An interactive evaluator simplifies the programming language and the learning process Concretely, DrRacket has two advantages over conventional programming environments First, it enables novice programmers to manipulate data directly. Hence the language does not need facilities for reading input and writing output and novices don t need to spend valuable time on figuring out how these work. Second, the arrangement strictly separates data and data manipulation from input and output of information. Nowadays this separation is considered so fundamental to the construction of software that it has its own name: called model-view-controller architecture. In short, working in DrRacket ensures that you pick up fundamental software engineering ideas in a natural way. The parts of the book The book consists of a prologue, six parts, five intermezzos, and an epilogue. While the parts focus on program design, the intermezzos introduce other topics concerning programming and computing. Here is a brief overview Prologue: How to Program is a quick introduction to plain programming. It introduces everything needed to write a simple animation. Any novice to programming is bound to feel empowered, overwhelmed, or both. The final note explains that this is not how we should teach programming and that we really need to organize our thoughts in a better way than this prologue Fixed-Size Data thoroughly explains the most basic mechanisms of program design and key concepts of computing. It starts with a look at arithmetic in our language pecifically the arithmetic of atomic data--numbers, words, images and so on-before it http://www.ccs.neu.edw/home/matthias/iitdp2e/draft/part_preface.html 5/10 2015/119 Preface introduces functions and programs. At that point, the book switches to concepts of systematic design of batch and interactive programs plus simple functions. The rest of this part expands the realm of data with intervals, enumerations, itemizations structures and various combinations of these Intermezzo: BSL describes the teaching language in complete detail its vocabulary, its grammar, and its meaning. Computer scientists refer to these as syntax and semantics Arbitrarily Large Data extends Fixed-Size Data with the most interesting and useful form of data: arbitrarily large compound data. While a programmer may nest the kinds of data from Fixed-Size Data to represent information, the nesting is of a specific depth and breadth--meaning the piece of data is of a fixed size. This part shows how a subtle generalization gets us from there to data of arbitrary size and how to design functions that process this kind of data Intermezzo: Quote, Unquote introduces a short-hand for writing down large pieces of data: quotation and anti-quotation Although this notation is close to 60 years old, few appreciate its power and even fewer languages include such facilities Abstraction acknowledges that many of the functions from Arbitrarily Large Data look alike. No programming language should force programmers to create and maintain pieces of code that are that similar to each other; conversely, every good programming language comes with some mechanism for unifying such similarities. Computer scientists call this abstraction, and they know that abstraction greatly increases a programmer's productivity. Hence, this part introduces design recipes for creating abstractions and for using existing abstractions Intermezzo: Scope and Abstraction plays two roles. First, it explains the important concept of lexical scope, the idea that a programming language ties every occurrence of a name to a definition that a programmer can find with a plain inspection of the program. Second, it introduces a library with additional mechanisms for abstraction, so called for loops plus pattern matching. Both show how powerful the teaching languages actually are Intertwined Data generalizes the story of Arbitrarily Large Data in several directions and also introduces the idea of iterative refinement into the catalog of design concepts Intermezzo: The Nature of Numbers explains how"decimal"numbers realy work in (all) programming languages. Every budding programmer ought to know these basic facts, and in the context of this book, the ideas are easy to discuss and illustrate Generative Recursion injects a completely new design idea. While structural design and abstraction suffice for most problems that programmers encounter, they often lead to insufficiently"performant"programs. In other words, structurally designed programs might need too much time or memory or energy to compute the desired answers Computer scientists therefore replace structurally designed programs with programs that benefit from ad hoc insights into the problem domain This part of the book shows how to design a large class of just such programs, specifically which parts of the design remain systematic and which parts benefit from problem-specific insights. Intermezzo: The Cost of Computation uses the discussions from Generative Recursion to illustrate how computer scientists think about performance abstractly Accumulators adds a final trick to the tool box of designers: accumulators. Roughly speaking, an accumulator adds "memory"to a function. The addition of memory greatly improves the performance of structurally designed functions from the first four parts of the book. For the ad hoc programs from Generative Recursion, accumulators can make http://www.ccs.neu.edw/home/matthias/iitdp2e/draft/part_preface.html 6/10 2015/119 Preface he difference between finding an answer at all and never finding one. Epilogue: How Not to Program is both an assessment and a look ahead to what's next. Prolog SL The nature of numbers Quote, Unquote Scope and abstraction The cost of computation pilo Figure 2: The dependencies among parts and intermezzos (draft) To the Reader and the Instructor We would really like you to work through the entire book, from the first page to the last We would really like for instructors to cover as many pieces as possible, starting from Prologue all the way through the Epilogue. In our courses, we do so, and we make sure that, in the end, students create a sizable and entertaining program But, we understand that some circumstances call for significant cuts and that some instructors tastes call for slightly different ways to interpret the book. For those, figure 2 shows how the pieces depend on each other. Solid arrows suggest a mandatory sequence dotted lines are mere suggestions. Here are three possible shortened paths through the book A high-school instructor may want to cover(as much as possible of) parts Fixed-Size Data and Arbitrarily Large data, including a small project based on the design recipes of these two parts a college instructor in a quarter system may wish to focus on parts Fixed-Size Data Arbitrarily Large Data, Abstraction, and Generative Recursion, with the intermezzos on http://www.ccs.neu.edw/home/matthias/iitdp2e/draft/part_preface.html 7/10 2015/119 Preface *SL and scope A college instructor in a semester system may prefer to discuss performance trade-offs n designs as early as possible. In this case, it is best to cover parts Fixed-Size Data and Arbitrarily Large Data and then those chapters and sections of part Accumulators that do not depend on generative recursion At that point, it is possible to discuss Intermezzo: The Cost of Computation and to return to the remaining pieces of the book as desired Reading the prologue first is a good idea regardless of the chosen path Iteration of Sample topics the book revisits certain exercise and sample topics time and a gain. For example, pets are found all over Fixed-Size Data and even show up i Arbitrarily Large Data. Similarly, both Fixed- Size Data and Arbitrarily Large Data cover alternative approaches to implementing an interactive text editor. Graphs appear in Generative Recursion and immediately again in Accumulators. The purpose of these iterations is to motivate iterative refinement and to introduce it through the backdoor. We urge instructors to assign these themed sequences of exercises or to create their own sequences. The Differences This second edition of "How to Design Programs"differs from the first one in several aspects L. The second edition explicitly acknowledges the difference between designing a program and designing a bunch of functions. In particular, this edition focuses on two kinds of programs: interactive and graphical programs and batch programs 2. The design of a program proceeds in a top-down planning and a bottom-up construction fashion. We explicitly show how the interface to libraries dictates the shape of certain program elements. In particular, the very first phase of a program design yields a wish list of functions. While the concept of a wish list exists in the first edition, the second edition treats it as an explicit design element 3. The design of each wish on the wish list relies on the function design recipe. As in the first edition, the six parts focus on structural design, compositional design, generative recursion,and designs with accumulators 4. A key element of structural design is the definition of functions that compose others. This design-by-composition is especially useful for the world of We thank Dr. Kathi Fisler for focusing our batch programs Like generative attention on this point recursion, it requires a eureka specifically a recognition that the creation of intermediate data by one function and processing the intermediate data by a second function simplifies the overall design. Again, this kind of planning also creates a wish list, but formulating these wishes calls for an insightful development of an intermediate data definition This edition of the book weaves in a number of explicit exercises on design-by-composition. While testing has always been a part of our design philosophy, the teaching languages and drracket started supporting it properly only in 2002, just after we had released the first edition. This new edition heavily relies on this testing support http://www.ccs.neu.edw/home/matthias/iitdp2e/draft/part_preface.html 2015/119 Preface 5. This edition of the book drops the design of imperative programs. The old chapters remain available on-line. The material will be moved into the second volume of this series, How to Design Components 7. The book's examples and exercises employ new teachpacks. The preferred style is to link in these libraries via so-called require specifications, but it is still possible to add teachpacks via a menu in DrRacket B. Finally, this second edition differs from the first in terminology and notation Second edition first edition Signature contract Itemization union empty #true true #false false The last three differences greatly improve quotation for lists Acknowledgments from the first edition Four people deserve special thanks: Robert Corky"Cartwright, who co-developed a predecessor of Rice's introductory course with the first author; Daniel P. Friedman, for asking the first author to rewrite The Little LisPer (also mit Press)in 1984, because it tarted this project; John Clements, who designed, implemented, and maintains Drracket's stepper; and Paul Steckler, who faithfully supported the team with contributions to our suite of programming tools The development of the book benefited from many other friends and colleagues who used it in their courses and/ or gave detailed comments on early drafts. We are grateful to them Kathi Fisler, Daniel P. Friedman, John Greiner, John Stone, Geraldine Morin, andt for their help and their patience: lan Barland, John Clements, Bruce Duba, Mike Ernst Valdemar tamez a dozen generations of Comp 210 students at Rice University used early drafts of the text and contributed improvements in various ways. In addition, numerous attendees of our TeachScheme! workshops used early drafts in their classrooms. Many sent in comments and suggestions. As representative of these we mention the following active contributors: Ms Barbara Adler, Dr Stephen bloch, Mr Jack Clay, Dr Richard Clemens, Mr. Kyle Gillette, Ms Karen Buras, Mr Marvin Hernandez. Mr Michael Hunt. Ms Karen North, mr. Jamie raymond, and Mr robert reid. Christopher Felleisen patiently worked through the first few parts of the book with his father and provided direct insight into the views of a young student. Hrvoje Blazevic(sailing, at the time, as Master of the LPG/C Harriette), Joe Zachary(University of Utah) and Daniel P. Friedman (Indiana University) discovered numerous typos in the first printing, which we have now fixed. Thank you to everyone Finally, Matthias expresses his gratitude to Helga for her many years of patience and for creating a home for an absent-minded husband and father robby is grateful to Hsing-Huei Huang for her support and encouragement; without her, he would not have gotten anything done. Matthew thanks Wen Yuan for her constant support and enduring music Shriram is indebted to Kathi Fisler for support, patience and puns, and for her participation in this project Acknowledgments http://www.ccs.neu.edw/home/matthias/iitdp2e/draft/part_preface.html 9/10 【实例截图】
【核心代码】