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

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

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

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 Case

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

Advanced Recursion

Example: Sort

Example: From-Binary

Example: Mergesort

Example: Subsets

Pitfalls

Projects: 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

Functions That Take Variable Numbers of Arguments

Recursion on Arbitary 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

Implementing the Database Program Commands

Additions to the Program

Extra Work for Hotshots

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

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