On this page:
How to Design Programs, Second Edition

How to Design Programs, Second Edition

© 1 August 2014 MIT Press

This material is copyrighted and provided under the Creative Commons CC BY-NC-ND license [interpretation].

Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi

Do you notice the italics? Italicized words refer to technical terms. Here they refer to books on programming currently in bookstores.

Bad programming is easy. Even Dummies can learn it in 21 days.

Good programming requires thought, but everyone can do it and everyone can experience the extreme satisfaction that comes with it. The price is worth paying for the sheer joy of the discovery process, the elegance of the result, and the commercial benefits of a systematic program design process.

The goal of our book is to introduce readers of all ages and backgrounds to the craft of designing programs systematically. We assume few prerequisites: arithmetic, a tiny bit of middle school algebra, and the willingness to think through issues. We promise that the travails will pay off not just for future programmers but for anyone who has to follow a process or create one for others.

Draft Release

This document is the draft release of HtDP/2e. It is updated on a frequent basis. The stable version is released in conjunction with the PLT software and is thus more suitable for teaching than this draft.

Released on Tuesday, April 21st, 2015 2:48:08pm

How the Second Edition Differs from the First

This second edition of “How to Design Programs” differs from the first one in several aspects:

  1. 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, reactive (graphical) programs and so-called batch programs.Because graphical interactive programs are more interesting than batch programs, the book emphasizes the former over the latter.

  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 the 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 existed in the first edition, the second edition treats it as an explicit design element.

  3. The design of each wish on the wish list exploits the design recipe for functions. As in the first edition, the six parts focus on structural design, compositional design, generative recursion, and design of both structural and generative programs with accumulators.

  4. A key element of structural design is the definition of functions that compose others. This design-by-compositionWe thank Dr. Kathi Fisler for focusing our attention on this point. is especially useful for the world of batch programs. Like generative 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.

  5. While testing has always been a part of the “How to Design Programs” 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 now.

  6. This edition of the book drops the design of imperative programs. The old chapters remain available on-line. The material will flow 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.

  8. Finally, we decided to use a slightly different terminology:











We thank Ennas Abdussalam, Saad Bashir, Steven Belknap, Stephen Bloch, Elijah Botkin, Tomas Cabrera, Anthony Carrico, Rodolfo Carvalho, Estevo Castro, Stephen Chang, Nelson Chiu, Jack Clay, Richard Cleis, John Clements, Mark Engelberg, Christopher Felleisen, Sebastian Felleisen, Vladimir Gajić, Adrian German, Jack Gitelson, Kyle Gillette, Scott Greene, Ryan Golbeck, Josh Grams, Nadeem Abdul Hamid, Jeremy Hanlon, Craig Holbrook, Wayne Iba, Jordan Johnson, Blake Johnson, Erwin Junge, Gregor Kiczales, Eugene Kohlbecker, Caitlin Kramer, Jackson Lawler, Saad Mahmood, Jay McCarthy, Mike McHugh, Wade McReynolds, Elena Machkasova, David Moses, Ann E. Moskol, Scott Newson, Paul Ojanen, Prof. Robert Ordóñez, Laurent Orseau, Klaus Ostermann, Sinan Pehlivanoglu, Eric Parker, Nick Pleatsikas, Norman Ramsey, Krishnan Ravikumar, Jacob Rubin, Luis Sanjuán, Ryan “Havvy” Scheel, Lisa Scheuing, Willi Schiegel, Vinit Shah, Nick Shelley, Matthew Singer, Stephen Siegel, Joe Snikeris, Marc Smith, Dave Smylie, Vincent St-Amour, Reed Stevens, Kevin Sullivan, Éric Tanter, Sam Tobin-Hochstadt, Thanos Tsouanas, Mariska Twaalfhoven, Yuwang Yin, David Van Horn, Jan Vitek, Mitchell Wand, Michael Wijaya, G. Clifford Williams, Ewan Whittaker-Walker, Julia Wlochowski, Roelof Wobben and Mardin Yadegar, for comments on previous drafts of this second edition.

The HTML layout is due to Matthew Butternick who created these styles for the Racket documentation.

We are grateful to Ada Brunstein and Marie Lufkin Lee, our editors at MIT Press, who gave us permission to develop this second edition of "How to Design Programs" on-line.

    Prologue: How to Program

        Arithmetic and Arithmetic

        Inputs and Output

        Many Ways To Compute

        One Program, Many Definitions

        One More Definition

        You Are a Programmer Now


    I Fixed-Size Data

      1 Arithmetic

        1.1 The Arithmetic of Numbers

        1.2 The Arithmetic of Strings

        1.3 Mixing It Up

        1.4 The Arithmetic of Images

        1.5 The Arithmetic of Booleans

        1.6 Mixing It up with Booleans

        1.7 Predicates: Know Thy Data

      2 Functions And Programs

        2.1 Functions

        2.2 Composing Functions

        2.3 Global Constants

        2.4 Programs

      3 How to Design Programs

        3.1 Designing Functions

        3.2 Finger Exercises

        3.3 Domain Knowledge

        3.4 From Functions to Programs

        3.5 On Testing

        3.6 Designing World Programs

        3.7 Virtual Pet Worlds

      4 Intervals, Enumerations, Itemizations

        4.1 Programming with Conditionals

        4.2 How It Works

        4.3 Enumerations

        4.4 Intervals

        4.5 Itemizations

        4.6 Designing with Itemizations

        4.7 A Bit More about Worlds

      5 Adding Structure

        5.1 Structures

        5.2 Programming with Structures

        5.3 The Universe of Data

        5.4 Designing with Structures

        5.5 Structure in the World

        5.6 A Graphical Editor

        5.7 More Virtual Pets

      6 Itemizations and Structures

        6.1 Designing with Itemizations, Again

        6.2 Mixing up Worlds

        6.3 Input Errors

      7 Summary

    Intermezzo: BSL

        BSL: Vocabulary

        BSL: Grammar

        BSL: Meaning

        BSL: Errors

        Boolean Expressions

        Constant Definitions

        Structure Type Definitions

        BSL: Tests

    II Arbitrarily Large Data

      9 Lists

        9.1 Creating Lists

        9.2 What Is '(), What Is cons

        9.3 Programming with Lists

      10 Designing With Self-Referential Data Definitions

        10.1 Finger Exercises: Lists

        10.2 Non-empty Lists

        10.3 Natural Numbers

        10.4 Russian Dolls

        10.5 Lists and World

      11 More on Lists

        11.1 Functions that Produce Lists

        11.2 Structures in Lists

        11.3 Lists in Lists, Files

        11.4 A Graphical Editor, Revisited

      12 Design By Composition

        12.1 The list Function

        12.2 Composing Functions

        12.3 Recursive Auxiliary Functions

        12.4 Generalizing Functions

      13 Extended Exercises

        13.1 Word Games, Composition Illustrated

        13.2 Word Games, the Heart of the Problem

        13.3 Feeding Worms

        13.4 Simple Tetris

        13.5 Full Space War

        13.6 Finite State Machines

      14 Summary

    Intermezzo: Quote, Unquote


        Quasiquote And Unquote

        Unquote Splice

    III Abstraction

      16 Similarities Everywhere

        16.1 Similarities in Functions

        16.2 More Similarities in Functions

        16.3 Similarities in Data Definitions

        16.4 Functions Are Values

      17 Designing Abstractions

        17.1 Abstractions from Examples

        17.2 Similarities in Signatures

        17.3 Single Point of Control

        17.4 Abstractions from Templates

      18 Using Abstractions

        18.1 Existing Abstractions

        18.2 Local Function Definitions

        18.3 ... Add Expressive Power

        18.4 Using Abstractions, by Examples

        18.5 Designing with Abstractions

        18.6 Exercises and Projects

      19 Nameless Functions

        19.1 Functions from lambda

        19.2 lambda, Technically

        19.3 Abstracting with lambda

        19.4 Specifying with lambda

        19.5 Representing with lambda

      20 Summary

    Intermezzo: Scope and Abstraction


        For Loops

        Pattern Matching

    IV Intertwined Data

      22 The Poetry Of S-expressions

        22.1 Trees

        22.2 Forests

        22.3 S-expressions

        22.4 Designing With Intertwined Data

        22.5 Simplifying Functions

      23 Incremental Refinement

        23.1 Data Analysis

        23.2 Refining Data Definitions

        23.3 Refining Functions

      24 Refining Interpreters

        24.1 Interpreting Expressions

        24.2 Interpreting Variables

        24.3 Interpreting Functions

        24.4 Interpreting Everything

      25 The Commerce Of XML

        25.1 XML as S-expressions

        25.2 Rendering XML Enumerations

        25.3 Domain-Specific Languages

        25.4 Reading XML

      26 Simultaneous Processing

        26.1 Processing Two Lists Simultaneously: Case 1

        26.2 Processing Two Lists Simultaneously: Case 2

        26.3 Processing Two Lists Simultaneously: Case 3

        26.4 Function Simplification

        26.5 Designing Functions that Consume Two Complex Inputs

        26.6 Exercises on Processing Two Complex Inputs

      27 Summary

    Intermezzo: The Cost of Computation

    V Generative Recursion

      29 Non-standard Recursion

        29.1 Recursion without Structure

        29.2 Recursion that Ignores Structure

      30 Designing Algorithms

        30.1 Adapting the Design Recipe

        30.2 Termination

        30.3 Structural versus Generative Recursion

        30.4 Making Choices

      31 Variations on the Theme

        31.1 Fractals, a First Taste

        31.2 Binary Search

        31.3 A Glimpse at Parsing

      32 Mathematical Examples

        32.1 Newton’s Method

        32.2 Numeric Integration

        32.3 Extended Exercise: Gaussian Elimination

      33 Algorithms that Backtrack

        33.1 Traversing Graphs

        33.2 Extended Exercise: Checking (on) Queens

      34 Summary

    Intermezzo: The Nature of Numbers

        Fixed-size Number Arithmetic



        *SL Numbers

    VI Accumulators

      36 The Loss of Knowledge

        36.1 A Problem with Structural Processing

        36.2 A Problem with Generative Recursion

      37 Designing Accumulator-Style Functions

        37.1 Recognizing the Need for an Accumulator

        37.2 Adding Accumulators

        37.3 Transforming Functions into Accumulator-Style

        37.4 A Graphical Editor, with Mouse

      38 More Uses of Accumulation

        38.1 Accumulators and Trees

        38.2 Data Representations with Accumulators

        38.3 Accumulators as Results

      39 Summary

    Epilogue: How Not to Program