How to Design Programs: An Introduction to Programming and Computing

Citation

Felleisen, M., Findler, R. B., Flatt, M., & Krishnamurthi, S. (2018). How to Design Programs: An Introduction to Programming and Computing (2nd ed.). The MIT Press. Free official edition: https://htdp.org/

Chapter Summary

Prologue: How to Program

The prologue gets readers programming immediately in DrRacket: arithmetic on numbers, strings and images, then a small animation of a rocket landing, built up through several versions of one program. Its final section ("Not!") explains why this kind of quick, unplanned programming does not scale and sets up the book's alternative, systematic program design.

Chapters 1–2: Arithmetic; Functions and Programs

Part I, "Fixed-Size Data", begins with expressions over numbers, strings, images and Booleans, and predicates that test what kind of data a value is. Chapter 2 introduces function definitions, computing by substitution, composition of functions, global constants, and the two kinds of complete program the book uses: batch programs and interactive "world" programs built with big-bang.

Chapter 3: How to Design Programs

This is the core chapter of the book. It presents the design recipe for functions in six steps: data definitions, signature with purpose statement and header, functional examples, template, definition, and testing. It then scales the recipe up to whole programs, emphasizes the role of domain knowledge and testing with check-expect, and shows how to design world programs, using virtual pets as running examples.

Chapters 4–7: Intervals, Enumerations, and Itemizations; Adding Structure; Itemizations and Structures; Summary

These chapters extend the recipe to richer data. Chapter 4 covers conditionals and the data definitions they mirror (enumerations, intervals, itemizations), finishing with finite-state worlds such as a traffic light. Chapter 5 introduces structures, starting from posn, then structure type definitions, "the universe of data", designing with structures, and a graphical text editor. Chapter 6 combines itemizations and structures, checks inputs for errors, and discusses equality predicates. Chapter 7 summarizes the part: good programmers design rather than tinker, and the recipe has a process dimension and a data dimension.

Intermezzo 1: Beginning Student Language

The first intermezzo gives a precise account of the teaching language BSL: its vocabulary, grammar and meaning, evaluation as a sequence of algebraic steps, error messages, Boolean expressions, constant and structure definitions, and tests.

Chapters 8–10: Lists; Designing with Self-Referential Data Definitions; More on Lists

Part II, "Arbitrarily Large Data", introduces lists built from '() and cons and shows how self-referential data definitions lead to recursive functions whose templates follow the data. Chapter 9 adds non-empty lists, natural numbers as recursive data, nested "Russian doll" structures and lists inside world programs. Chapter 10 covers functions that produce lists, structures inside lists, lists of lists (read from files) and a revisited graphical editor.

Chapters 11–13: Design by Composition; Projects: Lists; Summary

Chapter 11 teaches decomposing a problem into auxiliary functions and composing them, including auxiliary functions that recur and that generalize. Chapter 12 offers larger projects: dictionaries, an iTunes library, word games, a worm game, simplified Tetris, a space-war game and finite-state machines. The summary stresses refining the recipe for self-references and writing "wish lists" with the needed data definitions.

Intermezzo 2: Quote, Unquote

A short intermezzo introduces quotation, quasiquotation, unquote and splicing as a compact notation for large pieces of data, together with symbols.

Chapters 14–15: Similarities Everywhere; Designing Abstractions

Part III, "Abstraction", starts by noticing that many functions from Part II look alike. Chapter 14 abstracts over similar functions and data definitions and shows that functions are values. Chapter 15 gives a design recipe for abstractions: abstracting from examples, generalizing signatures, creating a single point of control, and abstracting from templates.

Chapters 16–18: Using Abstractions; Nameless Functions; Summary

Chapter 16 teaches how to use existing abstractions such as map, filter and foldr, introduces local definitions and the extra expressive power they bring, and works through examples and projects. Chapter 17 introduces lambda for nameless functions and uses it to abstract, specify and even represent data. The summary presents abstraction as both creating and using reusable code.

Intermezzo 3: Scope and Abstraction

This intermezzo defines lexical scope, binding and bound occurrences of variables, and then introduces two further abstraction mechanisms: for loops in the Intermediate Student Language and pattern matching.

Chapters 19–20: The Poetry of S-expressions; Iterative Refinement

Part IV, "Intertwined Data", deals with data defined by several mutually referential definitions: trees, forests and S-expressions, with a project on binary search trees and a section on simplifying functions. Chapter 20 introduces iterative refinement explicitly, through a model of a computer's file system refined over several versions.

Chapters 21–22: Refining Interpreters; Project: The Commerce of XML

Chapter 21 designs, by iterative refinement, an interpreter for a small language of expressions, variables and functions, the heart of DrRacket's interactions area. Chapter 22 represents XML as S-expressions, renders XML enumerations, discusses domain-specific languages and reads XML data.

Chapters 23–24: Simultaneous Processing; Summary

Chapter 23 shows how to design functions that consume two complex inputs, distinguishing three cases (treating one input as atomic, processing both in lockstep, and handling all combinations with a two-dimensional table), and ends with a database project. The summary states that the design recipe scales to all forms of structural data.

Intermezzo 4: The Nature of Numbers

This intermezzo explains fixed-size number representations, overflow and underflow, and how the teaching languages distinguish exact from inexact numbers.

Chapters 25–26: Non-standard Recursion; Designing Algorithms

Part V, "Generative Recursion", introduces recursion that does not follow the structure of the data, such as splitting a problem into newly generated subproblems. Chapter 26 adapts the design recipe for such algorithms, with four new questions for the coding step, an explicit termination argument, and a comparison of structural and generative recursion.

Chapters 27–30: Variations on the Theme; Mathematical Examples; Algorithms that Backtrack; Summary

Examples of generative recursion include fractals, binary search and a glimpse of parsing (Chapter 27); Newton's method, numeric integration and a Gaussian elimination project (Chapter 28); and graph traversal with a backtracking project on the n queens puzzle (Chapter 29). The summary notes that most computer scientists call such functions algorithms and that they may not terminate on all inputs.

Intermezzo 5: The Cost of Computation

The last intermezzo explains why timing specific inputs says little, introduces abstract running time and the definition of "on the order of", and uses it to discuss why programs rely on predicates and selectors.

Chapters 31–34: The Loss of Knowledge; Designing Accumulator-Style Functions; More Uses of Accumulation; Summary

Part VI, "Accumulators", shows how structural and generative functions can "forget" knowledge as they recur, causing inefficiency or non-termination. It gives a recipe for recognizing the need for an accumulator, writing an accumulator statement and transforming functions into accumulator style, applied to trees, data representations and a mouse-driven graphical editor.

Epilogue: Moving On

The epilogue reviews computing and program design and suggests next steps: for future developers and computer scientists, a full language such as Racket, classes, objects and types; for everyone else, applying the design process in their own fields.

Key Concepts

Prologue and Chapters 1–3

• Design recipe: six steps (data definition; signature, purpose and header; examples; template; definition; tests) that lead from a problem statement to a tested function.
• Data definition: a statement of how real-world information is represented as data in the program, with examples.
• World program: an interactive program built with big-bang, a state, a rendering function and event handlers.

Chapters 4–7 and Intermezzo 1

• Itemization: a data definition listing distinct cases, mirrored by a cond with one clause per case in the template.
• Structure type: a programmer-defined compound data type with a constructor, selectors and a predicate.
• Algebraic model of computation: evaluating a BSL program by step-by-step substitution, as shown by DrRacket's stepper.

Chapters 8–13

• Self-referential data definition: a definition (such as a list) that refers to itself, leading to recursive functions.
• Template follows data: the shape of a function's code mirrors the shape of the data definition it processes.
• Wish list: a list of auxiliary functions, with signatures and purposes, to be designed later.

Chapters 14–18 and Intermezzo 3

• Abstraction: factoring out repeated code patterns into one function parameterized over the differences.
• Functions as values: passing and returning functions, the basis of map, filter, foldr and lambda.
• Lexical scope: the rule that each variable occurrence refers to a definition found by inspecting the program text.

Chapters 19–24

• Mutually referential data: several data definitions that refer to each other, requiring one template per definition.
• Iterative refinement: solving a simplified version of a problem first and then adding details step by step.

Chapters 25–30 and Intermezzo 5

• Generative recursion: recursion on newly generated subproblems based on an insight into the problem, rather than on the data's structure.
• Termination argument: an explanation of why a generative recursive function eventually stops, or a warning about inputs on which it does not.
• Abstract running time: measuring cost by the order of growth in the number of steps rather than by timing specific runs.

Chapters 31–34

• Accumulator: an extra parameter that carries knowledge gathered during a traversal.
• Accumulator statement: a description of what knowledge the accumulator represents, typically the difference between the original argument and the current one.

Critical Analysis

Strengths

• A teachable, explicit method. The six-step design recipe is presented in the preface as something students can copy onto an index card, and each part adds pointed questions for each step. Intermediate products (data definitions, examples, templates) make it possible for a stuck student or an instructor to see exactly where things went wrong.
• Data-driven progression. Each part introduces a new kind of data (fixed-size, arbitrarily large, intertwined) or a new design principle (abstraction, generative recursion, accumulators), and the recipe is extended accordingly, so the structure of the book itself teaches how program structure follows data.
• Teaching languages and environment designed for beginners. The sequence of teaching languages (BSL, BSL+, ISL, ISL+) gives error messages pitched at the learner's level, and DrRacket's stepper shows evaluation step by step. Interactive world programs with images give immediate visual feedback.
• Large exercise set with recurring themes. The online edition contains 528 numbered exercises, and themes such as virtual pets, a text editor and graphs return in several parts, which the preface describes as introducing iterative refinement "through the backdoor".

Limitations

• Not a mainstream language. The book teaches design in Racket-based teaching languages, not Python, Java or C; the preface argues this is deliberate, but students who need a particular industrial language must make the transition later, which the epilogue leaves to other books.
• Length and pace. With six parts, five intermezzos and over 500 exercises, the full book is long, and the preface itself proposes cutting it down for quarter and high-school courses. Readers looking for a quick introduction may find the early chapters slow.
• Limited coverage of state, objects and types. Mutation, classes and objects, and static types are largely deferred; the epilogue names them as next topics. Accumulator-style programming is shown functionally, and imperative loops are explicitly declared beyond scope.
• Prescriptive style. The insistence on following every step for even small functions can feel heavy to students with prior programming experience, though the authors argue that this discipline is the point.

Where It Fits in the Course

In this introductory programming list, How to Design Programs is an introductory book that focuses on method rather than a particular language. It contrasts with Matthes's Python Crash Course, which is generally described as a project-based introduction to Python, and with Downey's Think Python and Guttag's Introduction to Computation and Programming Using Python, which teach programming and computation in Python. Students who want a disciplined foundation in program design, testing and recursion can start with HtDP and then move to one of the Python books to transfer the recipe to a mainstream language, as the epilogue recommends.

Abelson and Sussman's Structure and Interpretation of Computer Programs shares the Lisp-family heritage and is generally regarded as more mathematically demanding; HtDP's preface positions itself as accessible to readers with only pre-algebra, so it is a sensible precursor. Kernighan and Ritchie's The C Programming Language addresses low-level programming and is best read after a first course.

How to Use This Book

The book is written for readers with no prior programming experience; the authors claim that pre-algebra is enough, and the free DrRacket environment is the only software needed. The preface addresses both independent readers and instructors.

Independent readers are asked to work through the whole book and to solve, or know how to solve, all the exercises. The preface also gives three shorter paths: a high-school course covering Parts I and II with a small game project; a college quarter covering Parts I, II, III and V with Intermezzos 1 and 3; and a college semester covering Parts I and II, then the parts of Part VI that do not depend on generative recursion, then Intermezzo 5 and the rest. In every path, Chapter 3 (the design recipe) is essential, and Chapters 8–9 and 14–16 are the foundations for recursion and abstraction.

Use the stepper to understand evaluation, write check-expect tests before definitions, and follow the template for each data definition rather than starting from a blank page. When stuck, return to the step of the recipe that failed, as the preface suggests instructors do with the index card.

Edition and Sources

This guide is based on the free online second edition at https://htdp.org/ (book text © 2014 MIT Press, online release dated 28 May 2026; print edition MIT Press 2018). It draws on the preface in full (including the design recipe, teaching languages, the plan of the parts, suggested course paths and differences from the first edition), the full table of contents, the prologue, the opening section and the summary chapter of each of the six parts, the opening sections of all five intermezzos, the epilogue, and selected sections in Parts I, IV and V.