No one can predict what kind of application packages will exist five or ten years from now. But application packages will continue to require some form of programming. To prepare students for these kinds of programming activities, schools can either force them to study algebra, which is the mathematical foundation of programming, or expose them to some form of programming Jsing modern programming languages and environments, schools can do the latter, they can do it effectively, and they can make algebra fun Design Recipes Cooking is at once child's play and adult joy. And cooking done with care is an act oflove Craig Claiborne(1920-2000), Food Editor, New York Times Learning to design programs is like learning to play soccer. a player must learn to trap a ball, to dribble with a ball, to pass, and to shoot a ball. Once the player knows those basic skills, the next goals are to learn to play a position, to play certain strategies, to choose among feasible strategies, and, on occasion, to create variations of a strategy because none of the existing strategies fits A programmer is also very much like an architect, a composer, or a Writer. They are creative form a mental outline, and refine it on paper until their writings reflect their mental image do P people who start with ideas in their heads and blank pieces of paper. They conceive of an idea much as possible. As they bring their ideas to paper, they employ basic-drawing,writing,and instrumental skills to express certain style elements ef a building, to describe a person's character or to formulate portions of a melody. They can practice theis trade because they have honed the basic skills for a long time and can use them on an instinctive level Programmers also form outlines, translate them into first designs, and iteratively refine them until they truly match the initialidea. Indeed, the best programmers edit and rewrite their programs many times-until they meet certain aesthetic standards. And just like soccer players, architects, composers, or writers, programmers must practice the basic skills of their trade for a long time before they can be truly creative Design recipes are the equivalent of soccer ball handling techniques, writing techniques, techniques of arrangements, and drawing skills. A single design recipe represents a point of the program design space. We have studied this space and have identified many important categories This book selects the most fundamental and the most practical recipes and presents them in increasing order of difficulty About half the design recipes focus on the connection between input data and programs. More specifically, they show how the template of a program is derived from the description of the input data. We call this data-driven program design, and it is the most frequently used form of design. Data-driven designs are easy to create, easy to understand, and easy to extend and modify Other design recipes introduce the notion of generative recursion, accumulation, and history sensitivity. The first one produces recursive programs that generate new instances of problems as they recur; accumulator-style programs collect data as they process inputs, and history-sensitive programs remember information between successive applications. Last, but not least, we also a design recipe for abstracting over programs. Abstracting is the act of generalizing two(or more) similar designs into one and of deriving the original instances from it TEAM FLY PRESENTS
-11- No one can predict what kind of application packages will exist five or ten years from now. But application packages will continue to require some form of programming. To prepare students for these kinds of programming activities, schools can either force them to study algebra, which is the mathematical foundation of programming, or expose them to some form of programming. Using modern programming languages and environments, schools can do the latter, they can do it effectively, and they can make algebra fun. Design Recipes Cooking is at once child's play and adult joy. And cooking done with care is an act of love. -- Craig Claiborne (1920-2000), Food Editor, New York Times Learning to design programs is like learning to play soccer. A player must learn to trap a ball, to dribble with a ball, to pass, and to shoot a ball. Once the player knows those basic skills, the next goals are to learn to play a position, to play certain strategies, to choose among feasible strategies, and, on occasion, to create variations of a strategy because none of the existing strategies fits. A programmer is also very much like an architect, a composer, or a writer. They are creative people who start with ideas in their heads and blank pieces of paper. They conceive of an idea, form a mental outline, and refine it on paper until their writings reflect their mental image as much as possible. As they bring their ideas to paper, they employ basic drawing, writing, and instrumental skills to express certain style elements of a building, to describe a person's character, or to formulate portions of a melody. They can practice their trade because they have honed their basic skills for a long time and can use them on an instinctive level. Programmers also form outlines, translate them into first designs, and iteratively refine them until they truly match the initial idea. Indeed, the best programmers edit and rewrite their programs many times until they meet certain aesthetic standards. And just like soccer players, architects, composers, or writers, programmers must practice the basic skills of their trade for a long time before they can be truly creative. Design recipes are the equivalent of soccer ball handling techniques, writing techniques, techniques of arrangements, and drawing skills. A single design recipe represents a point of the program design space. We have studied this space and have identified many important categories. This book selects the most fundamental and the most practical recipes and presents them in increasing order of difficulty.2 About half the design recipes focus on the connection between input data and programs. More specifically, they show how the template of a program is derived from the description of the input data. We call this data-driven program design, and it is the most frequently used form of design. Data-driven designs are easy to create, easy to understand, and easy to extend and modify. Other design recipes introduce the notion of generative recursion, accumulation, and history sensitivity. The first one produces recursive programs that generate new instances of problems as they recur; accumulator-style programs collect data as they process inputs; and history-sensitive programs remember information between successive applications. Last, but not least, we also introduce a design recipe for abstracting over programs. Abstracting is the act of generalizing two (or more) similar designs into one and of deriving the original instances from it. TEAMFLY TEAM FLY PRESENTS
On many occasions, a problem naturally suggests one design recipe On others, a programmer must choose from among several possibilities; each choice may produce programs with vastly different organizations. Making choices is natural for a creative programmer. But, unless a programmer is thoroughly familiar with the bag of design recipes to choose from and completely understands the consequences of choosing one over the other, the process is necessarily ad hoc and leads to whimsical, bad designs. We hope that by mapping out a collection of design recipes we can help programmers understand what to choose from and how to choose Now that we have explained what we mean by" programming"and"program design, "the reader can see why and how teaching program design instills thinking skills that are important in a variety of professions. To design a program properly, a student must 1. analyze a problem statement, typically stated as a word problem; 2. express its essence, abstractly and with examples 3. formulate statements and comments in a precise language; 4. evaluate and revise these activities in light of checks and tests; and 5. pay attention to details All of these are activities that are useful for a businessman, a lawyer, a journalist, a scientist, an engineer, and many others While traditional programming requires these skills, too, beginners often don' t understand thi connection. The problem is that traditional programming languages and traditional forms of programming force students to perform a large amount of book-keeping work and to memorize a large number of language-Specific facts. In short, menialwork drowns the teaching of essential skills. To avoid this problem, teachers must use a programming environment that imposes as little overhead as possible and that accommodates beginners. Because such tools didn't exist when we started, we developed them The Choice of scheme and DrScheme We ascribe beauty to that which is simple, which has no superfluous parts which exactly answers its end, which stands related to all things, which is the mean of many extremes Ralph Waldo Emerson, The Conduct of life We have chosen Scheme as the programming language for this book, and we have designed and implemented DrScheme, a programming environment for the language with special assistance for beginning students. The programming environment is freely available at the books official Web site 3 Still, the book it is not about programming in Scheme. We only use a small number of Scheme constructs in this book. Specifically, we use six constructs(function definition and application, conditional expressions, structure definition, local definitions, and assignments) plus a dozen or so basic functions. This tiny subset of the language is all that is needed to teach the principles of computing and programming. Someone who wishes to use Scheme as a tool will need to read additional material 12 TEAM FLY PRESENTS
-12- On many occasions, a problem naturally suggests one design recipe. On others, a programmer must choose from among several possibilities; each choice may produce programs with vastly different organizations. Making choices is natural for a creative programmer. But, unless a programmer is thoroughly familiar with the bag of design recipes to choose from and completely understands the consequences of choosing one over the other, the process is necessarily ad hoc and leads to whimsical, bad designs. We hope that by mapping out a collection of design recipes, we can help programmers understand what to choose from and how to choose. Now that we have explained what we mean by ``programming'' and ``program design,'' the reader can see why and how teaching program design instills thinking skills that are important in a variety of professions. To design a program properly, a student must: 1. analyze a problem statement, typically stated as a word problem; 2. express its essence, abstractly and with examples; 3. formulate statements and comments in a precise language; 4. evaluate and revise these activities in light of checks and tests; and 5. pay attention to details. All of these are activities that are useful for a businessman, a lawyer, a journalist, a scientist, an engineer, and many others. While traditional programming requires these skills, too, beginners often don't understand this connection. The problem is that traditional programming languages and traditional forms of programming force students to perform a large amount of book-keeping work and to memorize a large number of language-specific facts. In short, menial work drowns the teaching of essential skills. To avoid this problem, teachers must use a programming environment that imposes as little overhead as possible and that accommodates beginners. Because such tools didn't exist when we started, we developed them. The Choice of Scheme and DrScheme We ascribe beauty to that which is simple, which has no superfluous parts; which exactly answers its end, which stands related to all things, which is the mean of many extremes. -- Ralph Waldo Emerson, The Conduct of Life We have chosen Scheme as the programming language for this book, and we have designed and implemented DrScheme, a programming environment for the language with special assistance for beginning students. The programming environment is freely available at the book's official Web site.3 Still, the book it is not about programming in Scheme. We only use a small number of Scheme constructs in this book. Specifically, we use six constructs (function definition and application, conditional expressions, structure definition, local definitions, and assignments) plus a dozen or so basic functions. This tiny subset of the language is all that is needed to teach the principles of computing and programming. Someone who wishes to use Scheme as a tool will need to read additional material. TEAMFLY TEAM FLY PRESENTS
The choice of Scheme for beg c of programming that we pointed out at the beginning of theo hers is natural. First, the core of Scheme permits programmer focus on just those two elemer preface: programs as relations between quantities and evaluating programs for specific inputs Using just this core language, students can develop complete programs during the first session with a teacher Second, Scheme can easily be arranged as a tower of language levels. This property is crucial for beginners who make simple notational mistakes that generate obscure error messages about advanced features of a language. The result is often a wasteful search and a feeling of frustration on the student's part. To avoid this problem, our programming environment, DrScheme implements several carefully chosen sublanguages of Scheme. Based on this arrangement, the environment can signal error messages that are appropriate to a student's level of knowledge Better still, the layering of languages prevents many basic mistakes. We developed the layers and the protection modes by observing beginners for weeks in Rice's computer lab. As students learn more about programming and the language, the teacher can expose students to richer layers of the language, which allows students to write more interesting and more concise programs Third, the DrScheme programming environment offers a truly interactive evaluator. It consists of two windows: a Definitions window, where students define programs, and an Interactions window,which acts like a pocket calculator. Students can enter expressions into the latter,and DrScheme determines their values. In other words, computation starts with pocket-calculate arithmetic, which they know quite well, and quickly proceeds from there to calculations with structures,lists,and trees--the kinds of data that computer programs really manipulate Furthermore, an interactive mode of evaluation encourages students to experiment in all kinds of ways and thus stimulates their curiosity Finally, the use of an interactive evaluator with a rich data language permits students to focus on problem solving and program design activities The key improvement is that interactive evaluation renders a discussion of input and output operations(almost)superfluous. This has several consequences. First, input and output operations require memorization. Learning these things is tedious and boring. Conversely, students are better off learning problem-solving skills and using canned input and output support. Second, good text-oriented input requires deep programming skills, which are best acquired in a course on computational problem-solving Teaching bad text-oriented input is a waste of the teachers' and the students' time. Third, moderr software employs graphical user interfaces(GUD), which programmers design with editors and wizards" but not by hand. Again, students are best off learning to design the functions that are connected to rulers, buttons, text fields and so on, rather than memorizing the specific protocols that currently fashionable GUI libraries impose. In short, di ng input and output is a waste of valuable learning time during a first introduction to programming. If students decide to pursue programming in more depth, acquiring the necessary (Scheme) knowledge about input and output procedures is straightforward In summary, students can learn the core of Scheme in a couple of hours, yet the language is as powerful as a conventional programming language. As a result, students can focus immediately on the essence of programming, which greatly enhances their general problem-solving skills The parts of the book The book consists of eight parts and seven intermezzos. The parts focus on program design; the intermezzos introduce other topics concerning programming and computing. Figure 2 shows the -13- TEAM FLY PRESENTS
-13- The choice of Scheme for beginners is natural. First, the core of Scheme permits programmers to focus on just those two elements of programming that we pointed out at the beginning of the preface: programs as relations between quantities and evaluating programs for specific inputs. Using just this core language, students can develop complete programs during the first session with a teacher. Second, Scheme can easily be arranged as a tower of language levels. This property is crucial for beginners who make simple notational mistakes that generate obscure error messages about advanced features of a language. The result is often a wasteful search and a feeling of frustration on the student's part. To avoid this problem, our programming environment, DrScheme, implements several carefully chosen sublanguages of Scheme. Based on this arrangement, the environment can signal error messages that are appropriate to a student's level of knowledge. Better still, the layering of languages prevents many basic mistakes. We developed the layers and the protection modes by observing beginners for weeks in Rice's computer lab. As students learn more about programming and the language, the teacher can expose students to richer layers of the language, which allows students to write more interesting and more concise programs. Third, the DrScheme programming environment offers a truly interactive evaluator. It consists of two windows: a Definitions window, where students define programs, and an Interactions window, which acts like a pocket calculator. Students can enter expressions into the latter, and DrScheme determines their values. In other words, computation starts with pocket-calculator arithmetic, which they know quite well, and quickly proceeds from there to calculations with structures, lists, and trees -- the kinds of data that computer programs really manipulate. Furthermore, an interactive mode of evaluation encourages students to experiment in all kinds of ways and thus stimulates their curiosity. Finally, the use of an interactive evaluator with a rich data language permits students to focus on problem solving and program design activities. The key improvement is that interactive evaluation renders a discussion of input and output operations (almost) superfluous. This has several consequences. First, input and output operations require memorization. Learning these things is tedious and boring. Conversely, students are better off learning problem-solving skills and using canned input and output support. Second, good text-oriented input requires deep programming skills, which are best acquired in a course on computational problem-solving. Teaching bad text-oriented input is a waste of the teachers' and the students' time. Third, modern software employs graphical user interfaces (GUI), which programmers design with editors and ``wizards'' but not by hand. Again, students are best off learning to design the functions that are connected to rulers, buttons, text fields and so on, rather than memorizing the specific protocols that currently fashionable GUI libraries impose. In short, discussing input and output is a waste of valuable learning time during a first introduction to programming. If students decide to pursue programming in more depth, acquiring the necessary (Scheme) knowledge about input and output procedures is straightforward. In summary, students can learn the core of Scheme in a couple of hours, yet the language is as powerful as a conventional programming language. As a result, students can focus immediately on the essence of programming, which greatly enhances their general problem-solving skills. The Parts of the Book The book consists of eight parts and seven intermezzos. The parts focus on program design; the intermezzos introduce other topics concerning programming and computing. Figure 2 shows the TEAMFLY TEAM FLY PRESENTS
dependence graph for the pieces of the book. The graph demonstrates that there are several paths through the book and that a partial coverage of the material is feasible Parts I through Ill cover the foundations of data-driven program design. Part IV introduces abstraction in designs. Parts V and VI are about generative recursion and accumulation. For these first six parts, the book uses a completely functional --or algebraic--form of programming Or and the same expression always evaluates to the same result, no matter how often we evaluate it This property makes it easy to design, and to reason about, programs. To cope with interfaces between programs and the rest of the world, however, we enrich the language with assignment statements and abandon some of our algebraic reasoning. The last two parts show what this means for the design of programs. More precisely, they show how the design recipes of the first six parts apply and why we must be much more careful once assignments are added Intermezzos introduce topics that are important for computing and programming in general but not for program design per se. Some introduce the syntax and semantics of our chosen subsets of cheme on a rigorous basis, a few introduce additional programming constructs. Intermezzo 5 is Intermezzo 6 contrasts two ways of representing numbers and processing they ces vectors a discussion of the abstract cost of computing(time, space, energy) and introduc The coverage of some intermezzos can be delayed until a specific need arises. This is especially true of the intermezzos on Scheme's syntax and semantics. But, considering the central role of intermezzo 3 in figure 2, it should be covered in a timely fashion Part I T,2 tatun.3 Part TIc artly past V hrⅥI TidI. 7 Tutan. 6 ar& vI irt vIIT igure 2: The dependencies among parts and intermezzos 14 TEAM FLY PRESENTS
-14- dependence graph for the pieces of the book. The graph demonstrates that there are several paths through the book and that a partial coverage of the material is feasible. Parts I through III cover the foundations of data-driven program design. Part IV introduces abstraction in designs. Parts V and VI are about generative recursion and accumulation. For these first six parts, the book uses a completely functional -- or algebraic -- form of programming. One and the same expression always evaluates to the same result, no matter how often we evaluate it. This property makes it easy to design, and to reason about, programs. To cope with interfaces between programs and the rest of the world, however, we enrich the language with assignment statements and abandon some of our algebraic reasoning. The last two parts show what this means for the design of programs. More precisely, they show how the design recipes of the first six parts apply and why we must be much more careful once assignments are added. Intermezzos introduce topics that are important for computing and programming in general but not for program design per se. Some introduce the syntax and semantics of our chosen subsets of Scheme on a rigorous basis, a few introduce additional programming constructs. Intermezzo 5 is a discussion of the abstract cost of computing (time, space, energy) and introduces vectors. Intermezzo 6 contrasts two ways of representing numbers and processing them. The coverage of some intermezzos can be delayed until a specific need arises. This is especially true of the intermezzos on Scheme's syntax and semantics. But, considering the central role of intermezzo 3 in figure 2, it should be covered in a timely fashion. Figure 2: The dependencies among parts and intermezzos TEAMFLY TEAM FLY PRESENTS
ITERATIVE REFINEMENT AND ITERATION OF ToPICS: Systematic program design is particularly interesting and important for large projects. The step from small single-function problems to small design the core of a program and to add functionality to this core until the entire set or Is to multifunction projects requires an additional design idea: iterative refinement The goal requirements Is met Students in a first course can, and must, get their first taste of iterative refinement. Hence, in order to acquaint students with the technique, we have included extended exercises. Typically, a brief overview sets the stage for a collection of exercises. The exercises gently guide students through some design iterations. In section 16, the idea is spelled out explicitly. Furthermore, the book revisits certain exercise and example topics time and again. For example sections 66.7.4.10.3. 21. 4. 41. 4. and a few exercises in between the last two sections cover the idea of moving pictures across a canvas. The students thus see the same problem several times each time with more and more knowledge about how to organize programs Adding pieces of functionality to a program demonstrates why programmers must follow a design discipline. Solving the problem again shows students how to choose from alternative design recipes.Finally,on occasion, new knowledge just helps students improve the program organization; in other words, students learn that programs aren't finished after they work for the first time but that, like papers and books, they need editing TEACHPACKS: A second aspect of working on projects is that programmers have to work in teams In an instructional context, this means that one student's program has to fit precisely to someone elses. To simulate what" fitting one's function to someone else's"means,we provide DrScheme working with mistakes in- apartnet's program component. More technically, the projects alma teachpacks. Roughly speaking a teachpack simulates a team partner yet avoids the frustration always consist of a view and a model program component (in the sense of the model-view software architecture). In a typicaLsetting, students design the model component. The teachpacks provide the view components, often in the form of (graphical)user interfaces. Thus they eliminate the tedious, mindless portions of coding. Furthermore, this particular separation of concerns mimics that of real-world projects Fitting model components to view components requires students to pay attention to precise specifications of functions. It demonstrates the paramount importance of following a design discipline. It is also a critical skill for programmers and is often underemphasized in beginning courses. In part IV we show how to construct some simple GUls and how GUI events trigger the application of model functions. The goal is to explain that constructing GUIs is no mystery, but pend a lot of time on a topic that requires mostly rote learning and little computational thinking SCHEDULE: Each university, college, and school has its own needs and must find an appropriate schedule. At Rice University, we conventionally cover the entire book plus some addition material in a single semester. An instructor at a research university should probably keep up a similar pace. A high school teacher will necessarily pursue a slower pace. Many of the high schools that tested the book covered the first three parts in a semester; some used only the first 15 TEAM FLY PRESENTS
-15- ITERATIVE REFINEMENT AND ITERATION OF TOPICS: Systematic program design is particularly interesting and important for large projects. The step from small single-function problems to small multifunction projects requires an additional design idea: iterative refinement. The goal is to design the core of a program and to add functionality to this core until the entire set of requirements is met. Students in a first course can, and must, get their first taste of iterative refinement. Hence, in order to acquaint students with the technique, we have included extended exercises. Typically, a brief overview sets the stage for a collection of exercises. The exercises gently guide students through some design iterations. In section 16, the idea is spelled out explicitly. Furthermore, the book revisits certain exercise and example topics time and again. For example, sections 6.6, 7.4, 10.3, 21.4, 41.4, and a few exercises in between the last two sections cover the idea of moving pictures across a canvas. The students thus see the same problem several times, each time with more and more knowledge about how to organize programs. Adding pieces of functionality to a program demonstrates why programmers must follow a design discipline. Solving the problem again shows students how to choose from alternative design recipes. Finally, on occasion, new knowledge just helps students improve the program organization; in other words, students learn that programs aren't finished after they work for the first time but that, like papers and books, they need editing. TEACHPACKS: A second aspect of working on projects is that programmers have to work in teams. In an instructional context, this means that one student's program has to fit precisely to someone else's. To simulate what ``fitting one's function to someone else's'' means, we provide DrScheme teachpacks. Roughly speaking, a teachpack simulates a team partner yet avoids the frustration of working with mistakes in a partner's program component. More technically, the projects almost always consist of a view and a model program component (in the sense of the model-view software architecture). In a typical setting, students design the model component. The teachpacks provide the view components, often in the form of (graphical) user interfaces. Thus they eliminate the tedious, mindless portions of coding. Furthermore, this particular separation of concerns mimics that of real-world projects. Fitting model components to view components requires students to pay attention to precise specifications of functions. It demonstrates the paramount importance of following a design discipline. It is also a critical skill for programmers and is often underemphasized in beginning courses. In part IV we show how to construct some simple GUIs and how GUI events trigger the application of model functions. The goal is to explain that constructing GUIs is no mystery, but not to spend a lot of time on a topic that requires mostly rote learning and little computational thinking. SCHEDULE: Each university, college, and school has its own needs and must find an appropriate schedule. At Rice University, we conventionally cover the entire book plus some additional material in a single semester. An instructor at a research university should probably keep up a similar pace. A high school teacher will necessarily pursue a slower pace. Many of the high schools that tested the book covered the first three parts in a semester; some used only the first TEAMFLY TEAM FLY PRESENTS