How to Design Programs. An Introduction to Computing and Programming

Preface
Why Everyone Should Learn to Program
Design Recipes . . . . . . . . . . . . . .
The Choice of Scheme and DrScheme
The Parts of the Book
Acknowledgements .
I Processing Simple Forms of Data
1 Students, Teachers, and Computers
2 Numbers, Expressions, Simple Programs
2.1 Numbers and Arithmetic .
2.2 Variables and Programs
2.3 Word Problems . . .
2.4 Errors . . . . . . . . .
2.5 Designing Programs
3 Programs are Function Plus Variable Definitions
3.1 Composing Functions . . . . . . . . . . . .
3.2 Variable Definitions . . . . . . . . . . . . . .
3.3 Finger Exercises on Composing Functions .
4 Conditional Expressions and Functions
4.1 Booleans and Relations . . . . . . . .
4.2 Functions that Test Conditions . . .
4.3 Conditionals and Conditional Functions .
4.4 Designing Conditional Functions . . . . .
5 Symbolic Information 46
5.1 Finger Exercises with Symbols 49
6 Compound Data, Part 1: Structures 51
6.1 Structures . . . . . . . . . . . . . . . . . . . . 51
6.2 Extended Exercise: Drawing Simple Pictures 55
6.3 Structure Definitions . . . . . . . . . . . . 58
6.4 Data Definitions . . . . . . . . . . . . . . . . . 63
6.5 Designing Functions for Compound Data . . 65
6.6 Extended Exercise: Moving Circles and Rectangles . 72
6.7 Extended Exercise: Hangman . . . . . . . . . . . . . 76
7 The Varieties of Data 79
7.1 Mixing and Distinguishing Data 80
7.2 Designing Functions for Mixed Data 85
7.3 Composing Functions, Revisited . . 90
7.4 Extended Exercise: Moving Shapes . 93
7.5 Input Errors . . . . . . . . . . . . . . 94
Intermezzo 1: Syntax and Semantics 97
The Scheme Vocabulary 98
The SchemeGrammar . 98
The Meaning of Scheme 101
Errors . . . . . . . . . 105
Boolean Expressions 108
Variable Definitions . 109
Structure Definitions 111
II Processing Arbitrarily Large Data
9 Compound Data, Part 2: Lists
9.1 Lists . . . . . . . . . . . . .117
9.2 Data Definitions for Lists of Arbitrary Length . 122
9.3 Processing Lists of Arbitrary Length . . . . . . 125
9.4 Designing Functions for Self-Referential Data Definitions 128
9.5 More on Processing Simple Lists . . . . . . . . . . . . . . 131
10 More on Processing Lists
10.1 Functions that Produce Lists .
10.2 Lists that Contain Structures .
10.3 Extended Exercise: Moving Pictures
11 Natural Numbers
11.1 Defining Natural Numbers . . . . . . . . . . . . . . .
11.2 Processing Natural Numbers of Arbitrary Size . . . .
11.3 Extended Exercise: Creating Lists, Testing Functions .
11.4 Alternative Data Definitions for Natural Numbers
11.5 More on the Nature of Natural Numbers
12 Composing Functions, Revisited Again
12.1 Designing Complex Programs . . . . . . . . . . .
12.2 Recursive Auxiliary Functions . . . . . . . . . . .
12.3 Generalizing Problems, Generalizing Functions .
12.4 Extended Exercise: Rearranging Words . . . . .
Intermezzo 2: List Abbreviations
III More on Processing Arbitrarily Large Data
14 More Self-referential Data Definitions 189
14.1 Structures in Structures . . . . . . . 189
14.2 Extended Exercise: Binary Search Trees 199
14.3 Lists in Lists . . . . . . . . . . . . . . . . 204
14.4 Extended Exercise: Evaluating Scheme . 208
15 Mutually Referential Data Definitions 209
15.1 Lists of Structures, Lists in Structures . . . . . . . . . . . . . 210
15.2 Designing Functions for Mutually Referential Definitions . 217
15.3 Extended Exercise: More on Web Pages . . . . . . . . . . . 220
16 Development through Iterative Refinement 221
16.1 Data Analysis . . . . . . . . . . . . . . . 222
16.2 Defining Data Classes and Refining Them . 223
16.3 Refining Functions and Programs . . . . . . 227
17 Processing Two Complex Pieces of Data 228
17.1 Processing Two Lists Simultaneously: Case 1 229
17.2 Processing Two Lists Simultaneously: Case 2 231
17.3 Processing Two Lists Simultaneously: Case 3 235
17.4 Function Simplification . . . . . . . . . . . . . 240
17.5 Designing Functions that Consume Two Complex Inputs 242
17.6 Exercises on Processing Two Complex Inputs . 243
17.7 Extended Exercise: Evaluating Scheme, Part 2 . 247
17.8 Equality and Testing . . . . . . . . . . . . . . . 249
Intermezzo 3: Local Definitions and Lexical Scope 259
Organizing Programs with local . 259
Lexical Scope and Block Structure . . . . . . . . . . . . 276
IV Abstracting Designs 283
19 Similarities in Definitions 283
19.1 Similarities in Functions 284
19.2 Similarities in Data Definitions 293
20 Functions are Values 299
20.1 Syntax and Semantics . . . . . . . . . . . . . . . . . . 299
20.2 Contracts for Abstract and Polymorphic Functions . 301
21 Designing Abstractions from Examples 306
21.1 Abstracting from Examples . . . . . . . . . . . 306
21.2 Finger Exercises with Abstract List Functions . 312
21.3 Abstraction and a Single Point of Control . . . 315
21.4 Extended Exercise: Moving Pictures, Again . . 316
21.5 Note: Designing Abstractions from Templates 318
22 Designing Abstractions with First-Class Functions 319
22.1 Functions that Produce Functions . . . . . . . . 319
22.2 Designing Abstractions with Functions-as-Values 321
22.3 A First Look at Graphical User Interfaces . . . . . 325
23 Mathematical Examples
23.1 Sequences and Series . . . . . . .
23.2 Arithmetic Sequences and Series
23.3 Geometric Sequences and Series
23.4 The Area Under a Function
23.5 The Slope of a Function . . . . . .
Intermezzo 4: Defining Functions on the Fly
V Generative Recursion
25 A New Form of Recursion
25.1 Modeling a Ball on a Table .
25.2 Sorting Quickly . . . . . . .
26 Designing Algorithms
26.1 Termination . . . . . . . . . . . . . . . .
26.2 Structural versusGenerative Recursion
26.3 Making Choices . . . . . . . . . . . . . .
27 Variations on a Theme
27.1 Fractals . . . . . .
27.2 From Files to Lines, from Lists to Lists of Lists
27.3 Binary Search . . . . . . . . . . . . . . . .
27.4 Newton's Method . . . . . . . . . . . . . .
27.5 Extended Exercise: Gaussian Elimination
28 Algorithms that Backtrack
28.1 Traversing Graphs . . . . . . . . . . . . . .
28.2 Extended Exercise: Checking (on) Queens .
Intermezzo 5: The Cost of Computing and Vectors
Concrete Time, Abstract Time . . . .
The Definition of "on the Order of" .
A First Look at Vectors . . . . . . . .
VI Accumulating Knowledge
30 The Loss of Knowledge
30.1 A Problem with Structural Processing
30.2 A Problem withGenerative Recursion
31 Designing Accumulator-Style Functions
31.1 Recognizing the Need for an Accumulator
31.2 Accumulator-Style Functions . . . . . . . .
31.3 Transforming Functions into Accumulator-Style
32 More Uses of Accumulation
32.1 Extended Exercise: Accumulators on Trees
32.2 Extended Exercise: Missionaries and Cannibals .
32.3 Extended Exercise: Board Solitaire . . . . . . . .
Intermezzo 6: The Nature of Inexact Numbers
Fixed-size Number Arithmetic
Overflow . . . . . . . .
Underflow . . . . . . .
DrScheme's Numbers .
VII Changing the State of Variables
34 Memory for Functions
35 Assignment to Variables
35.1 Simple Assignments at Work
35.2 Sequencing Expression Evaluations .
35.3 Assignments and Functions
35.4 A First Useful Example . . . . .
36 Designing Functions with Memory
36.1 The Need for Memory . . . . .
36.2 Memory and State Variables . .
36.3 Functions that Initialize Memory
36.4 Functions that Change Memory .
37 Examples of Memory Usage
37.1 Initializing State . . . . . . . . . . . . .
37.2 State Changes from User Interactions .
37.3 State Changes from Recursion . . . .
37.4 Finger Exercises on State Changes .
37.5 Extended Exercise: Exploring Places
Intermezzo 7: The Final Syntax and Semantics
The Vocabulary of Advanced Scheme
The Grammar of Advanced Scheme
The Meaning of Advanced Scheme
Errors in Advanced Scheme . . . . .
VIII Changing Compound Values
39 Encapsulation
39.1 Abstracting with State Variables .
39.2 Practice with Encapsulation
40 Mutable Structures
40.1 Structures from Functions
40.2 Mutable Functional Structures .
40.3 Mutable Structures . . . . . . .
40.4 Mutable Vectors . . . . . . . . .
40.5 Changing Variables, Changing Structures
41 Designing Functions that Change Structures
41.1 Why Mutate Structures . . . . . . . . . . .
41.2 Structural Design Recipes and Mutation, Part 1 .
41.3 Structural Design Recipes and Mutation, Part 2 .
41.4 Extended Exercise: Moving Pictures, a Last Time .
42 Equality
42.1 Extensional Equality
42.2 Intensional Equality .
43 Changing Structures, Vectors, and Objects
43.1 More Practice with Vectors . . . . . . .
43.2 Collections of Structures with Cycles .
43.3 Backtracking with State . . . . . . . .
Epilogue
Computing .
Programming
Moving On . .
Index . . . 683