32 More Uses of accumulation 32.1 Extended Exercise, Accumulators on trees 32.2 Extended Exercise. Missionaries and Cannibals 32.3 Extended Exercise: Board Solitaire 33 ntermezzo 6: The Nature of inexact numbers 33.2 Fixed-size Number Arithmetic 33.4 Underflow 33.5 DrScheme's Numbers Vl Changing the State of variables 34 Memory for function 35 Assignment to Variables 35.1 Simple Assignments at Work 35.2 Sequencing Expression Evaluations 35.3 Assignments and functions 35.4 A First Useful Example 36 Designing Functions with memory 36. 1 The Need for Memory 36.3 Functions that Initialize Memory 36.4 Functions that Change Memory 37 Examples of Memory Usage 37.1 Initializing state 37.2 State Changes, fom User Interactions 37.3State Changes from Recursion 37.4 Finger Exercises on Stafe Changes 37.5 Extended Exercise. Exploring Places 38 Intermezzo 7: The Final Syntax and Semantics 38.2 The Vocabulary of Advanced Scheme 38.3 The grammar of advanced scheme 38. 4 The Meaning of Advanced Scheme 38.5 Errors in advanced scheme VIl Changing Compound values 39 Encapsulation 39.1 Abstracting with State Variables 39.2 Practice with Encapsulation 40 Mutable structures 40.1 Structures from Functions 40.2 Mutable Functional Structures 40. 3 Mutable Structures TEAM FLY PRESENTS
-6- 32 More Uses of Accumulation 32.1 Extended Exercise: Accumulators on Trees 32.2 Extended Exercise: Missionaries and Cannibals 32.3 Extended Exercise: Board Solitaire 33 Intermezzo 6: The Nature of Inexact Numbers 33.2 Fixed-size Number Arithmetic 33.3 Overflow 33.4 Underflow 33.5 DrScheme's Numbers VII Changing the State of Variables 34 Memory for Functions 35 Assignment to Variables 35.1 Simple Assignments at Work 35.2 Sequencing Expression Evaluations 35.3 Assignments and Functions 35.4 A First Useful Example 36 Designing Functions with Memory 36.1 The Need for Memory 36.2 Memory and State Variables 36.3 Functions that Initialize Memory 36.4 Functions that Change Memory 37 Examples of Memory Usage 37.1 Initializing State 37.2 State Changes from User Interactions 37.3 State Changes from Recursion 37.4 Finger Exercises on State Changes 37.5 Extended Exercise: Exploring Places 38 Intermezzo 7: The Final Syntax and Semantics 38.2 The Vocabulary of Advanced Scheme 38.3 The Grammar of Advanced Scheme 38.4 The Meaning of Advanced Scheme 38.5 Errors in Advanced Scheme VIII Changing Compound Values 39 Encapsulation 39.1 Abstracting with State Variables 39.2 Practice with Encapsulation 40 Mutable Structures 40.1 Structures from Functions 40.2 Mutable Functional Structures 40.3 Mutable Structures TEAMFLY TEAM FLY PRESENTS
40.4 Mutable Vectors 40.5 Changing variables. Changing Structures 41 Designing Functions that Change structures 41.1 Why Mutate Structures 41.2 Structural Design Recipes and Mutation, Part 1 41.3 Structural Design Recipes and Mutation, Part 2 41.4 Extended Exercise: Moving Pictures a Last Time 42 Equality 42. 1 Extensional Equality 42.2 Intensional Equality 43 Changing Structures, Vectors, and obiects 43.1 More Practice with Vectors 43.2 Collections of Structures with Cycles 43.3 Backtracking with State Epilogue Programming Moving On Index Flyhtear TEAM FLY PRESENTS
-7- 40.4 Mutable Vectors 40.5 Changing Variables, Changing Structures 41 Designing Functions that Change Structures 41.1 Why Mutate Structures 41.2 Structural Design Recipes and Mutation, Part 1 41.3 Structural Design Recipes and Mutation, Part 2 41.4 Extended Exercise: Moving Pictures, a Last Time 42 Equality 42.1 Extensional Equality 42.2 Intensional Equality 43 Changing Structures, Vectors, and Objects 43.1 More Practice with Vectors 43.2 Collections of Structures with Cycles 43.3 Backtracking with State Epilogue Computing Programming Moving On Index TEAMFLY TEAM FLY PRESENTS
Preface It goes against the grain of modern education to teach children to program. What fun is there in making plans acquiring discipline in organizing thoughtS, devoting attention to detail and learning to be self-critical? - Alan Perlis, Epigrams in Programming Many professions require some form of computer programming. Accountants program spreadsheets and word processors; photographers program photo editors; musicians program synthesizers; and professional programmers instruct plain computers. Programming has become a required skill Yet programming is more than just a vocational skill. Indeed, good programming is a fun activity, a creative outlet, and a way to express abstract ideas in a tangible form. And designing programs teaches a variety of skills that are important in all kinds of professions: critical reading, analytical thinking, creative synthesis, and attention to detail We therefore believe that the study of program design deserves the same central role in general education as mathematics and English. Or, put more succinctly, everyone should learn how to design programs. On one hand, program design teaches the same analytical skills as mathematics. But, unlike provides immediate feedback and thus leads to exploration, experimentation, and self-evaluation Furthermore, designing programs produces useful and fun things, which vastly increases the sense of accomplishment when compared to drill exercises in mathematics. On the other hand program design teaches the same analytical reading and writing skills as English. Even th smallest programming tasks are formulated as word problems. Without critical reading skills,a student cannot design programs that match the specification. Conversely, good program design methods force a student to articulate thoughts about programs in proper English The Design Recipe for Functions Problem analysis Data Definition Contract, Purpose Effect Statements, Header Examples Function Template Function Definition Tests Figure 1: The basic steps of a program design recipe This book is the first book on programming as the core subject of a liberal arts education. Its main focus is the design process that leads from problem statements to well-organized solutions TEAM FLY PRESENTS
-8- Preface It goes against the grain of modern education to teach children to program. What fun is there in making plans, acquiring discipline in organizing thoughts, devoting attention to detail and learning to be self-critical? -- Alan Perlis, Epigrams in Programming Many professions require some form of computer programming. Accountants program spreadsheets and word processors; photographers program photo editors; musicians program synthesizers; and professional programmers instruct plain computers. Programming has become a required skill. Yet programming is more than just a vocational skill. Indeed, good programming is a fun activity, a creative outlet, and a way to express abstract ideas in a tangible form. And designing programs teaches a variety of skills that are important in all kinds of professions: critical reading, analytical thinking, creative synthesis, and attention to detail. We therefore believe that the study of program design deserves the same central role in general education as mathematics and English. Or, put more succinctly, everyone should learn how to design programs. On one hand, program design teaches the same analytical skills as mathematics. But, unlike mathematics, working with programs is an active approach to learning. Interacting with software provides immediate feedback and thus leads to exploration, experimentation, and self-evaluation. Furthermore, designing programs produces useful and fun things, which vastly increases the sense of accomplishment when compared to drill exercises in mathematics. On the other hand, program design teaches the same analytical reading and writing skills as English. Even the smallest programming tasks are formulated as word problems. Without critical reading skills, a student cannot design programs that match the specification. Conversely, good program design methods force a student to articulate thoughts about programs in proper English. The Design Recipe for Functions Problem Analysis & Data Definition Contract, Purpose & Effect Statements, Header Examples Function Template Function Definition Tests Figure 1: The basic steps of a program design recipe This book is the first book on programming as the core subject of a liberal arts education. Its main focus is the design process that leads from problem statements to well-organized solutions; TEAMFLY TEAM FLY PRESENTS
it deemphasizes the study of programming language details, algorithmic minutiae, and specifi application domains. Our desire to focus on the design process requires two radical innovations for introductory courses. The first innovation is a set of explicit design guidelines. Existing curricula tend to provide vague and ill-defined suggestions, such as" design from top to bottom or make the program structural. We have instead developed design guidelines that lead students from a problem statement to a computational solution in step-by-step fashion with well- defined intermediate products. In the process they learn to read, to analyze, to organize, to experiment, to think in a systematic manner. The second innovation is a radically new programming environment. In the past, texts on programming ignored the role of the programming environment in the learning process; they simply assumed that students had access to a professional environment. This book provides a programming emvironment for beginners. It also grows with the students as they master more and more of the material until it supports a full fledged language for the whole spectrum of programming tasks: large-scale programming as well as scripting beginning programmer through the entire problem-solving process. With design recipes, i des a Our guidelines are formulated as a number of program design recipes. A design recipe gu beginner almost never again stares at a blank piece of paper or a blank computer screen. Instead the student will check the design recipe and use the question-and-answer guidelines to make some progress We created the design recipes by identifying categories of problems. The identification of a problem category is based on the classes of data that are used to represent the relevant with a checklist. Figure I shows the basic six steps if a design recipe checklist. Each step produces a well-defined intermediate product: 1.the description of the classof problem data; 2. the informal specification of a program's behavior; 3. the illustration of the behavior with examples 4. the development of a program - template or layout 5. the transformation of the template into a complete definition;and 6. the discovery of errors through testing The major difference concerns the relationship of steps 1 and 4 Design recipes help beginners and teachers alike. Teachers can use the recipes to inspect a beginner's problem-solving skills, to diagnose weaknesses, and to suggest specific remedial steps After all, each stage of the design recipe yields a well-defined, checkable product. If a beginner is stuck, a teacher can inspect the intermediate products and determine what the problem is Based on this analysis, the teacher can then provide guidance for a specific step in the recipe raise appropriate questions, and recommend additional practice exercises Why Everyone should Learn to Program And as imagination bodies forth he forms of th unknown and Turns them to shapes, and gives to airy nothing a local habitation and a name TEAM FLY PRESENTS
-9- it deemphasizes the study of programming language details, algorithmic minutiae, and specific application domains. Our desire to focus on the design process requires two radical innovations for introductory courses. The first innovation is a set of explicit design guidelines. Existing curricula tend to provide vague and ill-defined suggestions, such as ``design from top to bottom'' or ``make the program structural.'' We have instead developed design guidelines that lead students from a problem statement to a computational solution in step-by-step fashion with welldefined intermediate products. In the process they learn to read, to analyze, to organize, to experiment, to think in a systematic manner. The second innovation is a radically new programming environment. In the past, texts on programming ignored the role of the programming environment in the learning process; they simply assumed that students had access to a professional environment. This book provides a programming environment for beginners. It also grows with the students as they master more and more of the material until it supports a fullfledged language for the whole spectrum of programming tasks: large-scale programming as well as scripting. Our guidelines are formulated as a number of program design recipes. 1 A design recipe guides a beginning programmer through the entire problem-solving process. With design recipes, a beginner almost never again stares at a blank piece of paper or a blank computer screen. Instead, the student will check the design recipe and use the question-and-answer guidelines to make some progress. We created the design recipes by identifying categories of problems. The identification of a problem category is based on the classes of data that are used to represent the relevant information. Starting from the structure of this class description students derive the programs with a checklist. Figure 1 shows the basic six steps of a design recipe checklist. Each step produces a well-defined intermediate product: 1. the description of the class of problem data; 2. the informal specification of a program's behavior; 3. the illustration of the behavior with examples; 4. the development of a program template or layout; 5. the transformation of the template into a complete definition; and 6. the discovery of errors through testing. The major difference concerns the relationship of steps 1 and 4. Design recipes help beginners and teachers alike. Teachers can use the recipes to inspect a beginner's problem-solving skills, to diagnose weaknesses, and to suggest specific remedial steps. After all, each stage of the design recipe yields a well-defined, checkable product. If a beginner is stuck, a teacher can inspect the intermediate products and determine what the problem is. Based on this analysis, the teacher can then provide guidance for a specific step in the recipe, raise appropriate questions, and recommend additional practice exercises. Why Everyone Should Learn to Program And as imagination bodies forth The forms of things to unknown, and the poet's pen Turns them to shapes, and gives to airy nothing A local habitation and a name. TEAMFLY TEAM FLY PRESENTS
Shakespeare, A Midsummer Night's Dream V(i) Our claim that everyone programs or should learn to program might appear strange considering that, at first glance, fewer and fewer people seem to program these days. Instead, the majority of people use application packages, which dont seem to require any programming. Even programmers use"program generators, "packages that create programs from, say, business rules So why should anyone learn to program? The answer consists of two parts. First, it is indeed true that traditional forms ofprogramming are useful for just a few people. But, programming as we the authors understand it is useful for everyone: the administrative secretary who uses spreadsheets as well as the high-tech programmer. In other words, we have a broader notion of programming in mind than the traditional one. We explain our notion in a moment. Second, we teach our idea of programming with a technology that is based on the principle of minimal intrusion. Hence our notion of programming teaches problem-analysis and problem-solving skills without imposing the overhead of traditional programming notations and tools To get a better understanding of modern programming, take a closer look at spreadsheets, one of today's popular application packages. A user enters formulas into a spreadsheet. The formulas describe how a cell a depends on another cell B. Then, as the user enters a humber into B,the spreadsheet automatically calculates the contents of cell A. For complicated spreadsheets, a cell may depend on many other cells, not just one Other application packages require similar activities, Consider word processors and style sheets A style sheet specifies how to create a(part ofa)document from yet-to-be-determined words or sentences. When someone provides specific words and a style sheet, the word processor creates the document by replac les in the 'style sheet with specific words. Similarly, someone who conducts a Web search may wish to specify what words to look for, what words should be next to each other, and what words should not(occur in the page. In this case, the output depends or the search engine's cache of Web pages and the user's search expression Finally, using a program generator in many ways relies on the same skills as those necessary for application packages. a program generator creates a program in a traditional programming language, such as C++ or Java, from high-level descriptions, such as business rules or scientific laws. Such rules typically relate quantities, sales, and inventory records and thus specify computations. The other parts of the program, especially how it interacts with a user and how it stores data in the computer's disk, are generated with little or no human intervention All of these activities instruct some computer software to do something for us. Some use scientific notation, some may use stylized English, some use a concrete programming notation All of them are some form of programming. The essence of these activities boils down to two 1. relating one quantity to another quantity, and 2. evaluating a relationship by substituting values for na Indeed, the two concepts characterize programming at the lowest level, the computer,s native language, and in a modern fashionable language such as Java. A program relates its inputs to outputs; and, when a program is used for specific inputs, the evaluation substitutes concrete ues for names TEAM FLY PRESENTS
-10- -- Shakespeare, A Midsummer Night's Dream V(i) Our claim that everyone programs or should learn to program might appear strange considering that, at first glance, fewer and fewer people seem to program these days. Instead, the majority of people use application packages, which don't seem to require any programming. Even programmers use ``program generators,'' packages that create programs from, say, business rules. So why should anyone learn to program? The answer consists of two parts. First, it is indeed true that traditional forms of programming are useful for just a few people. But, programming as we the authors understand it is useful for everyone: the administrative secretary who uses spreadsheets as well as the high-tech programmer. In other words, we have a broader notion of programming in mind than the traditional one. We explain our notion in a moment. Second, we teach our idea of programming with a technology that is based on the principle of minimal intrusion. Hence our notion of programming teaches problem-analysis and problem-solving skills without imposing the overhead of traditional programming notations and tools. To get a better understanding of modern programming, take a closer look at spreadsheets, one of today's popular application packages. A user enters formulas into a spreadsheet. The formulas describe how a cell A depends on another cell B. Then, as the user enters a number into B, the spreadsheet automatically calculates the contents of cell A. For complicated spreadsheets, a cell may depend on many other cells, not just one. Other application packages require similar activities. Consider word processors and style sheets. A style sheet specifies how to create a (part of a) document from yet-to-be-determined words or sentences. When someone provides specific words and a style sheet, the word processor creates the document by replacing names in the style sheet with specific words. Similarly, someone who conducts a Web search may wish to specify what words to look for, what words should be next to each other, and what words should not occur in the page. In this case, the output depends on the search engine's cache of Web pages and the user's search expression. Finally, using a program generator in many ways relies on the same skills as those necessary for application packages. A program generator creates a program in a traditional programming language, such as C++ or Java, from high-level descriptions, such as business rules or scientific laws. Such rules typically relate quantities, sales, and inventory records and thus specify computations. The other parts of the program, especially how it interacts with a user and how it stores data in the computer's disk, are generated with little or no human intervention. All of these activities instruct some computer software to do something for us. Some use scientific notation, some may use stylized English, some use a concrete programming notation. All of them are some form of programming. The essence of these activities boils down to two concepts: 1. relating one quantity to another quantity, and 2. evaluating a relationship by substituting values for names. Indeed, the two concepts characterize programming at the lowest level, the computer's native language, and in a modern fashionable language such as Java. A program relates its inputs to outputs; and, when a program is used for specific inputs, the evaluation substitutes concrete values for names. TEAMFLY TEAM FLY PRESENTS