How to Design Programs, Second Edition

8.10.0.1

Please send reports about mistakes to authors @ htdp.org

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

Released on Monday, August 14th, 2023 6:15:39pm

Preface

Systematic Program Design

DrRacket and the Teaching Languages

Skills that Transfer

This Book and Its Parts

The Differences

Acknowledgments from the First Edition

Acknowledgments

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

Not!

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 Computing

2.3 Composing Functions

2.4 Global Constants

2.5 Programs

3 How to Design Programs

3.1 Designing Functions

3.2 Finger Exercises: Functions

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, and Itemizations

4.1 Programming with Conditionals

4.2 Computing Conditionally

4.3 Enumerations

4.4 Intervals

4.5 Itemizations

4.6 Designing with Itemizations

4.7 Finite State Worlds

5 Adding Structure

5.1 From Positions to posn Structures

5.2 Computing with posns

5.3 Programming with posn

5.4 Defining Structure Types

5.5 Computing with Structures

5.6 Programming with Structures

5.7 The Universe of Data

5.8 Designing with Structures

5.9 Structure in the World

5.10 A Graphical Editor

5.11 More Virtual Pets

6 Itemizations and Structures

6.1 Designing with Itemizations, Again

6.2 Mixing Up Worlds

6.3 Input Errors

6.4 Checking the World

6.5 Equality Predicates

7 Summary

Intermezzo 1: Beginning Student Language

BSL Vocabulary

BSL Grammar

BSL Meaning

Meaning and Computing

BSL Errors

Boolean Expressions

Constant Definitions

Structure Type Definitions

BSL Tests

BSL Error Messages

II Arbitrarily Large Data

8 Lists

8.1 Creating Lists

8.2 What Is '(), What Is cons

8.3 Programming with Lists

8.4 Computing with Lists

9 Designing with Self-Referential Data Definitions

9.1 Finger Exercises: Lists

9.6 A Note on Lists and Sets

10 More on Lists

10.1 Functions that Produce Lists

10.2 Structures in Lists

10.3 Lists in Lists, Files

10.4 A Graphical Editor, Revisited

11 Design by Composition

11.1 The list Function

11.2 Composing Functions

11.3 Auxiliary Functions that Recur

11.4 Auxiliary Functions that Generalize

12 Projects: Lists

12.1 Real-World Data: Dictionaries

12.2 Real-World Data: iTunes

12.3 Word Games, Composition Illustrated

12.4 Word Games, the Heart of the Problem

12.5 Feeding Worms

12.6 Simple Tetris

12.7 Full Space War

12.8 Finite State Machines

13 Summary

Intermezzo 2: Quote, Unquote

Quote

Quasiquote and Unquote

Unquote Splice

III Abstraction

14 Similarities Everywhere

14.1 Similarities in Functions

14.2 Different Similarities

14.3 Similarities in Data Definitions

14.4 Functions Are Values

14.5 Computing with Functions

15 Designing Abstractions

15.1 Abstractions from Examples

15.2 Similarities in Signatures

15.3 Single Point of Control

15.4 Abstractions from Templates

16 Using Abstractions

16.1 Existing Abstractions

16.2 Local Definitions

16.3 Local Definitions Add Expressive Power

16.4 Computing with local

16.5 Using Abstractions, by Example

16.6 Designing with Abstractions

16.7 Finger Exercises: Abstraction

16.8 Projects: Abstraction

17 Nameless Functions

17.1 Functions from lambda

17.2 Computing with lambda

17.3 Abstracting with lambda

17.4 Specifying with lambda

17.5 Representing with lambda

18 Summary

Intermezzo 3: Scope and Abstraction

19 The Poetry of S-expressions

19.1 Trees

19.2 Forests

19.3 S-expressions

19.4 Designing with Intertwined Data

19.5 Project: BSTs

19.6 Simplifying Functions

20 Iterative Refinement

20.1 Data Analysis

20.2 Refining Data Definitions

20.3 Refining Functions

21 Refining Interpreters

21.1 Interpreting Expressions

21.2 Interpreting Variables

21.3 Interpreting Functions

21.4 Interpreting Everything

22 Project: The Commerce of XML

22.1 XML as S-expressions

22.2 Rendering XML Enumerations

22.3 Domain-Specific Languages

22.4 Reading XML

23 Simultaneous Processing

23.1 Processing Two Lists Simultaneously: Case 1

23.2 Processing Two Lists Simultaneously: Case 2

23.3 Processing Two Lists Simultaneously: Case 3

23.4 Function Simplification

23.5 Designing Functions that Consume Two Complex Inputs

23.6 Finger Exercises: Two Inputs

23.7 Project: Database

24 Summary

Intermezzo 4: The Nature of Numbers

Fixed-Size Number Arithmetic

Overflow

Underflow

*SL Numbers

V Generative Recursion

25 Non-standard Recursion

25.1 Recursion without Structure

25.2 Recursion that Ignores Structure

26 Designing Algorithms

26.1 Adapting the Design Recipe

26.2 Termination

26.3 Structural versus Generative Recursion

26.4 Making Choices

27 Variations on the Theme

27.1 Fractals, a First Taste

27.2 Binary Search

27.3 A Glimpse at Parsing

28 Mathematical Examples

28.1 Newton’s Method

28.2 Numeric Integration

28.3 Project: Gaussian Elimination

29 Algorithms that Backtrack

29.1 Traversing Graphs

29.2 Project: Backtracking

30 Summary

Intermezzo 5: The Cost of Computation

Concrete Time, Abstract Time

The Definition of “On the Order Of”

Why Do Programs Use Predicates and Selectors?

VI Accumulators

31 The Loss of Knowledge

31.1 A Problem with Structural Processing

31.2 A Problem with Generative Recursion

32 Designing Accumulator-Style Functions

32.1 Recognizing the Need for an Accumulator

32.2 Adding Accumulators

32.3 Transforming Functions into Accumulator Style

32.4 A Graphical Editor, with Mouse

33 More Uses of Accumulation

33.1 Accumulators and Trees

33.2 Data Representations with Accumulators

33.3 Accumulators as Results

Onward, Developers and Computer Scientists

Onward, Accountants, Journalists, Surgeons, and Everyone Else