How to Design Programs : An Introduction to Programming and Computing

by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt and Shriram Krishnamurthi

• ISBN13: 9780262062183
• ISBN10: 0262062186
• Format: Hardcover
• Copyright: 2001-02-12
• Publisher: Mit Pr

Summary

This introduction to programming places computer science in the core of a liberal arts education. Unlike other introductory books, it focuses on the program design process. This approach fosters a variety of skills-critical reading, analytical thinking, creative synthesis, and attention to detail-that are important for everyone, not just future computer programmers. The book exposes readers to two fundamentally new ideas. First, it presents 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, based on the analysis; how to finish the program; and how to test. Each step produces a well-defined intermediate product. Second, the book comes with a novel programming environment, the first one explicitly designed for beginners. The environment grows with the readers as they master the material in the book until it supports a full-fledged language for the whole spectrum of programming tasks. All the book's support materials are available for free on the Web. The Web site includes the environment, teacher guides, exercises for all levels, solutions, and additional projects.

Table of Contents

Contents	v
List of Figures	xiii
Preface	xvii
Why Everyone Should Learn to Program	xx
Design Recipes	xxi
The Choice of Scheme and DrScheme	xxiv
The Parts of the Book	xxvi
Acknowledgments	xxix
I Processing Simple Forms of Data	3	(94)
Students, Teachers, and Computers	3	(2)
Numbers, Expressions, Simple Programs	5	(16)
Numbers and Arithmetic	5	(3)
Variables and Programs	8	(4)
Word Problems	12	(1)
Errors	13	(3)
Designing Programs	16	(5)
Programs are Function Plus Variable Definitions	21	(8)
Composing Functions	22	(4)
Variable Definitions	26	(1)
Finger Exercises on Composing Functions	27	(2)
Conditional Expressions and Functions	29	(17)
Booleans and Relations	29	(3)
Functions that Test Conditions	32	(5)
Conditionals and Conditional Functions	37	(3)
Designing Conditional Functions	40	(6)
Symbolic Information	46	(5)
Finger Exercises with Symbols	49	(2)
Compound Data, Part 1: Structures	51	(28)
Structures	51	(4)
Extended Exercise: Drawing Simple Pictures	55	(3)
Structure Definitions	58	(5)
Data Definitions	63	(2)
Designing Functions for Compound Data	65	(7)
Extended Exercise: Moving Circles and Rectangles	72	(4)
Extended Exercise: Hangman	76	(3)
The Varieties of Data	79	(18)
Mixing and Distinguishing Data	80	(5)
Designing Functions for Mixed Data	85	(5)
Composing Functions, Revisited	90	(3)
Extended Exercise: Moving Shapes	93	(1)
Input Errors	94	(3)
Intermezzo 1: Syntax and Semantics	97	(20)
The Scheme Vocabulary	98	(1)
The Scheme Grammar	98	(3)
The Meaning of Scheme	101	(4)
Errors	105	(3)
Boolean Expressions	108	(1)
Variable Definitions	109	(2)
Structure Definitions	111	(6)
II Processing Arbitrarily Large Data	117	(66)
Compound Data, Part 2: Lists	117	(20)
Lists	117	(5)
Data Definitions for Lists of Arbitrary Length	122	(3)
Processing Lists of Arbitrary Length	125	(3)
Designing Functions for Self-Referential Data Definitions	128	(3)
More on Processing Simple Lists	131	(6)
More on Processing Lists	137	(16)
Functions that Produce Lists	138	(5)
Lists that Contain Structures	143	(8)
Extended Exercise: Moving Pictures	151	(2)
Natural Numbers	153	(15)
Defining Natural Numbers	153	(1)
Processing Natural Numbers of Arbitrary Size	154	(4)
Extended Exercise: Creating Lists, Testing Functions	158	(2)
Alternative Data Definitions for Natural Numbers	160	(6)
More on the Nature of Natural Numbers	166	(2)
Composing Functions, Revisited Again	168	(15)
Designing Complex Programs	169	(1)
Recursive Auxiliary Functions	170	(6)
Generalizing Problems, Generalizing Functions	176	(4)
Extended Exercise: Rearranging Words	180	(3)
Intermezzo 2: List Abbreviations	183	(6)
III More on Processing Arbitrarily Large Data	189	(70)
More Self-referential Data Definitions	189	(20)
Structures in Structures	189	(10)
Extended Exercise: Binary Search Trees	199	(5)
Lists in Lists	204	(4)
Extended Exercise: Evaluating Scheme	208	(1)
Mutually Referential Data Definitions	209	(12)
Lists of Structures, Lists in Structures	210	(7)
Designing Functions for Mutually Referential Definitions	217	(3)
Extended Exercise: More on Web Pages	220	(1)
Development through Iterative Refinement	221	(7)
Data Analysis	222	(1)
Defining Data Classes and Refining Them	223	(4)
Refining Functions and Programs	227	(1)
Processing Two Complex Pieces of Data	228	(31)
Processing Two Lists Simultaneously: Case 1	229	(2)
Processing Two Lists Simultaneously: Case 2	231	(4)
Processing Two Lists Simultaneously: Case 3	235	(5)
Function Simplification	240	(2)
Designing Functions that Consume Two Complex Inputs	242	(1)
Exercises on Processing Two Complex Inputs	243	(4)
Extended Exercise: Evaluating Scheme, Part 2	247	(2)
Equality and Testing	249	(10)
Intermezzo 3: Local Definitions and Lexical Scope	259	(24)
Organizing Programs with local	259	(17)
Lexical Scope and Block Structure	276	(7)
IV Abstracting Designs	283	(67)
Similarities in Definitions	283	(16)
Similarities in Functions	284	(9)
Similarities in Data Definitions	293	(6)
Functions are Values	299	(7)
Syntax and Semantics	299	(2)
Contracts for Abstract and Polymorphic Functions	301	(5)
Designing Abstractions from Examples	306	(13)
Abstracting from Examples	306	(6)
Finger Exercises with Abstract List Functions	312	(3)
Abstraction and a Single Point of Control	315	(1)
Extended Exercise: Moving Pictures, Again	316	(2)
Note: Designing Abstractions from Templates	318	(1)
Designing Abstractions with First-Class Functions	319	(15)
Functions that Produce Functions	319	(2)
Designing Abstractions with Functions-as-Values	321	(4)
A First Look at Graphical User Interfaces	325	(9)
Mathematical Examples	334	(16)
Sequences and Series	335	(2)
Arithmetic Sequences and Series	337	(1)
Geometric Sequences and Series	338	(4)
The Area Under a Function	342	(2)
The Slope of a Function	344	(6)
Intermezzo 4: Defining Functions on the Fly	350	(7)
V Generative Recursion	357	(60)
A New Form of Recursion	357	(11)
Modeling a Ball on a Table	358	(4)
Sorting Quickly	362	(6)
Designing Algorithms	368	(13)
Termination	370	(4)
Structural versus Generative Recursion	374	(1)
Making Choices	375	(6)
Variations on a Theme	381	(25)
Fractals	381	(5)
From Files to Lines, from Lists to Lists of Lists	386	(5)
Binary Search	391	(8)
Newton's Method	399	(2)
Extended Exercise: Gaussian Elimination	401	(5)
Algorithms that Backtrack	406	(11)
Traversing Graphs	407	(7)
Extended Exercise: Checking (on) Queens	414	(3)
Intermezzo 5: The Cost of Computing and Vectors	417	(24)
Concrete Time, Abstract Time	417	(6)
The Definition of ``on the Order of''	423	(3)
A First Look at Vectors	426	(15)
VI Accumulating Knowledge	441	(37)
The Loss of Knowledge	441	(9)
A Problem with Structural Processing	441	(4)
A Problem with Generative Recursion	445	(5)
Designing Accumulator-Style Functions	450	(16)
Recognizing the Need for an Accumulator	451	(1)
Accumulator-Style Functions	452	(3)
Transforming Functions into Accumulator-Style	455	(11)
More Uses of Accumulation	466	(12)
Extended Exercise: Accumulators on Trees	466	(6)
Extended Exercise: Missionaries and Cannibals	472	(4)
Extended Exercise: Board Solitaire	476	(2)
Intermezzo 6: The Nature of Inexact Numbers	478	(13)
Fixed-size Number Arithmetic	478	(6)
Overflow	484	(1)
Underflow	485	(1)
DrScheme's Numbers	486	(5)
VII Changing the State of Variables	491	(57)
Memory for Functions	491	(5)
Assignment to Variables	496	(11)
Simple Assignments at Work	496	(3)
Sequencing Expression Evaluations	499	(2)
Assignments and Functions	501	(3)
A First Useful Example	504	(3)
Designing Functions with Memory	507	(14)
The Need for Memory	508	(2)
Memory and State Variables	510	(2)
Functions that Initialize Memory	512	(1)
Functions that Change Memory	513	(8)
Examples of Memory Usage	521	(27)
Initializing State	521	(3)
State Changes from User Interactions	524	(11)
State Changes from Recursion	535	(7)
Finger Exercises on State Changes	542	(2)
Extended Exercise: Exploring Places	544	(4)
Intermezzo 7: The Final Syntax and Semantics	548	(25)
The Vocabulary of Advanced Scheme	548	(1)
The Grammar of Advanced Scheme	548	(3)
The Meaning of Advanced Scheme	551	(15)
Errors in Advanced Scheme	566	(7)
VIII Changing Compound Values	573	(104)
Encapsulation	573	(14)
Abstracting with State Variables	573	(12)
Practice with Encapsulation	585	(2)
Mutable Structures	587	(21)
Structures from Functions	587	(3)
Mutable Functional Structures	590	(4)
Mutable Structures	594	(7)
Mutable Vectors	601	(2)
Changing Variables, Changing Structures	603	(5)
Designing Functions that Change Structures	608	(29)
Why Mutate Structures	608	(1)
Structural Design Recipes and Mutation, Part 1	609	(13)
Structural Design Recipes and Mutation, Part 2	622	(14)
Extended Exercise: Moving Pictures, a Last Time	636	(1)
Equality	637	(5)
Extensional Equality	637	(1)
Intensional Equality	638	(4)
Changing Structures, Vectors, and Objects	642	(35)
More Practice with Vectors	642	(18)
Collections of Structures with Cycles	660	(12)
Backtracking with State	672	(5)
Epilogue	677	(6)
Computing	677	(1)
Programming	678	(2)
Moving On	680	(3)
Index	683