For other word problems, we must inspect the problem to separate the given facts from what is to be computed. If a given is a fixed number, it shows up in the program. If it is an unknown number that is to be fixed by someone else later, it is an input. The question (or the imperative)in the problem statement suggests a name for the program Program Examples: To gain a better understanding of what the program should compute, we make up examples of inputs and determine what the output should be. For example, area-of-ring should produce 50. 24 for the inputs 5 and 3, because it is the difference between the area of the outer disk and the area of the inner disk We add examples to the purpose statement ;; area-of-ring number number number ii to compute the area of a ring whose radius is outer and whose hole has a radius of inner example: (area -of-ring 5 3) should produce 50.24 (define (area-of-ring outer inner Making up examples--before we write down the program's body --helps in many ways. First, it is the only sure way to discover logical errors with testing. If we use the finished program to make up examples, we are tempted to trust the program because it is so much easier to run the program than to predict what it does. Second, examples force us to think through the computational process, which, for the complicated cases we will encounter later, is critical to the development of fhe function body. Finally, examples illustrate the informal prose of a purpose statement Future readers of the program, such as teachers, colleagues, or buyers, greatly appreciate illustrations of abstract concepts The Body: Finally, we must formulate the program's body. That is, we must replace th in our header with an expression. The expression computes the answer fi the parameters, using Scheme's basic operations and Scheme programs that we already om We can only formulate the program s body if we understand how the program computes the output from the given inputs. If the input-output relationship is given as a mathematical formula, we just translate mathematics into Scheme. If, instead, we are revisit the examples from the second step and to understand how we computed the to given a word problem, we must craft the expression carefully. To this end, it is help outputs for specific inputs In our running example, the computational task was given via an informally stated formula that reused area-of-disk, a previously defined program. Here is the translation into scheme (define (area-of-ring outer inner (-(area-of (area-of-disk inner))) Testing: After we have completed the program definition, we must still test the progran At a minimum, we should ensure that the program computes the expected outputs for the program examples. To facilitate testing, we may wish to add the examples to the bottom 31- TEAM FLY PRESENTS
-31- For other word problems, we must inspect the problem to separate the given facts from what is to be computed. If a given is a fixed number, it shows up in the program. If it is an unknown number that is to be fixed by someone else later, it is an input. The question (or the imperative) in the problem statement suggests a name for the program. • Program Examples: To gain a better understanding of what the program should compute, we make up examples of inputs and determine what the output should be. For example, area-of-ring should produce 50.24 for the inputs 5 and 3, because it is the difference between the area of the outer disk and the area of the inner disk. We add examples to the purpose statement: ;; area-of-ring : number number -> number ;; to compute the area of a ring whose radius is ;; outer and whose hole has a radius of inner ;; example: (area-of-ring 5 3) should produce 50.24 (define (area-of-ring outer inner) ...) Making up examples -- before we write down the program's body -- helps in many ways. First, it is the only sure way to discover logical errors with testing. If we use the finished program to make up examples, we are tempted to trust the program because it is so much easier to run the program than to predict what it does. Second, examples force us to think through the computational process, which, for the complicated cases we will encounter later, is critical to the development of the function body. Finally, examples illustrate the informal prose of a purpose statement. Future readers of the program, such as teachers, colleagues, or buyers, greatly appreciate illustrations of abstract concepts. • The Body: Finally, we must formulate the program's body. That is, we must replace the ``...'' in our header with an expression. The expression computes the answer from the parameters, using Scheme's basic operations and Scheme programs that we already defined or intend to define. We can only formulate the program's body if we understand how the program computes the output from the given inputs. If the input-output relationship is given as a mathematical formula, we just translate mathematics into Scheme. If, instead, we are given a word problem, we must craft the expression carefully. To this end, it is helpful to revisit the examples from the second step and to understand how we computed the outputs for specific inputs. In our running example, the computational task was given via an informally stated formula that reused area-of-disk, a previously defined program. Here is the translation into Scheme: (define (area-of-ring outer inner) (- (area-of-disk outer) (area-of-disk inner))) • Testing: After we have completed the program definition, we must still test the program. At a minimum, we should ensure that the program computes the expected outputs for the program examples. To facilitate testing, we may wish to add the examples to the bottom TEAMFLY TEAM FLY PRESENTS
of the Definitions window as if they were equations. Then, when we click the Execu button,they are evaluated, and we see whether the program works properly on them. e Testing cannot show that a program produces the correct outputs for all possible inputs ecause there are typically an infinite number of possible inputs. But testing can reveal syntax errors, run-time problems, and logical mistakes For faulty outputs, we must pay special attention to our program examples. It is possible that the examples are wrong; that the program contains a logical mistake; or that both the examples and the program are wrong. In either case, we may have to step through the entire program development again Figure 3 shows what we get after we have developed the program according to our recipe Figure 4 summarizes the recipe in tabular form. It should be consulted whenever we design a program Phase activity Contrac to name the choose a name that fits the problem sstudy the problem Purpose and function for clues on how many unknown"givens"the function specify its consumes pick one variable per input; if possible,use classes of names that are mentioned for the "givens"in the problem input data and statement .describe what the function should produce using the chosen variables names formulate the contract class of output and header to describe its from xl purpose (define (name xl formulat Examples to characterize search the problem statement for examples work through the input the examples ,validate the results, if possible emake up utput relationship via Body to define the formulate how the function computes its results -develop function a Scheme expression that uses Scheme's primitive operations,other functions, and the variables stranslate the mathematical expressions in the problem statement when available Test cover apply the function to the inputs of the examples scheck mistakes that the outputs are as predict C typos"and logic) Figure 4: The design recipe at a glance -32- TEAM FLY PRESENTS
-32- of the Definitions window as if they were equations. Then, when we click the Execute button, they are evaluated, and we see whether the program works properly on them. Testing cannot show that a program produces the correct outputs for all possible inputs -- because there are typically an infinite number of possible inputs. But testing can reveal syntax errors, run-time problems, and logical mistakes. For faulty outputs, we must pay special attention to our program examples. It is possible that the examples are wrong; that the program contains a logical mistake; or that both the examples and the program are wrong. In either case, we may have to step through the entire program development again. Figure 3 shows what we get after we have developed the program according to our recipe. Figure 4 summarizes the recipe in tabular form. It should be consulted whenever we design a program. Phase Goal Activity Contract Purpose and Header to name the function; to specify its classes of input data and its class of output data; to describe its purpose; to formulate a header choose a name that fits the problem study the problem for clues on how many unknown ``givens'' the function consumes pick one variable per input; if possible, use names that are mentioned for the ``givens'' in the problem statement describe what the function should produce using the chosen variables names formulate the contract and header: ;; name : number ...--> number ;; to compute ... from x1 ... (define (name x1 ...) ...) Examples to characterize the inputoutput relationship via examples search the problem statement for examples work through the examples validate the results, if possible make up examples Body to define the function formulate how the function computes its results develop a Scheme expression that uses Scheme's primitive operations, other functions, and the variables translate the mathematical expressions in the problem statement, when available Test to discover mistakes (``typos'' and logic) apply the function to the inputs of the examples check that the outputs are as predicted Figure 4: The design recipe at a glance TEAMFLY TEAM FLY PRESENTS
The design recipe is not a magic bullet for the problems we encounter during the design of a program. It provides some guidance for a process that can often appear to be overwhelming. The most creative and most difficult step in our recipe concerns the design of the programs body.At this point, it relies heavily on our ability to read and understand written material, on our ability to extract mathematical relationships, and on our knowledge of basic facts. None of these skills is how much computing can contribute to this most complicated step %.exploit is specific to the specific to the development of computer programs; the knowledge we exploit is specific to the Domain Knowledge: Formulating the body of a program often requires knowledge about the area, also known as domain, from which the problem is drawn. This form of knowledge is called DOMAIN KNOWLEDGE. It may have to be drawn from simple mathematics, such as arithmetic, from complex mathematics, such as differential equations, or from non-mathematical disciplines music, biology, civil engineering, art, and so on Because programmers cannot know all of the application domains of computing, they must be prepared to understand the language of a variety of application areas so that they can discuss problems with domain experts. The language is often that of mathematics, but in some cases, the programmers must invent a language, especially a data language for the application area. For that reason, it is imperative that programmers have a solid understanding of the full possibilities of computer languages A Another advantage of Scheme's notation is that we always know where to place an operator or where to find it: to the immediate right of the opening parenthesis. This is important in computing because we need many more operators than just the few numerical operators that we use in arithmetic and algebra 5 It is common to speak ofthe area-of a circle, but mathematically speaking, the circle is only the disk's outer edge An arrow is keyed in as - followed by This statement is true for any other programming language as well, for example, spreadsheet languages, C, word processor macro. Scheme is simpler than most of these and easy to understand for computers. Unfortunately, to human beings who grow up on infix expressions such as 5+ 4, Scheme prefix expressions such as (+5 4)initially appear to be complicated. A bit of practice will quickly eliminate this misconception 2 We will find out in section why such errors are called syntax errors As we will see later, the order is not completely fixed. It is possible, and for a number of reasons, desirable to switch the order of some steps in some cases An arrow is keyed in as-followed by I Others also call them FORMAL ARGUMENTS or INPUT VARIABLES -33 TEAM FLY PRESENTS
-33- The design recipe is not a magic bullet for the problems we encounter during the design of a program. It provides some guidance for a process that can often appear to be overwhelming. The most creative and most difficult step in our recipe concerns the design of the program's body. At this point, it relies heavily on our ability to read and understand written material, on our ability to extract mathematical relationships, and on our knowledge of basic facts. None of these skills is specific to the development of computer programs; the knowledge we exploit is specific to the application domain in which we are working. The remainder of the book will show what and how much computing can contribute to this most complicated step. Domain Knowledge: Formulating the body of a program often requires knowledge about the area, also known as domain, from which the problem is drawn. This form of knowledge is called DOMAIN KNOWLEDGE. It may have to be drawn from simple mathematics, such as arithmetic, from complex mathematics, such as differential equations, or from non-mathematical disciplines: music, biology, civil engineering, art, and so on. Because programmers cannot know all of the application domains of computing, they must be prepared to understand the language of a variety of application areas so that they can discuss problems with domain experts. The language is often that of mathematics, but in some cases, the programmers must invent a language, especially a data language for the application area. For that reason, it is imperative that programmers have a solid understanding of the full possibilities of computer languages. 4 Another advantage of Scheme's notation is that we always know where to place an operator or where to find it: to the immediate right of the opening parenthesis. This is important in computing because we need many more operators than just the few numerical operators that we use in arithmetic and algebra. 5 It is common to speak of the area of a circle, but mathematically speaking, the circle is only the disk's outer edge. 6 An arrow is keyed in as - followed by >. 7 This statement is true for any other programming language as well, for example, spreadsheet languages, C, word processor macro. Scheme is simpler than most of these and easy to understand for computers. Unfortunately, to human beings who grow up on infix expressions such as 5 + 4, Scheme prefix expressions such as (+ 5 4) initially appear to be complicated. A bit of practice will quickly eliminate this misconception. 8 We will find out in section 8 why such errors are called syntax errors. 9 As we will see later, the order is not completely fixed. It is possible, and for a number of reasons, desirable to switch the order of some steps in some cases. 10 An arrow is keyed in as - followed by >. 11 Others also call them FORMAL ARGUMENTS or INPUT VARIABLES. TEAMFLY TEAM FLY PRESENTS
Section 3 Programs are function plus variable Definitions In general, a program consists not just of one, but of many definitions. The area-of-ring program, for example, consists of two definitions: the one for area-of-ring and another one for area-of-disk. We refer to both as FUNCTION DEFINITIONS and, using mathematical terminology in a loose way, say that the program is coMPOSED of several functions. Because the first one, area-of ring, is the function we really wish to use, we refer to it as the MAIN FUNCTION, the second one area-of-disk. is an AUXILIARY FUNCTION The use of auxiliary functions makes the design process manageable and renders programs readable. Compare the following two versions of area -of-ring (define (area-of-ring outer inner (define area-of -ring outer inner (-(area-of-disk outer outer outer)) (area-of-disk inner))) Inner x)))) The definition on the left composes auxiliary functions. Designing it helped us break up the original problem into smaller, more easily solvable problems. Reading it reminds us of our In contrast, the definition on the right requires a reader to reconstruct the idea that the two hole reasoning that the area is the difference between the area of the full disk and the area of the hole Expressions compute the afea ef two disks. Furthermore, we would have had to produce the right definition in one monolithic block without benefit of dividing the problem-solving process into smaller steps For a small program such as area-of-ring, the differences between the two styles are minor For large programs, however, using auxiliary functions is not an option but a necessity. That is even if we are asked to write a single program, we should consider breaking it up into several small programs and CoMPOSING them as needed. although we are not yet in a position to devel&& e truly large programs, we can still get a feeling for the idea by developing two versions in parallel The first subsection contrasts the two development styles with an example from the business domain. It demonstrates how breaking up a program into several function definitions can greatly increase our confidence in the correctness of the overall program. The second subsection introduces the concept of a variable definition, which is an additional important ingredient for the development of programs. The last subsection proposes some exercises 3.1 Composing Functions onsider the following problem -34- TEAM FLY PRESENTS
-34- Section 3 Programs are Function Plus Variable Definitions In general, a program consists not just of one, but of many definitions. The area-of-ring program, for example, consists of two definitions: the one for area-of-ring and another one for area-of-disk. We refer to both as FUNCTION DEFINITIONs and, using mathematical terminology in a loose way, say that the program is COMPOSED of several functions. Because the first one, area-ofring, is the function we really wish to use, we refer to it as the MAIN FUNCTION; the second one, area-of-disk, is an AUXILIARY FUNCTION. The use of auxiliary functions makes the design process manageable and renders programs readable. Compare the following two versions of area-of-ring: (define (area-of-ring outer inner) (- (area-of-disk outer) (area-of-disk inner))) (define (area-of-ring outer inner) (- (* 3.14 (* outer outer)) (* 3.14 (* inner inner)))) The definition on the left composes auxiliary functions. Designing it helped us break up the original problem into smaller, more easily solvable problems. Reading it reminds us of our reasoning that the area is the difference between the area of the full disk and the area of the hole. In contrast, the definition on the right requires a reader to reconstruct the idea that the two subexpressions compute the area of two disks. Furthermore, we would have had to produce the right definition in one monolithic block, without benefit of dividing the problem-solving process into smaller steps. For a small program such as area-of-ring, the differences between the two styles are minor. For large programs, however, using auxiliary functions is not an option but a necessity. That is, even if we are asked to write a single program, we should consider breaking it up into several small programs and COMPOSING them as needed. Although we are not yet in a position to develop truly large programs, we can still get a feeling for the idea by developing two versions in parallel. The first subsection contrasts the two development styles with an example from the business domain. It demonstrates how breaking up a program into several function definitions can greatly increase our confidence in the correctness of the overall program. The second subsection introduces the concept of a variable definition, which is an additional important ingredient for the development of programs. The last subsection proposes some exercises. 3.1 Composing Functions Consider the following problem: TEAMFLY TEAM FLY PRESENTS
Imagine the owner of a movie theater who has complete freedom in setting ticket prices. The more he charges, the fewer the people who can afford tickets. In a recent experiment the owner determined a precise relationship between the price of a ticket and average attendance. At a price of $5.00 per ticket, 120 people attend a performance Decreasing the price by a dime($.10) increases attendance by 15. Unfortunately the increased attendance also comes at an increased cost. Every performance costs the owner $180. Each attendee costs another four cents($0.04) The owner would like to know the exact relationship between profit and ticket price so that he can determine the price at which he can make the highest profit While the task is clear, how to go about it is not. All we can say at this point is that several quantities depend on each other When we are confronted with such a situation, it is best to tease out the various dependencies one at a time 1. Profit is the difference between revenue and costs 2. The revenue is exclusively generated by the sale of tickets. It is the product of ticket price and number of attendees 3. The costs consist of two parts: a fixed part($180)and a variable part that depends on the number of attendees 4. Finally, the problem statement also specifies how the number of attendees depends on the ticket price Let's formulate a function for each of these dependencies, after all, functions compute how quantities depend on each other We start with contracts, headers, and purpose statements. Here is the one for profit profit: numb ompute the between reve. at some gIve i (define (profit ticket<price It depends on the ticket price because both revenue and cost depend on the ticket price. Here are the remaining three number - number ;; to compute the revenue, given ticket-price (define (revenue ticket-price) Cos numbe ii to compute the costs, given ticket-price (define (cost ticket attendees number - number to compute the number of attendees, given ticket-price (define (attendees ticket-price) Each purpose statement is a rough transliteration of some part of the problem statement Exercise 3. 1.1. The next step is to make up examples for each of the functions. Determine how many attendees can afford a show at a ticket price of $3.00, $4.00, and $5.00. Use the examples to formulate a general rule that shows how to compute the number of attendees from the ticket price Make up more examples if needed -35- TEAM FLY PRESENTS
-35- Imagine the owner of a movie theater who has complete freedom in setting ticket prices. The more he charges, the fewer the people who can afford tickets. In a recent experiment the owner determined a precise relationship between the price of a ticket and average attendance. At a price of $5.00 per ticket, 120 people attend a performance. Decreasing the price by a dime ($.10) increases attendance by 15. Unfortunately, the increased attendance also comes at an increased cost. Every performance costs the owner $180. Each attendee costs another four cents ($0.04). The owner would like to know the exact relationship between profit and ticket price so that he can determine the price at which he can make the highest profit. While the task is clear, how to go about it is not. All we can say at this point is that several quantities depend on each other. When we are confronted with such a situation, it is best to tease out the various dependencies one at a time: 1. Profit is the difference between revenue and costs. 2. The revenue is exclusively generated by the sale of tickets. It is the product of ticket price and number of attendees. 3. The costs consist of two parts: a fixed part ($180) and a variable part that depends on the number of attendees. 4. Finally, the problem statement also specifies how the number of attendees depends on the ticket price. Let's formulate a function for each of these dependencies; after all, functions compute how quantities depend on each other. We start with contracts, headers, and purpose statements. Here is the one for profit: ;; profit : number -> number ;; to compute the profit as the difference between revenue and costs ;; at some given ticket-price (define (profit ticket-price) ...) It depends on the ticket price because both revenue and cost depend on the ticket price. Here are the remaining three: ;; revenue : number -> number ;; to compute the revenue, given ticket-price (define (revenue ticket-price) ...) ;; cost : number -> number ;; to compute the costs, given ticket-price (define (cost ticket-price) ...) ;; attendees : number -> number ;; to compute the number of attendees, given ticket-price (define (attendees ticket-price) ...) Each purpose statement is a rough transliteration of some part of the problem statement. Exercise 3.1.1. The next step is to make up examples for each of the functions. Determine how many attendees can afford a show at a ticket price of $3.00, $4.00, and $5.00. Use the examples to formulate a general rule that shows how to compute the number of attendees from the ticket price. Make up more examples if needed. TEAMFLY TEAM FLY PRESENTS