Simply Scheme - 2nd Edition: Introducing Computer Science

Description

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. 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