Felleisen Matthias, Findler Robert Bruce, Flat Matthew, Krishnamurthi Shriram. How to Design Programs. An Introduction to Computing and Programming

Boston: MIT Press, 2001. — 721 p.Why Everyone Should Learn to Program
Design Recipes
The Choice of Scheme and DrScheme
The Parts of the Book
Acknowledgements
Processing Simple Forms of Data
Students, Teachers, and Computers
Numbers, Expressions, Simple Programs
Numbers and Arithmetic
Variables and Programs
Word Problems
Errors
Designing Programs
Programs are Function Plus Variable Definitions
Composing Functions
Variable Definitions
Finger Exercises on Composing Functions
Conditional Expressions and Functions
Booleans and Relations
Functions that Test Conditions
Conditionals and Conditional Functions
Designing Conditional Functions
Symbolic Information
Finger Exercises with Symbols
Compound Data, Structures
Structures
Extended Exercise: Drawing Simple Pictures
Structure Definitions
Data Definitions
Designing Functions for Compound Data
Extended Exercise: Moving Circles and Rectangles
Extended Exercise: Hangman
The Varieties of Data
Mixing and Distinguishing Data
Designing Functions for Mixed Data
Composing Functions, Revisited
Extended Exercise: Moving Shapes
Input Errors
Intermezzo : Syntax and Semantics
The Scheme Vocabulary
The SchemeGrammar
The Meaning of Scheme
Errors
Boolean Expressions
Variable Definitions
Structure Definitions
Processing Arbitrarily Large Data
Compound Data, Part : Lists
Lists
Data Definitions for Lists of Arbitrary Length
Processing Lists of Arbitrary Length
Designing Functions for Self-Referential Data Definitions
More on Processing Simple Lists
More on Processing Lists
Functions that Produce Lists
Lists that Contain Structures
Extended Exercise: Moving Pictures
Natural Numbers
Defining Natural Numbers
Processing Natural Numbers of Arbitrary Size
Extended Exercise: Creating Lists, Testing Functions
Alternative Data Definitions for Natural Numbers
More on the Nature of Natural Numbers
Composing Functions, Revisited Again
Designing Complex Programs
Recursive Auxiliary Functions
Generalizing Problems, Generalizing Functions
Extended Exercise: Rearranging Words
Intermezzo : List Abbreviations
More on Processing Arbitrarily Large Data
More Self-referential Data Definitions
Structures in Structures
Extended Exercise: Binary Search Trees
Lists in Lists
Extended Exercise: Evaluating Scheme
Mutually Referential Data Definitions
Lists of Structures, Lists in Structures
Designing Functions for Mutually Referential Definitions
Extended Exercise: More on Web Pages
Development through Iterative Refinement
Data Analysis
Defining Data Classes and Refining Them
Refining Functions and Programs
Processing Two Complex Pieces of Data
Processing Two Lists Simultaneously: Case
Processing Two Lists Simultaneously: Case
Processing Two Lists Simultaneously: Case
Function Simplification
Designing Functions that Consume Two Complex Inputs
Exercises on Processing Two Complex Inputs
Extended Exercise: Evaluating Scheme, Part
Equality and Testing
Intermezzo : Local Definitions and Lexical Scope
Organizing Programs with local
Lexical Scope and Block Structure
Abstracting Designs
Similarities in Definitions
Similarities in Functions
Similarities in Data Definitions
Functions are Values
Syntax and Semantics
Contracts for Abstract and Polymorphic Functions
Designing Abstractions from Examples
Abstracting from Examples
Finger Exercises with Abstract List Functions
Abstraction and a Single Point of Control
Extended Exercise: Moving Pictures, Again
Note: Designing Abstractions from Templates
Designing Abstractions with First-Class Functions
Functions that Produce Functions
Designing Abstractions with Functions-as-Values
A First Look at Graphical User Interfaces
Mathematical Examples
Sequences and Series
Arithmetic Sequences and Series
Geometric Sequences and Series
The Area Under a Function
The Slope of a Function
Intermezzo : Defining Functions on the Fly
Generative Recursion
A New Form of Recursion
Modeling a Ball on a Table
Sorting Quickly
Designing Algorithms
Termination
Structural versusGenerative Recursion
Making Choices
Variations on a Theme
Fractals
From Files to Lines, from Lists to Lists of Lists
Binary Search
Newton's Method
Extended Exercise: Gaussian Elimination
Algorithms that Backtrack
Traversing Graphs
Extended Exercise: Checking (on) Queens
Intermezzo : The Cost of Computing and Vectors
Concrete Time, Abstract Time
The Definition of "on the Order of"
A First Look at Vectors
Accumulating Knowledge
The Loss of Knowledge
A Problem with Structural Processing
A Problem withGenerative Recursion
Designing Accumulator-Style Functions
Recognizing the Need for an Accumulator
Accumulator-Style Functions
Transforming Functions into Accumulator-Style
More Uses of Accumulation
Extended Exercise: Accumulators on Trees
Extended Exercise: Missionaries and Cannibals
Extended Exercise: Board Solitaire
Intermezzo : The Nature of Inexact Numbers
Fixed-size Number Arithmetic
Overflow
Underflow
DrScheme's Numbers
Changing the State of Variables
Memory for Functions
Assignment to Variables
Simple Assignments at Work
Sequencing Expression Evaluations
Assignments and Functions
A First Useful Example
Designing Functions with Memory
The Need for Memory
Memory and State Variables
Functions that Initialize Memory
Functions that Change Memory
Examples of Memory Usage
Initializing State
State Changes from User Interactions
State Changes from Recursion
Finger Exercises on State Changes
Extended Exercise: Exploring Places
Intermezzo : The Final Syntax and Semantics
The Vocabulary of Advanced Scheme
The Grammar of Advanced Scheme
The Meaning of Advanced Scheme
Errors in Advanced Scheme
Changing Compound Values
Encapsulation
Abstracting with State Variables
Practice with Encapsulation
Mutable Structures
Structures from Functions
Mutable Functional Structures
Mutable Structures
Mutable Vectors
Changing Variables, Changing Structures
Designing Functions that Change Structures
Why Mutate Structures
Structural Design Recipes and Mutation, Part
Structural Design Recipes and Mutation, Part
Extended Exercise: Moving Pictures, a Last Time
Equality
Extensional Equality
Intensional Equality
Changing Structures, Vectors, and Objects
More Practice with Vectors
Collections of Structures with Cycles
Backtracking with State
Epilogue
Computing
Programming
Moving On