2.1 Arithmetic 2.1.1 The Arithmetic of Numbers 2.1.2 The Arithmetic of Strings 2.1.3 Mixing It Up 2.1.4 The Arithmetic of Images 2.1.5 The Arithmetic of Booleans 2.1.6 Mixing It Up with Booleans 2.1.7 Predicates: Know Thy Data 2.2 Functions and Programs 2.2.1 Functions 2.2.2 Composing Functions 2.2.3 Programs 2.3 How to Design Programs 2.3.1 Designing Functions 2.3.2 Finger Exercises 2.3.3 Domain Knowledge 2.3.4 From Functions to Programs 2.3.5 On Testing 2.3.6 Designing World Programs 2.3.7 Virtual Pet Worlds 2.4 Intervals, Enumerations, etc. 2.4.1 Conditional Computations 2.4.2 How It Works 2.4.3 Enumerations 2.4.4 Intervals 2.4.5 Itemizations 2.4.6 Designing with Itemizations 2.4.7 A Bit More About Worlds 2.5 Adding Structure 2.5.1 Structures 2.5.2 Programming with Structures 2.5.3 The Universe of Data 2.5.4 Designing with Structures 2.5.5 Structure in the World 2.5.6 A Graphical Editor 2.5.7 More Virtual Pets 2.6 Itemizations and Structures 2.6.1 Designing with Itemizations, Again 2.6.2 Mixing up Worlds 2.6.3 Input Errors 2.7 Summary

### 2Fixed-Size Data

#### 2.1Arithmetic

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.

It is not necessary to understand all forms of data or all operations at once; it suffices to know what exists and where to find out more. Here we take a look at the “arithmetic” of BSL, the Beginning Student language. Thus far, we know how to use operations:
• write "(",

• write down the name of a primitive operation op,

• write down the arguments, separated by some space, and

• write down ")".

Recall what you are writing down is called an expression.

Just as a reminder, here is a primitive expression:

(+ 1 2)

It uses +, the operation for adding two numbers, followed by two arguments, which are plain numbers. But here is another, somewhat complex example:

(+ 1 (+ 1 (+ 1 1) 2) 3 4 5)

This second example exploits two points in our description that are open to interpretation. First, some primitive operations may consume more than two arguments. Second, the arguments don’t have to be numbers or data per se; they can be expressions, too.

Evaluating expressions is also straightforward. First, BSL evaluates all the arguments of a primitive application. Second, it “feeds” the resulting pieces of data to the primitive operation, which produces a result. Thus,
 (+ 1 2) = 3
and
 (+ 1 (+ 1 (+ 1 1) 2) 3 (+ 2 2) 5) = (+ 1 (+ 1 2 2) 3 4 5) = (+ 1 5 3 4 5) = 18
These calculations should look familiar, because they are the same kind of calculations that you performed in mathematics classes. You may have written down the steps in a different way; you may have never been taught how to write down a sequence of calculation steps. Yet, BSL performs calculations just like you do, and this should be a relief. It guarantees that you understand what it does with primitive operations and primitive data, so there is some hope that you can predict what your programs will compute. Generally speaking, it is critical for a programmer to know how the chosen language calculates, because otherwise a program’s computation may harm the people who use them or on whose behalf the programs calculate.

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.

##### 2.1.1The Arithmetic of Numbers

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) 0

and use it happily ever after. Or look in the HelpDesk. You will find there that in addition to operations, BSL also recognizes the names of some widely used numbers, e.g., pi and e.

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:
 (define x 3) (define y 4)
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 distance

from 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:
 > x 3 > y 4 > (+ x 10) 13 > (* x y) 12
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.

##### 2.1.2The Arithmetic of Strings

A wide-spread prejudice about computers concerns its innards. Many believe that it is all about bits and bytes—whatever those are—and possibly numbers, because everyone knows that computers can calculate. While it is true that electrical engineers must understand and study the computer as just such an object, programmers and everyone else should never (ever) succumb to this thinking.

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.

BSL includes only one operation that exclusively consumes and produces strings: string-append, which, as we have seen in Prologue: How to Program concatenates two given strings into one. You should think of string-append as an operation that is just like +. While the latter consumes two (or more) numbers and produces a new number, the former consumes two or more strings and produces a new string:
 > (string-append "what a " "lovely " "day" " for learning BSL") "what a lovely day for learning BSL"
Nothing about the given numbers changes when + adds them up; and nothing about the given strings changes when string-append juxtaposes them into one big string.

Exercise 2: Add the following two lines to the definitions area:
 (define prefix "hello") (define suffix "world")
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.

##### 2.1.3Mixing It Up

All other operations concerning strings consume or produce data other than strings. Here are some examples:
• string-length consumes a string and produces a (natural) number;

• string-ith consumes a string s together with a natural number i and then extracts the one-character substring located at the ith position (counting from 0); and

• number->string consumes a number and produces a string.

Also look up substring and find out what it does.

If the documentation in HelpDesk appears confusing, experiment with the functions in the interaction area. Give them appropriate arguments, find out what they compute. Also use inappropriate arguments for some operations just to find out how BSL reacts:
> (string-length 42)

string-length: expects a string, given 42

As you can see, BSL reports an error. The first part “string-length” informs you about the operation that is misapplied; the second half states what is wrong with the arguments. In this specific example, string-length is supposed to be applied to a string but is given a number, specifically 42.

Naturally, it is possible to nest operations that consume and produce different kinds of data as long as you keep track of what is proper and what is not. Consider this expression from the Prologue:

(+ (string-length "hello world") 60)

The inner expression applies string-length to our favorite string, "hello world". The outer expression has + consume the result of the inner expression and 60. Let us calculate out the result:
 (+ (string-length "hello world") 60) = (+ 11 60) = 71
Not surprisingly, calculating with such nested expressions that deal with a mix of data is no different from calculating with numeric expressions. Here is another example:
 (+ (string-length (number->string 42)) 2) = (+ (string-length "42") 2) = (+ 2 2) = 4
Before you go on, construct some nested expressions that mix data in the wrong way, e.g.,

(+ (string-length 42) 1)

Run them in DrRacket. Study the red error message but also watch what DrRacket highlights in the definitions area.

Exercise 3: Add the following two lines to the definitions area:
 (define str "helloworld") (define i 5)
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:
 (define str "helloworld") (define ind "0123456789") (define i 5)

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.

##### 2.1.4The Arithmetic of Images

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.

Your programs can also create an image with primitive operations on images. These primitive operations come in three flavors. The first kind concerns the creation of images:
• 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.

These functions should really have an obvious meaning. All you need to know is that mode strings means either "solid" or "outline" and color strings are strings such as "orange", "black", etc. Play with these functions; enter (ellipse 10 20 "solid" "green") into DrRacket’s interaction window and see what happens. Also use your mouse to save the resulting images.

BSL comes with many more image creation functions. Here is one that creates star images:
 > (star 12 "solid" "green")
Look up the documentation for regular-polygon and experiment.

The second kind of functions on images concern image properties:
• image-width determines the width of a given image in terms of pixels;

• image-height determines the height of an image;

A proper understanding of the third kind of image primitives—functions that compose images—requires the introduction of one new idea: the anchor point. An image isn’t just a single pixels; it consists of many pixels. Specifically, each image is like a photograph, i.e., a rectangle of pixels. One of these pixels—the upper left one—is the designated anchor point. When you use an image primitive to compose two images, the composition happens with respect to the anchor points unless you specify some other point explicitly:

• 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 ybetween 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.

• overlay/align is like overlay but accepts two strings that shift the anchor points to other parts of the rectangles. There are nine different positions overall; experiment with all possibilities!

The "2htdp/image" teachpack comes with many other primitive functions for combining images. As you get familiar with image processing, you will want to read up on those. For now, we introduce three more because they are important for creating animated scenes and images for games:
• 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.

Copy and paste the image into your DrRacket.

Exercise 5: Add the following line to the definitions area:

(define cat )

Create an expression that computes the area of the image. See exercise 1 for how to create expressions in DrRacket.

Exercise 6: Use the picture primitives to create the image of a simple automobile.

Exercise 7: Use the picture primitives to create the image of a simple boat.

Exercise 8: Use the picture primitives to create the image of a simple tree.

##### 2.1.5The Arithmetic of Booleans

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.

Calculating with Boolean values is simple, too. In particular, BSL programs get away with three operations: or, and, and not. These operations are kind of like addition, multiplication, and negation for numbers. Of course, because there are only two Boolean values, it is actually possible to demonstrate how these functions work in all possible situations:
• or checks whether any of the given Boolean values is true:
 > (or true true) true > (or true false) true > (or false true) true > (or false false) false

• and checks whether all of the given Boolean values are true:
 > (and true true) true > (and true false) false > (and false true) false > (and false false) false

• and not always picks the Boolean that isn’t given:
 > (not true) false > (not false) true

It shouldn’t come as a surprise that or and and may be used with more than two Boolean values.

Finally, there is more to or and and than these explanations suggest, but to explain the extra bit requires another look at mixing up data in nested expressions.

Exercise 9: Add the following two lines to the definitions area of DrRacket:
 (define b1 true) (define b2 false)
Create an expression that computes whether b1 is false or b2 is true. So in this particular case, the answer is false. (Why?)

See exercise 1 for how to create expressions in DrRacket. How many possible combinations of true and false can you think of for associating with b1 and b2?

##### 2.1.6Mixing It Up with Booleans

One important use of Boolean values concerns calculations with many different kinds of data. We know from the prologue that BSL programs may name values via definitions. For example, we could start a program like this

(define x 2)

and then compute its inverse:

(define inverse-of-x (/ 1 x))

This works fine, as long as we don’t edit the program and change x to 0.

This is where Boolean values come in, in particular conditional calculations. First, the primitive function = determines whether two (or more) numbers are equal. If so, it produces true, otherwise false. Second, there is kind of BSL expression that we haven’t mentioned so far: the if expression. It uses the word “if” as if it were a primitive function; it isn’t. The word “if” is followed by three expressions, separated by blank spaces (that includes tabs, line breaks, etc). Naturally the entire expression is enclosed in parentheses. Here is an example:

(if (= x 0) 0 (/ 1 x))

This if expression contains the subexpressions (= x 0), 0, and (/ 1 x). The evaluation of this expression proceeds in two steps:
1. The first expression is always evaluated. Its result must be a Boolean.

2. If the result of the first expression is true, then the second expression is evaluated; otherwise the third one. Whatever their results are they are also the result of the entire if expression.

You can experiment with if expressions in the interactions area:
 > (if (= x 0) 0 (/ 1 x)) 0.5
And you can reason out the result of this interaction yourself. Since x is 2, it is not equal to 0. Hence, (= x 0) produces the result false, meaning the third expression is evaluated and its result becomes the result of the entire if expression.

Now imagine you edit the definition so that it looks like this:

(define x 0)

What do you think

(if (= x 0) 0 (/ 1 x))

evaluates to in this context? Why?

In addition to =, BSL provides a host of other comparison primitives. Explain what the following four comparison primitives determine about numbers: <, <=, >, >=.

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.

Images also come with one comparison operation: image=?. Like string=?, image=? compares two images for equality. You may wonder why it is ever necessary to compare strings with each other. So imagine a program that deals with traffic lights. It may use the strings "green", "yellow", and "red". This kind of program may contain a fragment such as this:
 (define current-color ...) (define next-color (if (string=? "green" current-color) "yellow" ...))
The dots here aren’t a part of the program of course. Replace them with a string that refers to a color. It should be easy to imagine that this fragment deals with the computation that determines which light bulb is to be turned on next and which one should be turned off.

The next few chapters introduce better expressions than if to express conditional computations and, most importantly, systematic ways for designing them.

Exercise 10: Add the following line to the definitions area:

(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".

##### 2.1.7Predicates: Know Thy Data

Remember the expression (string-length 42) and its result. Actually, the expression doesn’t have a result; it signals an error. DrRacket lets you know about errors via red text in the interactions area and high-lighting of the expression. This way of marking errors is particular good when you use this expression (or its relatives) deeply nested within some other expression:

(* (+ (string-length 42) 1) pi)

Experiment with this expression by entering it into both DrRacket’s interactions area and in the definitions area (plus clicking on RUN).

Of course, you really don’t want such error-signaling expressions in your program. And usually, you don’t make such obvious mistakes as adding true to "hello world". It is quite common, however, that programs deal with variables that may stand for either a number or a string:
 (define in ...) (string-length in)
A variable such as in can be a place holder for any value, including a number, and this value then shows up in the string-length expression.

One way to prevent such accidents is to use a predicate, which is a function that consumes a value and determines whether or not it belongs to some class of data. For example, the predicate number? determines whether the given value is a number or not:
 > (number? 4) true > (number? pi) true > (number? true) false > (number? "fortytwo") false
As you see, the predicates produce Boolean values. Hence, when predicates are combined with conditional expressions, programs can protect expressions from misuse:
 (define in ...) (if (string? in) (string-length in) ...)

Every class of data that we introduced in this chapter comes with a predicate: string?, image?, and boolean?. Experiment with them to ensure you understand how they work.

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—while useful—play no role in this book. The second direction concerns the degree of exactness that we have mentioned before. There are two predicates: exact? and inexact?, and there are even functions that convert exact numbers into inexact ones, and vice versa. For now, just keep in mind that there are two kinds of numbers. Later, we are going to discuss the nature of numbers in some detail.

Exercise 11: Add the following line to the definitions area of DrRacket:

(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.

Exercise 12: Now relax, eat, sleep, and then tackle the next chapter.

#### 2.2Functions and Programs

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—at least abstractly—functions. Once we can deal with functions, writing programs is within reach, though we need to understand that functions, like people, can collaborate (though following mathematics, we don’t call it “collaboration” but composition).

##### 2.2.1Functions

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.

Like expressions, function definitions in BSL come in a uniform shape:
• 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 “)”.

Just like an expression, the shape of a definition consists of pairs of balanced opening and closing parentheses, mingled with text.

Here are some silly examples:

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—also called arguments or parametersa function consumes. Thus, f is a one-argument function, which we also refer to as a unary function. In contrast, g is a two-argument function, also dubbed binary, and h is a ternary or three-argument function. The expression—often referred to as the function bodydetermines the output.

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.

Variables aren’t data, but they represent data. For example, a constant definition such as

(define x 3)

says that x always stands for 3. The variables in a function header, i.e., the variables that follow the function name, are placeholders for unknown pieces of data in the function body. Consider the following fragment of a definition:

(define (ff a) ...)

Its function header is (ff a), meaning ff consumes one piece of input, and the variable a is a placeholder for this input. Of course, at the time we define a function, we don’t know what its input(s) will be. Indeed, the whole point of defining a function is that we can use the function many times on many different inputs.

In short, the function bodies of useful functions refer to the function parameters. A reference to a function parameter is really a reference to the piece of data that is the input to the function. If we complete the definition of ff like this
 (define (ff a) (* 10 a))
we are saying that the output of a function is ten times its input. Presumably this function is going to be supplied with numbers as inputs, because it makes no sense to multiply images or Boolean values or strings with 10.

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.

Applications: A function application puts defined functions to work and it looks just like the applications of a primitive operation:
• write “(”,

• write down the name of a defined function f,

• write down as many arguments as f consumes, separated by some space, and

• write down “)”.

With this bit of explanation, you can now experiment with functions in the interactions area just as we suggested you experiment with primitives to find out what they compute. The following four experiments, for example, confirm that f from above produces the same value no matter what input it is applied to:
 > (f 1) 1 > (f 2) 1 > (f "hello world") 1 > (f true) 1
Evaluate (f (circle 3 "solid" "red")) in the interactions area to show that not even images as inputs change f’s behavior. Here is what happens when the function is applied to too few or too many arguments:
> (f)

f: expects 1 argument, but found none

> (f 1 2 3 4 5)

f: expects only 1 argument, but found 5

It signals an error that is just like those you see when you apply a primitive to the wrong number of arguments:
> (+)

+: 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.

Here is a sample calculation for f:
 (f (+ 1 1)) = (f 2) = 1
It is time to explore the stepper in DrRacket. Enter the definition of ff into the definitions area, followed by the expression (ff (+ 1 1)). Then click the STEPPER. When the stepper window comes up, use the NEXT STEP and watch how the stepper performs the same calculations as we do. In general, the interactions area computes what an expression evaluates to while the stepper displays how this evaluation proceeds. Of course, because x does not occur in the body of f, replacing all occurrences of x with 2 produces just the function body, which is 1. For ff, whose parameter is a and whose body is (* 10 a), we get a very different kind of calculation:
 (ff (+ 1 1)) = (ff 2) = (* 10 2) = 20

Functions don’t have to be applied at the prompt in the interactions area. It is perfectly acceptable to use function applications nested within an expression:
 > (+ (ff 3) 2) 32 > (* (ff 4) (+ (ff 3) 2)) 1280
Using our rules of computation, these results are predictable. Here is the calculation for the first expression:
 (+ (ff 3) 2) = (+ (* 10 3) 2) = (+ 30 2) = 32
Naturally, we can reuse the result of this calculation to determine the result of the second expression:
 (* (ff 4) (+ (ff 3) 2)) = (* (* 10 4) (+ (ff 3) 2)) = (* 40 (+ (ff 3) 2)) = (* 40 32) = 1280
In short, programs compute in the same way as students in middle school and high school: via substitution and via arithmetic.

This description also generalizes to functions that process strings, Boolean values, images, and other forms of data. Recall the following “law” of string arithmetic:
 (string-append "hello" " " "world") = "hello world"
Now suppose we define a function that creates the opening of a letter:
 (define (opening first last) (string-append "Dear " first ","))
An experiment in the interactions area yields the expected result:
 > (opening "Matthew" "Krishnamurthi") "Dear Matthew,"
Most importantly, though, our laws of evaluating expressions explain why this result is the proper one:
 (opening "Matthew" "Krishnamurthi") = (string-append "Dear " "Matthew" ",") = "Dear Matthew,"

To summarize, this section introduces the notation for function applications—the way of putting functions to work—and the mechanism for evaluating function applications and expressions in general. Our key insight is that substitution of argument values for parameters plus basic laws about primitive operations empower us to predict how a function or an expression compute their results—a critical ability if we wish to understand what our programs really do and not just blindly hope for the best.

Exercise 13: Define a function that consumes two numbers, x and y, and that computes the distance of point (x,y) to the origin.

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 14: Define the function cube-volume, which accepts the length of a side of a cube and computes its volume. If you have time, consider defining cube-surface, too.

Exercise 15: Define the function string-first, which extracts the first character from a non-empty string. Don’t worry about empty strings.

Exercise 16: Define the function string-last, which extracts the last character from a non-empty string. Don’t worry about empty strings.

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.

##### 2.2.2Composing Functions

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—built-in primitives as well as functions that you define—and turn the result of one function application into the input for another. In analogy to middle school mathematics, we call this way of defining functions composition, and we call these additional functions auxiliary functions or helper functions.

Consider a program for filling in letter templates. It consumes the first and last name of the addressee, an opening with the letter body, and a closing:
 (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))
Now enter these four definitions into the definitions area and click on RUN. You can then evaluate expressions in the interactions area and create small letters:
 > (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"
Note how the result is a long string that contains occurrences of "\n". These substrings represent the newline character within a string. Once the string is written to a file, it is broken into actual lines wherever "\n" occurs.

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:

The advantage of following this slogan is that you get reasonably small functions, each of which is easy to comprehend, and whose composition is easy to understand. Later, we see that creating small functions that work correctly is much easier than creating one large function. Better yet, if you ever need to change a part of the program due to some change to the problem statement, it tends to be much easier to find the relevant program parts when it is organized as a collection of small functions.

Here is a small illustration of this point with a sample problem:

Sample Problem: Imagine the owner of a movie theater who has complete freedom in setting ticket prices. The more he charges, the fewer the people who can afford tickets. In a recent experiment the owner determined a precise relationship between the price of a ticket and average attendance. At a price of \$5.00 per ticket, 120 people attend a performance. Decreasing the price by a dime (\$.10) increases attendance by 15. Unfortunately, the increased attendance also comes at an increased cost. Every performance costs the owner \$180. Each attendee costs another four cents (\$0.04). The owner would like to know the exact relationship between profit and ticket price so that he can determine the price at which he can make the highest profit.

While the task is clear, how to go about it is not. All we can say at this point is that several quantities depend on each other.

When we are confronted with such a situation, it is best to tease out the various dependencies one at a time:
1. 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:

 (define (attendees ticket-price) (+ 120 (* (/ 15 0.1) (- 5.0 ticket-price))))
2. The revenue is exclusively generated by the sale of tickets, meaning it is exactly the product of ticket price and number of attendees:

 (define (revenue ticket-price) (*  (attendees ticket-price) ticket-price))
3. 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:

 (define (cost ticket-price) (+ 180 (* 0.04 (attendees ticket-price))))
4. Finally, profit is the difference between revenue and costs:

 (define (profit ticket-price) (- (revenue ticket-price) (cost ticket-price)))

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.

These four functions are all there is to the computation of the profit, and we can now use the profit function to determine a good ticket price.

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.

Here is an alternative version of the same program, given as a single function definition:
 (define (profit price) (- (* (+ 120 (* (/ 15 0.1) (- 5.0 price))) price) (+ 180 (* 0.04 (+ 120 (* (/ 15 0.1) (- 5.0 price)))))))
Enter this definition into DrRacket and ensure that it produces the same results as the original version for \$1, \$2, \$3, \$4, and \$5. A single look should suffice to show how much more difficult it is to comprehend this one function compared to the above four.

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.

##### 2.2.3Programs

You are ready to create simple programs. On the surface, a program is just a bunch of function definitions. From a different perspective, namely the one of invoking or launching a program, however, there are at least two distinct kinds of programs:
• 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.

There are other kinds of programs, and you will get to know those as you continue to study computer science.

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.

Global Constants: The prologue demonstrates that good programmers want to define constants in addition to functions. To define a constant means to give a name to a value. In BSL, such a definition has the following shape:
• write “(define ”,

• write down the name of the variable,

• ... followed by a space and an expression,

• write down “)”.

The name of a constant is a global variable while the definition is called a constant definition. We tend to call the expression in a constant definition (the) right-hand side (of the definition).

As also illustrated in the prologue, constants come in all shapes and forms: numbers, images, strings, and so on. Here are some simple examples,
 ; 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))
The first two are numeric constants, the last two are strings and images. We use upper-case letters for global constants by convention, because it ensures that no matter how large the program is, the readers of our programs can easily distinguish such variables from others.

All functions in a program may refer to these global variables. A reference to a variable is just like using the corresponding constants. The advantage of using variable names instead of constants is that a single edit of a constant definition affects all uses. For example, we may wish to add digits to ALMOST-PI or enlarge an empty scene:
 (define ALMOST-PI 3.14159) ; an empty scene: (define MT (empty-scene 200 800))

Our sample definitions employ literal constants on the right hand side even though a constant definition allows arbitrary expressions. Here is how a programmer can use the extra power. Suppose a program needs to deal with an image of some size and its center:
 (define WIDTH 100) (define HEIGHT 200) (define MID-WIDTH (/ WIDTH 2)) (define MID-HEIGHT (/ HEIGHT 2))
The first two definitions are conventional. The latter two introduce so-called computed constants, i.e., variables whose values are not just literal constants but the results of some calculations.

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.

Once programs are created, you want to use or launch them. For a batch program, to launch means to invoke the main function. Recall the letter program from the chapter on Composing Functions. We launched this program once, with the inputs "Matthew", "Krishnamurthi", and "Felleisen". Of course, programs are useful because you can launch them for many different inputs, and this is true for letter, too:
 > (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.

You can produce some batch programs with the "batch-io" teachpack, which adds two functions to our vocabulary: of task:
• read-file, which reads the content of an entire file as a string, and

• write-file, which creates a file from a given string.

When you evaluate these expressions in DrRacket, you need to save the definitions area in a file first, because write-file and read-file work only in the same directory as your program. For example, (write-file "sample.dat" "212") would create a file with the number
 212
in it and nothing else, not one extra character. Conversely, evaluating (read-file "sample.dat") immediately afterwards produces the string "212":
 > (write-file "sample.dat" "212") "sample.dat" > (read-file "sample.dat") "212"
The result true for the use of write-file is just an acknowledgment that the creation of the file from the string happened. The function produces false if the file exists; furthermore it replaces its content with the given string.

In the context of our letter-writing program, experiment with the following expression in the interactions area:
 (write-file "Matthew-Krishnamurthi.txt" (letter "Matthew" "Krishnamurthi" "Felleisen"))
Doing so deposits the string that our letter function produces into the file, though with the substring "\n" interpreted as a newline:
 Dear Matthew, we have discovered that all people with the last name Krishnamurthi have won our lottery. So, Matthew, hurry and pick up your prize. Sincerely, Felleisen

From here it is a short step to a simple letter writing program. Here is a main function:
 (define (main fst last signature-name) (write-file (string-append fst "-" last ".txt") (letter fst last signature-name)))
It uses its first two arguments to create a file name for the write-file function. To create the actual letter it uses all three arguments. You can now use main to write many different letters, each of which is deposited in a separate file.

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:

 (define (f2c f) (* 5/9 (- f 32)))

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.

Launching this trivial program in the interactions area works as usual:
 > (f2c 32) 0 > (f2c 212) 100 > (f2c -40) -40
But suppose we wish to use this function as part of a program that reads the Fahrenheit temperature from a file, converts this number into a Celsius temperature, and then creates another file that contains the result.

From here, the rest is about composing functions. Here is the main function, which we call convert just to clarify that main functions don’t have to be called main:
 (define (convert in out) (write-file out (number->string (f2c (string->number (read-file in))))))
Since this convert function composes a large number of “helper” functions, let us step through its body carefully:
• 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;

• which write-file out ... places in the file named out.

Remember, if the file called out already exists, the result of (convert in out) is false; otherwise it is true.

We understand that this long list of explanation might look overwhelming. The average function composition in a pre-algebra course involves two functions, possibly three. In contrast to programs, however, these mathematical exercises are useless and accomplish little. The convert function is the main function of a program and you can use it to accomplish something real. For example,
 > (convert "sample.dat" "out.dat") "out.dat"
You can also create or edit the file "sample.dat" in a file editor. Just be careful that the editor doesn’t add a newline or any other invisible characters. launches the program for the input file named "sample.dat", which we created above, and leaves the result in a file called "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")

Figure 6: Converting Fahrenheit temperatures into Celsius

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—labeled convert—into the same folder as your program, which you may then distribute to your friends (who use the same kind of computer). They can install this program and they can run it—without knowing anything about DrRacket, as long as they create a file called "sample.dat" in the same folder where they installed the program. After the program is run, they can find the result in the file "out.dat".

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.

The following examples don’t work and need to be revised because big-bang now requires a to-draw clause precisely to avoid this problem.

The simplest big-bang expression is this:
If you evaluate this expression in DrRacket, be sure to have your mouse near the STOP because the evaluation doesn’t stop on its own

Here is another big-bang expression:
 (big-bang 100 (on-tick sub1) (stop-when zero?))
It contains two clauses, telling the computer to apply the BSL primitive operation sub1 every time the clock ticks and to check the result with another BSL primitive, zero?. The evaluation of the expression is to stop if this second application produces true. And indeed, when you request the evaluation of this expression in the interactions area, it actually stops and produces 0. Other than that, nothing happens though.

For the third example, we add one clause to the second example:
 (big-bang 100 (on-tick sub1) (to-draw render) (stop-when zero?))
Like the second example, this expression specifies that sub1 is used for every clock tick and zero? is used to test the result of the application. In addition it says that the result of using sub1 is turned into a scene with render.

Unlike sub1 and zero?, render isn’t a part of BSL, meaning we must define it. To do so, we should at least know to what it is applied. For now it suffices to know that it is applied to a number. Given this much information, one reasonable definition for render is this:
 (define (render t) (text (number->string t) 12 "red"))
This function converts the given number into a string and then creates an image from this string (with a 12-point, red font).

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.

In order to understand the evaluation of big-bang expressions in general, let us look at a schematic one: Beyond on-tick, to-draw, and stop-when clauses, a big-bang expression may also contain on-key and on-mouse clauses. They are obviously associated with the keyboard and the mouse of your computer, and they mostly function just like the on-tick clause. For now we ignore them, but you should know that there is more to big-bang than we discuss here.
 (big-bang cw0 (on-tick tock) (to-draw render) (stop-when end?))
We assume that the functions tock, render, and end? are either BSL primitive operations or defined functions.

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 this application—whatever it is—becomes the next current world, a relationship that the following table concisely summarizes:

 clock tick 1 2 3 4 5 ... current world (cw) cw0 cw1 cw2 cw3 cw4 ... (tock cw) cw1 cw2 cw3 cw4 cw5 ...

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.

#### 2.3How to Design 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.

Exercise 26: Research the “year 2000” problem and what it meant for programmers.

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—though not all programmers use a method like the design recipe to come up with programs. The rest of this chapter is dedicated to the first baby steps into the world of the design recipe; all of the following chapters refine the design recipe in one way or another.

##### 2.3.1Designing Functions

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—often called the program’s domain in computer science—and the results of a program’s computation are turned into information in this domain.

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—the technology of analyzing text and separating it into its grammatical pieces—and that immediately requires (a lot of) expertise in program design.

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.

Figure 7: From information to data, and back

Given the central role of information and data, program design must clearly start with the connection between them. Specifically, we—the programmers—must decide how to use our chosen programming language to represent the relevant pieces of information as data and how we should interpret data as information. Figure 7 displays this idea abstractly, but let us also make it concrete.

Suppose you are designing a program that consumes information in the form of numbers and that also produces numbers. Then choosing a representation and an interpretation means to understand what a piece of data such as 42 means in the domain:
• 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 key is to know how to go from numbers as information to numbers as data and vice versa.

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.

Here is a data definition that could be useful for one of the examples from above:
 ; Temperature is a Number. ; interp. degrees Celsius
The first line introduces the name of the data collection, Temperature, and tells us that the class consists of all Numbers. So, for example, if we ask whether 102 is a temperature, you can respond with “yes” because 102 is a number and all numbers are temperatures. Similarly, if we ask whether "cold" is a Temperature, you will say “no” because no string belongs to Temperature. And, if we asked you to make up a sample Temperature, you might come up with something like -400.

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.

The Process: Once you understand how to represent input information as data and to interpret output data as information, the design of an individual function proceeds according to a straightforward process:
1. 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.

2. 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:

• 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:

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

what does the function compute?

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,
 ; Number String Image -> Image ; add s to img, y pixels from top, 10 pixels to the left (define (add-image y s img) (empty-scene 100 100))

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.

3. 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:

 ; Number -> Number ; compute the area of a square whose side is len (define (area-of-square len) 0)

 ; Number -> Number ; compute the area of a square whose side is len ; given: 2, expect: 4 ; given: 7, expect: 49 (define (area-of-square len) 0)
4. 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.,
 ; Number -> Number ; compute the area of a square whose side is len ; given: 2, expect: 4 ; given: 7, expect: 49 (define (area-of-square len) (... len ...))
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.

5. 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:
 ; Number -> Number ; compute the area of a square whose side is len ; given: 2, expect: 4 ; given: 7, expect: 49 (define (area-of-square len) (sqr len))

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.

6. 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) 4 > (area-of-square 7) 49
The 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:
1. You miscalculated and determined the wrong expected output for some of the examples.

2. 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.

3. Both the examples and the function definition are wrong.

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.

##### 2.3.2Finger Exercises

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.

Exercise 27: Design the function string-first, which extracts the first character from a non-empty string. Don’t worry about empty strings.

Exercise 28: Design the function string-last, which extracts the last character from a non-empty string.

Exercise 29: Design the function image-area, which computes the area of a given image. Note: The area is also the number of pixels in the picture.

Exercise 30: Design the function string-rest, which produces a string like the given one with the first character removed.

Exercise 31: Design the function string-remove-last, which produces a string like the given one with the last character removed.

##### 2.3.3Domain Knowledge

It is natural to wonder what knowledge it takes to code up the body of a function. A little bit of reflection should tell you that this step demands a good knowledge about the domain of the program, also known as domain knowledge. Indeed, there are two forms of domain knowledge:
1. 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.

2. 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.

Since you can never anticipate in which area you work or with which programming language you must work, it is imperative that you have a solid understanding of the full possibilities of whatever computer languages are around, good, and popular. Otherwise some domain expert with half-baked programming knowledge takes over your job, too.

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.

##### 2.3.4From Functions to Programs

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.

##### 2.3.5On Testing

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—and others to be discussed—it is critical to mechanize tests and not perform them manually in the interactions area. BSL in the DrRacket environment includes a testing facility, as many programming systems do.

To introduce this testing facility, we take a second look at the function that converts temperatures in Fahrenheit to Celsius temperatures from Programs. Here is the definition, reformulated according to the design recipe:
 ; Number -> Number ; convert Fahrenheit temperatures to Celsius temperatures ; given 32, expected 0 ; given 212, expected 100 ; given -40, expected -40 (define (f2c f) (* 5/9 (- f 32)))
Testing the function’s examples requires three interactions and three comparisons between two numbers each. You can formulate these tests as follows and add them to the definitions area in DrRacket:
 (check-expect (f2c -40) -40) (check-expect (f2c 32) 0) (check-expect (f2c 212) 100)
When you now click the RUN button, you see a report from BSL that the program passed all three tests—and you had nothing else to do.

In addition to getting tests run automatically, the check-expect forms show another advantage when tests fail. To see how this works, change one of the above tests so that the result is wrong, e.g.,

(check-expect (f2c -40) 40)

When you now click the RUN button, an additional window pops up. The window’s text explains that one of three tests failed. For the failed test, the window displays three pieces: the actual value, i.e., the result of the function call (-40); the expected value (40); and a hyperlink to the text of the failed test case.

 ; 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)))

Figure 8: Testing in BSL

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 reason—to improve its look or to add a piece of functionality—the next click re-tests the function.

Last but not least, check-expect also works for images. That is, you can and should test image-producing functions. Say you wish to design the function render, which places the image of a car, dubbed CAR, into a background scene, named BACKGROUND. For the design of this function, you may formulate the following tests:
 (check-expect (render 50) ) (check-expect (render 200) )
That is, you could use an image editor to create images of the expected results. Alternatively, you could formulate expressions—possibly in the interactions area of DrRacket—that compute the expected results:
 (check-expect (render 50) (place-image CAR 50 Y-CAR BACKGROUND)) (check-expect (render 200) (place-image CAR 200 Y-CAR BACKGROUND))
Doing so also helps you figure out how to express the function. Both styles are useful, though in this book we prefer the second one.

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.

##### 2.3.6Designing World Programs

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.

DrRacket is a small operating system and the big-bang form from the "universe" teachpack is your means to install event handlers. Specifically, the various clauses in a big-bang expression inform DrRacket which function should deal with which kind of event. Take this expression, for example:
 (big-bang w0 (on-tick cth) (on-key keh) (on-mouse meh) ...)
The three clauses inform DrRacket that
• the function cth mentioned in the on-tick clause is for handling clock ticks;

• keh, specified in the on-key clause, deals with events triggered by key strokes; and

• meh is for processing mouse events.

Once the big-bang expression is evaluated, DrRacket acts just like a real operating system, watching the clock, the key board, and the mouse for events and dispatching to your designated BSL functions.

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:

 event: big-bang e1 e2 e3 e4 current world: w0 w1 w2 w3 w4 clock tick: -- (cth w0) (cth w1) (cth w2) (cth w3) key stroke: -- (keh w0 ...) (keh w1 ...) (keh w2 ...) (keh w3 ...) mouse click: -- (meh w0 ...) (meh w1 ...) (meh w2 ...) (meh w3 ...)
The first row enumerates all events that have taken place since DrRacket started evaluating the big-bang expression, starting with the “big bang” event itself.Although you might imagine that two events happen at the same time, DrRacket arranges all events in a linear sequence. The second row is the current world. As the table says, big-bang installs the given world, dubbed w0, as the first world. The remaining worlds in this row are the results of processing the current event and the previous world. For example, w1 is the world that results from processing event e1 in world w0, which could be (cth w0), (keh w0 ...), or (meh w0 ...). While the remaining cells indicate how to compute all possible future worlds from a world and an event, only one of these results is chosen as the next world, because only one event happens at a time.

Let us make this concrete. Suppose e1 is the key stroke "a", e2 and e3 are clock ticks, and e4 is a “button down” mouse event taking place at the position (90,100). Then
1. w1 is the result of (keh w0 "a"), i.e., the fourth cell in the e1 column;

2. w2 is the result of (cth w1), i.e., the third cell in the e2 column;

3. w3 is the result of (cth w2), i.e., again the third cell in the e3 column; and

4. w4 is the result of (meh w3 90 100 "button-down").

We can actually express these four steps as a sequence of four definitions:
 (define w1 (keh w0 "a")) (define w2 (cth w1)) (define w3 (cth w2)) (define w4 (meh w3 "button-down" 90 100))
and even as a function composition:Composing event handlers is truly important when it comes to testing world programs and removing the occasional error.

(define w4 (meh (cth (cth (keh w0 "a"))) 90 100 "button-down"))

Event handlers really are functions that consume worlds and events and produce worlds.

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.

Let us make this concrete with a sample problem:

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 this problem statement, it is easy to imagine a series of images that the program would display:

Pay special attention as to what changes from image to image.

Assuming you have read the problem statement carefully, and that you understand how the world changes and what stays the same, the design of the world program proceeds in three big steps:
1. 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:
1. “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.

2. 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.

2. 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.

 ; CarState is a Number ; the number of pixels between the left border and the car
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.

3. 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:

1. if your world should react to clock ticks:

2. if your world should react to key strokes:

3. if your world should react to mouse clicks:

4. if you want the world to be rendered to the canvas:

4. 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:
 ; main : CarState -> CarState ; launch the program from some initial state (define (main ws) (big-bang ws (on-tick tock) (to-draw render)))
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:

(main SomeCarState)

When the evaluation of the big-bang expression is terminated (for now, close the world canvas), it returns the current state of the world.

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:

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.

As mentioned in the design recipe, the signature for the clock-tick handler is dictated by what we named the class of data that represents the state of the world. It does need a purpose statement and a header:
 ; CarState -> CarState ; the clock ticked; move the car by three pixels (define (tock ws) ws)
Since the state of the world represents the distance between the left margin of the canvas and the car, and since the car moves at three pixels per clock tick, a concise purpose statement combines these two facts into one. This makes it also easy to create examples and to define the function:
 ; CarState -> CarState ; the clock ticked; move the car by three pixels ; example: ; given: 20, expected 23 ; given: 78, expected 81 (define (tock ws) (+ ws 3))

The last design step calls for tests to confirm that the examples work as expected. So we click the RUN button and test:
 > (tock 20) 23 > (tock 78) 81
Since the results are as expected, the design of tock is finished.

Our second entry on the wish list specifies a function that translates the state of the world into a scene:
 ; CarState -> Image ; place the car into a scene, according to the given world state (define (render ws) (empty-scene 300 50))
As for tock, the signature is dictated by the choice of CarState in our data definition. The purpose statement tells us what the function produces from the given world state, i.e., a scene with a car. The function header is obviously not computing what the purpose statement demands, but this is acceptable for a header.

To make examples for a rendering function, we suggest arranging a table like this:
 ws = 50 ws = 100 ws = 150 ws = 200
It lists the given world states in the first column, and in the second column you see the desired scenes. For your first few rendering functions, you may just wish to draw these images by hand.

Even though this kind of image table is intuitive and explains what the running function is going to display—a moving car—it does not explain how the function creates this result. To get from here to there, we recommend writing down expressions that create the images in a third column of the table:

ws =

50

 (place-image CAR 50 Y-CAR BACKGROUND)

ws =

100

 (place-image CAR 100 Y-CAR BACKGROUND)

ws =

150

 (place-image CAR 150 Y-CAR BACKGROUND)

ws =

200

 (place-image CAR 200 Y-CAR BACKGROUND)
The capitalized names refer to the obvious constants: the image of a car, its fixed y coordinate, and the background scene, which is probably empty.

This extended table suggests a pattern for the formula that goes into the body of the render function:
 ; CarState -> Image ; place the car into a scene, according to the given world state (define (render ws) (place-image CAR ws Y-CAR BACKGROUND))
All you have to do from here is create the car image, an image (start with an empty scene), and determine at which y coordinate you want to place it.

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 used
 (define tree (underlay/xy (circle 10 'solid 'green) 9 15 (rectangle 2 20 'solid 'brown)))
to 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.

 ; AnimationState is a Number ; interp. the number of clock ticks since the animation started
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.

How do you think this program relates to the animate function from Prologue: How to Program?

Exercise 35: Use the data definition from the preceding exercise to design a program that moves a red dot according to a sine wave.

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.

The problem looks easy and suggests a relative straightforward data definition for representing the state of the world:
 ; AllKeys is a String. ; interp. the sequence of keys pressed since ; big-bang created the canvas
Just to emphasize that names don’t matter when used consistently, we don’t use WorldState this time. The second sentence of the problem statement also spells out some physical and graphical constants:
 ; physical constants: (define WIDTH 100) (define HEIGHT 50) ; graphical constant: (define MT (empty-scene WIDTH HEIGHT))

From the data definition and the desire to deal with key events, we get a wish list with two functions:
• the function remember to manage key strokes:
 ; AllKeys String -> AllKeys ; add ke to ak, the state of the world (define (remember ak ke) ak)

• the function show to display the current state of the world:
 ; AllKeys -> Image ; render the string as a text and place it into MT (define (show ak) MT)

Here we spelled out a complete purpose, signature, and header for each function.

Next we need to pick one of the two wishes and finish it. We choose remember and move to example-tests:
 ; 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)
One interpretation for the examples is that some user has entered the word "hello" so far and next presses the space bar, which is represented as the string " "; furthermore, if the state of the world is ever "hello " and the user presses the “w” key, the next state of the world should be "hello w". Both example-tests say that the state of the world represents the key strokes seen so far as a string, when read from left to right; the next key stroke is added at the end. Thus, the examples suggest the obvious function definition:
 ; 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))
Copy the code to DrRacket, click on RUN, and thus confirm that the example-tests work fine.

The design of the remaining function, render, is equally straightforward, mostly because the problem almost dictates the examples:
 ; 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))
The key to the example is that by writing down expressions that construct the desired output, we can easily guess what the function should look like. Notice, though, the whimsically chosen positions of the text; nothing in the problem statement dictates this. We simply pick something and stick to it. If this were a for-money project, you would ask your customer of course if the program works as imagined before you move on to add other features.

As we have said before, tests exist to reveal flaws; they can’t show that the program truly works. For that, you must run the program and experiment, and eventually you must allow the expected user to play with intermediate designs. So here is how you launch this interactive program:

(big-bang "" (on-key remember) (to-draw show))

This opens the world canvas, enabling you to press keys and see them reflected there:

Even though it isn’t immediately obvious, we choose to press the “h” key. The first image shows the empty canvas, the second one reflects the key event.

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)

Figure 9: A mouse event recorder

To play with this program, copy it into the definitions area of DrRacket and click RUN. In the interactions area, evaluate

(big-bang (empty-scene 100 100) (to-draw show) (on-mouse clack))

This opens the world’s canvas and allows you to move the mouse and to record its movement. Doing so produces a canvas that looks roughly like this:

What this picture reveals is that a computer and its operating system do not track every single move of your mouse. Instead they sample mouse events sufficiently often and tell your program about those sample events. Usually these samples are sufficient.

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.

##### 2.3.7Virtual Pet Worlds

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.

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.

Exercise 38: Improve the cat animation with a second, slightly different image:

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.

#### 2.4Intervals, Enumerations, etc.

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.

##### 2.4.1Conditional Computations

Recall the brief introduction to conditional expressions in Prologue: How to Program. Since cond is the most complicated expression form in this book, let us take a close look at its general shape:
 (cond [ConditionExpression1 ResultExpression1] [ConditionExpression2 ResultExpression2] .... [ConditionexpressionN ResultExpressionN])
Like all expressions, a cond expression starts with ( and ends with ). Like all expressions except for function application, a cond is marked with a keyword, in this case of course the word cond. Following the keyword, a programmer writes as many cond-lines as needed; each cond line consists of two expressions, enclosed in opening and closing brackets: [ and ]. The use of brackets isn’t necessary; it is a convention to make cond-lines stand out. Put differently, it is perfectly acceptable to use pairs of [ and ] in place of pairs of ( and ) and vice versa.

Here is a function definition that uses a conditional expression:
 (define (next traffic-light-state) (cond [(string=? "red" traffic-light-state) "green"] [(string=? "green" traffic-light-state) "yellow"] [(string=? "yellow" traffic-light-state) "red"]))
Like the mathematical example in Prologue: How to Program, this example illustrates the convenience of using cond expressions. In many problem contexts, a function must distinguish several different situations. With a cond expression, you can use one line per possibility and thus remind the reader of the code of the different situations from the problem statement.

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.

When the conditions get too complex in a cond expression, you occasionally wish to say something like "in all other cases." For these kinds of problems, cond expressions permit the use of the else keyword for the very last cond line:
 (cond [ConditionExpression1 ResultExpression1] [ConditionExpression2 ResultExpression2] .... [else DefaultResultExpression])
If you make the mistake of using else in some other cond line, BSL in DrRacket signals a mistake:
 > (cond [(> x 0) 10] [else 20] [(< x 10) 30])

cond: found an else clause that isn't the last clause in its cond expression

Just like in the real world, BSL respects grammatical rules above anything else. If the grammar isn’t correct, it makes no sense to figure out what an expression means.

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:

 ; PositiveNumber is a Number greater or equal to 0. ; PositiveNumber -> String ; compute the reward level from the given score s
 (define (reward s) (cond [(<= 0 s 10) "bronze"] [(and (< 10 s) (<= s 20)) "silver"] [(< 20 s) "gold"]))
 (define (reward s) (cond [(<= 0 s 10) "bronze"] [(and (< 10 s) (<= s 20)) "silver"] [else "gold"]))
To formulate the last condition for the function on the left, you must calculate that (< 20 s) holds if
While the calculation looks simple in this case, it is easy to make small mistakes and to introduce bugs into your program. It is therefore better to formulate the function definition as shown on the right, if you know that you want the exact opposite—called a complementof all previous conditions in a cond.

##### 2.4.2How It Works

From reading the Many Ways to Compute and Mixing It Up with Booleans, you roughly know how DrRacket evaluates conditional expressions. Let us recapitulate the idea a bit more precisely for cond expression. Re-consider this definition
 (define (reward s) (cond [(<= 0 s 10) "bronze"] [(and (< 10 s) (<= s 20)) "silver"] [else "gold"]))
The function reward consumes a numeric score (positive number) and produces a color string.

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.

Take for example

(reward 3)

You know that DrRacket replaces function applications with the function’s body after substituting the argument for the parameter:
 (cond [(<= 0 3 10) "bronze"] [(and (< 10 3) (<= 3 20)) "silver"] [else "gold"])
For a cond expression, DrRacket evaluates one condition at a time. For the first one that evaluates to true it replaces the cond with the result expression:
 (cond [(<= 0 3 10) "bronze"] [(and (< 10 3) (<= 3 20)) "silver"] [else "gold"]) = (cond [true "bronze"] [(and (< 10 3) (<= 3 20)) "silver"] [else "gold"]) = "bronze"
In this particular example, the first condition—which the substitution turned into an ordinary expression in the arithmetic of Boolean values—evaluates to true because 0 is less than 3 and 3 is less than 10.

Here is a second example:
 (reward 21) = (cond [(<= 0 21 10) "bronze"] [(and (< 10 21) (<= 21 20)) "silver"] [else "gold"]) = (cond [false "bronze"] [(and (< 10 21) (<= 21 20)) "silver"] [else "gold"]) = (cond [(and (< 10 21) (<= 21 20)) "silver"] [else "gold"])
Note how the first condition evaluated to false now, and as mentioned in Many Ways to Compute the entire cond clause is dropped. The rest of the calculation proceeds as expected:
 ... = (cond [(and (< 10 21) (<= 21 20)) "silver"] [else "gold"]) = (cond [(and true (<= 21 20)) "silver"] [else "gold"]) = (cond [(and true false) "silver"] [else "gold"]) = (cond [false "silver"] [else "gold"]) = (cond [else "gold"]) = "gold"
Like the first condition, the second one also evaluates to false, though in many steps, and so the calculation proceeds to the third cond line. The else tells DrRacket to just replace the entire cond expression with the result expression from this clause.

Exercise 40: Enter the definition of reward and the application (reward 18) into the Definitions area of DrRacket and use the stepper to find out how DrRacket evaluates applications of the function.

Exercise 41: A cond expression is really just an expression and may therefore show up in the middle of another expression:
 (- 200 (cond [(> y 200) 0] [else y]))
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:

(place-image ROCKET X ... MTSCN)

with ... indicating where they differ. Eliminate the common code from the two branches with a reformulation of create-rocket-scene.v5 that uses a nested cond expression.

##### 2.4.3Enumerations

Not all strings represent mouse events. If you looked in HelpDesk when the last section introduced the on-mouse clause for big-bang, you found out that only six strings are used to notify programs of mouse events:
 ; A MouseEvt is one of these strings: ; – "button-down" ; – "button-up" ; – "drag" ; – "move" ; – "enter" ; – "leave"
The interpretation of these strings is quite obvious. One of the first two strings shows up when the computer user clicks the mouse button or releases it. In contrast, the third and fourth are about moving the mouse and possibly holding down the mouse button at the same time. Finally, the last two strings represent the events of a mouse moving over the edge of the canvas, either going into the canvas from the outside or vice versa.

More importantly, the data definition for representing mouse events as strings looks quite different from the data definitions we have seen so far. It is called an enumeration. It should not come as a surprise either that enumerations are common. Here is a simple one:
 ; A TrafficLight shows one of three colors: ; – "red" ; – "green" ; – "yellow" ; interp. each element of TrafficLight represents which colored ; bulb is currently turned on
We call it simplistic because it does not include the "off" state, the "blinking red" state, or the "blinking yellow" state. It is a simplistic representation of the states that a traffic light can take on. Unlike others, this data definition also uses a slightly different phrase to explain what a term (TrafficLight) means but this is an inessential difference.

Programming with enumerations is mostly straightforward. When a function’s input is a class of data whose description spells out its elements on a case-by-case basis, the function should distinguish just those cases and compute the result on a per-cases basis. For example, if you wanted to define a function that computes the next state of a traffic light, given the current state as an element of TrafficLight, you would come up with a definition like this one:
 ; 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"]))
Because the data definition for TrafficLight consists of three distinct elements, the traffic-light-next function naturally distinguishes between three different cases. For each case, the result expression is just another string, the one that corresponds to the next case.

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.

Here is an important example:
 ; A 1String is a string of length 1, ; including " " (the space bar), "\t" (tab), ; "\r" (return), and "\b" (backspace).
You know that such a data definition is proper if you can describe all of its elements with a BSL test. In the case of 1String, you can find out whether some string s belongs to the collection with

(= (string-length s) 1)

An alternative way to check that you have succeeded is to enumerate all the members of the collection of data that you wish to describe:
 ; A 1String is one of: ; – "q" ; – "w" ; – "e" ; – "r" ; – "t" ; – "y" ; ...
In this case you can see that it suffices to go along the key board and to express all keys as strings.

You know where to find the rest of this data definition. The data definition for representing key strokes is a realistic example that employs this same technique. Here is an excerpt:
 ; A KeyEvent is one of: ; – a single-character string, i.e., a string of length 1 ; – "left" ; – "right" ; – "up" ; – "down" ; – ...
The first item in this enumeration describes the same bunch of strings that 1String describes. The clauses that follow enumerate strings for special key events, such as pressing one of the four arrow keys or releasing a key.

If you were asked to design an interactive program with a function for key events, your function should have the following outline:
 ; TrafficLight KeyEvent -> ... (define (handle-key-events w ke) (cond [(= (string-length ke) 1) ...] [(string=? "left" ke) ...] [(string=? "right" ke) ...] [(string=? "up" ke) ...] [(string=? "down" ke) ...] ...))
Again the body of your function consists of a cond expression and for each line in the enumeration of the data definition, your function contains one cond line. The condition in the first cond line identifies the KeyEvents identified in the first clause of the enumeration, the second cond clause corresponds to the second data enumeration clause, and so on.

 ; 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)
 (define (nxt p k) (cond [(= (string-length k) 1) p] [(string=? "left" k) (- p 5)] [(string=? "right" k) (+ p 5)] [else p]))
 (define (nxt p k) (cond [(string=? "left" k) (- p 5)] [(string=? "right" k) (+ p 5)] [else p]))

Figure 10: Conditional functions and special enumerations

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.

##### 2.4.4Intervals

Imagine yourself responding to the following sample design task:

Sample Problem: Design a program that simulates the landing of a UFO.

After a bit of thinking, you should come up with a program like in the figure below. Read the data definition and the function definitions carefully before you read on.

 ; 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)))

Figure 11: Landing a UFO

Before you release this "game" program, however, you may wish to add the display of status line to the canvas:

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."

You are free to use appropriate colors for the status line.

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:

Exercise 44: Determine the integers that each of the four intervals contains.

The interval concept helps us formulate a data definition that captures the revised problem statement better than the "numbers" based definition:
 ; constants: (define CLOSE (/ HEIGHT 3)) ; A WorldState falls into one of three intervals: ; – between 0 and CLOSE ; – between CLOSE and HEIGHT ; – below HEIGHT

Specifically, there are three intervals, which we may picture as follows:

What you see is the standard number line, turned vertical and broken into intervals. Each interval starts with an angular downward-pointing bracket () and ends with an upward-pointing bracket (). The picture identifies three intervals in this manner:
• 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.

Of course, one can also think of the last interval as one that starts at HEIGHT and goes on forever.

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.

BSL functions avoid them naturally due to the way cond expressions are evaluated. Consider this natural organization of a function that consumes elements of WorldState:
 ; WorldState -> WorldState (define (f y) (cond [(<= 0 y CLOSE) ...] [(<= CLOSE y HEIGHT) ...] [(>= y HEIGHT) ...]))
The three cond lines correspond to the three intervals. Each condition identifies those values of y that are in between the limits of the intervals. Due to the way cond lines are checked one by one, however, a y value of CLOSE makes BSL pick the first cond line, and a y value of HEIGHT triggers the evaluation of the second ResultExpression.

If we wanted to make this choice obvious and immediate for every reader of our code, we would use different conditions:
 ; WorldState -> WorldState (define (g y) (cond [(<= 0 y CLOSE) ...] [(and (< CLOSE y) (<= y HEIGHT)) ...] [(> y HEIGHT) ...]))
Note how the second cond line of g uses an and expression to combine a strictly-less check with a less-than-or-equal check instead of f’s <= with three arguments.

Given all that, we can complete the definition of the function that adds the requested status line to our UFO animation:
 ; 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))]))
The function uses a cond expression to distinguish the three intervals. In each cond line, the ResultExpression uses render (from the above figure) to create the image with the descending UFO and then places an appropriate text at position (10,10) with place-image.

To run the animation with this function, you need to change the main function just a tiny bit:
 ; WorldState -> WorldState (define (main y0) (big-bang y0 (on-tick nxt) (to-draw render/status)))

One aspect of this function definition should disturb you, and to clarify why, let us refine the sample problem from above just a tiny bit:

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."

You could imagine such a change to the problem statement after your customer has run your program.

At this point, you have no choice but to change the function render/status at three distinct places because you have three copies of one external piece of information: the location of the status line. To avoid multiple changes for a single element, programmers try to avoid copies. You have two choices to fix this problem here. The first one is to use constant definitions, which we have seen before. The second one is to think of the cond expression as an expression that may appear anywhere in a function, including in the middle of some other expression:
 ; 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)))
In this revised definition of render/status, the cond expression is the first argument to place-image. As you can see, its result is always a text image and it is placed at position (10,10) into the image created by (render y).

##### 2.4.5Itemizations

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.

Here is an obvious example, rewriting an important example from Enumerations:
 ; A KeyEvent is one of: ; – 1String ; – "left" ; – "right" ; – "up" ; – "down" ; – ...
In this case, the KeyEvent data definition should refer to the 1String data definition. Since functions that deal with KeyEvents often deal with 1Strings separately from the rest and do so with an auxiliary function, we now have a convenient way to express signatures for these functions, too.

The description of the string->number primitive, which we used before, employs the idea of an itemization in a sophisticated way. Its signature is
 ; string->number : String -> NorF ; converts the given string into a number; ; produces false if impossible
meaning that the result signature names a simple class of data:
 ; A NorF is one of: ; – false ; – a Number
This itemization combines one piece of data (false) with a large class of data (Number).

Now imagine a function that consumes the result of string->number and adds 3, dealing with false as if it were 0:
 ; 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)]))
As above, the function’s body consists of a cond expression with as many clauses as there are items in the enumeration of the data definition. The first cond clause recognizes when the function is applied to false; the corresponding result is 3 as requested. The second clause is about numbers and adds 3 as required.

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.

This revised version of the “rocket launch” problem requires the user to launch the rocket. Its wording suggests a data definition that represents two classes of states:
 ; A LR (short for: launching rocket) is one of: ; – "resting" ; – non-negative number ; interp. a rocket on the ground or the height of a rocket in flight
One state represents the rocket on the ground; the other one is about a rocket in flight. While the interpretation of "resting" is obvious, the interpretation of numbers is a bit ambiguous. Any given number could refer to at least two different notions of “height:”
1. the word “height” could refer to the distance between the ground and the rocket’s point of reference, say, its center; or

2. it might mean the distance between the top of the canvas and the reference point.

Either one works fine. The second one uses the conventional computer meaning of the word, and is thus slightly more convenient for functions that translate the state of the world into an image.

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.

This revision of the problem calls for three distinct classes of states:
 ; A LRCD (short for: launching rocket count down) is one of: ; – "resting" ; – a number in [-3,-1] ; – a non-negative number ; interp. a rocket resting on the ground, in count-down mode, ;   or the height of an in-flight rocket
The new second class of data—three negative numbers—represent the world after the user pressed the space bar and before the rocket lifts off.

Now that we have the data definition, we write down the obvious physical and graphical constants:

 ; physical constants (define HEIGHT 300) (define WIDTH  100) (define YDELTA 3) ; graphical constants (define BACKG  (empty-scene WIDTH HEIGHT)) (define ROCKET (rectangle 5 30 "solid" "red")) ; use your favorite image
The YDELTA constant describes how fast the rocket moves along the y axis, as specified in the problem statement. The first two constants are made up as is the graphical constant for the rocket.

Recall from Designing World Programs that the next step is to design at least three functions:
• one for displaying the current state of the world as an image:
 ; LRCD -> Image ; render the state as a resting or flying rocket (define (show x) BACKG)

• one for reacting to the user’s key presses, the space bar in this problem:
 ; LRCD KeyEvent -> LRCD ; start the count-down when space bar is pressed, ; and the rocket is resting (define (launch x) x)

• and one for reacting to clock ticks once the simulation is launched:
 ; LRCD -> LRCD ; raise the rocket by YDELTA if it is moving already (define (fly x) x)

While the design strategy for world programs—specifically, the mandates of the "universe" teachpack—dictates the signature, we have added purpose statements that match the problem.

From here, we use the design recipe for functions to create complete definitions for all three of them, starting with examples for the first one:
 (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))
As before in this chapter, we pick one per subclass in the data definition. The first example shows the resting state, the second the middle of a count down, and the last one the rocket in flight. Furthermore, we express the expected values as expressions that draw appropriate images. We used DrRacket’s interaction area to create these images; what would you do?

A first look at the examples suggests the introduction of at least one additional constant:

(define ROCKET-CENTER (/ (image-height ROCKET) 2))

This value is used at least twice to place the rocket at the appropriate place, namely on the ground of the empty scene.

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.

In general, intervals deserve special attention when you make up examples, that is, they deserve at least three kinds of examples: from each end and another one from inside. Since the second subclass of LRCD is a (finite) interval and the third one is a half-open interval, let us add take a closer look at their end points:
• 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:
 (check-expect (show HEIGHT) (place-image ROCKET 10 HEIGHT BACKG))
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:
 (check-expect (show HEIGHT) (place-image ROCKET 10 (- HEIGHT ROCKET-CENTER) BACKG)) (check-expect (show 53) (place-image ROCKET 10 (- 53 ROCKET-CENTER) BACKG))

• Last but not least, you should determine the result you now expect from (show 0). It is a simple but revealing exercise.

Following the precedents in this chapter, show should use a cond expression to deal with the three clauses of the data definition:
 (define (show x) (cond [(string? x) ...] [(<= -3 x -1) ...] [(>= x 0) ...]))
Each clause identifies the corresponding subclass with a precise condition: (string? x) picks the first subclass, which consists of just one element, the string "resting"; (<= -3 x -1) completely describes the second subclass of data; and (> x 0) is a test for all non-negative numbers.

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?

Combining the examples and the above skeleton of the show function yields a complete definition in a reasonably straightforward manner:
 (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)]))
Indeed, this way of defining functions is highly effective and is an essential element of the full-fledged design recipe that we are developing in this book.

Exercise 47: Take a second look at show. An expression of the shape

(place-image ROCKET 10 (- ... 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.

Let us move on to the second function, which deals with the key event to launch the rocket. We have its header material, so we formulate examples as tests next:
 (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)
An inspection of these six examples shows that the first two are about the first subclass of LRCD, the third and fourth concern the count-down, and the last two are about key events when the rocket is already in the air.

Since writing down the sketch of a cond expression worked well for the design of the show function, we do it again:
 (define (launch x ke) (cond [(string? x) ...] [(<= -3 x -1) ...] [(>= x 0) ...]))
Looking back at the examples suggests that nothing changes when the world is in a state that is represented by the second or third subclass of data. Put differently, it is obvious that launch should produce xthe current state of the world—when this happens:
 (define (launch x ke) (cond [(string? x) ...] [(<= -3 x -1) x] [(>= x 0) x]))
Finally, the first example identifies the exact case when the launch function produces a new world state:
 (define (launch x ke) (cond [(string? x) (if (string=? " " ke) -3 x)] [(<= -3 x -1) x] [(>= x 0) x]))
Specifically, when the state of the world is "resting" and the user presses the space bar, the function starts the count-down with -3.

Copy the code into the definitions area of DrRacket and ensure that the above definitions work. At that point, you may wish to add a function for running the program:
 ; LRCD -> LRCD (define (main1 s) (big-bang s (to-draw show) (on-key launch)))
This function does not specify what to do when the clock ticks; after all, we haven’t designed fly yet. Still, with main1 it is possible to run this incomplete version of the program and to check that you can start the count-down.

 ; 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)]))

Figure 12: Launching a count-down and a lift-off

The design of flythe clock-tick handler—proceeds just like the design of the preceding two functions, and the above figure displays the result of the design process. Once again the key is to cover the space of possible input data with a good bunch of examples, especially for the two intervals. These examples ensure that the count-down and the transition from the count-down to the lift-off work properly.

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 program—but also a program that behaves a but strangely. Experienced programmers tell you that using negative numbers to represent the count-down phase is too “brittle.” The next chapter introduces the means to provide a good data definition for this problem. Before we go there, however, let’s summarize how to design programs that consume data described by itemizations.

##### 2.4.6Designing with Itemizations

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.

In this section, we refine the design recipe of From Functions to Programs so that you can proceed in a systematic manner when you must encounter problems concerning functions that consume itemizations, including enumerations and intervals. To keep the explanation grounded, we illustrate the six design steps via the following, somewhat simple example:

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.

So keep this problem in mind as we reconsider the steps of our design recipe:
1. 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:
 ; A Price falls into one of three intervals: ; — 0 through 1000; ; — 1000 through 10000; ; — 10000 and above.
Make sure you understand how these three ranges relate to the original problem.

2. As far as the signature, purpose statement, and function header are concerned, nothing changes.

Example: Here is the material for our running example.
 ; Price -> Number ; compute the amount of tax charged for price p (define (sales-tax p) 0)

3. 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:
 0 537 1000.00 1282 10000.00 12017 0 0 ??? 64.1 ??? 961.36
Stop 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.

4. 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.

Example:

 ; Price -> Number ; compute the amount of tax charged for price p (define (sales-tax p) (cond [(and (<= 0 p) (< p 1000)) ...] [(and (<= 1000 p) (< p 10000)) ...] [(>= p 10000) ...]))
5. 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.

Example:

 ; Price -> Number ; compute the amount of tax charged for price p (define (sales-tax p) (cond [(and (<= 0 p) (< p 1000)) 0] [(and (<= p 1000) (< p 10000)) (* 0.05 p)] [(>= p 10000) (* 0.08 p)]))
6. Last but not least, run the tests and make sure that the tests cover all cond clauses in the function.

Exercise 49: Introduce constant definitions that separate the intervals for low prices and luxury prices from the others so that the legislator in Tax Land can easily raise the taxes even more.

##### 2.4.7A Bit More About Worlds

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.

Figure 13: How a traffic light functions

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—red, yellow, and green—we pick three strings, as shown in the data definition of TrafficLight.

Figure 14: How to represent a traffic light

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.

Now that we know how to represent the states of our world, how to go from one to the next, and that we should do so at every tick of the clock, we can write down the signature, the purpose statement, and a stub for the two functions we must design:
 ; 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))
In the past, we have used the names render and next a lot to name the functions that translate a state of the world into an image and that deal with clock ticks. From now on, we prefix these names with some syllable that suggests to which world the functions belong. The specific functions have been the subject of a design exercise or an actual exercise before, meaning we can leave them to exercises now.

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:
 (define SPACE 5) ; the space between bulbs (define RAD (* SPACE 2)) ; a bulb's radius
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.

Figure 15: A transition diagram for a door with an automatic closer

Following our recipe, we start with a translation of the three real-world states into BSL data:
 ; A DoorState is one of: ; – "locked" ; – "closed" ; – "open"
That is, we use three strings to represent the three states, and the interpretation of these strings is natural.

The next step of a world design demands that we translate the actions in our domain—the arrows in the left-hand diagram—into interactions with the computer that the "universe" teachpack can deal with. Our pictorial representation of the door’s states and transitions, specifically the arrow from open to closed suggests the use of a function that simulates time. For the other three arrows, we could use either keyboard events or mouse clicks or both. Let us uses three keystrokes: "u" for unlocking the door, "l" for locking it, and " " for pushing it open. The right-hand side diagram expresses these choices graphically; specifically, it translates the above state-machine diagram from the world of information into the world of data and function suggestions.

Once we have decided to use the passing of time for one action and key presses for another, we must design functions that map the current state of the world—represented as DoorStateinto the next state of the world. Put differently, we have just created a wish list with two handler functions that have the following signature and purpose statements:
• 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.

The last wish comes from the fact that a simulation should represent states with images.

We start with door-closer. Since door-closer acts as the on-tick handler, we get its signature from our choice of DoorState as the collection of world states:
 ; DoorState -> DoorState ; closes an open door over the period of one tick (define (door-closer state-of-door) state-of-door)
Making up examples is trivial when the world can only be in one of three states. Here we use a table to express the basic idea, just like in some of the mathematical examples before:
 given state desired state "locked" "locked" "closed" "closed" "open" "closed"
This table can easily be expressed as BSL examples:
 (check-expect (door-closer "locked") "locked") (check-expect (door-closer "closed") "closed") (check-expect (door-closer "open") "closed")

The template step demands a conditional with three clauses:
 (define (door-closer state-of-door) (cond [(string=? "locked" state-of-door) ...] [(string=? "closed" state-of-door) ...] [(string=? "open" state-of-door) ...]))
and the process of turning this template into a function definition is dictated by the examples:
 (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"]))
Don’t forget to run the example-tests.

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:

 ; DoorState KeyEvent -> DoorState ; three key events simulate actions on the door (define (door-actions s k) s)
As for door-closer, we summarize the examples in a table:
 given state "locked" "closed" "closed" "open" given key event "u" "l" " " — desired state "closed" "locked" "open" "open"
The examples combine what the above picture shows and the choices we made about mapping actions to keyboard events. Of course, unlike the table of example for door-closer, this table is incomplete. Think of some other examples; then consider why we consider the table sufficient.

From here, it is straightforward to create a complete design:
 (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]))
Note the use of and to combine two conditions: one concerning the current state of the door and another one concerning the given key.

Last but not least we need a function that renders the current state of the world as a scene. For simplicity, let us just use a large text for this purpose:
 ; DoorState -> Image ; translate the current state of the door into a large text (check-expect (door-render "closed") (text "closed" 40 "red")) (define (door-render s) (text s 40 "red"))
Here is how we run the program:
 ; 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)))
Now it is time for you to collect the pieces and run them in DrRacket to see whether it all works.

Exercise 51: During a door simulation the “open” state is barely visible. Modify door-simulation so that the clock ticks only every three seconds. Re-run the simulation.

 ; 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)))

Figure 16: A door-simulation program

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.

##### 2.5.1Structures

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.

DrRacket, which is basically a BSL program, represents such locations with posn structures. A posn structure combines two numbers. That is, a posn is a single value that contains two values. We can create a posn structure with the operation make-posn, which consumes two numbers and makes a posn. For example,
 (make-posn 3 4) (make-posn 8 6) (make-posn 5 12)
are expressions that create posn structures. Each of these structures has the same status as a number or a Boolean or a string as far as computations are concerned. In particular, both primitive operations and functions can consume and produce structures.

Now consider designing a function that computes the distance of some location to the origin of the canvas:

The picture clarifies that “distance” means the length of the most direct path from the location to the top-left corner of the canvas—“as the crow flies” they say.

Here are the signature, header, and purpose statement:
 ; Posn -> Number ; to compute the distance of a-posn to the origin (define (distance-to-0 a-posn) 0)
The key is that distance-to-0 consumes a single value, some posn. It produces a single value, the distance of the location to the origin.

In order to make up examples, you need to know how to compute this distance. For points with 0 as one of the coordinates, the result is the other coordinate:
 (check-expect (distance-to-0 (make-posn 0 5)) 5) (check-expect (distance-to-0 (make-posn 7 0))  7)
For the general case, you could try to figure out the formula from some basic geometry knowledge, or you may recall the formula from your mathematics courses. As you know though, we consider this domain knowledge that you should have but just in case you don’t, we supply it; after all, this domain knowledge isn’t what computer science should teach. Here is the domain knowledge:

With this formula, you can compute the distance of a location from its two coordinates (x,y). Given this formula, we can easily make up some more functional examples from the above data examples:
 (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)
Just in case you’re wondering, we rigged the examples so that the results would be easy to figure out. This isn’t the case for all posn structures.

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.

To describe how posn-x, posn-y, and make-posn are related, we experiment with the functions in the interactions area of DrRacket:
 > (posn-x (make-posn 7 0)) 7
and
 > (posn-y (make-posn 7 0)) 0
The experiments should remind you of equations that are roughly analogous to the equations that govern addition and subtraction; adding z right after subtracting z from a number yields just this original number. In a way the equations only confirm what we already know.

So suppose we have the following definition in the definitions area of DrRacket:

(define a-posn (make-posn 7 0))

Then we can use the two operations as follows in the interactions area window:
 > (posn-x a-posn) 7 > (posn-y a-posn) 0
Naturally, we can nest such expressions:
 > (* (posn-x a-posn) 7) 49 > (+ (posn-y a-posn) 13) 13
In short, posn-x and posn-y are primitive functions that work on posn structures just like + and - work on numbers; figure out what happens when you apply posn-x to a number.

At this point we know enough to complete the definition of distance-to-0. We know that the function’s a-posn parameter is a posn structure and that the structure contains two numbers, which we can extract with (posn-x a-posn) and (posn-y a-posn). Let us add this knowledge to our function outline:
 (define (distance-to-0 a-posn) (... (posn-x a-posn) ... ... (posn-y a-posn) ...))
Using this outline and the examples, the rest is easy:
 (define (distance-to-0 a-posn) (sqrt (+ (sqr (posn-x a-posn)) (sqr (posn-y a-posn)))))

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.

Exercise 52: Evaluate the following expressions:
by hand. Show all steps. Assume that sqr performs its computation in a single step. Check the results with DrRacket stepper.

Exercise 53: The Manhattan distance of a point to the origin considers a path that follows a rectangular grid, like those rigid blocks in Manhattan.

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.

A structure type definition is, as the term says, a form of definition. Here is how the creator of DrRacket defined the posn structure type in BSL:

(define-struct posn (x y))

In general, a structure type definition has this shape:

(define-struct StructureName (FieldName ... FieldName))

The keyword define-struct signals to the reader (and to DrRacket) that a structure type is defined. It is followed by a name, here posn. The third part of a structure type definition is a sequence of names enclosed in parentheses, e.g., (x y); these names are the fields of the structure type.

Unlike a plain function definition, a structure type definition defines many functions simultaneously. Specifically, it defines three kinds of primitive operations:
• 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.

The rest of the program can use these operations as if they were built-in primitives.

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.

This naming convention appears to be complicated but, with a little bit of practice, it is easy to remember. It also immediately explains the functions that come with posns: make-posn is the constructor, posn-x and posn-y are selectors. While we haven’t encountered posn? yet, we now know that it exists and we can confirm our ideas of how it works with experiments in the interactions area. Once again assume that we have

(define a-posn (make-posn 7 0))

in the definitions window. If posn? is a predicate that distinguishes posns from all other values, then we should expect that it yields false for numbers and true for a-posn:
 > (posn? a-posn) true > (posn? 42) false > (posn? true) false > (posn? (make-posn 3 4)) true
Naturally, for Boolean values it also produces false, and when applied to other instances of posn, it returns true.

Enough with posns for a while, let us look at a struct definition that we might use to keep track of entries on a contact list like the one in your cell phone:

(define-struct entry (name phone email))

Just for practice, here are the functions that this definition introduces:
• 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 entryand produces a value; and

• the predicate entry?.

So each entry combines three values or, equivalently, each entry has three fields. Thus, the expression

(make-entry "Sarah Lee" "666-7771" "lee@classy-university.edu")

creates an entry structure with "Sarah Lee" in the name field, "412-666-7771" in the phone field, and "lee@classy-university.edu" in the email field.

One way to think of an structure instance is as a lock box with as many compartments as there are fields:

The box itself carries a label, identifying it as an instance of a specific structure type definition. Each compartment, too, is labeled. All labels in such pictures are italicized. A different structure instance, say,

(make-entry "Tara Harper" "666-7770" "harper@small-college.edu")

is illustrated with a similar box picture, though the content of the compartments differs:

In the context of this imagery, a selector is like a labeled key that opens a compartment with the same label. Of course, in addition to matching labels, the key works only for appropriately labeled boxes.

Let’s us make this concrete again. Enter these definitions
 (define pl (make-entry "Sarah Lee" "666-7771" "lee@classy-university.edu")) (define bh (make-entry "Tara Harper" "666-7770" "harper@small-college.edu"))
into the definitions area and then experiment with expressions like these:
> (entry-name pl)

"Sarah Lee"

> (entry-name bh)

"Tara Harper"

> (entry-name (make-posn 42 5))

entry-name: expects an entry, given (posn 42 5)

When entry-name is applied to the above instance of entry, it extracts the value in the name field; otherwise it signals an error. The other selectors work just fine, too:
 > (entry-email pl) "lee@classy-university.edu" > (entry-phone pl) "666-7771"

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.

Nested Structures: The speed of a moving ball is the number of pixels it moves per clock tick. Its velocity is the speed plus the direction in which it moves. When a ball moves along a horizontal or vertical line, an integer (or a real number) is a perfectly adequate data representation for a its velocity:
• A positive number means the ball moves in one direction.

• A negative number means it moves in the opposite direction.

We can use this domain knowledge to formulate a structure type definition for representing the bouncing ball from the example mentioned at the beginning of this chapter:

(define-struct ball (location velocity))

For a ball moving up and down, both fields are going to contain numbers, with the first one telling us how many pixels the ball is from the top of the canvas and the second one the direction and speed at which it is moving. Thus, (make-ball 10 -3) could represent a ball that is 10 pixels from the top and moves 3 pixels per clock tick toward the top. Remember that computer scientists reverse the direction of the y axis.

Exercise 55: There are other ways to represent bouncing balls. Here is one:
 (define SPEED 3) (define-struct balld (location direction)) (make-balld 10 'up)
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.

Let us use posn structures to represent locations and let us introduce a vel structure type for velocities:

(define-struct vel (deltax deltay))

In case you are wondering, the word “delta” is commonly used to speak of “change” when it comes to simulations of physical activities.

Now we can use instances of ball to represent balls that move in straight lines but not necessarily horizontal or vertical lines:

(define ball1 (make-ball (make-posn 30 40) (make-vel -10 5)))

One way to interpret this instance is to think of a ball that is 30 pixels from the left, 40 pixels from the top. It moves 10 pixels toward the left per clock tick, because subtracting 10 pixels from the x coordinate brings it closer to the left. As for the vertical direction the ball drops at 5 pixels per clock tick, because adding positive numbers to a y coordinate increases the distance to the top.

Since structures instances are values, it should not come as a surprise that for ball1 we create a structure containing a structure. Pictorially, it just means a box may contain boxes:

In this case, the outer box contains two boxes, one per field. In general, structure instances—and thus boxes—can be nested arbitrarily deep, and we are going to study examples of this kind.

Working with values such as ball1 is just like working with plain structures:
> (ball-velocity ball1)

(vel ...)

> (vel-deltax (ball-velocity ball1))

-10

> (posn-x (ball-velocity ball1))

posn-x: expects a posn, given (vel ...)

Applying ball-velocity to ball1 extracts the value of the velocity field, which is an instance of vel. Just like with numeric arithmetic, we can also evaluate nested expressions, e.g., (vel-deltax (ball-velocity ball1)). Since the inner expression extracts the velocity from ball1, the outer expression extracts the value of the deltax field, which in this case is -10. Finally, using posn-x on a velocity signals an error.

Exercise 56: An alternative to the nested data representation of balls is a flat representation:

(define-struct ballf (x y deltax deltay))

Create an instance of ballf that is interpreted in the same way as ball1.

Let us briefly look at the example of contact lists. Many cell phones support contact lists that allow two or three phone numbers per name: one for a home line, one for the office, and one for a cell phone number. Since the information is clearly arranged in a hierarchical manner, the data representation should be similar so that it is easy to go back and forth:
 (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"))
The intention here is that an entry on a contact list has four fields: a name and three phone records. The latter are represented with instance of phone, which separate the area code from the phone number proper.

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.

The purpose of a data definition for structure types is to describe what kind of data each field may contain. For some structure type definitions doing so is easy and obvious:
 (define-struct posn (x y)) ; A Posn is a structure: (make-posn Number Number) ; interp. the number of pixels from left and from top
It doesn’t make any sense to use other kinds of data to create a posn. Similarly, all instances of entry, our structure type definition for entries on a contact lists, are obviously supposed to be strings according to our usage in the preceding section:
 (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
In both cases, it is also easy to describe how a reader should interpret instances of these structures in the application domain.

In contrast, the ball structure type definition allows two distinct interpretations:
 (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
Whichever one we are to use in a program, we must stick to it in a consistent manner. As the preceding section shows, however, it is also possible to use ball structures in an entirely different manner:
 ; 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
To do so, we use names for the two data collections that are not as closely related to the structure type definition as usual. They are just names, however, and as long as we use the names consistently, we can call these data collections whatever we want. Here we introduce a second collection of data (Ball-2d), distinct from the first one (Ball-1d), to describe data representations for balls that move in straight lines across a world canvas. In short, it is possible to use one and the same structure type in two different ways. Of course, within one program you should stick to one and only one use; otherwise you are setting yourself up for problems.

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.

Exercise 57: Formulate a data definition for the above phone structure type definition that accommodates the given examples.

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.

##### 2.5.2Programming with Structures

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.

Since a mouse click is represented with a Posn, the sample problem practically dictates the signature:
 ; 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 (define (scene+dot p s) s)
It also includes a well-phrased purpose statement though, as discussed before, you are better off using the function’s parameters to state it. Doing so establishes a connection between the function and its purpose and helps with the design.

Next we work out a couple of examples using the visual constants suggested in the sample problem and introduced above:
 (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))
The second example clarifies that scene+dot does not just add a dot to an empty image; it really adds it to the given scene. Question is where the dot is added. Given that the function consumes a Posn, we know that the function can extract the values of the x and y fields:
 (define (scene+dot p s) (... (posn-x p) ... (posn-y p) ...))
Once you see these additional pieces in the body of the function, the rest of the definition should be straightforward:
 (define (scene+dot p s) (place-image DOT (posn-x p) (posn-y p) s))
Using place-image the function puts DOT into s at the coordinates contained in p.

 ; 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))

Figure 17: Adding a dot to a scene

A function may produce structures, not just consume then. Indeed, a common kind of function consumes and produces structures:

Sample Problem: Design the function x+ and y-. The former consumes a Posn and increases the x coordinate by 3; the latter consumes a Posn and decreases the y coordinate by 3.

It is easy to imagine that this kind of problem comes up as you are creating a game that moves some object along horizontal and vertical lines.

We can copy the first few steps of the design of scene+dot:
 ; Posn -> Posn ; increase the x coordinate of p by 3 (check-expect (x+ (make-posn 10 0)) (make-posn 13 0)) (define (x+ p) (... (posn-x p) ... (posn-y p) ...))
The signature, the purpose, the example all come almost straight out of the problem statement. Instead of a “header”—a function with a default result—our sketch contains the two selector expressions for Posns. After all, the information for the result must come from the inputs, and the input is a structure that contains two values.

Finishing the design is a small step now. Since the desired result is a Posn and since the latter are created with make-posn, we should use it to combine the pieces in the function skeleton:
 ; Posn -> Posn ; increase the x coordinate of p by 3 (check-expect (x+ (make-posn 10 0)) (make-posn 13 0)) (define (x+ p) (make-posn (+ (posn-x p) 3) (posn-y p)))
Of course, the function must also add 3 to the x coordinate. For practice, we leave the design of y- to you.

Here is a variant of the problem:

Sample Problem: Design the function posn-up-x, which consumes a Posn p and a Number n. It produces a Posn like p with n in the x field.

Functions such as posn-up-x are called updaters and they are extremely useful as we shall see.

We define the function without further ado:
 ; Posn Number -> Posn ; update p's x coordinate with n (check-expect (posn-up-x (make-posn -10 22) 100) (make-posn 100 22)) (define (posn-up-x p n) (make-posn n (posn-y p)))
You should try to understand how we got to this definition. The neatest point is that we can define x+ with posn-up-x:
 ; Posn -> Posn ; increase the x coordinate of p by 3 ; version2 (check-expect (x+ (make-posn 10 0)) (make-posn 13 0)) (define (x+ p) (posn-up-x p (+ (posn-x p) 3)))
Do the same for y-.

When you are given a location and a velocity per time unit (e.g., clock tick), you can find out the next location by “adding” the velocity to the location. Finally, many functions deal with nested structures. We illustrate this point with another small excerpt from a world program.

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 v
Design the function move1, which moves some given UFO for one tick of the clock.

Let us start with some examples that explore the data definitions a bit:
 (define v1 (make-velocity 8 -3)) (define v2 (make-velocity -5 -3)) (define p1 (make-posn 22 80)) (define p2 (make-posn 30 77)) (define u1 (make-ufo p1 v1)) (define u2 (make-ufo p1 v2)) (define u3 (make-ufo p2 v1)) (define u4 (make-ufo p2 v2))
The first four are elements of Velocity and Posn, respectively. The last four combine the first four in all possible combinations. Note that these definitions must be ordered in this manner, unlike function definitions, which can come in any order.

Next we write down a signature, a purpose, and a function header plus some examples:
 ; 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)
For the function examples, we make use of the data examples and our domain knowledge of positions and velocities. Specifically, we know that a vehicle that is moving north at 60 miles per hour and west at 10 miles per hour is going to end up 60 miles north from here and 10 miles west after one hour of driving. (Calculate where it is going to be after two hours.)

Above we decided that a function that consumes a structure instance can (and probably must) extract information from the structure to compute its result. So once again we add selector expressions to the function definition:
 (define (ufo-move u) (... (ufo-loc u) ; a Posn ... (ufo-vel u) ; a Velocity ...))
For good measure we have added comments that explain what kind of value each selector expression extracts. Naturally this knowledge comes from the data definition for UFO.

The addition of the selector expressions and their comments immediately raises the questions whether we shouldn’t refine this sketch even more. After all the elements of Posn and Velocity are also structures and we could extract values from them in turn:
 ... (posn-x (ufo-loc u)) ... (posn-y (ufo-loc u)) ... ... (velocity-dx (ufo-vel u)) ... (velocity-dy (ufo-vel u)) ...
Doing so makes the sketch look quite complex, however. Instead we contemplate how we should combine the given Posn and the given Velocity in order to obtain the next location of the UFO.

Our domain knowledge says that we should “add” the two together, where “adding” can’t mean the operation we usually apply to numbers. So let us just imagine that we had a function for adding a Velocity to a Posn:
 ; Posn Velocity -> Posn ; “add” v to p (define (posn+ p v) p)
Writing down the signature, purpose, and header like this is actually a legitimate way of programming. In this book we call it “making a wish” and indeed “making a wish list,” just as we said we would in From Functions to Programs.

The key is to make wishes in such a way that you can complete the function that you are working on. In this manner, you can split difficult programming tasks into different tasks, a technique that helps you solve problems in reasonably small steps. For our running example, you get this complete definition for move-ufo:
 (define (ufo-move u) (make-ufo (posn+ (ufo-loc u) (ufo-vel u)) (ufo-vel u)))
Because posn+ is a complete—even though bad definition—you can even click RUN and check that DrRacket doesn’t complain about your BSL grammar.

In geometry courses, they called this function translation. Now it is time to focus on posn+. We have completed the first two steps of the design (data definitions, signature/purpose/header), so we must create examples. One easy way to create functional examples for a “wish” is to use the examples for the original function and to turn them into examples for the new function:
 (check-expect (posn+ p1 v1) p2) (check-expect (posn+ p1 v2) (make-posn 17 77))
For this problem, we know that (ufo-move (make-ufo p1 v1)) should produce p2. At the same time, we know that ufo-move applies posn+ to p1 and v1, implying that posn+ must produce p2 for these inputs.

At this point we add selector expressions to our design sketch:
 (define (posn+ p v) (... (posn-x p) ... (posn-y p) ... ... (velocity-dx v) ... (velocity-dy v) ...))
Because posn+ consumes instances of Posn and Velocity and because each piece of data is an instance of a two-field structure, we get four expressions. In contrast to the nested selector expressions from above though, these are simple applications of a selector to a parameter.

If you remind yourself now what these four expressions represent, or if you just recall how we computed the desired results from the two structures, completing the definition of posn+ is straightforward:
 (define (posn+ p v) (make-posn (+ (posn-x p) (velocity-dx v)) (+ (posn-y p) (velocity-dy v))))
The first step is to add the velocity in the x direction to the x coordinate and the velocity in the y direction to the y coordinate. Doing so yields two expressions that compute the two new coordinates. With make-posn we can combine the two coordinates into a single Posn again, as desired.

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.

##### 2.5.3The Universe of Data

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.

Figure 18: The universe of data

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.

Figure 19: The meaning of a data definition

Practically the data definition of preceding chapters restrict built-in collections of data. They do so via an explicit or implicit itemization of all included values. For example, the region shaded with gray stripes in the near-by figure depicts the following data definition:
 ; A BS is one of: ; — "hello", ; — "world", or ; — pi.
While a data definition picking out two strings and one number is silly, note the stylized mix of English and BSL that is used. Its meaning is precise and unambiguous, clarifying exactly which elements belong into BS and which ones don’t.

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.

Figure 20: Adding structure to a universe

The addition of another structure type definition mixes and matches everything, too. Say we add the above structure type definition for ball, which also comes with two fields. As the third bubble in figure 20 shows, this addition creates instances of ball that contain numbers, posns, and so on as well as instances of posn that contain instances of ball. Try it out in DrRacket! Add

(define-struct ball (location velocity))

to the definitions area, hit RUN, and create some structure instances like this:
 > (make-posn (make-ball "hello" 1) false) (posn (ball "hello" 1) false) > (make-posn (make-ball (make-ball (make-posn 1 2) 3) 4) 5) (posn (ball (ball (posn 1 2) 3) 4) 5)
Of course, there are no limits on how far you can nest these structure, as the second expression illustrates. Play with structures and learn.

Figure 21: Imposing a data definition on structures

In mathematics and physics courses, you encounter one such kind of data: cartesian points. They also combine two numbers into one item. As far as the pragmatics of data definitions is concerned, a data definition for structure types describes large collections of data via combinations of existing data definitions with instances. When we write

; Posn is (make-posn Number Number)

we are describing an infinite number of possible instances of posn. Like above, the data definitions use combinations of English, names of other data collections defined elsewhere or built-in, data constructors. Nothing else should show up in a data definition.

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.

Exercise 58: Formulate data definitions for the following structure type definitions:
As above, make sensible assumptions as to what kind of values go with which fields.

Exercise 59: Provide a structure type definition and a data definition for representing points in time since midnight. A point in time consists of three numbers: hours, minutes, and seconds.

Exercise 60: Provide a structure type definition and a data definition for representing three-letter words. A word consists of letters, which we represent with the one-letter strings "a" through "z".

Programmers not only write data definitions, they also read them—to understand a program, to eliminate errors from a program, to expand the kind of data it can deal with, etc. The purpose of reading a data definition is to understand how to create data that belongs to the designated collection of data and to determine whether some piece of daat belongs to some specified class of data.

Since data definitions play such a central and important role in the design process, it is often best to illustrate data definitions with examples just like you illustrate the behavior of functions with examples. And indeed, creating data examples from a data definition is straightforward:
• 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.

That’s all there is to constructing examples from data definitions for most of the book, though data definitions are going to become much more complex than what you have seen so far.

Exercise 61: Create examples for the following data definitions:
•  ; A Color is one of: ; — "white" ; — "yellow" ; — "orange" ; — "green" ; — "red" ; — "blue" ; — "black"

Note: DrRacket recognizes many more strings as colors.

•  ; H (a “happiness scale value”) is a number in [0,100], i.e., ; a number between 0 and 100
•  (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)
•  ; Weapon is one of: ; — false ; — Posn ; interp. false means the missile hasn't been fired yet; ;   an instance of Posn means the missile is in flight
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.

##### 2.5.4Designing with Structures

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.

1. 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.

2. Nothing changes for this step. You still need a signature, a purpose statement, and a function header.

3. 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.

4. 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.

5. 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.

6. 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.

##### 2.5.5Structure in the World

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.

Consider a space invader game, in which some UFO descends along a straight vertical line and some tank moves on the horizontal at the bottom. If both objects move at known constant speeds, all you need to describe these two objects is one piece of information per object: the y coordinate for the UFO and the x coordinate for the tank. So putting those together requires a structure with two fields:

(define-struct space-game (ufo tank))

We leave it to you to formulate an adequate data definition for this structure type definition including an interpretation. You should also ponder the hyphen in the name of the structure. BSL really allows you to use all kinds of characters in the names of variables, functions, structures, and field names. So what are the selector names for this structure? How about the predicate?

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.

Let us return to our imaginary space invader game for a moment. Clearly, an UFO that descends only along a vertical line is boring. If we want to play a game of “tank versus UFO” with some “weapon” on the former, the UFO must be able to descend in non-trivial lines, perhaps jumping randomly. This implies that we need two coordinate to describe the location of the UFO, meaning that our revised data definition for the space game becomes:
 ; SpaceGame is (make-space-game Posn Number). ; interp. (make-space-game (make-posn ux uy) tx) means that the ; UFO is currently at (ux,uy) and the tank's x coordinate is tx

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.

##### 2.5.6A Graphical Editor

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 disappears—if there is a letter to start with.

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.

Now take a look at the following editor configuration:

The red line indicates the cursor. You should have no problem imagining how this configuration came about. You entered the text “helloworld” and then you hit the left arrow key five times, causing the cursor to move from the end of the text to the position between “o” and “w” in this text. If you now press the space bar, the editor should change its display as follows:

In short, it should show the phrase “hello world” with a cursor between the newly inserted space and the “w” from the original text.

Obviously this world program must keep track of two pieces of information:
1. the text entered so far

2. the current location of the cursor.

And this suggests a structure type with two fields.

We can imagine several different ways of going from the information to data and back. For example, one field in the structure may contain the entire text entered and the other the number of characters between the left and the cursor. Another data representation is to use two strings in the two fields: the part of the text to the left of the cursor and the part of the text to its right. Here is our preferred approach to representing the state of an editor:
 (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
Solve the next few exercises based on this data representation.

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.

Exercise 67: Define the function run. It should consume a string for the pre field of an editor and should then launch an interactive editor, using render and edit from the preceding two exercises.

Exercise 68: You should notice that if you type a lot, your editor program does not display all of the text. Instead the text is cut off at the right margin.

Modify your function edit from exercise 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.

Exercise 69: Develop a data representation based on our first idea, i.e., using a string and an index. Then solve exercises exercise 65 through exercise 68 again.

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.

##### 2.5.7More Virtual Pets

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 72: Modify your program of the preceding exercises so that it stops when the cat’s happiness ever falls to 0.

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.

#### 2.6Itemizations and Structures

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.

Remember the imaginary space invader game from near the end of the preceding chapter. Thus far, it involves one UFO, descending from space, and one tank on the ground, moving horizontally. Our data representation uses a structure with two fields: one for the data representation of the UFO and another one for the data representation of the tank. Naturally players will want a tank that can fire a weapon and, all of a sudden, your imaginary game must represent an additional kind of state that contains three independently moving objects: the UFO, the tank, and the missile. Since a world state may now be one of two distinct kinds of structures, it is natural to use an itemization of structures to describe all possible states:
1. the state of the world is a structure with two fields, or

2. the state of the world is a structure with three fields.

As far as our domain is concerned—that is, the actual game—the first kind of state is before the tank has fired the weapon and the second one means the one and only missile has been fired. No need to worry, the next chapter is about firing as many missiles as you want, without reloading.

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.

##### 2.6.1Designing with Itemizations, Again

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.

For the running example, we need a data representation for two different structures to represent the game state:
 (define-struct aim (ufo tank)) (define-struct fired (ufo tank missile))
The first one is for the time period when the player is trying to get the tank in position for a shot; and the second one is for representing states after the missile is fired. Before we can formulate a data definition for the complete game state, however, we need data representations for the tank, the UFO, and the missile, i.e., the game objects.

Assuming constant definitions for such physical constants as WIDTH and HEIGHTwhich you were supposed to develop before reading this subsection—we can formulate the data definitions for the game objects like this:
 ; 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
Each of these data definitions describes nothing but a structure, either a newly defined one (tank) or a built-in data collection (Posn). Concerning the latter, it may surprise you a little bit that Posns are used to represent two distinct aspects of the world. Then again we have used numbers (and strings and Boolean values) to represent many different kinds of information in the “real” world, so reusing a collection of structures such as Posn isn’t a big deal.

Now we are in a position to formulate the data definitions for the state of the space invader game:
 ; A SIGS (short for “space invader game state”) is one of: ; – (make-aim UFO Tank) ; – (make-fired UFO Tank Missile)
The shape of the data definition is that of an itemization. Each clause, however, describes the content of a structure type. Thus one take-away from this definition is that it is not the case that every structure type definition comes with one data definition; here one data definition involves two distinct structure type definitions. Still each item describes structure instances just like those we have seen so far. Most importantly, they define how each field is associated with an existing data collection.

The meaning of such a data definition is also straightforward. It introduces the name SIGS for a collection of data, namely all those structure instances that you can create according to the definition. So let us create some:
• 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:
 (make-fired (make-posn 20 10) (make-tank 28 -3) (make-posn 28 (- HEIGHT TANK-HEIGHT)))
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:
 (make-fired (make-posn 20 100) (make-tank 100 3) (make-posn 22 103))
This example assumes that the canvas is more than 100 pixels tall.

You should notice that the first instance of SIGS is generated according to the first clause of the data definition, and the second and third follow the second clause. Naturally the numbers in each field depend on your choices for global game constants.

Exercise 76: Explain why the three instances are generated according to the first or second clause of the data definition.

Exercise 77: Sketch how each of the three game states could be rendered assuming a 200 by 200 canvas.

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:

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

Recall that the distance of a Cartesian point to the origin is the square root of the sum of the squares of its coordinates. For plain numbers, keep in mind that their y coordinates is 0; conversely, when making up tests, you should know the distance to the origin for Cartesian points whose y or x coordinate is 0.

Exercise 78: A programmer has chosen to represent locations as Cartesian points or just points:
 ; Location is one of: ; – Posn ; – Number ; interp. Posn are positions on the Cartesian grid, ; Numbers are positions on the number line
Design 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.

The signature of a rendering function looks like this
 ; SIGS -> Image ; to add TANK, UFO, and possibly the MISSILE to BACKGROUND (define (si-render s) BACKGROUND)
where we assume that TANK, UFO, MISSILE and BACKGROUND are the requested image constants from exercise 75. You should recall that this signature is just an instance of the general signature for rendering functions, which always consume the collections of world states and produce some image.

s =

si-render

 (make-aim (make-posn 10 20) (make-tank 28 -3))

 (make-fired (make-posn 10 20) (make-tank 28 -3) (make-posn 32 (- HEIGHT TANK-HEIGHT 10)))

 (make-fired (make-posn 20 100) (make-tank 100 3) (make-posn 22 103))

Figure 22: Rendering space invader game states

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.

Next we turn to the development of the template, the most important step of the design process. First, you know that the body of si-render must be a cond expression with two cond clauses. Following the design recipe, the two conditions are (aim? s) and (fired? s), and they distinguish the two possible kinds of data that si-render may consume:
 (define (si-render s) (cond [(aim? s) ...] [(fired? s) ...]))
Second, you must add selector expressions to each of the cond clauses that deals with structured input data. In this case, both clauses concern the processing of structures: aim and fired. The former comes with two fields and thus requires two selector expressions for the first cond clause, and the latter kind of structures consists of three values and thus demands three selector expressions:
 (define (si-render s) (cond [(aim? s) (... (aim-tank s) ... (aim-ufo s) ...)] [(fired? s) (... (fired-tank s) ... (fired-ufo s) ... (fired-missile s) ...)]))
And this is all there is to the template now.

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.

Consider the first cond clause, where you have a data representation of a tank—that is, (aim-tank s), and the data representation of a UFO—that is, (aim-ufo s). From the first example, you also know that you need to add the two objects to the background scenery. In addition, the design recipe suggests that if these pieces of data come with their own data definition, you should consider defining helper (auxiliary) functions. Thus, you should consider this expression
 ... (tank-render (aim-tank s) (ufo-render (aim-ufo s) BACKGROUND)) ...
where tank-render and ufo-render are functions that deal with tanks and ufos, respectively. Here are the two entries for your wish list:
 ; Tank Image -> Image ; add t to the given image im (define (tank-render t im) im) ; UFO Image -> Image ; add u to the given image im (define (ufo-render u im) im)
As you can easily see, the wish list entries are just the result of the second step of the design recipe.

With a bit of analogy, it is easy to see how to deal with the second cond clause in the exact same way:
 (define (si-render s) (cond [(aim? s) (tank-render (aim-tank s) (ufo-render (aim-ufo s) BACKGROUND))] [(fired? s) (tank-render (fired-tank s) (ufo-render (fired-ufo s) (missile-render (fired-missile s) BACKGROUND)))]))
Best of all, we can immediately re-use our wish list functions, tank-render and ufo-render, and all we need to add is a function for adding a missile to an scenery. The appropriate wish list entry for the latter is here:
 ; Missile Image -> Image ; add m to the given image im (define (missile-render m im) im)
As above, the comment describes in sufficient detail what we want.

Exercise 79: Design the functions tank-render, ufo-render, and missile-render. Is the result of
 ... (tank-render (fired-tank s) (ufo-render (fired-ufo s) (missile-render (fired-missile s) BACKGROUND))) ...
the same as the result of
 ... (ufo-render (fired-ufo s) (tank-render (fired-tank s) (missile-render (fired-missile s) BACKGROUND))) ...
What 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:
 ; random : N -> N ; (random n) produces a number in [0,n) (define (random n) ... magic happens here ...)

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.

 ; SIGS.v2 -> Image ; render the given game state and added it to BACKGROUND (define (si-render.v2 s) (tank-render (fired-tank s) (ufo-render (fired-ufo s) (missile-render.v2 (fired-missile s) BACKGROUND))))

Figure 23: Rendering game states again

Data representations are rarely unique. For example, we could use a single structure type to represent the states of a space invader game—if we are willing to change the representations of missiles:

 (define-struct sigs (ufo tank missile)) ; SIGS.v2 (short for “space invader game state” version 2) ; is (make-sigs UFO</