it-ebooks - How to Design Programs, Second Edition

From: How to Design Programs, Second Edition

Please send reports about mistakes to matthias @ ccs.neu.edu after double-checking in the

This document is the current, stable release of HtDP/2e. It isupdated in sync with semester breaks (summer, new years). It is thuswell-suited for courses. In contrast, changes on a frequent basis; it should be consultedwhen people discover problems and/or errors in this document. If suchflaws exist in both documents, please report them to the first author.

Many professions require some form of programming. Accountants program spreadsheets; musicians program synthesizers; authors program word processors; and web designers program style sheets. When we wrote these words for the first edition of the book (19952000), people considered them futuristic; by now, programming has become a required skill and numerous outletsbooks, on-line courses, K-12 curriculacater to this need, always with the goal of enhancing peoples job prospects.

The typical course on programming teaches a tinker until it works approach. When it works, students exclaim It works! and move on. Sadly, this phrase is also the shortest lie in computing, and it has cost many people many hours of their lives. In contrast, this book focuses on habits of good programming , addressing both professional and vocational programmers.

With good programming, we mean an approach to the creation of software that relies on systematic thought, planning, and understanding from the very beginning, at every stage and for every step. To emphasize the point, we speak of systematic program design and systematically designed programs . Critically, the latter articulates the rationale of the desired functionality. Good programming also satisfies an aesthetic sense of accomplishment; the elegance of a good program is comparable to time-tested poems or the black-and-white photographs of a bygone era. In short, programming differs from good programming like crayon sketches in a diner from oil paintings in a museum.

everyone can design programs

everyone can experience the satisfaction that comes with creative design.

program designbut not programming deserves the same rolein a liberal-arts education as mathematics and language skills.

A program interacts with people, dubbed users , and each other, in which case we often speak of server and client components. Hence any reasonably complete program consists of many building blocks: some deal with input, some create output, some bridge the gap between those two. We choose to use functions as fundamental building blocks, because everyone encounters functions in pre-algebra and because the simplest programs are just such functions. The key is to discover which functions are needed, how to connect them, and how to build them from basic ingredients.

In this context, systematic program design refers to a mix of two concepts: design recipes and iterative refinement. We drewinspiration from Michael Jacksons method for creating COBOL programs plusconversations with Daniel Friedman on recursion, Robert Harper on typetheory, and Daniel Jackson on software design. The design recipes are a creation of the authors; and here, they enable the use of the latter.

1. From Problem Analysis to Data Definitions

   Identify the information that must be represented and how it isrepresented in the chosen programming language. Formulate data definitionsand illustrate them with examples.

2. Signature, Purpose Statement, Header

   State which data the desired function consumes andproduces. Articulate what the function computes as a conciseone-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 the data definitions into an outline of the function.

5. Function Definition

   Fill in the gaps in the function template. Exploit the purposestatement and the examples.

6. Testing

   Articulate the examples as tests and ensure that the functionpasses all. Doing so discovers mistakes and also helps others read andunderstand the definition when the need arisesand it will arise for anyserious program.

Figure 1: The basic steps of a function design recipe

Design Recipes apply to both complete programs and individual functions. This book deals with just two recipes for complete programs: one for programs with graphical user interface (GUI) and one for batch programs. In contrast, design recipes for functions come in a wide variety of flavors: for atomic forms of data such as numbers; for enumerations of different kinds of data; for data that compounds other data in a fixed manner; for finite but arbitrarily large data; and so on.

The function-level design recipes share a common designprocess . on one side of an index card. Whenstudents are stuck, ask them to produce their card and point them to thestep where they are stuck. For the chosen data representation in step 1, writing down examples proves how real-world information is encoded as data and how data is interpreted as information. Step 3 says that a problem-solver must work through concrete scenarios to gain an understanding of what the desired function is expected to compute for specific examples. This understanding is exploited in step 5, when it is time to define the function. Finally, step 6 demands that examples are turned into automated test code, which ensures that the function works properly for some cases. Running the function on real-world data may reveal other discrepancies between expectations and results.

Each step of the design process comes with pointed questions. For certain stepssay, the creation of the functional examples or the templatethe questions may appeal to the data definition. The answers almost automatically create an intermediate product. Instructors The most important questions arethose for steps 4 and 5. Ask students to write down these questions intheir own words on the back of their index card. This scaffolding pays off when it comes time to take the one creative step in the process: the completion of the function definition. And even then, help is available in almost all cases.

The novelty of this approach is the creation of intermediate products for beginner-level programs. When a novice is stuck, an expert or an instructor can inspect the existing intermediate products. The inspection is likely to use the generic questions from the design process and thus drive the novice to correct himself or herself. And this self-empowering process is the key difference between programming and program design.