How to Design Programs: An Introduction to Programming and Computing, 2nd Edition

Contents......Page 5
Preface......Page 13
 Systematic Program Design......Page 14
 DrRacket and the Teaching Languages......Page 16
 Skills that Transfer......Page 18
 This Book and Its Parts......Page 19
 The Differences......Page 23
Prologue: How to Program......Page 29
 Arithmetic and Arithmetic......Page 33
 Inputs and Output......Page 38
 Many Ways to Compute......Page 44
 One Program, Many Definitions......Page 48
 One More Definition......Page 52
 You Are a Programmer Now......Page 54
 Not!......Page 56
 1. Arithmetic......Page 59
  1.1 The Arithmetic of Numbers......Page 61
  1.2 The Arithmetic of Strings......Page 63
  1.3 Mixing It Up......Page 65
  1.4 The Arithmetic of Images......Page 66
  1.5 The Arithmetic of Booleans......Page 70
  1.6 Mixing It Up with Booleans......Page 71
  1.7 Predicates: Know Thy Data......Page 73
 2. Functions and Programs......Page 75
  2.1 Functions......Page 76
  2.2 Computing......Page 80
  2.3 Composing Functions......Page 84
  2.4 Global Constants......Page 88
  2.5 Programs......Page 90
 3. How to Design Programs......Page 103
  3.1 Designing Functions......Page 104
  3.3 Domain Knowledge......Page 112
  3.4 From Functions to Programs......Page 113
  3.5 On Testing......Page 114
  3.6 Designing World Programs......Page 116
  3.7 Virtual Pet Worlds......Page 126
 4. Intervals, Enumerations, and Itemizations......Page 128
  4.1 Programming with Conditionals......Page 129
  4.2 Computing Conditionally......Page 131
  4.3 Enumerations......Page 134
  4.4 Intervals......Page 138
  4.5 Itemizations......Page 144
  4.6 Designing with Itemizations......Page 153
  4.7 Finite State Worlds......Page 156
 5. Adding Structure......Page 164
  5.2 Computing with posns......Page 165
  5.3 Programming with posn......Page 167
  5.4 Defining Structure Types......Page 169
  5.5 Computing with Structures......Page 174
  5.6 Programming with Structures......Page 178
  5.7 The Universe of Data......Page 187
  5.8 Designing with Structures......Page 192
  5.9 Structure in the World......Page 194
  5.10 A Graphical Editor......Page 195
  5.11 More Virtual Pets......Page 198
  6.1 Designing with Itemizations, Again......Page 200
  6.2 Mixing Up Worlds......Page 214
  6.3 Input Errors......Page 216
  6.4 Checking the World......Page 222
  6.5 Equality Predicates......Page 224
 7. Summary......Page 226
Intermezzo 1: Beginning Student Language......Page 228
 8. Lists......Page 257
  8.1 Creating Lists......Page 258
  8.2 What Is \' (), What Is cons......Page 263
  8.3 Programming with Lists......Page 265
  8.4 Computing with Lists......Page 270
 9. Designing with Self-Referential Data Definitions......Page 272
  9.1 Finger Exercises: Lists......Page 280
  9.2 Non-empty Lists......Page 283
  9.3 Natural Numbers......Page 289
  9.4 Russian Dolls......Page 294
  9.5 Lists and World......Page 298
  9.6 A Note on Lists and Sets......Page 304
 10. More on Lists......Page 308
  10.1 Functions that Produce Lists......Page 309
  10.2 Structures in Lists......Page 312
  10.3 Lists in Lists, Files......Page 317
  10.4 A Graphical Editor, Revisited......Page 327
  11.1 The list Function......Page 340
  11.2 Composing Functions......Page 343
  11.3 Auxiliary Functions that Recur......Page 344
  11.4 Auxiliary Functions that Generalize......Page 352
  12.1 Real-World Data: Dictionaries......Page 363
  12.2 Real-World Data: iTunes......Page 365
  12.3 Word Games, Composition Illustrated......Page 371
  12.4 Word Games, the Heart of the Problem......Page 376
  12.5 Feeding Worms......Page 378
  12.6 Simple Tetris......Page 382
  12.7 Full Space War......Page 385
  12.8 Finite State Machines......Page 386
 13. Summary......Page 393
Intermezzo 2: Quote, Unquote......Page 395
III. Abstraction......Page 407
  14.1 Similarities in Functions......Page 408
  14.2 Different Similarities......Page 410
  14.3 Similarities in Data Definitions......Page 414
  14.4 Functions Are Values......Page 418
  14.5 Computing with Functions......Page 419
  15.1 Abstractions from Examples......Page 423
  15.2 Similarities in Signatures......Page 430
  15.3 Single Point of Control......Page 435
  15.4 Abstractions from Templates......Page 436
 16. Using Abstractions......Page 437
  16.1 Existing Abstractions......Page 439
  16.2 Local Definitions......Page 442
  16.3 Local Definitions Add Expressive Power......Page 447
  16.4 Computing with local......Page 449
  16.5 Using Abstractions, by Example......Page 454
  16.6 Designing with Abstractions......Page 459
  16.7 Finger Exercises: Abstraction......Page 462
  16.8 Projects: Abstraction......Page 463
 17. Nameless Functions......Page 465
  17.1 Functions from lambda......Page 466
  17.2 Computing with lambda......Page 469
  17.3 Abstracting with lambda......Page 471
  17.4 Specifying with lambda......Page 475
  17.5 Representing with lambda......Page 483
 18. Summary......Page 488
Intermezzo 3: Scope and Abstraction......Page 490
 19. The Poetry of S-expressions......Page 513
  19.1 Trees......Page 514
  19.2 Forests......Page 523
  19.3 S-expressions......Page 525
  19.4 Designing with Intertwined Data......Page 532
  19.5 Project: BSTs......Page 534
  19.6 Simplifying Functions......Page 538
 20. Iterative Refinement......Page 540
  20.1 Data Analysis......Page 542
  20.2 Refining Data Definitions......Page 543
  20.3 Refining Functions......Page 546
 21. Refining Interpreters......Page 548
  21.1 Interpreting Expressions......Page 549
  21.2 Interpreting Variables......Page 552
  21.3 Interpreting Functions......Page 555
  21.4 Interpreting Everything......Page 558
 22. Project: The Commerce of XML......Page 559
  22.1 XML as S-expressions......Page 560
  22.2 Rendering XML Enumerations......Page 567
  22.3 Domain-Specific Languages......Page 573
  22.4 Reading XML......Page 578
 23. Simultaneous Processing......Page 583
  23.1 Processing Two Lists Simultaneously: Case 1......Page 584
  23.2 Processing Two Lists Simultaneously: Case 2......Page 585
  23.3 Processing Two Lists Simultaneously: Case 3......Page 588
  23.4 Function Simplification......Page 592
  23.5 Designing Functions that Consume Two Complex Inputs......Page 594
  23.6 Finger Exercises: Two Inputs......Page 596
  23.7 Project: Database......Page 600
 24. Summary......Page 614
Intermezzo 4: The Nature of Numbers......Page 615
V. Generative Recursion......Page 629
  25.1 Recursion without Structure......Page 630
  25.2 Recursion that Ignores Structure......Page 634
 26. Designing Algorithms......Page 640
  26.1 Adapting the Design Recipe......Page 641
  26.2 Termination......Page 643
  26.3 Structural versus Generative Recursion......Page 647
  26.4 Making Choices......Page 648
 27. Variations on the Theme......Page 653
  27.1 Fractals, a First Taste......Page 654
  27.2 Binary Search......Page 658
  27.3 A Glimpse at Parsing......Page 664
  28.1 Newton’s Method......Page 669
  28.2 Numeric Integration......Page 673
  28.3 Project: Gaussian Elimination......Page 681
  29.1 Traversing Graphs......Page 687
  29.2 Project: Backtracking......Page 697
 30. Summary......Page 705
Intermezzo 5: The Cost of Computation......Page 706
VI. Accumulators......Page 721
  31.1 A Problem with Structural Processing......Page 722
  31.2 A Problem with Generative Recursion......Page 727
 32. Designing Accumulator-Style Functions......Page 731
  32.1 Recognizing the Need for an Accumulator......Page 732
  32.2 Adding Accumulators......Page 734
  32.3 Transforming Functions into Accumulator Style......Page 737
  32.4 A Graphical Editor, with Mouse......Page 751
  33.1 Accumulators and Trees......Page 753
  33.2 Data Representations with Accumulators......Page 760
  33.3 Accumulators as Results......Page 766
 34. Summary......Page 773
 Computing......Page 777
 Program Design......Page 778
 Onward, Developers and Computer Scientists......Page 779
 Onward, Accountants, Journalists, Surgeons, and Everyone Else......Page 780
Index......Page 783