When a programmer studies a new language, the first item of business is the language’s “arithmetic,” meaning its basic forms of data and the operations that a program can perform on this data. At the same time, we need to learn how to express data and how to express operations on data.
write down the name of a primitive operation op,
write down the arguments, separated by some space, and
write down ")".
(+ 1 2)
It is not necessary to read and understand the entire chapter in order to make progress. As soon as you sense that this chapter is slowing you down, move on to the next one. Keep in mind, though, that you may wish to return here and find out more about the basic forms of data in BSL when the going gets rough.
The rest of this chapter introduces four forms of data: numbers, strings, images, and Boolean values. It also illustrates how these forms of data are manipulated with primitive operations, often called built-in operations or primitives. Because of the nature of BSL, this book also refers to primitives as functions though you will need to read the remaining chapters of this first part to understand the reason for this terminology.
Most people think “numbers” and “operations on numbers” when they hear “arithmetic.” “Operations on numbers” means adding two numbers to yield a third; subtracting one number from another; or even determining the greatest common divisor of two numbers. If we don’t take arithmetic too literally, we may even include the sine of an angle, rounding a real number to the closest integer, and so on.
The BSL language supports Numbers and arithmetic in all these forms. As discussed in the Prologue, an arithmetic operation such as + is used like this:
(+ 3 4)
that is, in prefix notation form. Here are some of the operations on numbers that our language provides: +, -, *, /, abs, add1, ceiling, denominator, exact->inexact, expt, floor, gcd, log, max, numerator, quotient, random, remainder, sqr, and tan. We picked our way through the alphabet, just to show the variety of operations. Explore what these do in the interactions area, and then find out how many more there are and what they do.
If you need an operation on numbers that you know from grade school or high school, chances are that BSL knows about it, too. Guess its name and experiment in the interaction area. Say you need to compute the sin of some angle; try
> (sin 0)
and use it happily ever after. Or look in the HelpDesk. You will find there that in addition to operations, BSL also recognizes the names of some widely used numbers, for example, pi and e.You might not know e if you have not studied calculus. It’s a real number, close to 2.718, commonly called “Euler’s constant.”
When it comes to numbers, BSL programs may use natural numbers, integers, rational numbers, real numbers, and complex numbers. We assume that you have heard of the first four. The last one may have been mentioned in your high school. If not, don’t worry; while complex numbers are useful for all kinds of calculations, a novice doesn’t have to know about them.
A truly important distinction concerns the precision of numbers. For now, it is important to understand that BSL distinguishes exact numbers and inexact numbers. When it calculates with exact numbers, BSL preserves this precision whenever possible. For example, (/ 4 6) produces the precise fraction 2/3, which DrRacket can render as a proper fraction, an improper fraction, or as a mixed decimal. Play with your computer’s mouse to find the menu that changes the fraction into decimal expansion and other presentations.
Some of BSL’s numeric operations cannot produce an exact result. For example, using the sqrt operation on 2 produces an irrational number that cannot be described with a finite number of digits. Because computers are of finite size and BSL must somehow fit such numbers into the computer, it chooses an approximation: #i1.4142135623730951. As mentioned in the Prologue, the #i prefix warns novice programmers of this lack of precision. While most programming languages choose to reduce precision in this manner, few advertise it and fewer even warn programmers.
Exercise 1: The direct goal of this exercise is to create an expression that computes the distance of some specific Cartesian point (x,y) from the origin (0,0). The indirect goal is to introduce some basic programming habits, especially the use of the interactions area to develop expressions.The values for x and y are given as definitions in the definitions area (top half) of DrRacket:The expected result for these values is 5 but your expression should produce the correct result even after you change these definitions.Just in case you have not taken geometry courses or in case you forgot the formula that you encountered there, the point (x,y) has the distancefrom the origin. After all, we are teaching you how to design programs not how to be a geometer.To develop the desired expression, it is best to hit RUN and to experiment in the interactions area. The RUN action tells DrRacket what the current values of x and y are so that you can experiment with expressions that involve x and y:Once you have the expression that produces the correct result, copy it from the interactions area to the definitions area, right below the two variable definitions.
To confirm that the expression works properly, change the two definitions so that x represents 12 and y stands for 5. If you click RUN now, the result should be 13.
Your mathematics teacher would say that you computed the distance formula. To use the formula on alternative inputs, you need to open DrRacket, edit the definitions of x and y so they represent the desired coordinates, and click RUN. But this way of reusing the distance formula is cumbersome and naive. Instead, we will soon show you a way to define functions, which makes re-using formulas straightforward. For now, we use this kind of exercise to call attention to the idea of functions and to prepare you for programming with them.
A wide-spread prejudice about computers concerns its innards. Many believe
that it is all about bits and bytes—
Programming languages are about calculating with information, and information comes in all shapes and forms. For example, a program may deal with colors, names, business letters, or conversations between people. Even though we could encode this kind of information as numbers, it would be a horrible idea. Just imagine remembering large tables of codes, such as 0 means “red” and 1 means “hello,” etc.
Instead most programming languages provide at least one kind of data that deals with such symbolic information. For now, we use BSL’s strings. Generally speaking, a String is a sequence of the characters that you can enter on the keyboard enclosed in double quotes, plus a few others, about which we aren’t concerned just yet. In Prologue: How to Program, we have seen a number of BSL strings: "hello", "world", "blue", "red", etc. The first two are words that may show up in a conversation or in a letter; the others are names of colors that we may wish to use.
> (string-append "what a " "lovely " "day" " for learning BSL")
"what a lovely day for learning BSL"
Then use string primitives to create an expression that concatenates prefix and suffix and adds "_" between them. When you run this program, you will see "hello_world" in the interactions area.
See exercise 1 for how to create expressions using DrRacket.
> (string-length 42)
string-length: expects a string, given 42
Then create an expression using string primitives that adds "_" at position i. In general this means the resulting string is longer than the original one; here the expected result is "hello_world".Position means i characters from the left of the string—
but computer scientists start counting at 0. Thus, the 5th letter in this example is "w", because the 0th letter is "h". Hint: when you encounter such “counting problems” you may wish to add a string of digits below str to help with counting:
See exercise 1 for how to create expressions in DrRacket.
Exercise 4: Use the same setup as in exercise 3. Then create an expression that deletes the ith position from str. Clearly this expression creates a shorter string than the given one; contemplate which values you may choose for i.
Images represent symbolic data somewhat like strings. To work with images, use the "2htdp/image" teachpack. Like strings, you used DrRacket to insert images wherever you would insert an expression into your program, because images are values just like numbers and strings.
circle produces a circle image from a radius, a mode string, and a color string;
ellipse produces an ellipse from two radii, a mode string, and a color string;
line produces a line from two points and a color string;
rectangle produces a rectangle from a width, a height, a mode string, and a color string;
text produces a text image from a string, a font size, and a color string; and
triangle produces an upward-pointing equilateral triangle from a size, a mode string, and a color string.
> (star 12 "solid" "green")
A proper understanding of the third kind of image primitives—
overlay/xy is like overlay but accepts two numbers—
x and y— between two image arguments. It shifts the second image by x pixels to the right and y pixels down — all with respect to the images’ anchor points. Of course, the image is shifted left for a negative x and up for a positive y.
empty-scene creates an framed rectangle of a specified width and height;
place-image places an image into a scene at a specified position. If the image doesn’t fit into the given scene, it is appropriately cropped.
add-line consumes an scene, four numbers, and a color to draw a line of that color into the given image. Again, experiment with it to find out how the four arguments work together.
(define cat )Create an expression that computes the area of the image. See exercise 1 for how to create expressions in DrRacket.
We need one last kind of primitive data before we can design programs: Boolean values. There are only two kinds of Boolean values: true and false. Programs use Boolean values for representing decisions or the status of switches.
- and not always picks the Boolean that isn’t given:
Create an expression that computes whether b1 is false or b2 is true. So in this particular case, the answer is false. (Why?)
(define x 2)
(define x 0)
Strings aren’t compared with = and its relatives. Instead, you must use string=? or string<=? or string>=? if you are ever in a position where you need to compare strings. While it is obvious that string=? checks whether the two given strings are equal, the other two primitives are open to interpretation. Look up their documentation, or experiment with them, guess, and then check in the documentation whether you guessed right.
The next few chapters introduce better expressions than if to express conditional computations and, most importantly, systematic ways for designing them.
(define cat )Create an expression that computes whether the image is "tall" or "wide". An image should be labeled "tall" if its height is larger or equal to its width; otherwise it is "wide". See exercise 1 for how to create expressions in DrRacket; as you experiment, replace the image of the cat with rectangles of your choice to ensure you know the expected answer.
Now try the following modification. Create an expression that computes whether a picture is "tall", "wide", or "square".
In addition to predicates that distinguish different forms of data, programming languages also come with predicates that distinguish different kinds of numbers. In BSL, numbers are classified in two ways: by construction and by their exactness. Construction refers to the familiar sets of numbers: integer?, rational?, real?, and complex?. You may know these terms from secondary school.Evaluate (sqrt -1) in the interactions area and take a close look at the result. The result you see is the first so-called complex number anyone encounters. While your mathematics teacher may have told you that one doesn’t compute the square root of negative numbers, truth is that real mathematicians and programmers find it acceptable and useful to do so anyway. But don’t worry: understanding complex numbers is not essential to being a programmer. As for exactness, we have mentioned the idea before. For now, experiment with exact? and inexact? to make sure they perform the checks that their names suggest. Later we are going to discuss the nature of numbers in some detail.
(define in "hello")Then create an expression that converts whatever in represents to a number. For a string, it determines how long the string is; for an image, it uses the area; for a number, it decrements the number, unless it is already 0 or negative; for true it uses 10 and for false 20.
See exercise 1 for how to create expressions in DrRacket.
As far as programming is concerned, arithmetic is half the game. The other half is “algebra.” Of course, our notion of “algebra” relates to the school notion of algebra just as much as the notion of “arithmetic” from the preceding chapter relates to the ordinary notion of grade-school arithmetic. The creation of real programs involves variables and thus functions, meaning basic notions from algebra. Once we can deal with functions, we can move on to programs, which “compose” functions to achieve their overall purpose.
From a high-level perspective, a program is a function. A program, like a function in mathematics, consumes inputs, and it produces outputs. In contrast to mathematical functions, programs work with a whole variety of data: numbers, strings, images, and so on. Furthermore, programs may not consume all of the data at once; instead a program may incrementally request more data or not, depending on what the computation needs. Last but not least, programs are triggered by external events. For example, a scheduling program in an operating system may launch a monthly payroll program on the last day of every month. Or, a spreadsheet program may react to certain events on the keyboard with filling some cells with numbers.
Definitions: While many programming languages obscure the relationship between programs and functions, BSL brings it to the fore. Every BSL programs consists of definitions, usually followed by an expression that involves those definitions. There are two kinds of definitions:
constant definitions, of the shape (define AVariable AnExpression), which we encountered in the preceding chapter; and
function definitions, which come in many flavors, one of which we used in the Prologue.
the name of the function,
followed by one or more variables, separated by space and ending in “)”,
and an expression followed by “)”.
Before we explain why these examples are silly, we need to explain what
function definitions mean. Roughly speaking, a function definition
introduces a new operation on data; put differently, it adds an operation
to our vocabulary if we think of the primitive operations as the ones that
are always available. Like a primitive function, a defined function
consumes inputs. The number of variables determines how many inputs—
The examples are silly because the expressions inside the functions do not involve the variables. Since variables are about inputs, not mentioning them in the expressions means that the function’s output is independent of their input. We don’t need to write functions or programs if the output is always the same.
(define x 3)
For now, the only remaining question is how a function obtains its inputs. And to this end, we turn to the notion of applying a function.
write down the name of a defined function f,
write down as many arguments as f consumes, separated by some space, and
write down “)”.
> (f 1)
> (f 2)
> (f "hello world")
> (f true)
f: expects 1 argument, but found none
> (f 1 2 3 4 5)
f: expects only 1 argument, but found 5
+: expects at least 2 arguments, but found none
Evaluating a function application proceeds in three steps. First, DrRacket determines the values of the argument expressions. Second, it checks that the number of arguments and the number of function parameters (inputs) are the same. If not, it signals an error. Finally, if the number of actual inputs is the number of expected inputs, DrRacket computes the value of the body of the function, with all parameters replaced by the corresponding argument values. The value of this computation is the value of the function application.
> (opening "Matthew" "Krishnamurthi")
To summarize, this section introduces the notation for function
In exercise 1 you developed the right-hand side for this function. All you really need to do is add a function header. Remember this idea in case you are ever stuck with a function. Use the recipe of exercise 1 to develop the expression in the interactions area, and then write down the function definition.
Exercise 17: Define the function bool-imply. It consumes two Boolean values, call them b1 and b2. The answer of the function is true if b1 is false or b2 is true. Note: Logicians call this Boolean operation implication and often use the symbol =>, pronounced “implies,” for this purpose. While BSL could define a function with this name, we avoid that name because it is too similar to the comparison operations for numbers <= and >=, and it would thus easily be confused. See exercise 9.
Exercise 18: Define the function image-area, which computes the area of a given image. Note: The area is also the number of pixels in the picture. See exercise 5 for ideas.
Exercise 19: Define the function image-classify, which consumes an image and produces "tall" if the image is taller than it is wide, "wide" if it is wider than it is tall, or "square" if its width and height are the same. See exercise 10 for ideas.
Exercise 20: Define the function string-join, which consumes two strings and appends them with "_" in between. See exercise 2 for ideas.
Exercise 21: Define the function string-insert, which consumes a string and a number i and which inserts "_" at the ith position of the string. Assume i is a number between 0 and the length of the given string (inclusive). See exercise 3 for ideas. Also ponder the question how string-insert ought to cope with empty strings.
Exercise 22: Define the function string-delete, which consumes a string and a number i and which deletes the ith position from str. Assume i is a number between 0 (inclusive) and the length of the given string (exclusive). See exercise 4 for ideas. Can string-delete deal with empty strings?
A program rarely consists of a single function definition and an
application of that function. Instead, a typical program consists of a
“main” function or a small collection of “main event handlers.” All of
these use other functions—
(define (letter fst lst signature-name) (string-append (opening fst) "\n\n" (body fst lst) "\n\n" (closing signature-name))) (define (opening fst) (string-append "Dear " fst ",")) (define (body fst lst) (string-append "We have discovered that all people with the last name " "\n" lst " have won our lottery. So, " fst ", " "\n" "hurry and pick up your prize.")) (define (closing signature-name) (string-append "Sincerely," "\n\n" signature-name))
> (letter "Matthew" "Krishnamurthi" "Felleisen")
"Dear Matthew,\n\nWe have discovered that all people with the last name \n\nKrishnamurthi have won our lottery. So, Matthew, hurry \n\nand pick up your prize.\n\nSincerely,\n\nFelleisen"
In general, when a problem refers to distinct tasks of computation, a program should consist of one function per task and a main function that puts it all together. We formulate this idea as a simple slogan:
Define one function per task.
The advantage of following this slogan is that you get reasonably small functions, each of which is easy to comprehend, and whose composition is easy to understand. Later, we see that creating small functions that work correctly is much easier than creating one large function. Better yet, if you ever need to change a part of the program due to some change to the problem statement, it tends to be much easier to find the relevant program parts when it is organized as a collection of small functions.
Here is a small illustration of this point with a sample problem:
Sample Problem: Imagine the owner of a monopolistic movie theater. He has complete freedom in setting ticket prices. The more he charges, the fewer the people who can afford tickets. The less he charges, the more it costs to run a show because attendance goes up. In a recent experiment the owner determined a relationship between the price of a ticket and average attendance.At a price of $5.00 per ticket, 120 people attend a performance. For each 10-cent change in the ticket price, the average attendance changes by 15 people. That is, if the owner charges $5.10, some 105 people attend on the average; if the prices goes down to $4.90, average attendance increases to 135. Let us translate this idea into a mathematical formula:
avg. attendance = 120 - (change in price * (15 people / 0.10))Stop! Explain the minus sign before you proceed.
Unfortunately, the increased attendance also comes at an increased cost. Every performance comes at a fixed costs of $180 to the owner plus a variable cost of $0.04 per attendee.
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.
The problem statement specifies how the number of attendees depends on the ticket price. Computing this number is clearly a separate task and thus deserves its own function definition:The function mentions the four constants—
120, 5.0, 15, and 0.1— determined by the owner’s experience.
The revenue is exclusively generated by the sale of tickets, meaning it is exactly the product of ticket price and number of attendees:The number of attendees is calculated by the attendees function of course.
The costs consist of two parts: a fixed part ($180) and a variable part that depends on the number of attendees. Given that the number of attendees is a function of the ticket price, a function for computing the cost of a show also consumes the price of a ticket and uses it to compute the number of tickets sold with attendees:Again, this function also uses attendees to determine the number of attendees.
Finally, profit is the difference between revenue and costs:
Even the definition of profit suggests that we use the functions revenue and cost. Hence, the profit function must consume the price of a ticket and hand this number to the two functions it uses.
Exercise 23: Our solution to the sample problem contains several constants in the middle of functions. As One Program, Many Definitions already points out, it is best to give names to such constants so that future readers understand where these numbers come from. Collect all definitions in DrRacket’s definitions area and change them so that all magic numbers are refactored into constant definitions.
Exercise 24: Determine the potential profit for the following ticket prices: $1, $2, $3, $4, and $5. Which price should the owner of the movie theater choose to maximize his profits? Determine the best ticket price down to a dime.
Exercise 25: After studying the costs of a show, the owner discovered several ways of lowering the cost. As a result of his improvements, he no longer has a fixed cost. He now simply pays $1.50 per attendee.
Modify both programs to reflect this change. When the programs are modified, test them again with ticket prices of $3, $4, and $5 and compare the results.
a batch program consumes all of its inputs at once and computes its result. Its main function composes auxiliary functions, which may refer to additional auxiliary functions, and so on. When we launch a batch program, the operating system calls the main function on its inputs and waits for the program’s output.
an interactive program consumes some of its inputs, computes, produces some output, consumes more input, and so on. We call the appearance of an input an event, and we create interactive programs as event-driven programs. The main function of such an event-driven program uses an expression to describe which functions to call for which kinds of events. When we launch an interactive program, the main function informs the operating system of this description, then the operating system calls the matching functions when the next input shows up. The operating system also knows how to present the result of these function calls as output.
In this section we present simple examples of both batch and interactive programs. Before we do so, however, we need one more ingredient: constant definitions.
write “(define ”,
write down the name of the variable ...
followed by a space and an expression, and
write down “)”.
; temperature (in deg F) when water freezes: (define FREEZING 32) ; useful to compute the area of a disk: (define ALMOST-PI 3.14) ; a blank line: (define NL "\n") ; an empty scene: (define MT (empty-scene 100 100))
Batch Programs: As mentioned, a batch program consumes all of its inputs at once and computes the result from these inputs. Its main function may expect the arguments themselves or the names of files from which to retrieve the inputs; similarly, it may just return the output or it may place it in a file.
Once programs are created, we want to use them. In DrRacket, we launch batch programs in the interactions area so that we can watch the program at work.
Programs are even more useful if they can retrieve the input from some file and deliver the output to some other file. The name batch program originated from the early days of computing when a program read an entire file (or several files) and placed the result in some other file(s), without any intervention after the launch. Conceptually, we can think of the program as reading an entire file at once and producing the result file(s) all at once.
> (read-file "sample.dat")
> (write-file 'stdout "212")
Let us illustrate the creation of a batch program with a simple example. Suppose we wish to create a program that converts a temperature measured on a Fahrenheit thermometer into a Celsius temperature. Don’t worry, this question isn’t a test about your physicsThis book is not about memorizing facts, but we do expect you to know where to find them. Do you know where to find out how temperatures are converted? knowledge; here is the conversion formula:
Naturally in this formula f is the Fahrenheit temperature and c is the Celsius temperature. Translating this into BSL is straightforward:
Recall that 5/9 is a number, a rational fraction to be precise, and more importantly, that c depends on the given f, which is what the function notation expresses.
> (f2c 32)
> (f2c 212)
> (f2c -40)
(read-file in) retrieves the content of the file called in as a string;
string->number turns this string into a number;
f2c interprets the number as a Fahrenheit temperature and converts it into a Celsius temperature;
number->string consumes this Celsius temperature and turns it into a string;
> (convert "sample.dat" 'stdout)
> (convert "sample.dat" "out.dat")
> (read-file "out.dat")
(define (convert in out) (write-file out (number->string (f2c (string->number (read-file in)))))) (define (f2c f) (* 5/9 (- f 32))) (convert "sample.dat" "out.dat")
In addition to running the batch program, it is also instructive to step through the computation. Make sure that the file "sample.dat" exists and contains just a number, then click the STEP button in DrRacket. Doing so opens another window in which you can peruse the computational process that the call to the main function of a batch program triggers. You will see that the process follows the above outline.
Exercise 26: Recall the letter program from Composing Functions. We launched this program once, with the inputs "Matthew", "Krishnamurthi", and "Felleisen". Here is how to launch the program and have it write its output to the interactions area:
> (write-file 'stdout (letter "Matthew" "Krishnamurthi" "Felleisen"))
We have discovered that all people with the last name
Krishnamurthi have won our lottery. So, Matthew,
hurry and pick up your prize.
'stdoutOf course, programs are useful because you can launch them for many different inputs, and this is true for letter, too. Stop! Run letter on the following three inputs:
"Robby" "Flatt" "Felleisen"
"Christopher" "Columbus" "Felleisen"
"ZC" "Krishnamurthi" "Flatt"From here it is a short step to a simple batch program that reads names from three files and writes a letter to one:
(define (main in-fst in-lst in-signature out) (write-file out (letter (read-file in-fst) (read-file in-lst) (read-file in-signature))))The function consumes four strings: the first three are the names of input files and the last one serves as output file. It uses the first three to read one string each from the three named files, hands these strings to letter, and eventually writes the result of this function call into the file named by out, the fourth argument to main.
Create appropriate files, launch main, and check whether it delivers the expected letter.
Note: Once you understand Programming With Lists, you will be able to use other functions from "batch-io", and then you will have no problem writing letters for tens of thousands of lucky lottery winners.
Interactive Programs: No matter how you look at it, batch programs are old-fashioned. Even if businesses have used them for decades to automate useful tasks, people prefer interactive programs. Indeed, in this day and age, people mostly interact with programs via a keyboard and a mouse generating input events such as key presses or mouse clicks. Furthermore, interactive programs can also react to computer-generated events, for example, clock ticks or the arrival of a message from some other computer.
Designing an interactive program requires more work than designing a batch program. Specifically, an interactive program designates some function as the one that takes care of keyboard events, another function for dealing with clock tick, a third one for presenting the current state as an image, and so forth. It is the task of an interactive program’s main function to communicate these designations to the operating system, that is, the software platform on which the program is launched.
In BSL, the "universe" teachpack provides this communication mechanisms. For now, the key mechanism is the big-bang expression. It describes to DrRacket how the interactive program deals with clock ticks, key presses, mouse clicks, and so on. A big-bang expression consists of one required subexpression and one required clause. The subexpression evaluates to the initial state of the program, and the required clause tells DrRacket how to render the current state as a program.
> (number->square 5) > (number->square 10) > (number->square 20)
every time the clock ticks, subtract 1 from the current state;
then check whether zero? is true of the new state and if so, stop; and
every time the state changes, use number->square to render it as an image.
With this explanation, you may wish to re-examine Prologue: How to Program because it shows several interactive programs. Like a batch program, an interactive program comes with a main function; unlike a batch program, the main program of an interactive program almost always uses a big-bang expression to install event handling functions, which are defined separately.
In addition to to-draw, on-tick, and stop-when clauses, a world program may also specify on-key and on-mouse clauses. With on-key an interactive program can react to key strokes, and with on-mouse it can treat mouse clicks. For now, all you need to know that on-key needs a function that takes two inputs: the current world and a string, which represents the key stroke.
> (place-dot-at 89) > (place-dot-at 22) > (stop 89 "q")
> (main 90)
By now, you may feel that these first two chapters are somewhat overwhelming and that they introduced just too many new concepts. That is correct. To overcome this feeling, the next chapter takes a step back and explains how to design programs systematically from scratch, especially interactive programs. So take a breather and continue when ready.
The first few chapters of this book show that learning to program requires some mastery of many concepts. On the one hand, programming needs some language, a notation for communicating what we wish to compute. The languages for formulating programs are artificial constructions, though acquiring a programming language shares some elements with acquiring a natural language: we need to learn the vocabulary of the programming language, to figure out its grammar, and to understand what its "phrases" mean.
On the other hand, it is critical to learn how to get from a problem statement to a program. We need to determine what is relevant in the problem statement and what can be ignored. We need to tease out what the program consumes, what it produces, and how it relates inputs to outputs. We have to know, or find out, whether the chosen language and its libraries provide certain basic operations for the data that our program is to process. If not, we might have to develop auxiliary functions that implement these operations. Finally, once we have a program, we must check whether it actually performs the intended computation. And this might reveal all kinds of errors, which we need to be able to understand and fix.
In his book “The Mythical Man-Month” Fred Brooks describes and contrasts these forms of programming on the first pages. In addition to “garage programming” and a “programming product,” he also recognizes “component programming” and “systems programming.” This book is about the “programming products;” our next two books will cover “components” and “systems” design. All this sounds rather complex and you might wonder why we don’t just muddle our way through, experimenting here and there, leaving well enough alone when the results look decent. This approach to programming, often dubbed “garage programming,” is common and succeeds on many occasions; sometimes it is the launching pad for a start-up company. Nevertheless, the start-up cannot sell the results of the “garage effort” because only the original programmers and their friends can use them.
A good program comes with a short write-up that explains what it does, what inputs it expects, and what it produces. Ideally, it also comes with some assurance that it actually works. In the best circumstances, the program’s connection to the problem statement is evident so that a small change to the problem statement is easy to translate into a small change to the program. Software engineers call this a “programming product.”
The word “other” also includes older versions of the programmer who usually cannot recall all the thinking that the younger version put into the production of the program.
All this extra work is necessary because programmers don’t create programs for themselves. Programmers write programs for other programmers to read, and on occasion, people run these programs to get work done. Most programs are large, complex collections of collaborating functions, and nobody can write all these functions in a day. Programmers join projects, write code, leave projects, and others take over their work. Another difficulty is that the programmer’s clients tend to change their mind about what problem they really want solved. They usually have it almost right, but more often than not, they get some details wrong. Worse, complex logical constructions such as programs almost always suffer from human errors; in short, programmers make mistakes. Eventually someone discovers these errors and programmers must fix them. They need to re-read the programs from a month ago, a year ago, or twenty years ago and change them.
In this book, we present a design recipe that integrates a step-by-step
process with a way of organizing programs around problem data. For the
readers who don’t like to stare at blank screens for a long time, this
design recipe offers a way to make progress in a systematic manner. For
those of you who teach others to design programs, the recipe is a
device for diagnosing a novice’s difficulties. For others, our
recipe might be something that they can apply to other areas, say
medicine, journalism, or engineering. For those who wish to
become real programmers, the design recipe also offers a way to understand
and work on existing programs—
Information and Data: The purpose of a program is to describe a
computation, a process that leads
from one collection of information to another. In a sense, a program is like
the instruction a mathematics teacher gives to grade school
students. Unlike a student, however, a program works with more than
numbers; it calculates with navigation information, looks up a person’s
address, turns on switches, or processes the state of a video game. All
this information comes from a part of the real world—
“Information” plays a central role in our description. Think of information as facts about the program’s domain. For a program that deals with a furniture catalog, a “table with five legs” or a “square table of two by two meters” are pieces of information. A game program deals with a different kind of domain, where “five” might refer to the number of pixels per clock tick that some objects travels on its way from one part of the screen to another. Or, a payroll program is likely to deal with “five deductions.”
For a program to process information, it must turn it into some form of data, also called values, in the programming language; then it processes the data; and once it is finished, it turns the resulting data into information again. An interactive program may even intermingle these steps, acquiring more information from the world as needed and delivering information in between.
We use BSL and DrRacket so that you do not have to worry about the
translation of information into data. In DrRacket’s BSL you can apply a
function directly to data and observe what it produces. As a result, we
avoid the serious chicken-and-egg problem of writing functions that
convert information into data and vice versa. For simple kinds of
information, designing such program pieces is trivial; for anything other
than simple information, you need to know about parsing—
Software engineers use the slogan model-view-control (MVC) for the way BSL and DrRacket separate data processing from parsing information into data and turning data into information. Indeed, it is now accepted wisdom that well-engineered software systems enforce this separation, even though most introductory books still co-mingle them. Thus, working with BSL and DrRacket allows you to focus on the design of the core of programs and, when you have enough experience with that, you can learn to design the information-data translation parts.
Here we use the "batch-io" and "universe" teachpacks to demonstrate
how complete programs are designed. That is, this book—
Given the central role of information and data, program design must clearly
start with the connection between them. Specifically, we—
42 may refer to the number of pixels from the top margin in the domain of images;
42 may denote the number of pixels per clock tick that a simulation or game object moves;
42 may mean a temperature, on the Fahrenheit, Celsius, or Kelvin scale for the domain of physics;
42 may specify the size of some table if the domain of the program is a furniture catalog; or
42 could just count the number of chars a batch program has read.
The word “class” is a popular computer science substitute for the word “set.” In analogy to other set theory mathematics, we also say a value is some element of a class.
Since this knowledge is so important for everyone who reads the program, we often write it down in the form of comments, which we call data definitions. The purpose of a data definition is two-fold. On the one hand, it names a class or a collection of data, typically using a meaningful word. On the other hand, it informs readers how to create elements of this class of data and how to decide whether some random piece of data is an element of this collection.
; Temperature is a Number. ; interp. degrees Celsius
If you happen to know that the lowest possible temperatures is approximately -274, you may wonder whether it is possible to express this knowledge in a data definition. Since data definitions in BSL are really just English descriptions of classes, you may indeed define the class of temperatures in a much more accurate manner than shown above. In this book, we use a stylized form of English for such data definitions, and the next chapter introduces the style for imposing constraints such as “larger than -274.”
At this point, you have encountered the names of some data: Number, String, Image, and Boolean values. With what you know right now, formulating a new data definition means nothing more than introducing a new name for an existing form of data, for example, “temperature” for numbers. Even this limited knowledge, though, suffices to explain the outline of our design process.
- Express how you wish to represent information as data. A one-line comment suffices, for example,
; We use plain numbers to represent temperatures.Formulate data definitions, like the one for Temperature above for the classes of data you consider critical for the success of your program.
Write down a signature, a purpose statement, and a function header.
A function signature (but always shortened to signature here) is a BSL comment that tells the readers of your design how many inputs your function consumes, from what collection of data they are drawn, and what kind of output data it produces. Here are three examples:
A purpose statement is a BSL comment that summarizes the purpose of the function in a single line. If you are ever in doubt about a purpose statement, write down the shortest possible answer to the question
- for a function that consumes one string and produces a number:
- for a function that consumes a temperature and that produces a string:As this signature points out, introducing a data definition as an alias for an existing form of data makes it easy to read the intention behind signatures.
Nevertheless, we recommend to stay away from aliasing data definitions for now. A proliferation of such names can cause quite some confusion. It takes practice to balance the need for new names and the readability of programs, and there are more important ideas to understand for now.
- for a function that consumes a number, a string, and an image and that produces an image:
what does the function compute?Every reader of your program should understand what your functions compute without having to read the function itself.
A multi-function program should also come with a purpose statement. Indeed, good programmers write two purpose statements: one for the reader who may have to modify the code and another one for the person who wishes to use the program but not read it.Finally, a header is a simplistic function definition, also called a stub. Pick one parameter for each input data class in the signature; the body of the function can be any piece of data from the output class. The following three function headers match the above three signatures:Our parameter names reflect what kind of data the parameter represents. Sometimes, you may wish to use names that suggest the purpose of the parameter.When you formulate a purpose statement, it is often useful to employ the parameter names to clarify what is computed. For example,
At this point, you can click the RUN button and experiment with the function. Of course, the result is always the same value, which makes these experiments quite boring.
Illustrate the signature and the purpose statement with some functional examples. To construct a functional example, pick one piece of data from each input class from the signature and determine what you expect back.
Suppose you are designing a function that computes the area of a square. Clearly this function consumes the length of the square’s side, and that is best represented with a (positive) number. The first process step should have produced something like this:
Add the examples between the purpose statement and the function header:
The next step is to take inventory,The term “inventory” in this context is due to Dr. Stephen Bloch who uses it in his writings on program design. We use “template” for historical reasons. to understand what are the givens and what we do need to compute. For the simple functions we are considering right now, we know that they are given data via parameters. While parameters are placeholders for values that we don’t know yet, we do know that it is from this unknown data that the function must compute its result. To remind ourselves of this fact, we replace the function’s body with a template.For now, the template contains just the parameters, e.g.,The dots remind you that this isn’t a complete function, but a template, a suggestion for an organization.
The templates of this section look boring. Later, when we introduce complex forms of data, templates become interesting, too.
It is now time to code. In general, to code means to program, though often in the narrowest possible way, namely, to write executable expressions and function definitions.To us, coding means to replace the body of the function with an expression that attempts to compute from the pieces in the template what the purpose statement promises. Here is the complete definition for area-of-square:To complete the add-image function takes a bit more work than that:
; Number String Image -> Image ; add s to img, y pixels from top, 10 pixels to the left ; given: ; 5 for y, ; "hello" for s, and ; (empty-scene 100 100) for img ; expected: ; (place-image (text "hello" 10 "red") 10 5 (empty-scene 100 100)) (define (add-image y s img) (place-image (text s 10 "red") 10 y img))In particular, the function needs to turn the given string s into an image, which is then placed into the given scene.
- The last step of a proper design is to test the function on the examples that you worked out before. For now, click the RUN button and enter function applications that match the examples in the interactions area:
> (area-of-square 2)
> (area-of-square 7)
49The results must match the output that you expect; you must inspect each result and make sure it is equal to what is written down in the example portion of the design. If the result doesn’t match the expected output, consider the following three possibilities:
When you do encounter a mismatch between expected results and actual values, we recommend that you first re-assure yourself that the expected results are correct. If so, assume that the mistake is in the function definition. Otherwise, fix the example and then run the tests again. If you are still encountering problems, you may have encountered the third, rather rare situation.
You miscalculated and determined the wrong expected output for some of the examples.
Alternatively, the function definition computes the wrong result. When this is the case, you have a logical error in your program, also known as a bug.
Both the examples and the function definition are wrong.
The first few of the following exercises are almost copies of previous ones. The difference is that this time they used the word “design” not “define,” meaning you should use the design recipe to create these functions and your solutions should include the relevant pieces. (Skip the template; it is useless here.) Finally, as the title of the section suggests these exercises are practice exercises to help you internalize the process. Until the steps become second nature, never skip one; that leads to easily avoided errors and unproductive searches for the causes of those flaws. There is plenty of room left in programming for complicated errors. We have no need to waste our time on silly mistakes.
Knowledge from external domains such as mathematics, music, biology, civil engineering, art, etc. 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. This language is often that of mathematics, but in some cases, the programmers must learn a language as they work through problems with domain experts.
And knowledge about the library functions in the chosen programming language. When your task is to translate a mathematical formula involving the tangent function, you need to know or guess that your chosen language comes with a function such as BSL’s tan. When, however, you need to use BSL to design image-producing functions, you will benefit from understanding the possibilities of the "2htdp/image" teachpacks.
You can recognize problems that demand domain knowledge from the data definitions that you work out. As long as the data definitions use classes that exist in the chosen programming language, the definition of the function body (and program) mostly relies on expertise in the domain. Later, when we introduce complex forms of data, the design of functions demands deep knowledge of computer science.
Not all programs consist of a single function definition. Some require several functions, many also use constant definitions. No matter what, it is always important to design each function of a program systematically, though both global constants and the presence of auxiliary functions change the design process a bit.
When you have defined global constants, your functions may use those global constants to compute results. You may wish to add these constants when you create templates as if they were parameters; after all, they belong to the inventory of things that may contribute to the function definition. Adding global constants to templates, however, can quickly make those templates look messy. In short, keep global constants in mind when you define functions.
Multi-function programs are complex. On the one hand, the design of interactive functions automatically demands the design of several functions. On the other hand, even the design of batch programs may require dealing with several different tasks. Sometimes the problem statement itself suggests different tasks; other times you will discover the need for auxiliary functions as you are in the middle of designing some function.
For all cases, we recommend keeping around a list of needed functions or a wish list.The term “wish list” in this context is due to Dr. John Stone. Each entry on a wish list should consist of three things: a meaningful name for the function, a signature, and a purpose statement. For the design of a batch program, put the main function on the wish list and start designing it. For the design of an interactive program, you can put the event handlers, the stop-when function, and the scene-rendering function on the list. As long as the list isn’t empty, pick a wish and design the function. If you discover during the design that you need another function, put it on the list. When the list is empty, you are done.
Testing quickly becomes a labor-intensive chore. While it is easy to run tests and discover syntactic errors (clicking the RUN button does this) and run-time errors (the application of a primitive operation to the wrong kind of data), comparing the result of an interaction with the expected result is tiresome. For complex programs, you will tend to write lots of examples and tests and you will have to compare complex (large) values. If you haven’t thought so, you will soon think that this is burdensome and perform sloppy comparisons.
At the same time, testing is a major step to discover the flaws in a
program. Sloppy testing quickly leads to functions with hidden
For these reasons—
(check-expect (f2c -40) 40)
; Number -> Number ; convert Fahrenheit temperatures to Celsius temperatures (check-expect (f2c -40) -40) (check-expect (f2c 32) 0) (check-expect (f2c 212) 100) (define (f2c f) (* 5/9 (- f 32)))
You can place check-expect specifications above or below the
function definition that they test. When you click RUN, DrRacket
collects all check-expect specifications and evaluates them
after all function definitions have been added to the
“vocabulary” of operations. The above figure shows how to exploit this
freedom to combine the example and test step. Instead of writing down the
examples as comments, you can translate them directly into tests. When
you’re all done with the design of the function, clicking RUN
performs the test. And if you ever change the function for some
(check-expect (render 50) (place-image CAR 50 Y-CAR BACKGROUND)) (check-expect (render 200) (place-image CAR 200 Y-CAR BACKGROUND))
Because it is so useful to have DrRacket conduct the tests and not to check everything yourself manually, we immediately switch to this style of testing for the rest of the book. This form of testing is dubbed unit testing, and BSL’s unit testing framework is especially tuned for novice programmers. One day you will switch to some other programming language; one of your first tasks will be to figure out its unit testing framework.
The "universe" teachpack supports the construction of some interactive programs. Specifically, you can use the "universe" teachpack to construct so-called world programs; interactive programs that deal with clock ticks, mouse clicks, and key strokes. In order to interact with people, world programs also create images that DrRacket displays in a graphical canvas.
While the previous chapter introduces the "universe" teachpack in an ad hoc way, this section demonstrates how the design recipe helps you create world programs. The first section provides some basic knowledge about big-bang, the major construct for wiring up world programs. The second section extends this knowledge to deal with mouse clicks and key strokes. Once you have digested this terminology, you are ready to design world programs. The last section starts a series of exercises, which run through a couple of chapters in this book; take a close look and create your own favorite virtual pet.
Describing Worlds: A raw computer is a nearly useless piece of physical equipment; it is called hardware because you can touch it. This equipment becomes useful once you install software, and the first piece of software is usually installed on a computer is an operating system. It has the task of managing the computer for you, including connected devices such as the monitor, the keyboard, the mouse, the speakers, and so on. When you press a key on the keyboard, the operating system runs a function that processes the key stroke. We say that the key stroke is an key event, and the function is an event handler. Similarly, when the clock ticks, the operating system runs an event handler for clock ticks and, when you perform some action with the mouse, the operating system launches the event handler for mouse clicks.
Naturally, different programs have different needs. One program may interpret key strokes as signals to control a nuclear reactor; another passes them to a word processor. To make one and the same computer work on these radically different tasks, programs install event handlers. That is, they tell the operating system to use certain functions for dealing with clock ticks and other functions for dealing with mouse clicks. If a program doesn’t need to handle key strokes, the program says nothing about key events and the operating system ignores them.
The key questions are what arguments DrRacket supplies to your event handlers for key strokes, mouse clicks, and clock ticks and what kind of results it expects from these event handlers. Like a real operating system, DrRacket gives these functions access to the current state of the world. For key events and mouse events, DrRacket also supplies information about these events.
The initial state is the value of w0, because our big-bang expression says so. It also is the state that DrRacket hands to the first event handling function that it uses. DrRacket expects that this event handling function produces a new state of the world, let us call it w1. The point is that DrRacket keeps this result around until the second event happens. Here is a table that describes this relationship among worlds and event handling functions:
(keh w0 ...)
(keh w1 ...)
(keh w2 ...)
(keh w3 ...)
(meh w0 ...)
(meh w1 ...)
(meh w2 ...)
(meh w3 ...)
w1 is the result of (keh w0 "a"), i.e., the fourth cell in the e1 column;
w2 is the result of (cth w1), i.e., the third cell in the e2 column;
w3 is the result of (cth w2), i.e., again the third cell in the e3 column; and
w4 is the result of (meh w3 90 100 "button-down").
(define w4 (meh (cth (cth (keh w0 "a"))) 90 100 "button-down"))
In short, the sequence of events determines in which order you traverse the above tables of possible worlds to arrive at the one and only one current world for each time slot. Note that DrRacket does not touch the current world; it merely safeguards it and passes it to event handling functions when needed.
Designing Worlds: Now that you understand how big-bang works, you can focus on the truly important problem of designing world programs. As you might guess, the design starts with the data definition for the states of the world. To this end we assume that you have a problem statement and that you are able to imagine what the world program may display in various situations.
Sample Problem: Design a program that moves a car across the world canvas, from left to right, at the rate of three pixels per clock tick.
- For all those properties of the world that remain the same, introduce constant definitions. In BSL, we capture constants via global constant definitions. For the purpose of designing worlds, we distinguish between two kinds of constants:
“physical” constants, which describe general attributes of objects in the domain, such as the speed or velocity of an object, its color, its height, its width, its radius, and so forth. Of course these constants don’t really refer to physical facts, but many are analogous to physical aspects of the real world.In the context of the car animation from the previous section, the WHEEL-RADIUS constant is a “physical” constant, and its definition may look like this:Note how some constants are computed from others.
graphical constants, which are images that the program uses to create the scenes that appear on the canvas.Here are some graphical constant definitions:
(define WHL (circle WHEEL-RADIUS "solid" "black")) (define BDY (above (rectangle (/ BODY-LENGTH 2) (/ BODY-HEIGHT 2) "solid" "red") (rectangle BODY-LENGTH BODY-HEIGHT "solid" "red"))) (define SPC (rectangle WHEEL-DISTANCE 1 "solid" "white")) (define WH* (beside WHL SPC WHL)) (define CAR (underlay/xy BDY WHEEL-RADIUS BODY-HEIGHT WH*))Graphical constants are usually computed, and the computations tend to involve the physical constants. To create good looking images, you need to experiment. But, keep in mind that good images are not important to understand this book; if you have fun creating them, feel free to spend time on the task. We are happy with simple images.
Those properties that change over time or in reaction to other events make up the current state of the world. Your task is to render the possible states of the world, to develop a data definition that describes all possible states of the world. As before, you must equip this data definition with a comment that tells readers how to represent world information as data and how to interpret data as information in the world.
For the running example of an animated car, the only thing that changes is its distance to the left (or right) border of the canvas. A distance is measured in numbers, so the following is an adequate data definition in this example.An alternative is to count the number of clock ticks that have passed and to use this number as the state of the world. We leave this design variant as an exercise.
Once you have a data representation for the state of the world, you need to decide which kind of interactions you wish to use for which kind of transitions from one world state to another. Depending on your decisions, you need to design several or all of the following four functions:
- if your world reacts to clock ticks:
- if your world reacts to key strokes:
- if your world reacts to mouse clicks:
- if you want the world to be rendered to the canvas:
Last but not least, you need to define a main function that puts it all together. Unlike all other functions, a main function for world programs doesn’t demand design. As a matter of fact, it doesn’t require testing. Its sole reason for existing is that you can run your world program conveniently once all tests for the event handling functions are completed.Here is our proposed main function for the sample problem:The definition assumes that you have named the clock tick handler tock and the draw function render.
In other words, the desire to design an interactive program dictates several initial entries for your wish list. Later we introduce additional entries so that you can also design world programs that deal with key presses and mouse events. After you have designed the event handling functions, you can launch an interactive program with a big-bang expression:
A note on names: Naturally, you don’t have to use the name “CarState” for the class of data that represents the states of the world; any name will do as long as you use it consistently for the signatures of the big-bang functions. Also, you don’t have to use the names tock, render, or end?; you can name these functions whatever you like, as long as you use the same names when you write down the clauses of the big-bang expression.
A note on design: Even after settling on the data definition, a careful programmer shouldn’t be completely happy. The image of the car (and a car itself) isn’t just a mathematical point without width and height. Thus, “the number of pixels from the left margin” is ambiguous. Does this statement measure the distance between the left margin and the left end of the car? Its center point? Or even its right end? While this kind of reflection may seem far-fetched, it becomes highly relevant and on occasion life-critical in some programming domains. We ignore this issue for now and leave it to BSL’s image primitives to make the decision for us.
Good programs establish a single point of control for all aspects, not just the graphical constants. Several chapters deal with this issue.
Exercise 33: Good programmers ensure that an image such as CAR can be enlarged or reduced via a single change to a constant definition. We started the development of our car image with a single plain definition:
(define WHEEL-RADIUS 5)All other dimensions of the car and its pieces are based on the wheel’s radius. Changing WHEEL-RADIUS from 5 to 10 doubles the size of the car image, and setting it to 3 reduces it. This kind of program organization is dubbed single point of control, and good design employs single point of control as much as possible.
Now develop your favorite image of a car; name your image CAR. Remember to experiment and make sure you can re-size the image easily.
The rest of this section demonstrates how to apply the third design
> (tock 20)
> (tock 78)
; CarState -> Image ; place the car into a scene, according to the given world state (define (render ws) (empty-scene 300 50))
; CarState -> Image ; place the car into a scene, according to the given world state (define (render ws) (place-image CAR ws Y-CAR BACKGROUND))
And then, you just need to test, which means evaluating expressions such as (render 50), (render 100), (render 150), and (render 200) and making sure that the resulting image is what you want. Naturally, this is somewhat more difficult than checking that a number is what you want. For now, we and you need to rely on your eyes, which is why doing this is called an eyeball test. In the penultimate subsection, we return to the testing issue in general and the one for images in particular.
Exercise 34: Finish the sample problem and get the program to run. That is, assuming that you have solved the exercise of creating the image of a car, define the constants BACKGROUND and Y-CAR. Then assemble the appropriate big-bang expression. When your program runs to your satisfaction, add a tree to scenery. We usedto create a tree-like shape. Also add a clause to the big-bang expression that stops the animation when the car has disappeared on the right side of the canvas.
Like the original data definition, this one also equates the states of the world with the class of numbers. Its interpretation, however, explains that the number means something entirely different.
Design functions tock and render and develop a big-bang expression so that you get once again an animation of a car traveling from left to right across the world’s canvas.
Of Mice and Characters: Before you design world programs that deal with key strokes and mouse events, it is a good idea to practice with small, nearly trivial examples to understand what the event handlers can and cannot compute. We start with a simple problem concerning key strokes:
Sample Problem: Design a program that keeps track of all key strokes. The program should display the accumulated key strokes as a red text in the 11 point font.
; AllKeys is a String. ; interp. the sequence of keys pressed since ; big-bang created the canvas
; physical constants: (define WIDTH 100) (define HEIGHT 50) ; graphical constant: (define MT (empty-scene WIDTH HEIGHT))
- the function remember to manage key strokes:
- the function show to display the current state of the world:
; AllKeys String -> AllKeys ; add ke to ak, the state of the world (check-expect (remember "hello" " ") "hello ") (check-expect (remember "hello " "w") "hello w") (define (remember ak ke) ak)
; AllKeys String -> AllKeys ; add ke to ak, the state of the world (check-expect (remember "hello" " ") "hello ") (check-expect (remember "hello " "w") "hello w") (define (remember ak ke) (string-append ak ke))
; AllKeys -> Image ; render the string as a text and place it into MT (check-expect (show "hello") (place-image (text "hello" 11 "red") 10 20 MT)) (check-expect (show "mark") (place-image (text "mark" 11 "red") 10 20 MT)) (define (show ak) (place-image (text ak 11 "red") 10 20 MT))
Exercise 37: Key event handlers are also applied to strings such as "\t" (the tab key) and "\r". Appearances are deceiving, however. These strings consists of a single character and remember therefore adds them to the end of the current world state. Read the documentation of on-key to find out which strings belong to KeyEvent; then change remember so that it also ignores all one-character strings that represent key strokes.
Let us look at a program that interacts with the mouse. The figure below displays the simplest such program; it is an interactive program that just records where the mouse events occur via small dots.It is acceptable to break the rule of separating data representations and image rendering for such experimental programs, whose purpose it is to determine how newly introduced things work. It ignores what kind of mouse event occurs, and it also ignores the first guideline about the separation of state representation and its image. Instead the program uses images as the state of the world. Specifically, the state of the world is an image that contains red dots where a mouse event occurred. When another event is signaled, the clack function just paints another dot into the current state of the world.
; AllMouseEvts is an element of Image. ; graphical constants (define MT (empty-scene 100 100)) ; clack : AllMouseEvts Number Number String -> AllMouseEvts ; add a dot at (x,y) to ws (check-expect (clack MT 10 20 "something mousy") (place-image (circle 1 "solid" "red") 10 20 MT)) (check-expect (clack (place-image (circle 1 "solid" "red") 1 2 MT) 3 3 "") (place-image (circle 1 "solid" "red") 3 3 (place-image (circle 1 "solid" "red") 1 2 MT))) (define (clack ws x y action) (place-image (circle 1 "solid" "red") x y ws)) ; show : AllMouseEvts -> AllMouseEvts ; just reveal the current world state (check-expect (show MT) MT) (define (show ws) ws)
Normal interactive programs don’t ignore the kind of mouse events that takes place. Just like the key event tracker above, they inspect the string and compute different results, depending on what kind of string they received. Designing such programs requires a bit more knowledge about BSL and a bit more insight into design than we have presented so far. And the next chapter introduces all this.
This exercise section introduces the first two elements of a virtual pet game. It starts with just a display of a cat that keeps walking across the screen. Of course, all the walking makes the cat unhappy and its unhappiness shows. Like all pets, you can try petting, which helps some, or you can try feeding, which helps a lot more.
So let’s start with an image of our favorite cat:
Copy the cat image and paste it into DrRacket, then give the image a name with define.
Exercise 38: Design a “virtual cat” world program that continuously moves the cat from left to right, by three pixels at a time. Whenever the cat disappears on the right it should re-appear on the left.
Adjust the rendering function so that it uses one cat image or the other based on whether x coordinate is odd. Read up on odd? in the help desk.
Exercise 40: Our virtual pet game will need a gauge to show how happy the cat is. If you ignore the cat, it becomes less happy. If you pet the cat, it becomes happier. If you feed the cat, it becomes much, much happier. We feed the cat by pressing the down arrow key, and we pet it by pressing the up arrow key.
Do not integrate your solution to this exercise with the program of the preceding two exercises; you don’t know enough yet.Design a world program that maintains and displays a “happiness gauge” over time. With each clock tick, happiness decreases by -0.1, starting with 100, the maximum score; it never falls below 0, the minimum happiness score.
To show the level of happiness, we use a scene with a solid, red rectangle with a black frame. For a happiness level of 0, the red bar should be gone; for a happiness level of 100, the bar should go all the way across the scene.
Thus far you have four choices to represent information as data: numbers, strings, images, and Boolean values. For many problems this is enough, but there are many more for which these four collections of data in BSL (or different ones in different programming languages) don’t suffice. Put differently, programming with just the built-in collections of data is often clumsy and therefore error prone.
At a minimum, good programmers must learn to design programs with restrictions on these built-in collections. One way to restrict is to enumerate a bunch of elements from a collection and to say that these are the only ones that are going to be used for some problem. Enumerating elements works only when there is a finite number of them. To accommodate collections with “infinitely” many elements, we introduce intervals, which are collections of elements that satisfy a specific property.
Infinite may just mean “so large that enumerating the elements is entirely impractical.”
Defining enumerations and intervals means distinguishing among different kinds of elements. To distinguish in code requires conditional functions, that is, functions that choose different ways of computing results depending on the value of some argument. Both Many Ways To Compute and Mixing It Up With Booleans illustrate with examples how to write such functions. In both, however, there is no design system; all you have is some new construct in your favorite programming language (that’s BSL) and some examples on how to use it.
In this chapter, we introduce enumerations and intervals and discuss a general design strategy for these forms of input data. We start with a second look at the cond expression. Then we go through three different scenarios of distinct subclasses of data: enumerations, intervals, and itemizations, which mix the first two. The chapter ends with a section on the general design strategy for such situations.
A note on pragmatics: Contrast cond expressions with if expressions from Mixing It Up With Booleans. The latter distinguish one situation from all others. As such, if expressions are much less suited for multi-situation contexts; they are best used when all we wish to say is “one or the other.” We therefore always use cond for situations when we wish to remind the reader of our code that some distinct situations come directly from data definitions. For other pieces of code, we use whatever construct is most convenient.
Just looking at the cond expression you cannot predict which of the three cond clauses is going to be used. And that is the point of a function. The function deals with many different inputs, for example, 2, 3, 7, 18, 29. For each of these inputs, it may have to proceed in a different manner. Differentiating among the different classes of inputs is the purpose of the cond expression.
Exercise 42: A cond expression is really just an expression and may therefore show up in the middle of another expression:Evaluate the above expression for two distinct values of y: 100 and 210.Nesting cond expressions can eliminate common expressions. Recall the following function definition from Prologue: How to Program:
(define (create-rocket-scene.v5 h) (cond [(<= h ROCKET-CENTER-TO-BOTTOM) (place-image ROCKET 50 h MTSCN)] [(> h ROCKET-CENTER-TO-BOTTOM) (place-image ROCKET 50 ROCKET-CENTER-TO-BOTTOM MTSCN)]))As you can see, both branches of the cond expression have the following shape:
; A TrafficLight shows one of three colors: ; – "red" ; – "green" ; – "yellow" ; interp. each element of TrafficLight represents which colored ; bulb is currently turned on
; TrafficLight -> TrafficLight ; given state s, determine the next state of the traffic light (check-expect (traffic-light-next "red") "green") (define (traffic-light-next s) (cond [(string=? "red" s) "green"] [(string=? "green" s) "yellow"] [(string=? "yellow" s) "red"]))
Exercise 43: If you copy and paste the above function definition into the definitions area of DrRacket and click RUN, DrRacket highlights two of the three cond lines. This coloring tells you that your test cases do not cover all possible cases. Add enough tests to make DrRacket happy.
Exercise 44: Design a function that renders the state of a traffic light as a solid circle of the appropriate color. When you have tested this function sufficiently, enter a big-bang expression that displays your traffic light and that changes its state on every clock tick.
The main idea of an enumeration is that it defines a collection of data as a finite number of pieces of data. Each item explicitly spells out which piece of data belongs to the class of data that we are defining. Usually, the piece of data is just shown as is; on some occasions, the item of an enumeration is an English sentence that describes a finite number of elements of pieces of data with a single phrase.
; A 1String is one of: ; – "q" ; – "w" ; – "e" ; – "r" ; – "t" ; – "y" ; ...
; Position is a Number. ; interp. distance between the left periphery and the ball ; Position KeyEvent -> Position ; compute the next location of the ball (check-expect (nxt 13 "left") 8) (check-expect (nxt 13 "right") 18) (check-expect (nxt 13 "a") 13)
When programs rely on data definitions that are defined by a programming language (such as BSL) or its libraries (such as the "universe" teachpack), it is common that they use only a part of the enumeration. To illustrate this point, let us look at a representative problem.
Sample Problem: Design an interactive program that moves a red dot left or right on a horizontal line in response keystrokes on the "left" and "right" arrow keys.
Figure 10 presents two solutions to this problem. The function on the left is organized according to the basic idea of using one cond clause per line in the data definition of the input, here KeyEvent. In contrast, the right-hand side displays a function that uses the three essential lines: two for the keys that matter and one for everything else. The re-ordering is appropriate because only two of the cond-lines are relevant and they can be cleanly separated from other lines. Naturally, this kind of re-arrangement is done after the function is designed properly.
Sample Problem: Design a program that simulates the landing of a UFO.
; WorldState is a Number ; interp. height of UFO (from top) ; constants: (define WIDTH 300) (define HEIGHT 100) (define CLOSE (/ HEIGHT 3)) ; visual constants: (define MT (empty-scene WIDTH HEIGHT)) (define UFO (overlay (circle 10 "solid" "green") (rectangle 40 2 "solid" "green"))) ; WorldState -> WorldState ; compute next location of UFO (check-expect (nxt 11) 14) (define (nxt y) (+ y 3)) ; WorldState -> Image ; place UFO at given height into the center of MT (check-expect (render 11) (place-image UFO (/ WIDTH 2) 11 MT)) (define (render y) (place-image UFO (/ WIDTH 2) y MT)) ; run program run ; WorldState -> WorldState (define (main y0) (big-bang y0 (on-tick nxt) (to-draw render)))
Sample Problem: The status line says "descending" when the UFO’s height is above one third of the height of the canvas. It switches to "closing in" below that. And finally, when the UFO has reached the bottom of the canvas, the status notifies the player that the UFO has "landed."
In this case, we don’t have a finite enumeration of distinct elements or distinct subclasses of data. After all conceptually the interval between 0 and HEIGHT (for some number greater than 0) contains an infinite number of numbers and a large number of integers. Therefore we use intervals to superimpose some organization on the generic data definition, which just uses "numbers" to describe the class of coordinates.
An interval is a description of a class of (real or rational or integer) numbers via boundaries. The simplest interval has two boundaries: left and right. If the left boundary is to be included in the interval, we say it is a closed on the left. Similarly, a right-closed interval includes its right boundary. Finally, if an interval does not include a boundary, it is said to be open at that boundary.
Pictures of, and notations for, intervals use brackets for closed boundaries and parentheses for open boundaries. Here are four pictures of simple intervals:
[3,5] is a closed interval:
(3,5] is a left-open interval:
[3,5) is a right-open interval:
and (3,5) is an open interval:
the upper interval goes from 0 to CLOSE;
the middle one starts at CLOSE and reaches HEIGHT; and
the lower, invisible interval is just a single line at HEIGHT.
Visualizing the data definition in this manner helps with the design of functions in many ways. First, it immediately suggests how to pick examples. Clearly we want the function to work inside of all the intervals and we want the function to work properly at the ends of each interval. Second, the image as well as the data definition tell us that we need to formulate a condition that determines whether or not some "point" is within one of the intervals.
Putting the two together also raises a question, namely, how exactly the function deals with the end points. In the context of our example, two points on the number line belong to two intervals: CLOSE belongs to both the upper interval and the middle one, while HEIGHT seems to fall into both the middle one and the lowest one. Such overlaps usually cause problems for programs, and they ought to be avoided.
; WorldState -> WorldState (define (f y) (cond [(<= 0 y CLOSE) ...] [(<= CLOSE y HEIGHT) ...] [(>= y HEIGHT) ...]))
; WorldState -> Image ; add a status line to the scene create by render (check-expect (render/status 10) (place-image (text "descending" 11 "green") 10 10 (render 10))) (define (render/status y) (cond [(<= 0 y CLOSE) (place-image (text "descending" 11 "green") 10 10 (render y))] [(and (< CLOSE y) (<= y HEIGHT)) (place-image (text "closing in" 11 "orange") 10 10 (render y))] [(> y HEIGHT) (place-image (text "landed" 11 "red") 10 10 (render y))]))
Sample Problem: The status line, positioned at (20,20), says "descending" when the UFO’s height is above one third of the height of the canvas. It switches to "closing in" below that. And finally, when the UFO has reached the bottom of the canvas, the status notifies the player that the UFO has "landed."
; WorldState -> Image ; add a status line to the scene create by render (check-expect (render/status 42) (place-image (text "descending" 11 "green") 20 20 (render 42))) (define (render/status y) (place-image (cond [(<= 0 y CLOSE) (text "descending" 11 "green")] [(and (< CLOSE y) (<= y HEIGHT)) (text "closing in" 11 "orange")] [(> y HEIGHT) (text "landed" 11 "red")]) 20 20 (render y)))
An interval distinguishes different subclasses of numbers; an enumeration spells out item for item the useful elements of an existing class of data. Data definitions that use itemizations generalize intervals and enumerations. They allow the combination of any existing data classes (defined elsewhere) with each other and with individual pieces of data.
; A KeyEvent is one of: ; – 1String ; – "left" ; – "right" ; – "up" ; – "down" ; – ...
; string->number : String -> NorF ; converts the given string into a number; ; produces false if impossible
; A NorF is one of: ; – false ; – a Number
; NorF -> Number ; add 3 to the given number; 3 otherwise (check-expect (add3 false) 3) (check-expect (add3 0.12) 3.12) (define (add3 x) (cond [(false? x) 3] [else (+ x 3)]))
Let’s solve a somewhat more purposeful design task:
Sample Problem: Design a program that launches a rocket when the user of your program presses the space bar and displays the rising rocket. The rocket is to move upward at a rate of three pixels per clock tick.
the word “height” could refer to the distance between the ground and the rocket’s point of reference, say, its center; or
it could mean the distance between the top of the canvas and the reference point.
To drive home this choice, exercise 50 below asks you to solve the exercises of this section using the first interpretation of “height.”
Exercise 46: The design recipe for world programs demands that you translate information into data and vice versa to ensure a complete understanding of the data definition. In some way it is best to draw some world scenarios and to represent them with data and, conversely, to pick some data examples and to draw pictures that match them. Do so for the LR definition, including at least HEIGHT and 0 as examples.
In reality, rocket launches come with count-downs:
Sample Problem: Design a program that launches a rocket when the user presses the space bar. At that point, the simulation starts a count-down for three ticks, before it displays the scenery of a rising rocket. The rocket should move upward at a rate of three pixels per clock tick.
Now that we have the data definition, we write down the obvious physical and graphical constants:
- one for displaying the current state of the world as an image:
- one for reacting to the user’s key presses, the space bar in this problem:As Designing World Programs says, a key event handler is applied to two values: the current state of the world and the key event.
- and one for reacting to clock ticks once the simulation is launched:
(check-expect (show "resting") (place-image ROCKET 10 (- HEIGHT (/ (image-height ROCKET) 2)) BACKG)) (check-expect (show -2) (place-image (text "-2" 20 "red") 10 (* 3/4 WIDTH) (place-image ROCKET 10 (- HEIGHT (/ (image-height ROCKET) 2)) BACKG))) (check-expect (show 53) (place-image ROCKET 10 53 BACKG))
A second look at the examples reveals that making examples also means making choices. Nothing in the problem statement actually demands how exactly the rocket is displayed before it is launched but doing so is natural. Similarly, nothing says to display a number during the count down, but it adds a nice touch. Last but not least, if you solved exercise 46 you also know that HEIGHT and 0 are special points for the third clause of the data definition.
Clearly, (show -3) and (show -1) must produce images like the one for (show -2). After all, the rocket still rests on the ground, even if the count down numbers differ.
- The case for (show HEIGHT) is different. According to our agreement, HEIGHT represents the state when the rocket has just been launched. Pictorially this means the rocket is still resting on the ground. Based on the last test case above, here is the test case that expresses this insight:Except that if you evaluate the “expected value” expression by itself in DrRacket’s interaction area, you see that the rocket is half-way underground. This shouldn’t be the case of course, meaning we need to adjust this test case and the above:
Finally, determine the result you now expect from (show 0). It is a simple but revealing exercise.
Exercise 47: Why would it be incorrect to formulate the first condition as (string=? "resting" x)? Conversely, formulate a completely accurate condition, that is, a Boolean expression that evaluates to true precisely when x belongs to the first subclass of LRCD. Similarly, what is a completely accurate condition for the third clause?
(define (show x) (cond [(string? x) (place-image ROCKET 10 (- HEIGHT ROCKET-CENTER) BACKG)] [(<= -3 x -1) (place-image (text (number->string x) 20 "red") 10 (* 3/4 WIDTH) (place-image ROCKET 10 (- HEIGHT ROCKET-CENTER) BACKG))] [(>= x 0) (place-image ROCKET 10 (- x ROCKET-CENTER) BACKG)]))
Stop! Do you notice all the occurrences of 10 in the code? It always refers to the x coordinate of the rocket. So go ahead, create a constant definition for this 10. Now read on.
appears three different times in the function: twice to draw a resting rocket and once to draw a flying rocket. Define an auxiliary function that performs this work and thus shorten show. Why is this a good idea? We discussed this idea in Prologue: How to Program.
(check-expect (launch "resting" " ") -3) (check-expect (launch "resting" "a") "resting") (check-expect (launch -3 " ") -3) (check-expect (launch -1 " ") -1) (check-expect (launch 33 " ") 33) (check-expect (launch 33 "a") 33)
; LRCD -> LRCD ; raise the rocket by YDELTA if it is moving already (check-expect (fly "resting") "resting") (check-expect (fly -3) -2) (check-expect (fly -2) -1) (check-expect (fly -1) HEIGHT) (check-expect (fly 10) (- 10 YDELTA)) (check-expect (fly 22) (- 22 YDELTA)) (define (fly x) (cond [(string? x) x] [(<= -3 x -1) (if (= x -1) HEIGHT (+ x 1))] [(>= x 0) (- x YDELTA)]))
The design of fly—
Exercise 49: Define main2 so that you can launch the rocket and watch it lift off. Read up on the on-tick clause to determine the length of one tick and how to change it.
If you watch the entire launch, you will notice that once the rocket reaches the top, something curious happens. Explain. Add a stop-when clause to main2 so that the simulation of the lift-off stops gracefully when the rocket is out of sight.
In solving exercise 49 you now have a complete, working program but one that behaves a bit strangely. Experienced programmers tell you that using negative numbers to represent the count-down phase is too “brittle.” The next chapter introduces the means to provide a good data definition for this problem. Before we go there, however, let us reiterate in the following section how to design programs that consume data described by itemizations.
Exercise 50: Recall that the word “height” forced us to choose one of two possible interpretation. Now that you have solved the exercises in this section, solve them again using the first interpretation of the word. Compare and contrast the solutions.
What the preceding three sections have clarified is that the design of functions can and must exploit the organization of the data definition. Specifically, if a data definition singles out certain pieces of data or specifies ranges of data, then the creation of examples and the organization of the function reflects these cases and ranges.
Sample Problem: The state of Tax Land has created a three-stage sales tax to cope with its budget deficit. Inexpensive items, those costing less than $1,000, are not taxed. Luxury items, with a price of more than $10,000, are taxed at the rate of eight percent (8.00%). Everything in between comes with a five percent (5.25%) price tag.
Design a function for a cash register that computes the sales tax for each item. That is, design a function that, given the price of an item, computes the amount of tax to be charged.
When the problem statement distinguishes different classes of input information, we need carefully formulated data definitions.
A data definition should explicitly enumerate different subclasses of data or in some cases just individual pieces of data. Each of those subclasses represents a subclass of information. The key is that each subclass of data is distinct from every other class so that our function can distinguish the subclasses, too.Our sample problem deals with prices and taxes, which are usually positive numbers. It also clearly distinguishes three ranges of positive numbers:Make sure you understand how these three ranges relate to the original problem.
As far as the signature, purpose statement, and function header are concerned, we proceed as before.Here is the material for our running example:
For functional examples, however, it is imperative that we pick at least one example from each subclass in the data definition. Also, if a subclass is a finite range, be sure to pick examples from the boundaries of the range and from its interior.
Since our data definition involves three distinct intervals, let us pick all boundary examples and one price from inside each interval and determine the amount of tax for each: 0, 537, 1000, 1282, 10000, and 12017. Before you read on, try to calculate the tax for each of these prices.Here is our first attempt:
961.36Stop for a moment and think about the table entries with question marks.
These question marks point out that the problem statement uses the somewhat vague phrase “those costing less than $1,000” and “more than $10,000” to specify the tax table. While a programmer may immediately jump to the conclusion that these words mean “strictly less” or “strictly more,” the lawmakers may have meant to say “less or equal” or “more or equal,” respectively. Being skeptical, we decide here that Tax Land legislators always want more money to spend, so the tax rate for $1,000 is 5% and the rate for $10,000 is 8%. A programmer in a tax company would have to ask the tax-law specialist in the company; if you were designing your own tax software, you might have to visit your local library or tax office.
Once we have figured out how the boundaries are supposed to be interpreted in the domain, we need to also refine the data definition. Stop! Modify the data definition above so that it expresses the choices just made.Before we go, let us turn some of the examples into test cases:
(check-expect (sales-tax 537) 0) (check-expect (sales-tax 1000) (* 0.05 1000)) (check-expect (sales-tax 12017) (* 0.08 12017))Take a close look. Instead of just writing down the expected result, we write down how to compute the expected result. This makes it easier later to formulate the function definition.
Stop! Write down the remaining test cases. Think about why you may need more test cases than subclasses in the data definition.
The biggest novelty is the conditional template. In general,
the template mirrors the organization of subclasses with a cond.This slogan means two concrete things. First, the function’s body must be a conditional expression with as many clauses as there are distinct subclasses in the data definition. If the data definition mentions three distinct subclasses of input data, you need three cond clauses; if it has seventeen subclasses, the cond expression contains seventeen clauses. Second, you must formulate one condition expression per cond clause. Each expression involves the function parameter and identifies one of the subclasses of data in the data definition.
We are ready to define the function. Given that the function body already contains a schematic cond expression, it is natural to start from the various cond lines. For each cond line, we assume that the input parameter meets the condition and we take a look at corresponding test cases. To formulate the corresponding result expression, we write down the computation for this example as an expression that involves the function parameter. We ignore all other possible kinds of input data when you work on one line; the other cond clauses take care of those.
Finally, we run the tests and make sure that the tests cover all cond clauses in the function.
What do you do when one of your test cases fails? Review at the end of Designing Functions concerning test failures.
Let us exploit our knowledge to create a world that simulates a basic US traffic light. When the light is green and it is time to stop the traffic, the light turns yellow and after that turns red. When the light is red and it is time to get the traffic going, the light switches to green.
Figure 13 summarizes this description as a state transition diagram. Such a diagram consists of states and arrows that connect these states. Each state depicts a traffic light in one particular configuration: red, yellow, or green. Each arrow shows how the world can change, from which state it can transition to another state. Our sample diagram contains three arrows, because there are three possible ways in which the traffic light can change. Labels on the arrows indicate the reason for changes; a traffic light transitions from one state to another as time passes.
In many situations, state transition diagrams have only a finite number of states and arrows. Computer scientists call such diagrams finite state machines or automata, for short: FSA. While FSAs look simple at first glance, they play an important role in computer science.
To create a world program for an FSA, we must first pick a data
representation for the possible “states of the world,” which, according
to Designing World Programs, represents those aspects
of the world that may change in some ways as opposed to those that remain
the same. In the case of our traffic light, what changes is the color of
the light, that is, which bulb is turned on. The size of the bulbs, their
arrangement (horizontal or vertical), and other aspects don’t
change. Since there are only three states—
Figure 14 shows how to interpret the three elements of TrafficLight. Like the original figure, it consists of three states, arranged in such a way that it is easy to interpret each data element as a representation of a concrete configuration and to represent any such configuration as a piece of data. Also, the arrows are now labeled with tick to suggest that our world program uses the passing of time as the trigger that changes the state of the traffic light. Alternatively, we could use keystrokes or mouse events to switch the light, which would be especially appropriate if we wanted to simulate the manual operation of a traffic light.
; TrafficLight -> TrafficLight ; determine the next state of the traffic light, given current-state (define (tl-next current-state) current-state) ; TrafficLight -> Image ; render the current state of the traffic light as a image (define (tl-render current-state) (empty-scene 100 30))
Exercise 52: Finish the design of a world program that simulates the traffic light FSA. Here is the main function:
; TrafficLight -> TrafficLight ; simulate a traffic light that changes with each tick (define (traffic-light-simulation initial-state) (big-bang initial-state [to-draw tl-render] [on-tick tl-next 1]))The function uses as its argument the initial state for the big-bang expression. It tells DrRacket to re-draw the state of the world with tl-render and to react to clock ticks with tl-next. Also note it informs the computer that the clock should tick once per second (how?).
In short, you have two design tasks to complete: tl-render and tl-design.
Hint 1: Create a DrRacket buffer that includes the data definition for TrafficLight and the function definitions of tl-next and tl-render.For the design of the latter, we include some test cases:
(check-expect (tl-render "red") ) (check-expect (tl-render "yellow") ) (check-expect (tl-render "green") )Hint 2: We started from the following graphical constants:and introduced additional constants for the diameter, the width, the height, and so forth. You may find this auxiliary function helpful:
; TrafficLight TrafficLight -> Image ; render the c colored bulb of the traffic light, ; when on is the current state (define (bulb on c) (if (light=? on c) (circle RAD "solid" c) (circle RAD "outline" c)))
Hint 3: Look up the image primitive place-image; it simplifies the task quite a bit.
Here is another finite-state problem that introduces a few additional complications:
Sample Problem: Design a world program that simulates the working of a door with an automatic door closer. If this kind of door is locked, you can unlock it with a key. An unlocked door is closed but someone pushing at the door opens it. Once the person has passed through the door and lets go, the automatic door takes over and closes the door again. When a door is closed, it can be locked again.
To tease out the essential elements, we again draw a transition diagram; see the left-hand side of the figure. Like the traffic light, the door has three distinct states: locked, closed, and open. Locking and unlocking are the activities that cause the door to transition from the locked to the closed state and vice versa. As for opening an unlocked door, we say that one needs to push the door open. The remaining transition is unlike the others, because it doesn’t require any activities by anyone or anything else. Instead, the door closes automatically over time. The corresponding transition arrow is labeled with *time* to emphasize this.
The next step of a world design demands that we translate the actions in
door-closer, which closes the door during one tick;
door-actions, which manipulates the door in response to pressing a key; and
door-render, which translates the current state of the door into an image.
(check-expect (door-closer "locked") "locked") (check-expect (door-closer "closed") "closed") (check-expect (door-closer "open") "closed")
The second function, door-actions, takes care of the remaining three arrows of the diagram. Functions that deal with keyboard events consume both a world and a key event, meaning the signature is as follows:
given key event
(check-expect (door-actions "locked" "u") "closed") (check-expect (door-actions "closed" "l") "locked") (check-expect (door-actions "closed" " ") "open") (check-expect (door-actions "open" "a") "open") (check-expect (door-actions "closed" "a") "closed") (define (door-actions s k) (cond [(and (string=? "locked" s) (string=? "u" k)) "closed"] [(and (string=? "closed" s) (string=? "l" k)) "locked"] [(and (string=? "closed" s) (string=? " " k)) "open"] [else s]))
; A DoorState is one of: ; – "locked" ; – "closed" ; – "open" ; — — — — — — — — — — — — — — — — — — — — — — — — — — ; DoorState -> DoorState ; closes an open door over the period of one tick (check-expect (door-closer "locked") "locked") (check-expect (door-closer "closed") "closed") (check-expect (door-closer "open") "closed") (define (door-closer state-of-door) (cond [(string=? "locked" state-of-door) "locked"] [(string=? "closed" state-of-door) "closed"] [(string=? "open" state-of-door) "closed"])) ; — — — — — — — — — — — — — — — — — — — — — — — — — — ; DoorState KeyEvent -> DoorState ; three key events simulate actions on the door (check-expect (door-actions "locked" "u") "closed") (check-expect (door-actions "closed" "l") "locked") (check-expect (door-actions "closed" " ") "open") (check-expect (door-actions "open" "a") "open") (check-expect (door-actions "closed" "a") "closed") (define (door-actions s k) (cond [(and (string=? "locked" s) (string=? "u" k)) "closed"] [(and (string=? "closed" s) (string=? "l" k)) "locked"] [(and (string=? "closed" s) (string=? " " k)) "open"] [else s])) ; — — — — — — — — — — — — — — — — — — — — — — — — — — ; DoorState -> Image ; the current state of the door as a large red text (check-expect (door-render "closed") (text "closed" 40 "red")) (define (door-render s) (text s 40 "red")) ; — — — — — — — — — — — — — — — — — — — — — — — — — — ; DoorState -> DoorState ; simulate a door with an automatic door closer (define (door-simulation initial-state) (big-bang initial-state (on-tick door-closer) (on-key door-actions) (to-draw door-render)))
Well, we could play some mathematical tricks that would “merge” two numbers into a single number in such a way that we could later extract them again. While these tricks are well-known to trained computer scientists, it should be clear to every budding programmer that such coding tricks obscure the true intentions behind a program. We therefore don’t play this kind of game. Suppose you want to design a world program that simulates a ball bouncing back and forth between two of the four walls. For simplicity, assume that it always moves two pixels per clock tick. If you follow the design recipe, your first focus is to form a data representation for what changes over time. A bouncing ball with constant speed has two always-changing properties: the location of the ball and the direction of its movement. The problem is that the "universe" teachpack keeps track of only one value, and so the question arises how one piece of data can represent two changing quantities of information.
Here is another scenario that raises the same question. Your cell phone is mostly a few million lines of software with some plastic attached to them. Among other things, it administrates your list of contacts. Before we even consider a representation for your ever-growing list of phone numbers and friends, let us ponder the question of how to represent the information about a single contact, assuming each contact comes with a name, a phone number, and an email address. Especially in a context where you have lots and lots of contacts, it is important to glue together all the information that belongs to one contact; otherwise the various pieces could get scrambled by accident.
Every programming language provides some mechanism for combining several
pieces of data into one piece and for retrieving the constituent
values. BSL is no exception; it offers structure type definitions
as the fundamental mechanism for combining several values into one. In
general, a structure type definition introduces many different functions
into the available vocabulary, including one that creates structure
You may have encountered Cartesian points in your mathematics courses in school. They are closely related though their y coordinates mean something slightly different than the y coordinates of posns. A First Look: A location on a world canvas is uniquely identified by two pieces of data: the distance from the left margin and the distance from the top margin. The first is called an x-coordinate and the second one is the y-coordinate.
(check-expect (distance-to-0 (make-posn 3 4)) 5) (check-expect (distance-to-0 (make-posn 8 6)) 10) (check-expect (distance-to-0 (make-posn 5 12)) 13)
Next we can turn our attention to the definition of the function. The examples imply that the design of distance-to-0 doesn’t need to distinguish between different situations. Still, we are stuck because distance-to-0 has a single parameter that represents the entire pixel but we need the two coordinates to compute the distance. Put differently, we know how to combine two numbers into a posn structure using make-posn but we don’t know how to extract these numbers from a posn structure.
An alternative terminology is “to access the fields of a record.” We prefer to think of structures as containers from which we can extract other values. BSL provides operations for extracting values from structures. For posn structures, there are two such operations, one per coordinate: posn-x and posn-y. The former operation extracts the x coordinate; the latter extracts the y coordinate.
The function squares (posn-x a-posn) and (posn-y a-posn), which represent the x and y coordinates, sums up the results, and takes the square root. With DrRacket, we can also quickly check that our new function produces the proper results for our examples.
by hand. Show all steps. Assume that sqr performs its computation in a single step. Check the results with DrRacket’s stepper.
When placed in such a context, one cannot walk a straight path from a point to the origin; instead a person must follow the grid pattern. For a point such as (3,4), a local resident might say “go three blocks this way, turn right, and then go four blocks straight” to provide directions to get to the origin of the grid.
Design the function manhattan-distance, which measures the Manhattan distance of the given posn structure to the origin.
Defining a Structure: Unlike numbers or Boolean values, structures such as posn usually don’t come with a programming language. Only the mechanism to define structure types is provided; the rest is left up to the programmer. This is also true for BSL.
one constructor, a function that creates structure instances from as many values as there are fields; as mentioned, structure is short for structure instance. The phrase structure type is a generic name for the collection of all possible instances.
one selector per field, which extracts the value of the field from a structure instance; and
one structure predicate, which like ordinary predicates distinguishes instances from all other kinds of values.
One curious aspect of structure type definitions is that it makes up names for the various new operations it creates. Specifically, for the name of the constructor, it prefixes the structure name with “make-” and for the names of the selectors it postfixes the structure name with the field names. Finally, the predicate is just the structure name with “?” added; we pronounce this question mark as “huh” when we read program fragments aloud.
(define-struct entry (name phone email))
the constructor make-entry, which consumes three values and creates an instance of entry;
the selectors entry-name, entry-phone, and entry-email, which all consume one value—
an instance of entry— and produces a value; and
the predicate entry?.
(make-entry "Sarah Lee" "666-7771" "firstname.lastname@example.org")
(make-entry "Tara Harper" "666-7770" "email@example.com")
> (entry-name pl)
> (entry-name bh)
> (entry-name (make-posn 42 5))
entry-name: expects an entry, given (posn 42 5)
> (entry-email pl)
> (entry-phone pl)
Exercise 56: Write down the names of the functions (constructors, selectors, and predicates) that the following structure type definitions define:Make sensible guesses as to what kind of values go with which fields and create at least one instance per structure type definition. Then draw box representations for each of them.
A positive number means the ball moves in one direction.
A negative number means it moves in the opposite direction.
(define-struct ball (location velocity))
Interpret this program fragment in terms of a “world scenario” and then create other instances of balld.
Objects in games and simulations don’t always move along vertical or horizontal lines. They move in some “oblique” manner across the screen. Describing both the location and the velocity of a ball moving across a 2-dimensional world canvas demands two numbers: one per direction. For the location part, the two numbers represent the x and y coordinates. Velocity describes the changes in the x and y direction; in other words, these “change numbers” must be added to the respective coordinates to find out where the object is next.
(define-struct vel (deltax deltay))
> (ball-velocity ball1)
> (vel-deltax (ball-velocity ball1))
> (posn-x (ball-velocity ball1))
posn-x: expects a posn, given (vel ...)
(define-struct ballf (x y deltax deltay))Create an instance of ballf that is interpreted in the same way as ball1.
(define-struct centry (name home office cell)) (define-struct phone (area number)) (make-centry "Shriram Fisler" (make-phone 207 "363-2421") (make-phone 101 "776-1099") (make-phone 208 "112-9981"))
In sum, nesting information is natural. The best way to represent such information with data is to mirror the nesting with nested structure instances. Doing so makes it easy to interpret the data in the application domain of the program, and it is also straightforward to go from examples of information to data. Of course, it is really the task of data definitions to facilitates this task of going back and forth between information and data. We have not written data definitions so far, but we are going to catch up with this in the next section.
Data in Structures: Until now, data definitions have been rather boring. We have either used built-in collections of data to represent information (numbers, Boolean values, strings) or specified an itemization (interval or enumeration), which restricts an existing collection. The introduction of structures adds complexity to our data definitions.
(define-struct posn (x y)) ; A Posn is a structure: (make-posn Number Number) ; interp. the number of pixels from left and from top
(define-struct entry (name phone email)) ; An Entry is a structure: (make-entry String String String) ; interp. name, 7-digit phone number, and email address of a contact
(define-struct ball (location velocity)) ; A Ball-1d is a structure: (make-ball Number Number) ; interp. 1: the position from top and the velocity ; interp. 2: the position from left and the velocity
; A Ball-2d is a structure: (make-ball Posn Vel) ; interp. 2-dimensional position with a 2-dimensional velocity (define-struct vel (deltax deltay)) ; A Vel is a structure: (make-vel Number Number) ; interp. velocity in number of pixels per clock tick for each direction
Note also that Ball-2d refers to another one of our data definitions, namely, the one for Vel. While all other data definitions have thus far referred to built-in data collections (numbers, Boolean values, strings), it is perfectly acceptable and indeed common that one of your data definition refers to another. Later, when you design programs, such connections provide some guidance for the organization of programs.
The question of what data definitions really mean and is the topic of the next section.
Of course, at this point, it should really raise the question of what data definitions really mean and this is what the next section deals with.
Next formulate a data definition for phone numbers using this structure type definition:
(define-struct phone# (area switch phone))Historically, the first three digits make up the area code, the next three the code for the phone switch (exchange) of your neighborhood, and the last four represent the phone with respect to the neighborhood. Describe the content of the three fields as precisely as possible with intervals.
Structures defines distance-to-0, a function that consumed a structure and produced a number. Now we look at a few more such functions before formulating some general principles in the next section.
Sample Problem: Your team is designing a program that keeps track of the last mouse click on a 100 x 100 canvas. Together you chose Posn as the data representation for the x and y coordinates of the mouse click. Design a function that consumes a mouse click and a 100 x 100 scene and adds a circular red spot to the scene where the click occurred.
(check-expect (scene+dot (make-posn 10 20) MTS) (place-image DOT 10 20 MTS)) (check-expect (scene+dot (make-posn 88 73) (rectangle 100 100 "solid" "blue")) (place-image DOT 88 73 (rectangle 100 100 "solid" "blue")))
; visual constants (define MTS (empty-scene 100 100)) (define DOT (circle 3 "solid" "red")) ; Posn Image -> Image ; adds a red spot to s at p (check-expect (scene+dot (make-posn 10 20) MTS) (place-image DOT 10 20 MTS)) (check-expect (scene+dot (make-posn 88 73) MTS) (place-image DOT 88 73 MTS)) (define (scene+dot p s) (place-image DOT (posn-x p) (posn-y p) s))
When you are given a location and a velocity (change in location per time unit), you can find out the location after one time unit by adding the velocity to the location.
Sample Problem: Your team is designing a game program that keeps track of an object that moves across the canvas at changing speed. The chosen data representation is a structure that contains two Posns:
(define-struct velocity (dx dy)) ; A Velocity is a structure: (make-vel Number Number) ; interp. (make-vel a b) means that the object moves a steps ; along the horizontal and b steps along the vertical per tick (define-struct ufo (loc vel)) ; A UFO is a structure: (make-ufo Posn Velocity) ; interp. (make-ufo p v) is at location p ; moving at velocity vDesign the function move1, which moves some given UFO for one tick of the clock.
; UFO -> UFO ; move the ufo u, i.e., compute its new location in one clock ; tick from now and leave the velocity as is (check-expect (ufo-move u1) u3) (check-expect (ufo-move u2) (make-ufo (make-posn 17 77) v2)) (define (ufo-move u) u)
(define (ufo-move u) (make-ufo (posn+ (ufo-loc u) (ufo-vel u)) (ufo-vel u)))
Try it out. Enter these definitions and their test cases into the definitions area of DrRacket and make sure they work. It is the first time that we made a “wish” and you need to make sure you understand how the two functions work together.
In mathematics such collections are called sets. Every language comes with a universe of data. This data represents information from and about the external world; it is what programs manipulate.This universe of data is a collection that consists of collections of built-in data but also of classes of data that programs create.
Figure 18 shows one way to imagine the universe of BSL. Since there are an infinitely many numbers and strings, the collection of all data is infinite. We indicate “infinity” in the figure with “...” but a real definition would have to avoid this imprecision.
Neither programs nor individual functions in programs deal with the entire universe of data. It is the purpose of a data definition to describe parts of this universe and to name these parts so that we can refer to them concisely. Put differently, a named data definition is a description of a collection of data, and that name is usable in other data definitions and in function signatures. In a function signature, the name specifies what data a function will deal with and, implicitly, which part of the universe of data it won’t deal with.
; A BS is one of: ; — "hello", ; — "world", or ; — pi.
The introduction of structure types creates an entirely new picture. When a programmer defines a structure type, the universe expands with all possible structure instances. For example, the addition of a posn structure type means that instances of posn with all possible values in the two fields appear. The middle bubble in figure 20 depicts the addition of those values, showing things such as (make-posn "hello" 0) and even (make-posn (make-posn 0 1) 2). And yes, even though some of these instances of posn make no sense to us, it is indeed possible to construct all of them in a BSL program.
(define-struct ball (location velocity))
In mathematics and physics courses, you encounter one such kind of data: Cartesian coordinates, which also combine two numbers into one item. As far as the pragmatics of data definitions is concerned, a data definition for structure types describes large collections of data via combinations of existing data definitions with instances. When we write
Make sensible assumptions as to what kind of values go into each field.
Exercise 62: Provide a structure type definition and a data definition for representing lower-case three-letter words. A word consists of letters, represented with the one-letter strings "a" through "z".
Programmers not only write data definitions, they also read them in order to understand programs, to eliminate errors, to expand the kind of data it can deal with, and so on. We read a data definition to understand how to create data that belongs to the designated collection and to determine whether some piece of data belongs to some specified class.
for a built-in collection of data (number, string, Boolean, images), choose your favorite examples;
Note: on occasion, people use descriptive names to qualify built-in data collections, such as NegativeNumber or OneLetterString. They are no replacement for a well-written data definition.
for an enumeration, use several of the items of the enumeration;
for intervals, use the end points (if they are included) and at least one interior point;
for itemizations, deal with each part separately; and
for data definitions for structures, follow the natural language description, that is, use the constructor and pick an example from the data collection named for each field.
Note: DrRacket recognizes many more strings as colors.
(define-struct person (fstname lstname male?)) ; Person is (make-person String String Boolean)Is it a good idea to use a field name that looks like the name of a predicate?
(define-struct dog (owner name age happiness)) ; Dog is (make-dog Person String PositiveInteger H)
Add an interpretation to this data definition, too.The last definition is an unusual itemization, using both built-in data and a structure type definition. The next chapter deals with this kind of data definition in depth.
The introduction of structure types reinforces that the process of creating functions has (at least) six steps, something already discussed in Designing With Itemizations. It no longer suffices to rely on built-in data collections to represent information; it is now clear that programmers must create data definitions for all but the simplest problems.
When a problem calls for the representation of pieces of information that belong together or describe a natural whole, we need a structure type definition. It requires as many fields as there are relevant properties. An instance of this structure type corresponds to the whole, and the values in the fields to its attributes.
A data definition for a structure type introduces a name for the collection of instances that we consider legitimate. Furthermore it must describe which kind of data goes with which field. Use only names of built-in data collections or previously defined data definitions.
In the end, we (and others) must be able to use the data definition to create sample structure instances. Otherwise, something is wrong with our data definition. To ensure that we can create instances, our data definitions should come with one data examples.
We still need a signature, a purpose statement, and a function header but there is nothing new here.
We use the examples from the first step to create functional examples. For each field associated with intervals or enumerations, we make sure to pick end points and intermediate points to create functional examples.
For example, imagine designing a function that consumes a structure that combines TrafficLight with Number. Since TrafficLight contains three elements, we make sure to use all three in combination with numbers as input samples.
A function that consumes structures usually—
though not always— extracts the values from the various fields in the structure. To remind ourselves of this possibility, we write templates for such functions containing a selector for each field. Furthermore, we may want to write down next to each selector expression what kind of data it extracts from the given structure; such information is found in the data definition.
We do not, however, create selector expressions if a field value is itself a structure. In general, it is better to make a wish for an auxiliary function that processes the extracted field values.
We use the selector expressions from the template when we finally define the function, keeping in mind that we may not need (some of) them.
Test. Test as soon as the function header is written. Test until all expressions have been covered. And test again when you make changes.
Exercise 64: Create templates for functions that consume instances of the following structure types:
Exercise 65: Design the function time->seconds, which consumes instances of the time structures developed in exercise 61 and produces the number of seconds that have passed since midnight. For example, if you are representing 12 hours, 30 minutes, and 2 seconds with one of these structures and if you then apply time->seconds to this instance, the correct result is 45002.
Exercise 66: Design the function different. It consumes two (representations of) three-letter words and creates a word from the differences. For each position in the words, it uses the letter from the second word if the two are the same; otherwise it uses the marker "*". Note: The problem statement mentions two different tasks: one concerning words and one concerning letters. This suggests that you design two functions.
When a world program must track two different and independent pieces of information, we must use a collection of structures to represent the world state data. One field keeps track of one piece of information and the other field the second piece of information. Naturally, if the domain world contains more than two independent pieces of information, the structure type definition must specify as many fields as there are distinct pieces of information.
(define-struct space-game (ufo tank))
Every time we say piece of information, we don’t necessarily mean a single number or a single word. A piece of information may itself combine several components. Thus, creating a data representation for world states that consist of two (or more) complex pieces of information leads to nested structures.
Understanding what kind of data representations is needed for world programs takes practice. To this end, the following two sections introduce several reasonably complex problem statements. We recommend you solve them before moving on to the kind of games that you might like to design on your own.
One step of the programming process is to create a text document. To
program in BSL, you open DrRacket, type on the keyboard, and watch text
appear. Pressing the left arrow on the keyboard moves the cursor to the
left; pressing the backspace (or delete) key erases a single letter to the
left of the cursor—
This process is called “editing” though its precise name should be “text editing of programs” because we will use “editing” for a more demanding task than typing on a keyboard. When you write and revise other kinds of documents, say, an English assignment, you are likely to use other software applications, called word processors, though computer scientists dub all of them editor or even graphical editor.
You are now in a position to design a world program that acts as a one-line editor for plain text. Editing here includes entering letters and somehow changing the already existing text, including the deletion and the insertion of letters. This implies some notion of position within the text. People call this position a cursor; most graphical editors display it in such a way that it can easily be spotted.
the text entered so far
the current location of the cursor.
(define-struct editor (pre post)) ; Editor = (make-editor String String) ; interp. (make-editor s t) means the text in the editor is ; (string-append s t) with the cursor displayed between s and t
Exercise 67: Design the function render, which consumes an Editor and produces an image.
The purpose of the function is to render the text within an empty scene of 200 x 20 pixels. For the cursor, use a 1 x 20 red rectangle and for the strings, black text of size 11.Develop the image for a sample string in DrRacket’s interaction area. We started with this expression:When you are happy with the looks of the image, use the expression as a test and as a guide to the design of render.
Exercise 68: Design edit. The function consumes two inputs, an editor ed and a KeyEvent ke, and it produces another editor. Its task is to add a single-character KeyEvent ke to the end of the pre field of ed, unless ke denotes the backspace ("\b") key. In that case, it deletes the character immediately to the left of the cursor (if there are any). The function ignores the tab "\t" and rubout "\u007F" keys.
The function pays attention to only two KeyEvents longer than one letter: "left" and "right". The left arrow moves the cursor one character to the left (if any), and the right arrow moves it one character to the right (if any). All other such KeyEvents are ignored.
Develop a good number of examples for edit, paying attention to special cases. When we solved this exercise, we created 20 examples and turned all of them into tests.
Hint: Think of this function as consuming KeyEvents, a collection that is specified as an enumeration. It uses auxiliary functions to deal with the Editor structure. Keep a wish list handy; you will need to design additional functions for most of these auxiliary functions, such as string-first, string-rest, string-last, and string-remove-last. If you haven’t done so, solve the exercises in Functions.
Exercise 69: Define the function run. It consumes a string—
the pre field of an editor— and then launches an interactive editor, using render and edit from the preceding two exercises for the to-draw and on-key clauses.
Exercise 70: Notice that if you type a lot, your editor program does not display all of the text. Instead the text is cut off at the right margin. Modify your function edit from exercise 68 so that it ignores a keystroke if adding it to the end of the pre field would mean the rendered text is too wide for your canvas.
Follow the design recipe.
Note: The exercise is a first study of making design choices. It shows that the very first design choice concerns the data representation. Making the right choice requires planning ahead and weighing the complexity of each. Of course, getting good at this is a question of gaining experience.
And again, if you haven’t done so, solve the exercises in Functions.
In this section we continue our virtual zoo project from Virtual Pet Worlds. Specifically, the goal of the exercise is to combine the cat world program with the program for managing its happiness gauge. When the combined program runs, you see the cat walking across the canvas and, with each step, its happiness goes down. The only way to make the cat happy is to feed it (down arrow) or to pet it (up arrow). Finally, the goal of the last exercise is create another virtual, happy pet.
Exercise 72: Define a structure type that keeps track of the cat’s x coordinate and its happiness. Then formulate a data definition for cats, dubbed VCat, including an interpretation with respect to a combined world.
Exercise 73: Design a “happy cat” world program that presents an animated cat and that manages and displays its happiness level. The program must (1) use the structure type from the preceding exercise and (2) reuse the functions from the world programs in Virtual Pet Worlds.
Exercise 75: Extend your structure type definition and data definition to include a direction field. Adjust your program so that the cat moves in the specified direction. The program should move the cat in the current direction, and it should turn the cat around when it reaches either end of the scene.
(define cham )
This drawing of a chameleon is a transparent image. To insert it into DrRacket, insert it with the “Insert Image” menu item. Using this instruction preserves the transparency of the drawing’s pixels.
When a partly transparent image is combined with a colored shape, say a rectangle, the image takes on the underlying color. In the chameleon drawing, it is actually the inside of the animal that is transparent; the area outside is solid white. Try out this expression in your DrRacket, using the "2hdtp/image" teachpack:
(overlay cham (rectangle (image-width cham) (image-height cham) "solid" "red"))
Exercise 76: Design a world program that has the chameleon continuously walking across the screen, from left to right. When it reaches the right end of the screen, it disappears and immediately reappears on the left. Like the cat, the chameleon gets hungry from all the walking and, as time passes by, this hunger expresses itself as unhappiness.
For managing the chameleon’s happiness gauge, you may reuse the happiness gauge from the virtual cat. To make the chameleon happy, you feed it (down arrow, two points only); petting isn’t allowed. Of course, like all chameleon’s, ours can change color, too: "r" turns it red, "b" blue, and "g" green. Add the chameleon world program to the virtual cat game and reuse functions from the latter when possible.
Exercise 77: Copy your solution to exercise 76 and modify the copy so that the chameleon walks across a tricolor background. Our solution uses these colors: Have some Italian pizza when you’ve solved the problem.
(define BACKGROUND (beside (empty-scene WIDTH HEIGHT "green") (empty-scene WIDTH HEIGHT "white") (empty-scene WIDTH HEIGHT "red")))but you may use any colors you wish. Observe how the chameleon changes colors to blend in as it crosses the border between two colors.
When you watch the animation carefully, you will see the chameleon riding on a white rectangle. If you know how to use image editing software, modify the picture so that the white rectangle is invisible. Then the chameleon will really blend in!
In the preceding two chapters, we have encountered two new kinds of data definitions. Those that employ itemization (enumeration and intervals) are used to create small collections from large ones. Those that use structures combine multiple collections. Since this book keeps emphasizing that the development of data representations is the starting point for proper program design, it cannot surprise you that programmers frequently want to itemize data definitions that involve structures or use structures to combine itemized data.
the state of the world is a structure with two fields, or
the state of the world is a structure with three fields.
This chapter introduces the basic idea of itemizing data definitions that involve structures. Because we have all the other ingredients we need, we start straight with itemizing structures, After that, we discuss some examples, including world programs that benefit from our new power. The last section is about errors in programming.
Let us start with a refined problem statement for our space invader game from Programming With Structures.
Sample Problem: Design a game program using the "universe" teachpack for playing a simple space invader game. The player is in control of a tank (a small rectangle) that must defend our planet (the bottom of the canvas) from a UFO (see Intervals for one possibility) that descends from the top of the canvas to the bottom. In order to stop the UFO from landing, the player may fire a single missile (a triangle smaller than the tank) by hitting the space bar. In response, the missile emerges from the tank. If the UFO collides with the missile, the player wins; otherwise the UFO lands and the player loses.
Here are some details concerning the three game objects and their movements. First, the tank moves a constant speed along the bottom of the canvas though the player may use the left arrow key and the right arrow key to change directions. Second, the UFO descends at a constant velocity but makes small random jumps to the left or right. Third, once fired the missile ascends along a straight vertical line at a constant speed at least twice as fast as the UFO descends. Finally, the UFO and the missile collide if their reference points are close enough, for whatever you think “close enough” means.
The following two subsections use this sample problem as a running example, so study it well and solve the following exercise before you continue. Doing so should help you understand the problem in enough depth.
Exercise 78: Draw some sketches of what the game scenery looks like at various stages. Use the sketches to determine the constant and the variable pieces of the game. For the former, develop physical constants that describe the dimensions of the world (canvas), its objects, and the graphical constants used to render these objects. Then develop graphical constants for the tank, the UFO, the missile, and some background scenery. Finally, create your initial scene from the constants for the tank, the UFO, and the background.
Defining Itemizations: The first step in our design recipe calls for the development of data definitions. One purpose of a data definition is to describe the construction of data that represent the state of the world; another is to describe all possible pieces of data that the functions of the world program may consume. Since we haven’t seen itemizations that include structures, this first subsection introduces the basic idea via example. While this is straightforward and probably won’t surprise you, pay close attention.