Each name of a part, chapter, or appendix is a link to a description of that portion of the book.
| Preface | ix | |
|---|---|---|
| Part I: Procedural Abstraction | 1 | |
| 1 | Computer Science and Programming | 3 |
| 1.1 | What's It All About? | 3 |
| 1.2 | Programming in Scheme | 5 |
| Sidebar: Responsible Computer Use | 5 | |
| 1.3 | An Application: Quilting | 15 |
| 2 | Recursion and Induction | 22 |
| 2.1 | Recursion | 22 |
| Sidebar: Exponents | 28 | |
| 2.2 | Induction | 28 |
| 2.3 | Further Examples | 34 |
| 2.4 | An Application: Custom-Sized Quilts | 40 |
| 3 | Iteration and invariants | 48 |
| 3.1 | Iteration | 48 |
| 3.2 | Using Invariants | 54 |
| 3.3 | Perfect Numbers, Internal Definitions, and Let | 58 |
| 3.4 | Iterative Improvement: Approximating the Golden Ratio | 61 |
| 3.5 | An Application: The Josephus Problem | 65 |
| 4 | Orders of Growth and Tree Recursion | 75 |
| 4.1 | Orders of Growth | 75 |
| Sidebar: Logarithms | 82 | |
| 4.2 | Tree Recursion and Digital Signatures | 83 |
| Sidebar: Modular Arithmetic | 87 | |
| 4.3 | An Application: Fractal Curves | 95 |
| 5 | Higher-Order Procedures | 109 |
| 5.1 | Procedural Parameters | 109 |
| 5.2 | Uncomputability | 113 |
| Sidebar: Alan Turing | 116 | |
| 5.3 | Procedures That Make Procedures | 118 |
| 5.4 | An Application: Verifying ID Numbers | 120 |
| Part II: Data Abstraction | 131 | |
| 6 | Compound Data and Data Abstraction | 133 |
| 6.1 | Introduction | 133 |
| 6.2 | Nim | 135 |
| 6.3 | Representations and Implementations | 143 |
| 6.4 | Three-Pile Nim | 153 |
| 6.5 | An Application: Adding Strategies to Nim | 156 |
| Sidebar: Type Checking | 157 | |
| 7 | Lists | 167 |
| 7.1 | The Definition of a List | 167 |
| 7.2 | Constructing Lists | 169 |
| 7.3 | Basic List Processing Techniques | 172 |
| 7.4 | List Processing and Iteration | 179 |
| 7.5 | Tree Recursion and Lists | 182 |
| 7.6 | An Application: A Movie Query System | 187 |
| Sidebar: Is There More to Intelligence Than the Appearance of Intelligence? | 202 | |
| 8 | Trees | 212 |
| 8.1 | Binary Search Trees | 212 |
| 8.2 | Efficiency Issues with Binary Search Trees | 220 |
| Sidebar: Privacy Issues | 225 | |
| 8.3 | Expression Trees | 226 |
| 8.4 | An Application: Automated Phone Books | 229 |
| 9 | Generic Operations | 243 |
| 9.1 | Introduction | 243 |
| 9.2 | Multiple Representations | 244 |
| 9.3 | Exploiting Commonality | 253 |
| 9.4 | An Application: Computer Graphics | 262 |
| 10 | Implementing Programming Languages | 278 |
| 10.1 | Introduction | 278 |
| 10.2 | Syntax | 279 |
| Sidebar: The Expressiveness of EBNF | 285 | |
| 10.3 | Micro-Scheme | 289 |
| 10.4 | Global Definitions: Mini-Scheme | 303 |
| 10.5 | An Application: Adding Explanatory Output | 311 |
| Part III: Abstractions of State | 331 | |
| 11 | Computers with Memory | 333 |
| 11.1 | Introduction | 333 |
| 11.2 | An Example Computer Architecture | 333 |
| 11.3 | Programming the SLIM | 340 |
| Sidebar: What Can Be Stored in a Location? | 342 | |
| 11.4 | Iteration in Assembly Language | 349 |
| 11.5 | Recursion in Assembly Language | 357 |
| 11.6 | Memory in Scheme: Vectors | 361 |
| 11.7 | An Application: A Simulator for SLIM | 367 |
| 12 | Dynamic Programming | 379 |
| 12.1 | Introduction | 379 |
| 12.2 | Revisiting Tree Recursion | 380 |
| 12.3 | Memoization | 388 |
| 12.4 | Dynamic Programming | 398 |
| 12.5 | Comparing Memoization and Dynamic Programming | 406 |
| 12.6 | An Application: Formatting Paragraphs | 406 |
| 13 | Object-Based Abstractions | 420 |
| 13.1 | Introduction | 420 |
| 13.2 | Arithmetic Expressions Revisited | 421 |
| 13.3 | RA-Stack Implementations and Representation Invariants | 432 |
| Sidebar: Strings and Characters | 433 | |
| 13.4 | Queues | 446 |
| 13.5 | Binary Search Trees Revisited | 453 |
| 13.6 | An Application: Dictionaries | 472 |
| 14 | Object-Oriented Programming | 486 |
| 14.1 | Introduction | 486 |
| 14.2 | An Object-Oriented Program | 487 |
| 14.3 | Extensions and Variations | 511 |
| 14.4 | Implementing an Object-Oriented Programming System | 517 |
| 14.5 | An Application: Adventures in the Land of Gack | 543 |
| 15 | Java, Applets, and Concurrency | 577 |
| 15.1 | Introduction | 577 |
| 15.2 | Java | 578 |
| 15.3 | Event-Driven Graphical User Interfaces in Applets | 599 |
| 15.4 | Concurrency | 616 |
| Sidebar: Nested Calls to Synchronized Methods and Deadlock | 625 | |
| 15.5 | An Application: Simulating Compound Interest | 632 |
| Appendix: Nonstandard Extensions to Scheme | 645 | |
| Bibliography | 649 | |
| Index | 653 | |