Simply Scheme - 2nd Edition: Introducing Computer Science

✍ Scribed by Brian Harvey, Matthew Wright

• Publisher: The MIT Press
• Year: 1999
• Tongue: English
• Leaves: 613
• Edition: 2
• Category: Library

✦ Synopsis

This lively introduction to computer science and computer programming in Scheme is for non-computer science majors with a strong interest in the subject and for computer science majors who lack prior programming experience. The text allows the student to experience the computer as a tool for expressing ideas, not as a frustrating set of mathematical obstacles. This goal is supported by the use of Scheme, a modern dialect of Lisp, designed to emphasize symbolic programming.

✦ Table of Contents

Title Page
Copyright Page
Table of Contents
Foreword
Preface
To the Instructor
Acknowledgements
I Introduction: Functions
1 Showing Off Scheme
Talking to Scheme
Exiting Scheme
More Examples
Example: Acronyms
Example: Pig Latin
Example: Ice Cream Choices
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
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
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
The Truth about Substitution
Let
Pitfalls
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
Project: Scoring Bridge Hands
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
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
Pitfalls
Project: Spelling Names of Huge Numbers
15 Advanced Recursion
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
V Abstraction
17 Lists
Selectors and Constructors
Programming with Lists
The Truth about Sentences
Higher-Order Functions
Other Primitives for Lists
Association Lists
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
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
Limitations of Our Spreadsheet
Spreadsheet Commands
Moving the Selection
Putting Values in Cells
Formulas
Displaying Formula Values
Loading Spreadsheet Commands from a File
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
Additions to the Program
Extra Work for Hotshots
VII Conclusion: Computer Science
26 What’s Next?
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
Loading Our Programs
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
C Scheme Initialization File
D GNU General Public License
Credits
Alphabetical Table of Scheme Primitives
Glossary
Index of Defined Procedures