# Simply Scheme:Introducing Computer Science

 Brian HarveyMatthew WrightUniversity of California, Berkeley MIT Press web page for Simply Scheme

by Hal Abelson

### Preface

• One Big Idea: Symbolic Programming
• Lisp and Radical Computer Science
• Who Should Read This Book
• How to Read This Book

### To the Instructor

• Lists and Sentences
• Sentences and Words
• Higher-Order Procedures, Lambda, and Recursion
• Mutators and Environments

### Acknowledgments

(Note: The links on the Part headings below point to the introductions to the major parts of the book, each introducing one "big idea." Each introduction is about a page of text.)

## Part I. Introduction: Functions

### 1. Showing Off Scheme

• Talking to Scheme
• Recovering from Typing Errors
• Exiting Scheme
• More Examples
• Example: Acronyms
• Example: Pig Latin
• Example: Ice Cream Choices
• Example: Combinations from a Set
• Example: Factorial
• Play with the Procedures

### 2. Functions

• Arithmetic
• Words
• Domain and Range
• More Types: Sentences and Booleans
• Our Favorite Type: Functions
• Play with It
• Thinking about What You've Done

## Part II. Composition of Functions

### 3. Expressions

• Little People
• Result Replacement
• Plumbing Diagrams
• Pitfalls

### 4. Defining Your Own Procedures

• How to Define a Procedure
• Special Forms
• Functions and Procedures
• Argument Names versus Argument Values
• Procedure as Generalization
• Composability
• The Substitution Model
• Pitfalls

### 5. Words and Sentences

• Selectors
• Constructors
• First-Class Words and Sentences
• Pitfalls

### 6. True and False

• Predicates
• Using Predicates
• `If` Is a Special Form
• So Are `And` and `Or`
• Everything That Isn't False Is True
• Decisions, Decisions, Decisions
• `If` Is Composable
• Pitfalls

### 7. Variables

• How Little People Do Variables
• Global and Local Variables
• `Let`
• Pitfalls

## Part III. Functions as Data

### 8. Higher-Order Functions

• `Every`
• A Pause for Reflection
• `Keep`
• `Accumulate`
• Combining Higher-Order Functions
• Choosing the Right Tool
• First-Class Functions and First-Class Sentences
• `Repeated`
• Pitfalls

### 9. Lambda

• Procedures That Return Procedures
• The Truth about `Define`
• The Truth about `Let`
• Name Conflicts
• Named and Unnamed Functions
• Pitfalls

### 10. Example: Tic-Tac-Toe

• A Warning
• Technical Terms in Tic-Tac-Toe
• Thinking about the Program Structure
• The First Step: Triples
• Finding the Triples
• Using `Every` with Two-Argument Procedures
• Can the Computer Win on This Move?
• If So, in Which Square?
• Second Verse, Same as the First
• Now the Strategy Gets Complicated
• Finding the Pivots
• Taking the Offensive
• Leftovers
• Complete Program Listing

## Part IV. Recursion

### 11. Introduction to Recursion

• A Separate Procedure for Each Length
• Use What You Have to Get What You Need
• Notice That They're All the Same
• Notice That They're Almost All the Same
• Base Cases and Recursive Calls
• Pig Latin
• Problems for You to Try
• Our Solutions
• Pitfalls

### 12. The Leap of Faith

• From the Combining Method to the Leap of Faith
• Example: `Reverse`
• The Leap of Faith
• The Base Case
• Example: `Factorial`
• Likely Guesses for Smaller Subproblems
• Example: `Downup`
• Example: `Evens`
• Simplifying Base Cases
• Pitfalls

### 13. How Recursion Works

• Little People and Recursion
• Tracing
• Pitfalls

### 14. Common Patterns in Recursive Procedures

• The `Every` Pattern
• The `Keep` Pattern
• The `Accumulate` Pattern
• Combining Patterns
• Helper Procedures
• How to Use Recursive Patterns
• Problems That Don't Follow Patterns
• Pitfalls

### Project: Spelling Names of Huge Numbers

• Example: `Sort`
• Example: `From-Binary`
• Example: `Mergesort`
• Example: `Subsets`
• Pitfalls

### Project: Scoring Poker Hands

• Extra Work for Hotshots

### 16. Example: Pattern Matcher

• Problem Description
• Implementation: When Are Two Sentences Equal?
• When Are Two Sentences Nearly Equal?
• Matching with Alternatives
• Backtracking
• Matching Several Words
• Combining the Placeholders
• Naming the Matched Text
• The Final Version
• Abstract Data Types
• Backtracking and `Known-Values`
• How We Wrote It
• Complete Program Listing

## Part V. Abstraction

### 17. Lists

• Selectors and Constructors
• Programming with Lists
• Higher-Order Functions
• Other Primitives for Lists
• Association Lists
• Functions That Take Variable Numbers of Arguments
• Recursion on Arbitrary Structured Lists
• Pitfalls

### 18. Trees

• Example: The World
• How Big Is My Tree?
• Mutual Recursion
• Searching for a Datum in the Tree
• Locating a Datum in the Tree
• Representing Trees as Lists
• Abstract Data Types
• An Advanced Example: Parsing Arithmetic Expressions
• Pitfalls

### 19. Implementing Higher-Order Functions

• Generalizing Patterns
• The `Every` Pattern Revisited
• The Difference between `Map` and `Every`
• `Filter`
• `Accumulate` and `Reduce`
• Robustness
• Higher-Order Functions for Structured Lists
• The Zero-Trip Do Loop
• Pitfalls

## Part VI. Sequential Programming

### 20. Input and Output

• Printing
• Side Effects and Sequencing
• The `Begin` Special Form
• This Isn't Functional Programming
• Not Moving to the Next Line
• Strings
• A Higher-Order Procedure for Sequencing
• Tic-Tac-Toe Revisited
• Accepting User Input
• Aesthetic Board Display
• Reading and Writing Normal Text
• Formatted Text
• Sequential Programming and Order of Evaluation
• Pitfalls

### 21. Example: The `Functions` Program

• The Main Loop
• The Difference between a Procedure and Its Name
• The Association List of Functions
• Domain Checking
• Intentionally Confusing a Function with Its Name
• More on Higher-Order Functions
• More Robustness
• Complete Program Listing

### 22. Files

• Ports
• Writing Files for People to Read
• Using a File as a Database
• Transforming the Lines of a File
• Justifying Text
• Preserving Spacing of Text from Files
• Merging Two Files
• Writing Files for Scheme to Read
• Pitfalls

### 23. Vectors

• The Indy 500
• Vectors
• Using Vectors in Programs
• Non-Functional Procedures and State
• Shuffling a Deck
• More Vector Tools
• The Vector Pattern of Recursion
• Vectors versus Lists
• State, Sequence, and Effects
• Pitfalls

### 24. Example: A Spreadsheet Program

• Moving the Selection
• Putting Values in Cells
• Formulas
• Displaying Formula Values
• Application Programs and Abstraction

### 25. Implementing the Spreadsheet Program

• Cells, Cell Names, and Cell IDs
• The Command Processor
• Cell Selection Commands
• The `Load` Command
• The `Put` Command
• The Formula Translator
• The Dependency Manager
• The Expression Evaluator
• The Screen Printer
• The Cell Manager
• Complete Program Listing

### Project: A Database Program

• A Sample Session with Our Database
• How Databases Are Stored Internally
• The Current Database
• Implementing the Database Program Commands
• Extra Work for Hotshots

## Part VII. Conclusion: Computer Science

### 26. What's Next?

• The Best Computer Science Book
• Beyond SICP
• Standard Scheme
• Last Words

## Appendices

### A. Running Scheme

• The Program Development Cycle
• Integrated Editing
• Getting Our Programs
• Tuning Our Programs for Your System
• Versions of Scheme
• Scheme Standards

### B. Common Lisp

• Why Common Lisp Exists
• Defining Procedures and Variables
• The Naming Convention for Predicates
• No Words or Sentences
• True and False
• Files
• Arrays
• Equivalents to Scheme Primitives
• A Separate Name Space for Procedures
• `Lambda`
• More about `Function`
• Writing Higher-Order Procedures

### General Index

Brian Harvey, `bh@cs.berkeley.edu`

Matthew Wright, `matt@cnmat.berkeley.edu`