How to Design Programs An Introduction to Computing and Programming Matthias felleisen HOW TO DESIGN PROGRAMS Robert bruce findler Matthew flatt Shriram Krishnamurthi An Introduction to Programming and Computing Matthew Shriram Felleisen Findler he MIT Press Cambridge Massachusett on, Engl Book Description 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--critieal 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 TEAM FLY PRESENTS
-1- How to Design Programs An Introduction to Computing and Programming Matthias Felleisen Robert Bruce Findler Matthew Flatt Shriram Krishnamurthi The MIT Press Cambridge, Massachusetts London, England Book Description 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. TEAMFLY TEAM FLY PRESENTS
Contents Preface Why Everyone Should Learn to Program Design Recipes The Choice of scheme and DrScheme The Parts of the book Acknowledgments I Processing Simple Forms of Data 1 Students, Teachers, and Computers 2 Numbers, Expressions. Simple programs 2. 1 Numbers and Arithmetic 2.2 Variables and Programs 2. 3 Word Problems 2. 4 Errors 2.5 Designing Programs 3 Programs are function plus variable definitions 3. 1 Composing Functions 3.2 Variable Definitions 3.3 Finger Exercises on Composing Functions 4 Conditional Expressions and Functions 4.1 Booleans and Relations 4.2 Functions that Test Conditions 4.3 Conditionals and Conditional Functions 4.4 Designing Conditional Functions 5 Symbolic information 5.1 Finger Exercises with Symbols 6 Compound Data, Part 1: Structures 6.1 Structures 6.2 Extended Exercise: Drawing Simple Pictures 6.3 Structure definitions 6.4 Data definitions 6.5 Designing Functions for Compound Data 6.6 Extended Exercise: Moving Circles and rectangles 6.7 Extended Exercise: Hangman 7 The varieties of data 7.1 Mixing and Distinguishing Data 7.2 Designing Functions for Mixed Data 73 Composing Functions. Revisited TEAM FLY PRESENTS
-2- Contents Preface Why Everyone Should Learn to Program Design Recipes The Choice of Scheme and DrScheme The Parts of the Book Acknowledgments I Processing Simple Forms of Data 1 Students, Teachers, and Computers 2 Numbers, Expressions, Simple Programs 2.1 Numbers and Arithmetic 2.2 Variables and Programs 2.3 Word Problems 2.4 Errors 2.5 Designing Programs 3 Programs are Function Plus Variable Definitions 3.1 Composing Functions 3.2 Variable Definitions 3.3 Finger Exercises on Composing Functions 4 Conditional Expressions and Functions 4.1 Booleans and Relations 4.2 Functions that Test Conditions 4.3 Conditionals and Conditional Functions 4.4 Designing Conditional Functions 5 Symbolic Information 5.1 Finger Exercises with Symbols 6 Compound Data, Part 1: Structures 6.1 Structures 6.2 Extended Exercise: Drawing Simple Pictures 6.3 Structure Definitions 6.4 Data Definitions 6.5 Designing Functions for Compound Data 6.6 Extended Exercise: Moving Circles and Rectangles 6.7 Extended Exercise: Hangman 7 The Varieties of Data 7.1 Mixing and Distinguishing Data 7.2 Designing Functions for Mixed Data 7.3 Composing Functions, Revisited TEAMFLY TEAM FLY PRESENTS
7.4 Extended Exercise: Moving Shapes 7.5 Input errors 8 Intermezzo 1: Syntax and semantics 8.2 The Scheme vocabular 8. 3 The Scheme Grammar 8.4 The Meaning of Scheme 8.5 Errors 8.6 Boolean Expressions 8.7 Variable Definitions 8. 8 Structure definitions Processing arbitrarily large data 9 Compound Data. Part 2: Lists 9.1 Lists 9.2 Data Definitions for Lists of Arbitrary Length 9.3 Processing Lists of Arbitrary Length 9.4 Designing Functions for Self-Referential Data Definitions 9.5 More on Processing Simple Lists 10 More on processing lists 10.1 Functions that Produce lists 10.2 Lists that Contain Structures 10.3 Extended Exercise: Moving Pictures 11 Natural Numbers 11.1 Defining Natural Numbers 11.2 Processing Natura Numbers of Arbitrary Size 11.3 Extended Exereise Creating Lists, Testing Functions 11.4 Alternative Data Definitions for Natural Numbers 11. 5 More on the Nature of Natural Numbers 12 Composing Functions, Revisited again 12. 1 Designing Complex Programs 12.2 Recursive Auxiliary Functions 12.3 Generalizing Problems. Generalizing Functions 12.4 Extended Exercise: Rearranging Words 13 intermezzo 2: List abbreviations II More on Processing arbitrarily large data 14 More Self-referential Data Definitions 14.2 Extended Exercise: Binary Search Trees 14.3 Lists in Lists 14.4 Extended Exercise: Evaluating Scheme TEAM FLY PRESENTS
-3- 7.4 Extended Exercise: Moving Shapes 7.5 Input Errors 8 Intermezzo 1: Syntax and Semantics 8.2 The Scheme Vocabulary 8.3 The Scheme Grammar 8.4 The Meaning of Scheme 8.5 Errors 8.6 Boolean Expressions 8.7 Variable Definitions 8.8 Structure Definitions II Processing Arbitrarily Large Data 9 Compound Data, Part 2: Lists 9.1 Lists 9.2 Data Definitions for Lists of Arbitrary Length 9.3 Processing Lists of Arbitrary Length 9.4 Designing Functions for Self-Referential Data Definitions 9.5 More on Processing Simple Lists 10 More on Processing Lists 10.1 Functions that Produce Lists 10.2 Lists that Contain Structures 10.3 Extended Exercise: Moving Pictures 11 Natural Numbers 11.1 Defining Natural Numbers 11.2 Processing Natural Numbers of Arbitrary Size 11.3 Extended Exercise: Creating Lists, Testing Functions 11.4 Alternative Data Definitions for Natural Numbers 11.5 More on the Nature of Natural Numbers 12 Composing Functions, Revisited Again 12.1 Designing Complex Programs 12.2 Recursive Auxiliary Functions 12.3 Generalizing Problems, Generalizing Functions 12.4 Extended Exercise: Rearranging Words 13 Intermezzo 2: List Abbreviations III More on Processing Arbitrarily Large Data 14 More Self-referential Data Definitions 14.1 Structures in Structures 14.2 Extended Exercise: Binary Search Trees 14.3 Lists in Lists 14.4 Extended Exercise: Evaluating Scheme TEAMFLY TEAM FLY PRESENTS
15 Mutually Referential data Definitions 15.1 Lists of structures Lists in structures 15.2 Designing Functions for Mutually referential Definitions 15.3 Extended Exercise: More on Web Pages 16 Development through Iterative refinement 16.1 Data Analysis 16.2 Defining Data Classes and Refining Them 16.3 Refining Functions and Programs 17 Processing Two Complex Pieces of data 17. 1 Processing Two Lists Simultaneously: Case 17.2 Processing Two Lists Simultaneously: Case 2 17.3 Processing Two Lists Simultaneously: Case 3 17.4 Function Simplification 17.5 Designing Functions that Consume Two Complex Inputs 17.6 Exercises on Processing Two Complex Inputs 17.7 Extended Exercise: Evaluating scheme. Part 2 17.8 Equality and Testing 18 Intermezzo 3: Local Definitions and Lexical Scope 18.2 Organizing programs with local Syntax of local Semantics of local Pragmatics of local part 1 Pragmatics of local part 3 18.3 Lexical Scope and Block Structure N Abstracting designs 19 Similarities in definitions 19.1 Similarities in Functions 9.2 Similarities in data definitions 20 Functions are values 20. 1 Syntax and Semantics 20.2 Contracts for Abstract and Polymorphic Functions 21 Designing Abstractions from Examples 21. 1 Abstracting from Examples 21.2 Finger Exercises with Abstract List Functions 21.3 Abstraction and a Single point of control 21.4 Extended Exercise: Moving Pictures. Again 21.5 Note: Designing Abstractions from Templates 22 Designing abstractions with first- Class functions 22.1 Functions that produce functions 22.2 Designing Abstractions with Functions-as-Values 22.3 A First Look at Graphical User Interfaces TEAM FLY PRESENTS
-4- 15 Mutually Referential Data Definitions 15.1 Lists of Structures, Lists in Structures 15.2 Designing Functions for Mutually Referential Definitions 15.3 Extended Exercise: More on Web Pages 16 Development through Iterative Refinement 16.1 Data Analysis 16.2 Defining Data Classes and Refining Them 16.3 Refining Functions and Programs 17 Processing Two Complex Pieces of Data 17.1 Processing Two Lists Simultaneously: Case 1 17.2 Processing Two Lists Simultaneously: Case 2 17.3 Processing Two Lists Simultaneously: Case 3 17.4 Function Simplification 17.5 Designing Functions that Consume Two Complex Inputs 17.6 Exercises on Processing Two Complex Inputs 17.7 Extended Exercise: Evaluating Scheme, Part 2 17.8 Equality and Testing 18 Intermezzo 3: Local Definitions and Lexical Scope 18.2 Organizing Programs with local Syntax of local Semantics of local Pragmatics of local, Part 1 Pragmatics of local, Part 2 Pragmatics of local, Part 3 18.3 Lexical Scope and Block Structure IV Abstracting Designs 19 Similarities in Definitions 19.1 Similarities in Functions 19.2 Similarities in Data Definitions 20 Functions are Values 20.1 Syntax and Semantics 20.2 Contracts for Abstract and Polymorphic Functions 21 Designing Abstractions from Examples 21.1 Abstracting from Examples 21.2 Finger Exercises with Abstract List Functions 21.3 Abstraction and a Single Point of Control 21.4 Extended Exercise: Moving Pictures, Again 21.5 Note: Designing Abstractions from Templates 22 Designing Abstractions with First-Class Functions 22.1 Functions that Produce Functions 22.2 Designing Abstractions with Functions-as-Values 22.3 A First Look at Graphical User Interfaces TEAMFLY TEAM FLY PRESENTS
23 Mathematical Examples 23. 1 Sequences and Series 23.2 Arithmetic Sequences and Series 23.3 Geometric Sequences and Series aylor serl 23.4 The area under a function 23.5 The Slope of a Function 24 Intermezzo 4: Defining functions on the fly Syntax of lambda Scope and Semantics of lambda Pragmatics of lambda V Generative Recursion 25 A New form of recursion 25 1 Modeling a Ball on a Table 5.2 Sorting Quickly 26 Designing algorithms 26.1 Termination 26.2 Structural versus Generative recursion 26.3 Making choices 27 Variations on a theme 27.1 Fractals 27.2 From Files to Lines, from Lists to Lists ofLists 27.3 Binary Search 27.4 Newton's Method 27.5 Extended Exereise Gaussian Elimination 28 Algorithms that backtrack 28.1 Traversing Graphs 28.2 Extended Exercise: Checking(on) Queens 29 Intermezzo 5: The Cost of Computing and vectors 29.2 Concrete Time. Abstract Time 29 3 The Definition of"on the order of 29 4 A First look at vectors VI Accumulating knowledge 30 The loss of knowledge 30. 1 A Problem with Structural Processing 30.2 A Problem with Generative Recursion 31 Designing accumulator -Style functions 31.1 Recognizing the Need for an Accumulator 31.2 Accumulator-Style Functions 31.3 Transforming Functions into Accumulator-Style TEAM FLY PRESENTS
-5- 23 Mathematical Examples 23.1 Sequences and Series 23.2 Arithmetic Sequences and Series 23.3 Geometric Sequences and Series Taylor Series 23.4 The Area Under a Function 23.5 The Slope of a Function 24 Intermezzo 4: Defining Functions on the Fly Syntax of lambda Scope and Semantics of lambda Pragmatics of lambda V Generative Recursion 25 A New Form of Recursion 25.1 Modeling a Ball on a Table 25.2 Sorting Quickly 26 Designing Algorithms 26.1 Termination 26.2 Structural versus Generative Recursion 26.3 Making Choices 27 Variations on a Theme 27.1 Fractals 27.2 From Files to Lines, from Lists to Lists of Lists 27.3 Binary Search 27.4 Newton's Method 27.5 Extended Exercise: Gaussian Elimination 28 Algorithms that Backtrack 28.1 Traversing Graphs 28.2 Extended Exercise: Checking (on) Queens 29 Intermezzo 5: The Cost of Computing and Vectors 29.2 Concrete Time, Abstract Time 29.3 The Definition of ``on the Order of'' 29.4 A First Look at Vectors VI Accumulating Knowledge 30 The Loss of Knowledge 30.1 A Problem with Structural Processing 30.2 A Problem with Generative Recursion 31 Designing Accumulator-Style Functions 31.1 Recognizing the Need for an Accumulator 31.2 Accumulator-Style Functions 31.3 Transforming Functions into Accumulator-Style TEAMFLY TEAM FLY PRESENTS