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 primitive functions. In many cases, these manipulations involve more than one form of data.
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)
i.e., 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)
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 defined a distance function in a naive manner. To use the function, you need to open DrRacket, edit the definitions of x and y to the desired coordinates, and click RUN. We will soon show you the right way to define functions. For now, we use this kind of exercise to remind you of the idea and to prepare you for programming with functions.
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 create an expression using string primitives that concatenates prefix and suffix and adds "_" between them. So the result for these two definitions should be "hello_world".
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 places all the images to which it is applied on top of each other, using the default anchor point for each.
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".
Furthermore, programming languages classify numbers just as mathematics
teachers do. In BSL, numbers are classified in two different
directions. The first you may know from middle school or high school:
integer?, rational?, real?, and
complex?, even if you don’t know the last
one. Evaluate (sqrt -1) in the interactions area and
take a close look at the result. Your mathematics teacher may have told you
that one doesn’t compute the square root of negative numbers. Truth is that
in mathematics and in BSL, it is acceptable to do so, and the result is a
so-called complex number. Don’t worry, though, complex numbers—
(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. What we do mean is that the creation of interesting programs
involves variables and—
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 same (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.
write “(define (”,
write down the name of the function,
... followed by one or more variables, separated by space and ending in “)”,
write down an expression,
write down “)”.
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 operation, a defined operation
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 need to 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 imply and often they use the symbol => for this purpose. While BSL could define a function with this name, we avoid the name because it is too close 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 the middle. 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 whether string-insert should deal 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. Again consider the question whether string-delete can 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" (body fst lst) "\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" signature-name))
> (letter "Matthew" "Krishnamurthi" "Felleisen")
"Dear Matthew,\nwe have discovered that all people with the last name \nKrishnamurthi have won our lottery. So, Matthew, hurry \nand pick up your prize.\nSincerely,\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.
Sample Problem: Imagine the owner of a movie theater who has complete freedom in setting ticket prices. The more he charges, the fewer the people who can afford tickets. In a recent experiment the owner determined a precise relationship between the price of a ticket and average attendance. At a price of $5.00 per ticket, 120 people attend a performance. Decreasing the price by a dime ($.10) increases attendance by 15. Unfortunately, the increased attendance also comes at an increased cost. Every performance costs the owner $180. Each attendee costs another four cents ($0.04). The owner would like to know the exact relationship between profit and ticket price so that he can determine the price at which he can make the highest profit.
The problem statement also 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 revenue is exclusively generated by the sale of tickets, meaning it is exactly the product of ticket price and number of attendees:
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:
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.
batch programs, which consist of one main function, which uses auxiliary functions, which in turn use additional auxiliary functions, and so on. To launch a batch program means to call the main function on some inputs and to wait for its output.
interactive programs, which consists of several main functions, and an expression that informs the computer which of the functions takes care of which input and which of the functions produces output. Naturally, all of these functions may use auxiliary functions.
In this section we present some simple examples of both batch programs 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,
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 consists of one main function, which performs all the computations. On rare occasions, a program is just this one function. Most of the time, though, the main function employs numerous auxiliary functions, which in turn may also use other functions.
> (letter "Robby" "Flatt" "Felleisen")
"Dear Robby,\nwe have discovered that all people with the last name \nFlatt have won our lottery. So, Robby, hurry \nand pick up your prize.\nSincerely,\nFelleisen"
> (letter "Christopher" "Columbus" "Felleisen")
"Dear Christopher,\nwe have discovered that all people with the last name \nColumbus have won our lottery. So, Christopher, hurry \nand pick up your prize.\nSincerely,\nFelleisen"
> (letter "ZC" "Krishnamurthi" "Felleisen")
"Dear ZC,\nwe have discovered that all people with the last name \nKrishnamurthi have won our lottery. So, ZC, hurry \nand pick up your prize.\nSincerely,\nFelleisen"
Programs are even more useful if you can retrieve the input from some file on your computer and deliver the output to some other file. The name batch program originates from programs in the early days of computing when a program read an entire file and created some other file, without any other intervention.
(write-file "Matthew-Krishnamurthi.txt" (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.
(define (main fst last signature-name) (write-file (string-append fst "-" last ".txt") (letter fst last signature-name)))
This first batch program requires users to actually open DrRacket and to apply the function main to three strings. With read-file, we can do even better, namely we can construct batch programs that do not rely on any DrRacket knowledge from their users.
Let us illustrate the idea with a simple program just to see how things work. Suppose we wish to create a program that converts a temperature measured on the Fahrenheit thermometer into a Celsius temperature. Don’t worry, this question isn’t a test about your physics knowledge (though you should know where to find this kind of 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)
the function convert consumes two filenames: in for the file where the Fahrenheit temperature is found and out for where we want the Celsius result;
(read-file in) retrieves the content of the file called in as a string;
string->number turns it 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" "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, you should also step through the computation. Make sure that the file "sample.dat" exists and contains just a number, then click the STEP button. 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. In this case, the process follows the above outline, and it is quite instructive to see this process in action.
With the choice of a menu entry, DrRacket can also produce a so-called
executable, a stand-alone program like DrRacket
itself. Specifically, choose the entry Create Executable from the
Racket menu, and DrRacket will place a package—
Interactive Programs: No matter how you look at it, batch programs are old-fashioned and somewhat boring. Even if businesses have used them for decades to automate useful tasks, interactive programs are what people are used to and prefer over batch programs. Indeed, in this day and age, people mostly interact with programs via a keyboard and a mouse, that is, events such as key presses or mouse clicks. Furthermore, interactive programs can also react to computer-driven events, e.g., the fact that the clock has ticked or that a message has arrived from some other computer.
Launching interactive programs requires more work than launching a batch program. Specifically, an interactive program designates some function as the one that takes care of keyboard events, another function as the one that presents pictures, a third function for dealing with clock ticks, etc. Put differently, there isn’t a main function that is launched; instead there is an expression that tells the computer how to handle interaction events and the evaluation of this expression starts the program, which then computes in response to user events or computer events.
In BSL, the "universe" teachpack provides the mechanisms for specifying connections between the computer’s devices and the functions you have written. The most important mechanism is the big-bang expression. It consists of one required subexpression, which must evaluate to some piece of data, and a number of optional clauses, which determine which function deals with which event.
Copy this definition of render and the third big-bang example into the definitions area of DrRacket Then click RUN, and observe a separate window that counts down from 100 to 0. At that point, the evaluation stops and a 0 appears in the interactions area.
An explanation of this schematic expression must start with is the first,
required subexpression. The value of this first expression is installed as
a world, specifically the current world. Furthermore,
this big-bang expression tells the computer to apply the function
tock to the current world whenever the clock ticks. The result of
current world (cw)
Each current world is turned into an image with an application of render and this series of images is displayed in a separate window. Finally, the function end? is used to inspect each current world. If the result is true, the evaluation of the big-bang expression is stopped; otherwise it continues.
Coming up with big-bang expressions for interactive programs demands a different skill, namely, the skill of systematically designing a program. Indeed, you may already feel that these first two chapters are somewhat overwhelming and that they introduced just too many new concepts. To overcome this feeling, the next chapter takes a step back and explains how to design programs from scratch, especially interactive programs.
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 understand the vocabulary of the programming language; we need to figure out its grammar; and we must know what “phrases” mean.
On the other hand, when we are learning to program, 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 we can ignore. We need to understand what the program consumes, what it produces, and how it relates inputs to outputs. We must 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, and leaving it all alone when the results look decent. This approach to programming, often dubbed “garage programming,” is common and succeeds on many occasions; on some it is even the foundation for a start-up company. Nevertheless, the company cannot sell the results of the “garage effort” because they are usable only by the programmers themselves. These programs are like the first two batch programs we wrote in the preceding chapter.
In practice, a good program must come 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. Best of all the program should be connected to the problem statement in such a way 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. The reason is that most programs are large, complex collections of collaborating functions, and nobody can write all these functions in a day. So programmers join projects, write code, leave projects, and others take over their work. One part of the problem is that the programmer’s customers 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 program, the design recipe is a
device for diagnosing a novice’s difficulties. For yet others, the design
recipe may just be something that they can apply to other areas, say
medicine, journalism, or engineering, because program design isn’t the
right choice for their careers. Then again, for those of you 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 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—
One insight from this concise description is that information plays a central role. 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” and similar phrases.
For a program to process information, it must turn it into some form data, i.e., values in the programming language; then it processes the data; and once it is finished, it turns the resulting data into information again. A program may even intermingle these steps, acquiring more information from the world as needed and delivering information in between. You should recall that we apply the adjective “batch” to the plain programs and the others are called “interactive.”
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 trivial information, you should know about parsing—
BSL and DrRacket cleanly separate these tasks so that you can focus on designing the “core” of programs and, when you have enough expertise with that, you can learn to design the rest. Indeed, real software engineers have come up with the same idea and have a fancy name for it, model-view-control (MVC), meaning a program should separate its information processing view from the data processing model. Of course, if you really wish to make your programs process information, you can always use the "batch-io" teachpack to produce complete batch programs or the "universe" teachpack to produce complete interactive programs. As a matter of fact, to give you a sense of how complete programs are designed, this book and even this chapter provide a design recipe for such programs.
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 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, e.g., “temperature” for numbers. Even this limited knowledge, though, suffices to explain the outline of our design process.
- Articulate how you wish to represent information as data. A one-line comment suffices, e.g.,
; We use plain numbers to represent temperatures.Formulate a data definition, like the one for Temperature above, if you consider this class of data a critical matter for the success of your program.
Starting with the next section, the first step is to formulate a true data definition, because we begin to use complex forms of data to represent information.
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 a parameter per 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 somehow reflect what kind of data the parameter represents. In other cases, 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 third step is to take inventory, i.e., 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; that is, 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 result is 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 exercise. 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 says these exercises are practice exercises that you should solve to internalize the process. Until you internalize the design process, you should never skip a step; it leads to easily-avoided errors and unproductive searches for the causes of errors. There is plenty of room left in programming for complex errors. We have no need to waste our time on silly errors.
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 create a language as they work through problems with domain experts.
And knowledge about the library functions in the chosen 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 should understand 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 the data 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 the book introduces complex forms of data, the design of functions demands deep knowledge in computer science.
Not all programs consist of a single function definition. Some require several functions, for many you also want to 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 the results from the given data. In some sense, you should add these global constants to your template, because they belong to the inventory of things that may contribute to the 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.
The issue with multi-function programs is complex. On 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 “desired 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 flaws in a program. Sloppy testing quickly leads to functions with hidden problems, also known as bugs. Buggy functions then stand in the way of progress on large systems that use these functions, often in multiple ways.
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 though BSL’s unit testing framework is especially tuned for novice programmers. One day you will switch to some other programming language, and 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, i.e., 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 is the beginning of 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, often 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 question is 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, 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, etc. 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, i.e., 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, it should be obvious that the only thing that changes is its distance to the left (or right) border of the canvas. A distance is measured in numbers, meaning the following is an adequate data definition for this example.An alternative is of course 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 to 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 what you decide you need to design several or all of the following four functions:
- if your world should react to clock ticks:
- if your world should react to key strokes:
- if your world should react 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, to write “the number of pixels from the left margin” is an ambiguous interpretation statement. 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 32: 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 the 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 step to our sample problem. Since the car is supposed to move continuously across the canvas, and since the problem statement doesn’t mention any other action, we have two functions on our wish list: tock for dealing with a clock tick and render for creating an image from the state of the world.
> (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 so 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 33: Finish the sample exercise 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 Y-CAR and BACKGROUND. 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 36: 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 and change remember so that it also ignores all special one-character strings.
Let us look at a program that interacts with the mouse. The figure below displays the simplest such program, i.e., 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 ignore 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.
The purpose of this exercise section is to create 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 37: 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 39: 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.
This program is separate from the cat world program in the first two exercises. Do not integrate this program with the cat program of the previous exercise; you don’t know enough yet. If you think you want to make the cat and the happiness gauge play together read the next section. 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, which is 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 for data representation: 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 of 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, i.e., function 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 cases, 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 just 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, i.e., our first analysis of problem statements. For other pieces of code, we use whatever construct is most convenient.
Imagine designing a function that, as part of a game-playing program, computes some good-bye sentence at the end of the game. You might come up with a definition like this one:
If you just look at the cond expression it is impossible to know which of the three cond clauses is going to be used. And that is the point of a function of course. The function deals with many different inputs here: 2, 3, 7, 18, 29, etc. For each of these inputs, it may have to proceed in a different manner. Differentiating the different classes of inputs is the purpose of the cond expression.
Exercise 41: 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 42: 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 cases to make DrRacket happy.
Exercise 43: 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 ingredient of an enumeration is that it defines a collection of data as one of a number of pieces of data. Each item of the sequence explicitly spells out which piece of data belongs to the class of data that we name. 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" or "right" arrow key.
Figure 10 presents two solutions to this problem. The function on the left is organized according to the basic idea of using one cond line per clause 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 should say "descending" when the UFO’s height is above one third of the height of the canvas. It should switch to "closing in" below that. And finally, when the UFO has reached the bottom of the canvas, the status should notify 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 should deal with the end points. In the context of our example, two points on the number line belong to two intervals: CLOSE belongs to the upper interval and the middle one, while HEIGHT seems to fall into the middle one and the lower one. Such overlaps usually imply problems for programs, and they should 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)— should say "descending" when the UFO’s height is above one third of the height of the canvas. It should switch to "closing in" below that. And finally, when the UFO has reached the bottom of the canvas, the status should notify the player that the UFO has "landed."
; 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) (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")]) 10 10 (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 [(boolean? 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 should 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 might mean the distance between the top of the canvas and the reference point.
Exercise 45: 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:
- 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 45 you also know that HEIGHT and 0 are special points for the third clause of the data definition.
Clearly, (show -3) and (show -1) should 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 should still rest 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:
Last but not least, you should determine the result you now expect from (show 0). It is a simple but revealing exercise.
Exercise 46: Why would it be incorrect to formulate the first condition as (string=? "resting" x)? Conversely, formulate a completely accurate condition, i.e., 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)]))
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 the Prologue.
(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 48: Define main2 so that you can launch the rocket and watch it lift off. Read up on the on-tick clause and specify that one tick is actually one second.
If you watch the entire launch, you will notice that once the rocket reaches the top, something curious happens. Explain what happens. Add a stop-when clause to main2 so that the simulation of the lift-off stops gracefully when the rocket is out of sight.
Solving the exercise demonstrates that you now have a complete, working
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 $1,000 or less, are not taxed. Luxury items, with a price of $10,000 or more, are taxed at the rate of eight (8) percent. Everything in between comes with a five (5.25) percent 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, you 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 each other class so that your function can distinguish the subclasses, too.Example: 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, nothing changes.Example: Here is the material for our running example.
For functional examples, however, it is imperative that you pick at least one example per 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 the interior.
Example: 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 out first attempt:
961.36Stop for a moment and think about the table entries with question marks.
The point of these question marks is to point out that the problem statement uses the somewhat vague phrase “those costing $1,000 or less” and “$10,000 or more” to specify the tax table. While a programmer may immediately jump to the conclusion that these words mean “strictly less” or “strictly more,” a lawmaker or tax accountant 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 company would have to ask the tax-law specialist in the company or the state’s tax office.
Once you have figured out how the boundaries are supposed to be interpreted in the domain, you should also revise the data definition. Modify the data definition above to ensure that you can do so.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.
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 to you. 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 is about 17 subclasses, the cond expression contains 17 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.
The fifth step is 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, you assume that the input parameter meets the condition and you take a look at a corresponding example. To formulate the corresponding result expression, you write down the computation for this example as an expression that involves the function parameter. Ignore all other possible kinds of input data when you work on one line; the other cond clauses take care of those.
Last but not least, run the tests and make sure that the tests cover all cond clauses in the function.
Let us exploit our knowledge to create a world that simulates a traffic light. Just as a reminder, a traffic light in the US functions as follows. When the light is green and it is time to stop the traffic, the light turns yellow and after that it turns red. Conversely, when the light is red and it is time to get the traffic going, the light switches to green. There are a few other modes for a traffic light, but we ignore those here.
The figure above summarizes this description as a state transition diagram. Such a diagram consists of states and arrows that connect these states. Each state is one possible configuration. Here the states depict a traffic light in one particular state: red, yellow, or green. Each arrow shows how the world can change, from which state it can transition to which other 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 by.
In many cases, state transition diagrams have only a finite number of states and arrows. Computer scientists call such diagrams finite state machines or automata, 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, i.e., 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—
Our second figure 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 trivial to interpret each data element as a representation of a concrete “world state” and vice versa. Also, the arrows are now labeled with tick suggesting 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 a simulation of 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 50: The goal of this exercise is to 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 its argument as 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, etc. You may also 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, because 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 still closed but pushing at the door opens it. Once you have passed through the door and you let go, the automatic door closer takes over and closes the door again. When a door is closed, you can lock it 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 you need to push the door open. The remaining transition is unlike the others, because it doesn’t require any activities on your side. Instead, the door closes automatically over time. The corresponding transition arrow is labeled with *time* to emphasize this bit.
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 a data representation for all those things that change over time. A bouncing ball with constant speed still 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 for you, 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 (possibly several) mechanism for combining several pieces of data into one piece and, conversely, for retrieving those values later. BSL is no exception; it offers structure type definitions as the fundamental mechanism for combining several values into one piece of data. More generally, a structure type definition introduces many different functions, including one for creating structure instances, or structures for short, and several for extracting values from instances (keys for opening the compartment of a box and retrieving its content). The chapter starts with the mechanics of defining structure types, the idea of creating instances of these structure type, and then discusses the entire universe of BSL data. After presenting a design recipe for functions that consume structures, we end the chapter with a look at the use of structures in world programs.
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 `structure values as containers from which we can extract other values. Of course, 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 stepper.
When placed in such a context, you cannot walk a straight path from a point to the origin; instead you must follow the grid pattern. For a point such as (3,4), a local might tell you “go three blocks this way, turn right, and then go four blocks” to give you 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 54: 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 “diagonal” manner across the screen. Describing both the location and the velocity of a ball that moves across a 2-dimensional world canvas demands two numbers each: one per direction. For the location part, the two numbers represent the x and y coordinates. For the velocity part they are the changes in the x and y direction; in other words, these “change numbers” must be added to the respective coordinates if we wish 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, arranging information in a hierarchical manner 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 ignore data definitions so far, but we are going to catch up with this in the next section.
Data in Structures: Up to this point, data definitions have been rather boring. We either used built-in collections of data to represent information (numbers, Boolean values, strings) or we specified an itemization (interval or enumeration), which just restricts an existing collection. The introduction of structures adds a bit of complexity to this seemingly simple step.
(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 definition, 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 connection provide some guidance for the organization of programs. 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))Use numbers to describe the content of the three fields but be as precise as possible.
In the first subsection, we developed distance0, a function that consumed a structure and produced a number. To conclude this section, we look at a few more such functions before we formulate 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 representing the x and y coordinate of the mouse click. Design a function that consumes a mouse click and a 100 x 100 scene and adds a red spot to the latter where the former occurred.
(check-expect (scene+dot (make-posn 10 20) MTS) (place-image DOT 10 20 MTS)) (check-expect (scene+dot (make-posn 88 73) BLU) (place-image DOT 88 73 BLU))
; visual constants (define MTS (empty-scene 100 100)) (define BLU (place-image (rectangle 25 25 "solid" "blue") 50 50 MTS)) (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) BLU) (place-image DOT 88 73 BLU)) (define (scene+dot p s) (place-image DOT (posn-x p) (posn-y p) s))
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: UFO abbreviates “unidentified flying object” and in the 1950s, people called these things “flying saucers” and similar names.
(define-struct velocity (dx dy)) ; A Velocity is a structure: (make-vel Number Number) ; interp. (make-vel d e) means that the object moves d steps ; along the horizontal and e 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. These are the “things” that programs manipulate and how information from and about the external world is represented. This universe of data is a collection. In particular, the universe contains all pieces of data from the built-in collections.
The figure shows one way to imagine the universe of BSL. Since there is an infinite number of numbers and an infinite number of strings, the collection of all data is of course also 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 data definition is a description of a collection of data, and the name is then usable in other data definitions and in function signatures. For the latter, 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 second “universe 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, it is indeed possible to construct all these values in a BSL program.
(define-struct ball (location velocity))
The “result” of a data definition for structures is again a collection of data, i.e., those instances to be used with functions. In other words, the data definition for Posns identifies the region shaded with gray stripes in figure 21, which includes all those posns whose two fields contain numbers. At the same time, it is perfectly possible to construct an instance of posn that doesn’t satisfy this requirement, e.g., (make-posn (make-posn 1 1) "hello"), which contains a posn in the x field and a string in the y field.
As above, make sensible assumptions as to what kind of values go with which fields.
Programmers not only write data definitions, they also read them—
for a built-in collection of data (number, string, Boolean, images), choose your favorite examples;
Note: on occasion, people use qualifiers on built-in data collections, e.g., NegativeNumber, OneLetterString etc. You shouldn’t use them unless they are unambiguous, and when someone else used them but you don’t understand, you must ask to clarify the issue—
and you must formulate an improved data definition so that others don’t run into this problem.
for an enumeration, use several of the items of the enumeration;
for intervals, use the end points (if they are included) and some interior point;
for itemizations, deal with each part as suggested for the respective piece here; and
for data definitions for structures, follow the English, i.e., 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 (fst lst male?)) ; Person is (make-person String String Boolean)
(define-struct dog (owner name age happiness)) ; Dog is (make-dog Person String PositiveInteger H)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 that Designing with Itemizations already stated. It no longer suffice to rely on built-in data collections as the representation of information; it is now clear that programmers must create data definitions for each and every problem.
When a problem calls for the representation of pieces of information that belong together or that together describe a natural whole, you need a structure type definition. It should use 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.
As always a data definition for a structure type must introduce a name for the collection of instances that you consider legitimate. Furthermore it must describe which kind of data goes with which field. Use only names of built-in data collections or of collections specified with other data definitions.
In the end, you (and others) must be able to use the data definition to create sample structure instances. Otherwise, something is wrong with your data definition. To ensure that you can create instances, your data definitions should come with one data examples.
Nothing changes for this step. You still need a signature, a purpose statement, and a function header.
Use the examples from the first step to create functional examples. In case one of the fields is associated with intervals or enumerations, make sure to pick end points and intermediate points to create functional examples.
Example: Imagine you are designing a function that consumes a structure and assume that it combines TrafficLight with Number. Since the former collection contains just three elements, make sure to use all three in combination with numbers as input samples.
A function that consumes structures usually—
though not always— must extract the values from the various fields in the structure. To remind you of this possibility, a template for such a function should contain one selector per field. Furthermore, you may wish to write down next to each selector expression what kind of data it extracts from the given structure; you can find this information in the data definition.
Do not, however, create selector expressions if a field value is itself a structure. In general, you are better off making a wish for an auxiliary function that processes the extracted field values.
Use the selector expressions from the template when you finally define the function, but do keep in mind that you 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 in case you make changes.
Exercise 62: Create templates for functions that consume instances of the following structure types:
Exercise 63: Design the function time->seconds, which consumes instances of the time structures developed in exercise 59 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, then you should get 45002.
Exercise 64: 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, the collection of world state data should be a collection of structures. One field is used to keep track of one piece of information, and the other field is related to the second piece of information. Naturally, if the domain world contains more than two independent pieces of information, the structures must have as many fields as there are distinct pieces of information per world state.
(define-struct space-game (ufo tank))
Every time we say piece of information, we don’t mean a single number or a single word (or phrase). You must realize that a piece of information may itself combine several pieces of information. If so, creating a data representation for a world in which each state consists of two independent pieces of information obviously leads to nested structures.
Understanding when you should use what kind of data representation for world program takes practice. To this end, the following two sections introduce several reasonably complex problem statements. We recommend you solve those before you move on to games that you might like to design.
One part of “programming” is to create a text document. You type on your
keyboard and text appears in DrRacket. You press the left arrow on your
keyboard, and the cursor moves to the left. Whenever you press the
backspace (or delete) key, the 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 text-edit other kind of documents, say, your English assignment, you are likely to use other software applications, 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. Changing includes the deletion and the insertion of letters, which in turn, implies some notion of “position” within the text. People call this position a cursor, and most graphical editors display the cursor in such a way that you can easily spot it.
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 65: Design the function render, which consumes an Editor and produces an image.
The canvas for your editor program should be rendered within an empty scene of 200 x 20 pixels. For the cursor, use a 1 x 20 red rectangle. Use black text of size 11 for rendering the text.
Exercise 66: Design the function edit. It consumes two inputs: an editor e and a KeyEvent k. The function’s task is to add all single-character KeyEvent k to the end of the pre field of e, unless it denotes the backspace ("\b") key. In that case, it should delete the character immediately to the left of the cursor (if there are any). Also, the tab "\t" and rubout "\u007F" keys should be ignored. This covers all single-letter key events.
The function pays attention to only two KeyEvents that are longer than one letter: "left" and "right". The former moves the cursor one character to the left (if any), and the latter moves it one character to the right (if any). All other such KeyEvents are ignored.
Note: Develop a solid number of examples for edit, paying attention to special cases. When we developed this exercise, we developed 20 examples, and we turned all of them into tests.
Hint: Think of this function as a function that consumes an enumeration (KeyEvent) and uses auxiliary functions that then 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, string-remove-last, etc. If you haven’t done so, solve the exercises in Functions.
Modify your function edit from exercise 66 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 gathering 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 70: 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 71: 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 73: 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 the 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 74: 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.
In the preceding two chapters, you have encountered two new kinds of data definitions. Those that employ itemization (enumeration, intervals) are used to create small collections from large ones. Those for structures combine several collections. Since this book keeps reiterating that the development of data representations is the starting point for proper program design, it shouldn’t surprise you to find out that on many occasions programmers want to itemize data definitions that involve structures.
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. We start straight with the design of functions on this kind of data, because we have all the other ingredients we need. 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” (small rectangle) that must defend our planet (the bottom of the canvas) from a UFO (“flying saucer”) that descends from the top of the canvas to the bottom. In order to stop the UFO from landing, the player may fire one missile (a triangle smaller than the “tank”). To fire the missile, the player hits the space bar and, 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 movement of the three game objects. First, the tank moves a constant velocity along the bottom of the canvas. The player may use the left arrow key and the right arrow key to change directions. Second, the UFO descends at a constant speed 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” should mean.
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 75: 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) and its objects plus graphical constants that are useful for rendering these objects. Also develop graphical constants for the tank, the UFO, the missile, and some background scenery.
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 shouldn’t surprise you, you should still pay close attention.
; A UFO is Posn. ; interp. (make-posn x y) is the UFO's current location (define-struct tank (loc vel)) ; A Tank is (make-tank Number Number). ; interp. (make-tank x dx) means the tank is at (x ,HEIGHT) ; and that it moves dx pixels per clock tick ; A Missile is Posn. ; interp. (make-posn x y) is the missile's current location
- Here is an instance that describes the tank maneuvering into position to fire the missile:
(make-aim (make-posn 20 10) (make-tank 28 -3))
- This one is just like the previous one but the missile has been fired:Of course the capitalized names refer to the physical constants that you defined.
- Finally, here is one where the missile is close enough to the UFO for a collision:This example assumes that the canvas is more than 100 pixels tall.
The Design Recipe: With a new way of formulating data definitions comes an inspection of the design recipe. This chapter introduces a way to combine two means of describing data, and the revised design recipe reflects this, especially the first step:
When do you need this new way of defining data? We already know that the need for itemizations is due to the distinctions among different classes of information in the problem statement. Similarly, the need for structure-based data definitions is due to the demand to group several different pieces of information.
An itemization of different forms of data—
including collections of structures— is required when your problem statement distinguishes different kinds of information and when at least some of these pieces of information consist of several different pieces.
One thing to keep in mind is that you can split data definitions. That is, if a particular clause in your data definition looks overly complex, you may wish to write down a separate data definition for this clause and then just refer to this auxiliary definition via the name that it introduces.
Last but not least, be sure to formulate data examples for your data definitions.
As always, a function signature should only mention the names of data collections that you have defined or that are built-in. This doesn’t change and neither do the requirement to express a concise purpose statement or to add a function header that always produces a default value.
Nothing changes for the third step. You still need to formulate functional examples that illustrate the purpose statement from the second step, and you still need one example per item in the itemization of the data definition.
The development of the template now exploits two different dimensions: the itemization itself and the use of structures in some of its clauses.
By the first, the body of the template should consist of a cond expression that has as many cond clauses as the itemizations has items. Furthermore, you must add a condition to each cond clause that identifies the subclass of data in the corresponding item.
By the second, if an item deals with a structure, the template should contain the selector expressions—
in the cond clause that deals with the subclass of data described in the item.
When, however, you choose to describe the data with a separate data definition, then you do not add selector expressions. Instead, you develop a separate template for the separate data definition and indicate with a function call to this separate template that this subclass of data is processed separately.
Before you go through the work of writing down a complex template like this kind, you should briefly reflect on the nature of the function. If the problem statement suggests that there are several tasks to be performed, it is likely you need to write down a function composition in place of a template. Since at least one of these auxiliary functions is likely to deal with the given class of input data, you need to develop the template later.
Fill the gaps in the template. It is easy to say, but the more complex we make our data definitions, the more complex this step becomes. The good news is that the design recipe is about helping you along, and there are many ways in which it can do so.
If you are stuck, fill the easy cases first and use default values for the others. While this makes some of the test cases fail, you are making progress and you can visualize this progress.
If you are stuck on some cases of the itemization, analyze the examples that correspond to those cases. Analyze them. See what the pieces of the template compute from the given inputs. Then consider how you can combine these pieces—
possibly with some global constants— to compute the desired output. Consider using an auxiliary function.
Test. If tests fail, go back to the previous step.
Go back to From Functions to Programs, re-read the description of the simple design recipe, and compare it to the above. Also before you read on, try to solve the following exercise.
; Location is one of: ; – Posn ; – Number ; interp. Posn are positions on the Cartesian grid, ; Numbers are positions on the number lineDesign the function in-reach, which determines whether or not a given location’s distance to the origin is strictly less than some constant R.
Note: This function has no connection to any other material in this chapter.
Examples and Exercises: Let us illustrate the design recipe with the design of a rendering function for our space invader game. Recall that a big-bang expression needs such a rendering function to turn the state of the world into an image after every clock tick, mouse click, or key stroke.
We used a triangle that isn’t available in BSL graphical library. No big deal. Since the itemization in the data definition consists of two items, let us make three examples, using the data examples from above: see figure 22. (Unlike the function tables you find in mathematics books, this table is rendered vertically. The left column are sample inputs for our desired function, the right column lists the corresponding desired results. As you can see, we just used the data examples from the first step of the design recipe, and they cover both items of the itemization.
The template contains nearly everything we need to complete our task. In order to complete the definition, we need to figure out for each cond line how to combine the values we have into the expected result. Beyond the pieces of the input, we may also use globally defined constants, e.g., BACKGROUND, which is obviously of help here; primitive or built-in operations; and, if all else fails, wish-list functions, i.e., we describe functions that we wish we had.
the same as the result ofWhat do you call this property in your mathematics courses? Can you think of other possibilities?
Exercise 80: Design the function si-game-over? for use as the stop-when handler. The game should stop if the UFO has landed or if the missile has hit the UFO. For both conditions, we recommend that you check for proximity of one object to another.
Exercise 81: Design the function si-move, which is called for every clock tick. Accordingly it consumes an element of SIGS and produces another one. Its purposes is to move all objects according to their velocity.Don’t be afraid of “magic” here. It just means that you can’t design such a “function” yet. And yes, random isn’t really a mathematical function. For the random moves of the UFO, use the BSL function random:
To test functions that employ random, create a main function that calls an auxiliary function on just the random numbers. That way you can still test the auxiliary function where all the real computation happens.
Exercise 82: Design the function si-control, which plays the role of the key event handler. As such it consumes a game state and a KeyEvent and produces a new game state. This specific function should react to three different key events:
pressing the left arrow ensures that the tank moves left;
pressing the right arrow ensures that the tank moves right; and
pressing the space bar fires the missile if it hasn’t been launched yet.Enjoy the game.
Data representations are rarely unique. For example, we could use a single
structure type to represent the states of a space invader game—