A completely revised edition, offering new design recipes for interactive programs and support for images as plain values, testing, event-driven programming, and even distributed programming.
This introduction to programming places computer science at the core of a liberal arts education. Unlike other introductory books, it focuses on the program design process, presenting program design guidelines that show the reader how to analyze a problem statement, how to formulate concise goals, how to make up examples, how to develop an outline of the solution, how to finish the program, and how to test it. Because learning to design programs is about the study of principles and the acquisition of transferable skills, the text does not use an off-the-shelf industrial language but presents a tailor-made teaching language. For the same reason, it offers DrRacket, a programming environment for novices that supports playful, feedback-oriented learning. The environment grows with readers as they master the material in the book until it supports a full-fledged language for the whole spectrum of programming tasks.
This second edition has been completely revised. While the book continues to teach a systematic approach to program design, the second edition introduces different design recipes for interactive programs with graphical interfaces and batch programs. It also enriches its design recipes for functions with numerous new hints. Finally, the teaching languages and their IDE now come with support for images as plain values, testing, event-driven programming, and even distributed programming.
Conditions of Use
This book is licensed under a Creative Commons License (CC BY-NC-SA). You can download the ebook How to Design Programs, 2nd Edition for free.
- Title
- How to Design Programs, 2nd Edition
- Subtitle
- An Introduction to Programming and Computing
- Publisher
- The MIT Press
- Author(s)
- Matthew Flatt, Matthias Felleisen, Robert Bruce Findler, Shriram Krishnamurthi
- Published
- 2023-08-14
- Edition
- 2
- Format
- eBook (pdf, epub, mobi)
- Pages
- 981
- Language
- English
- ISBN-10
- 0262534800
- ISBN-13
- 9780262534802
- License
- CC BY-NC-SA
- Book Homepage
- Free eBook, Errata, Code, Solutions, etc.
Title Page Copyright Contents Preface Systematic Program Design DrRacket and the Teaching Languages Skills that Transfer This Book and Its Parts The Differences 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 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.2. Non-empty Lists 9.3. Natural Numbers 9.4. Russian Dolls 9.5. Lists and World 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 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 IV. Intertwined Data 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 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 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 34. Summary Epilogue: Moving On Computing Program Design Onward, Developers and Computer Scientists Onward, Accountants, Journalists, Surgeons, and Everyone Else Index