How to Design Programs, 2e

by Felleisen, Findler, Flatt, Krishnamurthi

ISBN: 9780262344128 | Copyright 2018

Click here to preview

Instructor Requests

Digital Exam/Desk Copy Print Exam/Desk Copy Ancillaries
Tabs

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.

Expand/Collapse All
Contents (pg. v)
Preface (pg. xiii)
Systematic Program Design (pg. xiv)
DrRacket and the Teaching Languages (pg. xvi)
Skills that Transfer (pg. xviii)
This Book and Its Parts (pg. xix)
The Differences (pg. xxiii)
Prologue: How to Program (pg. 3)
Arithmetic and Arithmetic (pg. 7)
Inputs and Output (pg. 12)
Many Ways to Compute (pg. 18)
One Program, Many Definitions (pg. 22)
One More Definition (pg. 26)
You Are a Programmer Now (pg. 28)
Not! (pg. 30)
I. Fixed-Size Data (pg. 33)
1. Arithmetic (pg. 33)
1.1 The Arithmetic of Numbers (pg. 35)
1.2 The Arithmetic of Strings (pg. 37)
1.3 Mixing It Up (pg. 39)
1.4 The Arithmetic of Images (pg. 40)
1.5 The Arithmetic of Booleans (pg. 44)
1.6 Mixing It Up with Booleans (pg. 45)
1.7 Predicates: Know Thy Data (pg. 47)
2. Functions and Programs (pg. 49)
2.1 Functions (pg. 50)
2.2 Computing (pg. 54)
2.3 Composing Functions (pg. 58)
2.4 Global Constants (pg. 62)
2.5 Programs (pg. 64)
3. How to Design Programs (pg. 77)
3.1 Designing Functions (pg. 78)
3.2 Finger Exercises: Functions (pg. 86)
3.3 Domain Knowledge (pg. 86)
3.4 From Functions to Programs (pg. 87)
3.5 On Testing (pg. 88)
3.6 Designing World Programs (pg. 90)
3.7 Virtual Pet Worlds (pg. 100)
4. Intervals, Enumerations, and Itemizations (pg. 102)
4.1 Programming with Conditionals (pg. 103)
4.2 Computing Conditionally (pg. 105)
4.3 Enumerations (pg. 108)
4.4 Intervals (pg. 112)
4.5 Itemizations (pg. 118)
4.6 Designing with Itemizations (pg. 127)
4.7 Finite State Worlds (pg. 130)
5. Adding Structure (pg. 138)
5.1 From Positions to posn Structures (pg. 139)
5.2 Computing with posns (pg. 139)
5.3 Programming with posn (pg. 141)
5.4 Defining Structure Types (pg. 143)
5.5 Computing with Structures (pg. 148)
5.6 Programming with Structures (pg. 152)
5.7 The Universe of Data (pg. 161)
5.8 Designing with Structures (pg. 166)
5.9 Structure in the World (pg. 168)
5.10 A Graphical Editor (pg. 169)
5.11 More Virtual Pets (pg. 172)
6. Itemizations and Structures (pg. 174)
6.1 Designing with Itemizations, Again (pg. 174)
6.2 Mixing Up Worlds (pg. 188)
6.3 Input Errors (pg. 190)
6.4 Checking the World (pg. 196)
6.5 Equality Predicates (pg. 198)
7. Summary (pg. 200)
Intermezzo 1: Beginning Student Language (pg. 202)
II. Arbitrarily Large Data (pg. 231)
8. Lists (pg. 231)
8.1 Creating Lists (pg. 232)
8.2 What Is ' (), What Is cons (pg. 237)
8.3 Programming with Lists (pg. 239)
8.4 Computing with Lists (pg. 244)
9. Designing with Self-Referential Data Definitions (pg. 246)
9.1 Finger Exercises: Lists (pg. 254)
9.2 Non-empty Lists (pg. 257)
9.3 Natural Numbers (pg. 263)
9.4 Russian Dolls (pg. 268)
9.5 Lists and World (pg. 272)
9.6 A Note on Lists and Sets (pg. 278)
10. More on Lists (pg. 282)
10.1 Functions that Produce Lists (pg. 283)
10.2 Structures in Lists (pg. 286)
10.3 Lists in Lists, Files (pg. 291)
10.4 A Graphical Editor, Revisited (pg. 301)
11. Design by Composition (pg. 314)
11.1 The list Function (pg. 314)
11.2 Composing Functions (pg. 317)
11.3 Auxiliary Functions that Recur (pg. 318)
11.4 Auxiliary Functions that Generalize (pg. 326)
12. Projects: Lists (pg. 337)
12.1 Real-World Data: Dictionaries (pg. 337)
12.2 Real-World Data: iTunes (pg. 339)
12.3 Word Games, Composition Illustrated (pg. 345)
12.4 Word Games, the Heart of the Problem (pg. 350)
12.5 Feeding Worms (pg. 352)
12.6 Simple Tetris (pg. 356)
12.7 Full Space War (pg. 359)
12.8 Finite State Machines (pg. 360)
13. Summary (pg. 367)
Intermezzo 2: Quote, Unquote (pg. 369)
III. Abstraction (pg. 381)
14. Similarities Everywhere (pg. 382)
14.1 Similarities in Functions (pg. 382)
14.2 Different Similarities (pg. 384)
14.3 Similarities in Data Definitions (pg. 388)
14.4 Functions Are Values (pg. 392)
14.5 Computing with Functions (pg. 393)
15. Designing Abstractions (pg. 397)
15.1 Abstractions from Examples (pg. 397)
15.2 Similarities in Signatures (pg. 404)
15.3 Single Point of Control (pg. 409)
15.4 Abstractions from Templates (pg. 410)
16. Using Abstractions (pg. 411)
16.1 Existing Abstractions (pg. 413)
16.2 Local Definitions (pg. 416)
16.3 Local Definitions Add Expressive Power (pg. 421)
16.4 Computing with local (pg. 423)
16.5 Using Abstractions, by Example (pg. 428)
16.6 Designing with Abstractions (pg. 433)
16.7 Finger Exercises: Abstraction (pg. 436)
16.8 Projects: Abstraction (pg. 437)
17. Nameless Functions (pg. 439)
17.1 Functions from lambda (pg. 440)
17.2 Computing with lambda (pg. 443)
17.3 Abstracting with lambda (pg. 445)
17.4 Specifying with lambda (pg. 449)
17.5 Representing with lambda (pg. 457)
18. Summary (pg. 462)
Intermezzo 3: Scope and Abstraction (pg. 464)
IV. Intertwined Data (pg. 487)
19. The Poetry of S-expressions (pg. 487)
19.1 Trees (pg. 488)
19.2 Forests (pg. 497)
19.3 S-expressions (pg. 499)
19.4 Designing with Intertwined Data (pg. 506)
19.5 Project: BSTs (pg. 508)
19.6 Simplifying Functions (pg. 512)
20. Iterative Refinement (pg. 514)
20.1 Data Analysis (pg. 516)
20.2 Refining Data Definitions (pg. 517)
20.3 Refining Functions (pg. 520)
21. Refining Interpreters (pg. 522)
21.1 Interpreting Expressions (pg. 523)
21.2 Interpreting Variables (pg. 526)
21.3 Interpreting Functions (pg. 529)
21.4 Interpreting Everything (pg. 532)
22. Project: The Commerce of XML (pg. 533)
22.1 XML as S-expressions (pg. 534)
22.2 Rendering XML Enumerations (pg. 541)
22.3 Domain-Specific Languages (pg. 547)
22.4 Reading XML (pg. 552)
23. Simultaneous Processing (pg. 557)
23.1 Processing Two Lists Simultaneously: Case 1� (pg. 558)
23.2 Processing Two Lists Simultaneously: Case 2� (pg. 559)
23.3 Processing Two Lists Simultaneously: Case 3� (pg. 562)
23.4 Function Simplification (pg. 566)
23.5 Designing Functions that Consume Two Complex Inputs� (pg. 568)
23.6 Finger Exercises: Two Inputs (pg. 570)
23.7 Project: Database (pg. 574)
24. Summary (pg. 588)
Intermezzo 4: The Nature of Numbers (pg. 589)
V. Generative Recursion (pg. 603)
25. Non-standard Recursion (pg. 604)
25.1 Recursion without Structure (pg. 604)
25.2 Recursion that Ignores Structure (pg. 608)
26. Designing Algorithms (pg. 614)
26.1 Adapting the Design Recipe (pg. 615)
26.2 Termination (pg. 617)
26.3 Structural versus Generative Recursion (pg. 621)
26.4 Making Choices (pg. 622)
27. Variations on the Theme (pg. 627)
27.1 Fractals, a First Taste (pg. 628)
27.2 Binary Search (pg. 632)
27.3 A Glimpse at Parsing (pg. 638)
28. Mathematical Examples (pg. 643)
28.1 Newton’s Method (pg. 643)
28.2 Numeric Integration (pg. 647)
28.3 Project: Gaussian Elimination (pg. 655)
29. Algorithms that Backtrack (pg. 661)
29.1 Traversing Graphs (pg. 661)
29.2 Project: Backtracking (pg. 671)
30. Summary (pg. 679)
Intermezzo 5: The Cost of Computation (pg. 680)
VI. Accumulators (pg. 695)
31. The Loss of Knowledge (pg. 696)
31.1 A Problem with Structural Processing (pg. 696)
31.2 A Problem with Generative Recursion (pg. 701)
32. Designing Accumulator-Style Functions (pg. 705)
32.1 Recognizing the Need for an Accumulator (pg. 706)
32.2 Adding Accumulators (pg. 708)
32.3 Transforming Functions into Accumulator Style& (pg. 711)
32.4 A Graphical Editor, with Mouse (pg. 725)
33. More Uses of Accumulation (pg. 727)
33.1 Accumulators and Trees (pg. 727)
33.2 Data Representations with Accumulators (pg. 734)
33.3 Accumulators as Results (pg. 740)
34. Summary (pg. 747)
Epilogue: Moving On (pg. 751)
Computing (pg. 751)
Program Design (pg. 752)
Onward, Developers and Computer Scientists (pg. 753)
Onward, Accountants, Journalists, Surgeons, and Everyone Else&# (pg. 754)
Index (pg. 757)

Matthias Felleisen

Matthias Felleisen is Trustee Professor of Computer Science at Northeastern University, recipient of the Karl V. Karlstrom Outstanding Educator Award, and co-author (with Daniel Friedman) of The Little Schemer and three other "Little" books published by the MIT Press.


Robert Bruce Findler

Robert Bruce Findler is Associate Professor of Computer Science at Northwestern University.

Matthew Flatt

Matthew Flatt is Associate Professor in the School of Computing at the University of Utah.


Shriram Krishnamurthi

Shriram Krishnamurthi is Assistant Professor of Computer Science at Brown University.


eTextbook
Go paperless today! Available online anytime, nothing to download or install.

Features

  • Bookmarking
  • Note taking
  • Highlighting