## Table of contents for How to design programs : an introduction to programming and computing / Matthias Felleisen ... [et al.].

Bibliographic record and links to related information available from the Library of Congress catalog. Note: Electronic data is machine generated. May be incomplete or contain other coding.

```

I Processing Simple Forms of Data                           3
1 Students, Teachers, and Computers                         3
2 Numbers, Expressions, Simple Programs                     5
2.1 Numbers and Arithmetic .........      ...........     5
2.2 Variables and Programs .....................          8
2.3 Word Problems ..    .......................          12
2.4  Errors  ........................................... 13
2.5 Designing Programs .......................           16
3 Programs are Function Plus Variable Definitions          21
3.1 Composing Functions .......     ...............      22
3.2  Variable Definitions .........................      26
3.3 Finger Exercises on Composing Functions ........... 27
4 Conditional Expressions and Functions                    29
4.1 Booleans and Relations .....................         29
4.2 Functions that Test Conditions  .................... 32
4.3 Conditionals and Conditional Functions ............  37
4.4 Designing Conditional Functions ................... 40

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 Scheme Grammar .......          ..................     98
The Meaning of Scheme ........................            101
Errors  ................................................. 105
Boolean Expressions  .........................            108
Variable Definitions  .....................                109
Structure Definitions  ..........................          111
II Processing Arbitrarily Large Data                         117
9 Compound Data, Part 2: Lists                               117
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                                 137
10.1 Functions that Produce Lists ...................... 138
10.2 Lists that Contain Structures ...................   143
10.3 Extended Exercise: Moving Pictures ............. .   151
11 Natural Numbers                                           153
11.1 Defining Natural Numbers ................... 153
11.2 Processing Natural Numbers of Arbitrary Size ........ 154
11.3 Extended Exercise: Creating Lists, Testing Functions ...... 158
11.4 Alternative Data Definitions for Natural Numbers ...... 160
11.5 More on the Nature of Natural Numbers ........... 166
12 Composing Functions, Revisited Again                     168
12.1 Designing Complex Programs .................. 169
12.2 Recursive Auxiliary Functions .... .............. 170
12.3 Generalizing Problems, Generalizing Functions ........ 176
12.4 Extended Exercise: Rearranging Words ............    180
Intermezzo 2: List Abbreviations                            183
III More on Processing Arbitrarily Large Data               189
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                                    334
23.1 Sequences and Series     ....................... 335
23.2 Arithmetic Sequences and Series ................... 337
23.3 Geometric Sequences and Series ............. 338
23.4 The Area Under a Function ........    ........... 342
23.5 The Slope of a Function . .................... 344
Intermezzo 4: Defining Functions on the Fly                 350
V   Generative Recursion                                    357
25 A New Form of Recursion                                  357
25.1 Modeling a Ball on a Table .......     ............ 358
25.2 Sorting Quickly ..  ....................... 362
26 Designing Algorithms                                     368
26.1 Termination        ........................ 370
26.2 Structural versus Generative Recursion ............ 374
26.3   Making Choices    ..........................      375
27 Variations on a Theme                                    381
27.1   Fractals  ........... ....................        381
27.2 From Files to Lines, from Lists to Lists of Lists ........ 386
27.3  Binary Search  .........  ..................       391
27.4 Newton's Method ................                   399
27.5 Extended Exercise: Gaussian Elimination  ....... .  401
28 Algorithms that Backtrack                                406
28.1 Traversing Graphs ........................ 407
28.2 Extended Exercise: Checking (on) Queens ........... 414
Intermezzo 5: The Cost of Computing and Vectors             417
Concrete Time, Abstract Time .......    .............. 417
The Definition of "on the Order of" ......... ........... 423
A First Look at Vectors ......................... 426

VI Accumulating Knowledge                                    441
30 The Loss of Knowledge                                     441
30.1 A Problem with Structural Processing ............ 441
30.2 A Problem with Generative Recursion ............. 445
31 Designing Accumulator-Style Functions                     450
31.1 Recognizing the Need for an Accumulator .......... 451
31.2 Accumulator-Style Functions ..................... 452
31.3 Transforming Functions into Accumulator-Style ....... 455
32 More Uses of Accumulation                                 466
32.1 Extended Exercise: Accumulators on Trees .......... 466
32.2 Extended Exercise: Missionaries and Cannibals ........ 472
32.3 Extended Exercise: Board Solitaire ........ .....  . 476
Intermezzo 6: The Nature of Inexact Numbers                  478
Fixed-size Number Arithmetic .................... 478
Overflow  .................................               484
Underflow  ................................               485
DrScheme's Numbers .......................... 486
VII Changing the State of Variables                          491
34 Memory for Functions                                      491
35 Assignment to Variables                                   496
35.1 Simple Assignments at Work .................. 496
35.2 Sequencing Expression Evaluations ........... ....   499
35.3 Assignments and Functions     ................... 501
35.4 A First Useful Example ..................            504
36 Designing Functions with Memory                           507
36.1 The Need for Memory ................... 508
36.2 Memory and State Variables   ................... 510
36.3 Functions that Initialize Memory ............... 512
36.4 Functions that Change Memory ................        513

37 Examples of Memory Usage                                 521
37.1   Initializing  State  ..........................   521
37.2 State Changes from User Interactions ...... .... .  524
37.3 State Changes from Recursion . .................. 535
37.4 Finger Exercises on State Changes ..........        542
37.5 Extended Exercise: Exploring Places  ........... ..544
Intermezzo 7: The Final Syntax and Semantics                548
The Vocabulary of Advanced Scheme     ...............    548
The Grammar of Advanced Scheme .....     ............ 548
The Meaning of Advanced Scheme .................. 551
Errors in Advanced Scheme ...................... 566
VIII Changing Compound Values                               573
39 Encapsulation                                            573
39.1 Abstracting with State Variables ................. 573
39.2 Practice with Encapsulation ... .................. 585
40 Mutable Structures                                       587
40.1 Structures from Functions    ................... 587
40.2 Mutable Functional Structures ................. 590
40.3  Mutable Structures  ........................       594
40.4 Mutable Vectors         ...................         601
40.5 Changing Variables, Changing Structures .......     603
41 Designing Functions that Change Structures               608
41.1 Why Mutate Structures ...........     ......... 608
41.2 Structural Design Recipes and Mutation, Part 1  .....  609
41.3 Structural Design Recipes and Mutation, Part 2  ......  622
41.4 Extended Exercise: Moving Pictures, a Last Time  .....  636
42 Equality                                                 637
42.1 Extensional Equality .................. 637
42.2 Intensional Equality .................. 638

43 Changing Structures, Vectors, and Objects               642
43.1 More Practice with Vectors ................ 642
43.2 Collections of Structures with Cycles .............. 660
43.3 Backtracking with State ..................... 672
Epilogue                                                   677
Computing  . ............................              677
Programming ............................                678
Moving On ......                          .680
Index                                                      683

```

Library of Congress subject headings for this publication: Computer programming, Electronic data processing