On this page:
1 Arithmetic
1.1 The Arithmetic of Numbers
1.2 The Arithmetic of Strings
1.3 Mixing It Up
1.4 The Arithmetic of Images
1.5 The Arithmetic of Booleans
1.6 Mixing It up with Booleans
1.7 Predicates:   Know Thy Data
2 Functions And Programs
2.1 Functions
2.2 Composing Functions
2.3 Global Constants
2.4 Programs
3 How To Design Programs
3.1 Designing Functions
3.2 Finger Exercises
3.3 Domain Knowledge
3.4 From Functions to Programs
3.5 On Testing
3.6 Designing World Programs
3.7 A Note on Mice and Characters
3.8 Virtual Pet Worlds
4 Intervals, Enumerations, Itemizations
4.1 Programming with Conditionals
4.2 How It Works
4.3 Enumerations
4.4 Intervals
4.5 Itemizations
4.6 Designing with Itemizations
4.7 A Bit More about Worlds
5 Adding Structure
5.1 Structures
5.2 Programming with Structures
5.3 The Universe of Data
5.4 Designing with Structures
5.5 Structure in the World
5.6 A Graphical Editor
5.7 More Virtual Pets
6 Itemizations and Structures
6.1 Designing with Itemizations, Again
6.2 Mixing up Worlds
6.3 Input Errors
7 Summary
6.1.1.3

I Fixed-Size Data

Every programming language comes with a language of data and a language of operations on data. The first language always provides some forms of atomic data; to represent the variety of information in the real world as data, a programmer must learn to compose basic data and to describe such compositions. Similarly, the second language provides some basic operations on data atomic; it is the programmer’s task to compose these operations into programs that perform the desired computations. We use arithmetic for the combination of these two parts of a programming language because it generalizes what you know from grade school.

This part introduces the arithmetic of Beginning Student language (BSL), the programming language used in the Prologue. From arithmetic, it is a short step to your first simple programs, which you may know as functions from mathematics. Before you know it, though, the process of writing programs looks confusing, and you will long for a way to organize your thoughts. We equate “organizing thoughts” with design, and this first part of the book introduces you to a systematic way of designing programs.

1 Arithmetic

It is not necessary to read the entire chapter before you proceed. You may wish to scan some of the material here, skip ahead, and return, when you encounter “arithmetic” functions that you don’t recognize.

From Prologue: How to Program, you know how to write down the kind of expression you know from first grade in BSL notation:
  • write "(",

  • write down the name of a primitive operation op,

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

  • write down ")".

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 the above description that are open to interpretation. First, primitive operations may consume more than two arguments. Second, the arguments don’t have to be numbers per se; they can be expressions, too.

Evaluating expressions is also straightforward. First, BSL evaluates all the arguments of a primitive operation. Second, it “feeds” the resulting pieces of data to the 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.

The rest of this chapter introduces four forms of atomic data of BSL: numbers, strings, images, and Boolean values.The next volume in the design series, How to Design Components, will explain how to create atomic data. We use the word “atomic” here in analogy to physics. You cannot peek inside atomic pieces of data, but you do have functions that combine several pieces of atomic pieces of data into another one, retrieve “properties” of them, also in terms of atomic data, and so on. The sections of this chapter introduce some of these functions, also called primitive operations or built-in operations. You can find others in the documentation of BSL that comes with DrRacket.

1.1 The 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)

that is, in prefix notation form. Here are some of the operations on numbers that our language provides: +, -, *, /, abs, add1, ceiling, denominator, exact->inexact, expt, floor, gcd, log, max, numerator, quotient, random, remainder, sqr, and tan. We picked our way through the alphabet, just to show the variety of operations. Explore what these do in the interactions area, and then find out how many more there are and what they do.

If you need an operation on numbers that you know from grade school or high school, chances are that BSL knows about it, too. Guess its name and experiment in the interaction area. Say you need to compute the sin of some angle; try

> (sin 0)

0

and use it happily ever after. Or look in the HelpDesk. You will find there that in addition to operations, BSL also recognizes the names of some widely used numbers, for example, pi and e.You might not know e if you have not studied calculus. It’s a real number, close to 2.718, commonly called “Euler’s constant.”

When it comes to numbers, BSL programs may use natural numbers, integers, rational numbers, real numbers, and complex numbers. We assume that you have heard of all but the last one. 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 a mathematical 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.

Note The word Number refers to a wide variety of numbers, including counting numbers, integers, rational numbers, real numbers, and even complex numbers. For most uses, you can safely equate Number with the number line from elementary school, though on occasion this translation is too imprecise. If we wish to be precise, we use appropriate words: Integer, Rational, and so on. We may even refine these notions using such standard terms as PositiveInteger, NonnegativeNumber, etc. End

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 computed the distance formula. To use the formula on alternative inputs, you need to open DrRacket, edit the definitions of x and y so they represent the desired coordinates, and click RUN. But this way of reusing the distance formula is cumbersome and naive. Instead, we will soon show you a way to define functions, which makes re-using formulas straightforward. For now, we use this kind of exercise to call attention to the idea of functions and to prepare you for programming with them.

1.2 The 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 need 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. 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 concatenates them into one big string.

Exercise 2. Add the following two lines to the definitions area:
(define prefix "hello")
(define suffix "world")
Then use string primitives to create an expression that concatenates prefix and suffix and adds "_" between them. When you run this program, you will see "hello_world" in the interactions area.

See exercise 1 for how to create expressions using DrRacket.

1.3 Mixing 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.

1.4 The Arithmetic of Images

Images represent symbolic data somewhat like strings. To work with images, use the "image" library. 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 basic 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.

The names of these operations mostly explain what kind of image they create. 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 operations; enter (ellipse 10 20 "solid" "green") into DrRacket’s interaction window and see what happens. Also use your mouse to save the resulting images.To save, (right)click on the image and use the pop-up menu to save the image.

BSL comes with many more image creation operations. Here is one that creates star images:
> (star 12 "solid" "green")

image

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 pixel; it consists of many pixels. Specifically, each image is like a photograph, that is, a rectangle of pixels. One of these pixels is an implicit 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 center as anchor point. You encountered this function in the Arithmetic and Arithmetic.

  • 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 first image’s top-left corner; unsurprisingly, a negative x shifts the image to the left and a negative y up.

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

The "image" library 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.

  • scene+line consumes a 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 counts the number of pixels in 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.

1.5 The 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?

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

1.7 Predicates: 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 particularly helpful 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.

In addition to predicates that distinguish different forms of data, programming languages also come with predicates that distinguish different kinds of numbers. In BSL, numbers are classified in two ways: by construction and by their exactness. Construction refers to the familiar sets of numbers: integer?, rational?, real?, and complex?.Evaluate (sqrt -1) in the interactions area and take a close look at the result. The result you see is the first so-called complex number anyone encounters. While your mathematics teacher may have told you that one doesn’t compute the square root of negative numbers, truth is that real mathematicians and programmers find it acceptable and useful to do so anyway. But don’t worry: understanding complex numbers is not essential to being a programmer. But many programming languages, including BSL, choose to use finite approximations to well-known constants, which leads to somewhat surprising results with the rational? predicate:
> (rational? pi)

#true

As for exactness, we have mentioned the idea before. For now, experiment with exact? and inexact? to make sure they perform the checks that their names suggest. Later we are going to discuss the nature of numbers in some detail.

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 Functions And Programs

As far as programming is concerned, “arithmetic” is half the game; the other half is “algebra.” Of course, “algebra” relates to the school notion of algebra as little/much as the notion of “arithmetic” from the preceding chapter relates to arithmetic taught in grade-school arithmetic. Specifically, the algebra notions needed are: variable, function definition, function application, and function composition. This chapter re-acquaints you with these notions in a fun and accessible manner.

2.1 Functions

A program is a function. Like functions, programs consume inputs and produce outputs. Unlike functions, programs work with a whole variety of data: numbers, strings, images, and so on. Furthermore, events in the real world trigger the launch of software applications, and the evaluation of programs may affect the world. For example, the calendar program on a computer may launch a monthly payroll program on the last day of every month, or a spreadsheet program may react to an accountant’s key presses by filling some cells with numbers. Lastly, programs may not consume all of the data at once; instead a program may decide to process data in an incremental manner.

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:

Like expressions, function definitions in BSL come in a uniform shape. We write down
  • “(define (”,

  • the name of the function,

  • followed by one or more variables, separated by space and ending in “)”,

  • and an expression followed by “)”.

And that is all there is to function definitions. 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 function, a defined function 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.

Useful function bodies 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 by 10.

For now, the only remaining question is how a function obtains its inputs. And to this end, we turn to the notion of applying a function.

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 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" "Fisler")

"Dear Matthew,"

Most importantly, though, our laws of evaluating expressions explain why this result is the proper one:
(opening "Matthew" "Fisler")
=
(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 Boolean operation implication and often use the symbol =>, pronounced “implies,” for this purpose. While BSL could define a function with this name, we avoid that name because it is too similar to the comparison operations for numbers <= and >=, and it would thus easily be confused. See exercise 9.

Exercise 18. Define the function image-area, which counts the number of pixels in a given image. See exercise 5 for ideas.

Exercise 19. Define the function image-classify, which consumes an image and produces "tall" if the image is taller than it is wide, "wide" if it is wider than it is tall, or "square" if its width and height are the same. See exercise 10 for ideas.

Exercise 20. Define the function string-join, which consumes two strings and appends them with "_" in between. See exercise 2 for ideas.

Exercise 21. Define the function string-insert, which consumes a string and a number i and which inserts "_" at the ith position of the string. Assume i is a number between 0 and the length of the given string (inclusive). See exercise 3 for ideas. Also ponder the question how string-insert ought to cope with empty strings.

Exercise 22. Define the function string-delete, which consumes a string and a number i and which deletes the ith position from str. Assume i is a number between 0 (inclusive) and the length of the given string (exclusive). See exercise 4 for ideas. Can string-delete deal with empty strings?

2.2 Composing 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, and it uses other functions—some that come with the chosen programming language and some programmer-defined ones—and turn the result of one function application into the input for another. In analogy to algebra, 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 as well as a signature. It produces a complete letter by plugging in holes in the opening, the body, and the signature of the template.

Here is a complete definition, consisting of four functions:
(define (letter fst lst signature-name)
  (string-append
    (opening fst)
    "\n\n"
    (body fst lst)
    "\n\n"
    (closing signature-name)))
 
(define (opening fst)
  (string-append "Dear " fst ","))
 
(define (body fst lst)
  (string-append
   "We have discovered that all people with the last name " "\n"
   lst " have won our lottery. So, " fst ", " "\n"
   "hurry and pick up your prize."))
 
(define (closing signature-name)
  (string-append
   "Sincerely,"
   "\n\n"
   signature-name))
The first one is the “main” function. It uses three auxiliary functions to produce the three pieces of the letter—the opening, the body, and the complete signature—and the composes the three results in the correct order with string-append.

Stop! Enter these definitions into DrRacket’s definitions area, click on RUN, and evaluate these expressions in the interactions area:
> (letter "Matthew" "Fisler" "Felleisen")

"Dear Matthew,\n\nWe have discovered that all people with ...\n\n"

> (letter "Kathi" "Felleisen" "Findler")

"Dear Kathi,\n\nWe have discovered that all people with ...\n\n"

Note how the result is a long string that contains occurrences of "\n". These substrings represent the newline character within a string.

If we were to print this string, the lines would be broken at these places, which is precisely what you would want:
> (require 2htdp/batch-io)
> (write-file 'stdout (letter "Matthew" "Fisler" "Felleisen"))

Dear Matthew,

 

We have discovered that all people with the last name

Fisler have won our lottery. So, Matthew,

hurry and pick up your prize.

 

Sincerely,

 

Felleisen

'stdout

The require brings in write-file, a function that can print a string to a file or console. Programs explains this concept in some more depth.

In general, when a problem refers to distinct tasks of computation, a program should consist of one function per task and a main function that puts it all together. We formulate this idea as a simple slogan:

Define one function per task.

The advantage of following this slogan is that you get reasonably small functions, each of which is easy to comprehend, and whose composition is easy to understand. Once you learn to design functions, you will recognize that getting small functions to work correctly is much easier than doing so with large ones. 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 parts when it is organized as a collection of small functions as opposed to a large, monolithic block.

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

Sample Problem: Imagine the owner of a monopolistic movie theater. He has complete freedom in setting ticket prices. The more he charges, the fewer the people who can afford tickets. The less he charges, the more it costs to run a show because attendance goes up. In a recent experiment the owner determined a relationship between the price of a ticket and average attendance.

At a price of $5.00 per ticket, 120 people attend a performance. For each 10-cent change in the ticket price, the average attendance changes by 15 people. That is, if the owner charges $5.10, some 105 people attend on the average; if the prices goes down to $4.90, average attendance increases to 135. Let us translate this idea into a mathematical formula:

image

Stop! Explain the minus sign before you proceed.

Unfortunately, the increased attendance also comes at an increased cost. Every performance comes at a fixed costs of $180 to the owner plus a variable cost of $0.04 per attendee.

The owner would like to know the exact relationship between profit and ticket price so that he maximize his 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 by one:
  1. The problem statement specifies how the number of attendees depends on the ticket price. Computing this number is clearly a separate task and thus deserves its own function definition:

    (define (attendees ticket-price)
      (- 120 (* (- ticket-price 5.0) (/ 15 0.1))))
    The function mentions the four constants—120, 5.0, 15, and 0.1determined by the owner’s experience.

  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)
      (* ticket-price (attendees ticket-price)))
    The number of attendees is calculated by the attendees function of course.

  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))))
    Again, this function also uses attendees to determine the number of attendees.

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

As Prologue: How to Program says, functions such as profit benefit from the use of global constants. Every programming language allows programmers to define constants. 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, and

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

Constant definitions introduce names for all shapes and forms of data: numbers, images, strings, and so on. Here are some simple examples:
; the current price of a movie ticket
(define CURRENT-PRICE 5)
 
; 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 a string and an image. By convention, we use upper-case letters for global constants, 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))

Most of our sample definitions employ literal constants on the right hand side, but the last one uses an expression. And indeed, a programmer can use arbitrary expressions to compute constants. 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))
It can use two definitions with literal constants on the right-hand side and two computed constants, that is, variables whose values are not just literal constants but the results of calculating the location of the center.

Again, we use a simple slogan to remind you about the importance of constants:

Introduce definitions for all constants mentioned in a problem statement.

Exercise 26. Define constants for the price optimization program so that the price sensitivity of attendance (15 people for every 10 cents) becomes a computed constant.

2.4 Programs

You are ready to create simple programs. From a coding perspective, a program is just a bunch of function and constant definitions. Usually one function is singled out as the “main” function, and this main function tends to compose others. From the perspective of launching a program, however, there are two distinct kinds:
  • a batch program consumes all of its inputs at once and computes its result. Its main function composes auxiliary functions, which may refer to additional auxiliary functions, and so on. When we launch a batch program, the operating system calls the main function on its inputs and waits for the program’s output.

  • an interactive program consumes some of its inputs, computes, produces some output, consumes more input, and so on. We call the appearance of an input an event, and we create interactive programs as event-driven programs. The main function of such an event-driven program uses an expression to describe which functions to call for which kinds of events. These functions are called event handlers.

    When we launch an interactive program, the main function informs the operating system of this description. As soon as input events happen, the operating system calls the matching event handler. Similarly, the operating system knows from the description when and how to present the results of these function calls as output.

This book focuses mostly on programs that interact via graphical user interfaces (GUI); there are other kinds of interactive programs, and you will get to know those as you continue to study computer science.

In this section we present simple examples of both batch and interactive programs.

Batch Programs As mentioned, a batch program consumes all of its inputs at once and computes the result from these inputs. Its main function may expect the arguments themselves or the names of files from which to retrieve the inputs; similarly, it may just return the output or it may place it in a file.

Once programs are created, we want to use them. In DrRacket, we launch batch programs in the interactions area so that we can watch the program at work.

Programs are even more useful if they can retrieve the input from some file and deliver the output to some other file. The name batch program originated from the early days of computing when a program read an entire file (or several files) and placed the result in some other file(s), without any intervention after the launch. Conceptually, we can think of the program as reading an entire file at once and producing the result file(s) all at once.

We create such file-based batch programs with the "batch-io" library, which adds two functions to our vocabulary (among others):
  • read-file, which reads the content of an entire file as a string, and

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

Before you evaluate these expressions in DrRacket, save the definitions area in a file. These functions write strings to files and read strings from them:
> (write-file "sample.dat" "212")

"sample.dat"

> (read-file "sample.dat")

"212"

After the first interaction is completed, the file named "sample.dat" contains this text

  212

and nothing else. The result of write-file is an acknowledgment that it has placed the string in the file. If the file already exists, it replaces its content with the given string; otherwise, it creates a file and makes the given string its content. The second interaction, (read-file "sample.dat"), produces "212" because it turns the content of "sample.dat" into a string.

The names 'stdout and 'stdin are short for standard output and input device, respectively. For historical and pragmatic reasons, write-file also accepts 'stdout, a special kind of token, as the first argument. It then displays the resulting file content in the current interactions area, for example:
> (write-file 'stdout "212")

212

'stdout

By analogy, read-file accepts 'stdin in lieu of a file name and then reads input from the current interactions area.

Let us illustrate the creation of a batch program with a simple example. Suppose we wish to create a program that convertsThis book is not about memorizing facts, but we do expect you to know where to find them. Do you know where to find out how temperatures are converted? a temperature measured on a Fahrenheit thermometer into a Celsius temperature. Don’t worry, this question isn’t a test about your physics knowledge; here is the conversion formula:

Naturally in this formula f is the Fahrenheit temperature and c is the Celsius temperature. While this formula might be good enough for a pre-algebra text book, a mathematician or a programmer would write c(f) on the left side of the equation to remind readers that f is a given value and c is computed from f.

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

Once we have the conversion formula in BSL, creating the main function means composing f2c with existing primitive functions:
(define (convert in out)
  (write-file out
    (number->string
      (f2c
        (string->number
          (read-file in))))))
We have called the main function convert, and it consumes two filenames: in for the file where the Fahrenheit temperature is found and out for where we want the Celsius result. A composition of five functions computes convert’s result. Let us step through convert’s body carefully to understand how this works:
  1. (read-file in) retrieves the content of the file called in as a string;

  2. string->number turns this string into a number;

  3. f2c interprets the number as a Fahrenheit temperature and converts it into a Celsius temperature;

  4. number->string consumes this Celsius temperature and turns it into a string;

  5. and (write-file out ...) places this string into the file named out.

This long list of steps might look overwhelming. The average function composition in a pre-algebra course involves two functions, possibly three. Keep in mind, though, that programs accomplish a real-world purpose while exercises in algebra merely illustrate this idea.

Since write-file is a way to create files, we can now launch convert: You can also create "sample.dat" with a file editor. Just be careful that the editor doesn’t add a newline or any other invisible characters.
> (write-file "sample.dat" "212")

"sample.dat"

> (convert "sample.dat" 'stdout)

100

'stdout

> (convert "sample.dat" "out.dat")

"out.dat"

> (read-file "out.dat")

"100"

For the first interaction, we use 'stdout so that we can view what convert outputs in DrRacket’s interactions area. For the second one, convert is given the name "out.dat". As expected, the call to convert returns this string; from the description of write-file we also know that it deposited a Fahrenheit temperature in the file. Here we read the content of this file with read-file, but you could also use another text editor to look at the file and to view the result.

(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, it is also instructive to step through the computation. Make sure that the file "sample.dat" exists and contains just a number, then click the STEP button in DrRacket. Doing so opens another window in which you can peruse the computational process that the call to the main function of a batch program triggers. You will see that the process follows the above outline.

Exercise 27. Recall the letter program from Composing Functions. We launched this program once, with the inputs "Matthew", "Fisler", and "Felleisen". Here is how to launch the program and have it write its output to the interactions area:
> (write-file 'stdout (letter "Matthew" "Fisler" "Felleisen"))

Dear Matthew,

 

We have discovered that all people with the last name

Fisler have won our lottery. So, Matthew,

hurry and pick up your prize.

 

Sincerely,

 

Felleisen

'stdout

Of course, programs are useful because you can launch them for many different inputs, and this is true for letter, too. Run letter on three inputs of your choice.

Here is a letter-writing batch program that reads names from three files and writes a letter to one:
(define (main in-fst in-lst in-signature out)
  (write-file out
              (letter (read-file in-fst)
                      (read-file in-lst)
                      (read-file in-signature))))
The function consumes four strings: the first three are the names of input files and the last one serves as output file. It uses the first three to read one string each from the three named files, hands these strings to letter, and eventually writes the result of this function call into the file named by out, the fourth argument to main.

Create appropriate files, launch main, and check whether it delivers the expected letter.

Note Once you understand Programming with Lists, you will be able to use other functions from the "batch-io" library, and then you will have no problem writing letters for tens of thousands of lucky lottery winners.

Interactive Programs No matter how you look at it, batch programs are old-fashioned. Even if businesses have used them for decades to automate useful tasks, people prefer interactive programs. Indeed, in this day and age, people mostly interact with desktop applications via a keyboard and a mouse generating input events such as key presses or mouse clicks. Furthermore, interactive programs can also react to computer-generated events, for example, clock ticks or the arrival of a message from some other computer.

Exercise 28. Most people no longer use desktop computers to run applications but cell phones, tablets, and their cars’ information control screens. Soon people will use wearable computers in the form of intelligent glasses, clothes, and sports gear. In the somewhat more distant future, people may come with built-in bio computers that directly interact with body functions. Think of ten different forms of events that software applications on such computers will have to deal with.

The purpose of this section is to introduce the mechanics of writing interactive BSL programs. Because many of the large examples in this book are interactive programs, we introduce the ideas slowly and carefully. You may wish to return to this section when you tackle some of the interactive programming projects; a second or third reading may clarify some of the advanced aspects of the mechanics.

By itself, a raw computer is a useless piece of physical equipment. It is called hardware because you can touch it. This equipment becomes useful once you install software, that is, a suite of programs. Usually the first piece of software to be 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. The way it works is that when a user presses a key on the keyboard, the operating system runs a function that processes key strokes. We say that the key stroke is a key event, and the function is an event handler. In the same vein, the operating system runs an event handler for clock ticks, for mouse actions, and so on. Conversely, after an event handler is done with its work, the operating system may have to change the image on the screen, ring a bell, or print a document. To accomplish these tasks, it also runs functions that translate the operating system’s data into sounds, images, and actions on the printer.

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 a general-purpose computer work on these radically different tasks, different programs install different event handlers. That is, a rocket launching program uses one kind of function to deal with clock ticks while an oven’s service functions uses a different kind.

Designing an interactive program requires a way to designate some function as the one that takes care of keyboard events, another function for dealing with clock tick, a third one for presenting some data as an image, and so forth. It is the task of an interactive program’s main function to communicate these designations to the operating system, that is, the software platform on which the program is launched.

DrRacket is a small operating system and BSL, one of its programming languages, comes with the "universe" library, which provides this communication mechanisms. That is, big-bang is your means to install event handlers and functions that translate data into presentable form. A big-bang expression consists of one required subexpression and one required clause. The subexpression evaluates to the initial state of the program, and the required clause tells DrRacket how to render the current state as a program.

Let us understand this idea step-by-step, starting with this function definition:
(define (number->square s)
  (square s "solid" "red"))
The function consumes a positive number and produces solid red square of that size. After clicking RUN, experiment with the function, like this:
> (number->square 5)

image

> (number->square 10)

image

> (number->square 20)

image

It behaves like a batch program, consuming a number and producing an image, which DrRacket renders for you.

Now try the following big-bang expression in the interactions area:
> (big-bang 100 [to-draw number->square])
A separate window appears, and it displays a 100 x 100 red square. In addition, the DrRacket interactions area does not display another prompt; it is as if the program keeps running and indeed, this is the case. To stop the program, click on DrRacket’s STOP button:
> (big-bang 100 [to-draw number->square])

100

When DrRacket stops the evaluation of a big-bang expression, it returns the current state, which in this case is just the initial state: 100.

Here is an interesting big-bang expression:
> (big-bang 100
            [to-draw number->square]
            [on-tick sub1]
            [stop-when zero?])
This big-bang expression adds two optional clauses to the previous one: the on-tick clause tells DrRacket how to deal with clock ticks and the stop-when clause says when to stop the program. We read it as follows, starting with 100 as the initial state:
  1. every time the clock ticks, subtract 1 from the current state;

  2. then check whether zero? is true of the new state and if so, stop; and

  3. every time an event handler is finished with its work, use number->square to render the state as an image.

Now hit the return key and observe what happens. Eventually the evaluation of the expressions terminates and DrRacket displays 0.

Stop! Explain in your own words how the expression is evaluated.

The big-bang expression keeps track of the current state. Initially this state is 100. Every time the clock ticks, it calls the clock tick handler and gets a new state. Hence, the state of big-bang changes as follows:

100, 99, 98, ..., 2, 1, 0

When the state’s value becomes 0, the evaluation is done. For every other state—from 100 to 1big-bang translates the state into an image, using number->square as the to-draw clause tells it to. Hence, the window displays a red square that shrinks from 100 x 100 pixels to 1 x 1 pixel over 100 clock ticks.

Let’s add a clause for dealing with key events. First, we need a function that consumes the current state of the world and a string that describes the key event and that returns a new state:
(define (reset s ke)
  100)
This function throws away its arguments and returns 100, which is the initial state of the big-bang expression we wish to modify. Second, we add an on-key clause to the big-bang expression:
> (big-bang 100
            [to-draw number->square]
            [on-tick sub1]
            [stop-when zero?]
            [on-key reset])
It says to call reset every time a key is pressed.

Stop! Explain what happens when you evaluate this expression, count to 10, and press "a".

What you will see is that the red square shrinks again, one pixel per clock tick. As soon as you press the "a" key on the keyboard though, the red square re-inflates to full size, because reset is called on the current length of the square and "a" and returns 100. This number becomes big-bang’s new state and number->square renders it as a full-sized red square.

In order to understand the evaluation of big-bang expressions in general, let us look at a schematic one:
(big-bang cw0
          (on-tick tock)
          (on-key ke-h)
          (on-mouse me-h)
          (to-draw render)
          (stop-when end?)
          ...)
This big-bang expression specifies three event handlers: tock, ke-h, and me-h. The last one is a mouse event handler, which consumes four inputs—the current world, two coordinates, and a string, which represents the kind of mouse event—and, like the other event handlers, returns a new world.

The evaluation of this big-bang expression starts with cw0, which is usually an expression. DrRacket, our operating system, installs the value of cw0 as the current state of the world, for short current world. It uses render to translate the current world into an image, which is then displayed in a separate window. Indeed, render is the only means for a big-bang expression to present data to the external world.

Here is how events are processed:
  • Every time the clock ticks, DrRacket applies tock to big-bang’s current world and receives a value in response; big-bang treats this return value as the next current world.

  • Every time a key is pressed, DrRacket applies ke-h to big-bang’s current world and a string that represents the key; for example, pressing the “a” key is represented with "a" and the left arrow key with "left". When ke-h returns a value, big-bang treats it as the next current world.

  • Every time a mouse enters the window, leaves it, moves, or is pressed, DrRacket applies me-h to big-bang’s current world, the event’s x and y coordinates, and a string that represents the kind of mouse event that happened; for example, pressing a mouse’s button is represented with "button-down". When me-h returns a value, big-bang treats it as the next current world.

All events are processed in order; if two events seem to happen at the same time, DrRacket acts as a tie-breaker and arranges them in some order.

After an event is processed, big-bang uses both end? and render to check the current world:
  • (end? cw) produces a Boolean value. If it is #t, big-bang stops the computation immediately. Otherwise it proceeds.

  • (render cw) is expected to produce an image and big-bang displays this image in a separate window.

current world

cw0

cw1

cw2

...

its image

(render cw0)

(render cw1)

(render cw2)

...

on clock tick

(tock cw0)

(tock cw1)

(tock cw2)

...

on key stroke

(ke-h cw0 ...)

(ke-h cw1 ...)

(ke-h cw2 ...)

...

on mouse event

(me-h cw0 ...)

(me-h cw1 ...)

(me-h cw2 ...)

...

Figure 7: How the world works

The table in figure 7 concisely summarizes this process. In the first row, it specifies the current time: the first clock tick, the second, and so forth. The second row associates the current time with a current world. With render, this series of current worlds is mapped to a series of images, which is displayed in the separate window. The last three rows specify the result of applying tock, ke-h, or me-h to the current world and additional event data as needed. Only one of these three expressions is evaluated; no matter which one, its result appears in the next column in row 1 as the next current world.

Let us read this table together. Imagine the following sequence of events: the user presses the “a” key, then the clock ticks, and finally the user presses uses the mouse to trigger a “button down” event at position (90,100). Then
  1. cw1 is the result of (ke-h cw0 "a"), i.e., the fourth cell in the second column;

  2. cw2 is the result of (tock cw1), i.e., the third cell in the third column; and

  3. cw3 is the result of (me-h cw2 90 100 "button-down").

We can actually express these three steps as a sequence of three definitions:
(define cw1 (ke-h cw0 "a"))
(define cw2 (tock cw1))
(define cw3 (me-h cw2 "button-down" 90 100))
Stop! Determine manually how big-bang displays each of these three states as an image. Furthermore, we can also compute cw3 via a function composition:

(define cw3 (me-h (tock (ke-h w0 "a")) 90 100 "button-down"))

Event handlers really are functions, and you can compose them just like ordinary functions. So it is perfectly acceptable to use the result of one function application and use it as the input for another one.

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 handlers and other functions when needed.

From here, it is straightforward to define a first interactive program:
(define (main y)
  (big-bang y
            [on-tick sub1]
            [stop-when zero?]
            [to-draw place-dot-at]
            [on-key stop]))
 
(define (place-dot-at y)
  (place-image (circle 3 "solid" "red") 50 y (empty-scene 100 100)))
 
(define (stop y ke)
  0)
The program consists of three functions: a main function launches a big-bang interactive program; place-dot-at translates the current world into an image; and stop throws away its inputs and produces 0.

After clicking RUN, we can ask DrRacket to evaluate applications of these handler functions. This is one way to confirm their workings or to just explore how they work:
> (place-dot-at 89)

image

> (place-dot-at 22)

image

> (stop 89 "q")

0

Stop! Try now to understand how main reacts when you press a key.

One way to find out is to launch main:
> (main 90)

Take a deep breath.

By now, you may feel that these first two chapters are overwhelming. They introduced so many new concepts, including a new language, its vocabulary, its meaning, its idioms, a tool for writing down texts in this vocabulary, running these so-called “programs,” and the inevitable question of how to create them when presented with a problem statement. To overcome this feeling, the next chapter takes a step back and explains how to design programs systematically from scratch, especially interactive programs. So take a breather and continue when ready.

3 How 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 learn the vocabulary of the programming language, to figure out its grammar, and to understand what its "phrases" mean.

On the other hand, it is critical to learn how to get from a problem statement to a program. We need to determine what is relevant in the problem statement and what can be ignored. We need to tease out what the program consumes, what it produces, and how it relates inputs to outputs. We have to know, or find out, whether the chosen language and its libraries provide certain basic operations for the data that our program is to process. If not, we might have to develop auxiliary functions that implement these operations. Finally, once we have a program, we must check whether it actually performs the intended computation. And this might reveal all kinds of errors, which we need to be able to understand and fix.

All this sounds rather complex and you might wonder why we don’t just muddle our way through, experimenting here and there, leaving well enough alone when the results look decent. This approach to programming, often dubbed “garage programming,” is common and succeeds on many occasions; sometimes it is the launching pad for a start-up company. Nevertheless, the start-up cannot sell the results of the “garage effort” because only the original programmers and their friends can use them.

A good program comes with a short write-up that explains what it does, what inputs it expects, and what it produces. Ideally, it also comes with some assurance that it actually works. In the best circumstances, the program’s connection to the problem statement is evident so that a small change to the problem statement is easy to translate into a small change to the program. Software engineers call this a “programming product.”

The word “other” also includes older versions of the programmer who usually cannot recall all the thinking that the younger version put into the production of the program.

All this extra work is necessary because programmers don’t create programs for themselves. Programmers write programs for other programmers to read, and on occasion, people run these programs to get work done. Most programs are large, complex collections of collaborating functions, and nobody can write all these functions in a day. Programmers join projects, write code, leave projects; others take over their programs and work on them. Another difficulty is that the programmer’s clients tend to change their mind about what problem they really want solved. They usually have it almost right, but more often than not, they get some details wrong. Worse, complex logical constructions such as programs almost always suffer from human errors; in short, programmers make mistakes. Eventually someone discovers these errors and programmers must fix them. They need to re-read the programs from a month ago, a year ago, or twenty years ago and change them.

Exercise 29. 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 programs, the recipe is a device for diagnosing a novice’s difficulties. For others, our recipe might be something that they can apply to other areas, say medicine, journalism, or engineering. For those who wish to become real programmers, the design recipe also offers a way to understand and work on existing programs—though not all programmers use a method like this 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; the following chapters and parts refine and expand the recipe in one way or another.

3.1 Designing Functions

Information and Data The purpose of a program is to describe a computational process of working through information and producing new information. In this sense, a program is like the instructions 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 inspects the state of a video game. All this information comes from a part of the real world—often called the program’s domainand the results of a program’s computation represents more information in this domain.

Information plays a central role in our description. Think of information as facts about the program’s domain. For a program that deals with a furniture catalog, a “table with five legs” or a “square table of two by two meters” are pieces of information. A game program deals with a different kind of domain, where “five” might refer to the number of pixels per clock tick that some objects travels on its way from one part of the screen to another. Or, a payroll program is likely to deal with “five deductions.”

For a program to process information, it must turn it into some form of data in the programming language; then it processes the data; and once it is finished, it turns the resulting data into information again. An interactive program may even intermingle these steps, acquiring more information from the world as needed and delivering information in between.

We use BSL and DrRacket so that you do not have to worry about the translation of information into data. In DrRacket’s BSL you can apply a function directly to data and observe what it produces. As a result, we avoid the serious chicken-and-egg problem of writing functions that convert information into data and vice versa. For simple kinds of information, designing such program pieces is trivial; for anything other than simple information, you need to know about parsing, for example, and that immediately requires a lot of expertise in program design.

Software engineers use the slogan model-view-controller (MVC) for the way BSL and DrRacket separate data processing from parsing information into data and turning data into information. Indeed, it is now accepted wisdom that well-engineered software systems enforce this separation, even though most introductory books still co-mingle them. Thus, working with BSL and DrRacket allows you to focus on the design of the core of programs and, when you have enough experience with that, you can learn to design the information-data translation parts.

Here we use three pre-installed teachpacks—"batch-io", "image", "universe"to demonstrate how complete programs are designed. That is, this book—starting with this chapter—provides a design recipe for batch and interactive programs to give you an idea of how complete programs are designed. But, keep in mind that the libraries of full-fledged programming languages offer many more tools than these teachpacks.

Figure 8: 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 8 explains this idea with an abstract diagram.

To make this idea concrete, let us consider some examples. 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 requires understanding 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 characters in a string.

The key is to know how to go from numbers as information to numbers as data and vice versa.

Computer scientists use “class” to mean something like a “mathematical set.”

Since this knowledge is so important for everyone who reads the program, we often write it down in the form of comments, which we call data definitions. The purpose of a data definition is two-fold. On the one hand, it names a class or a collection of data, typically using a meaningful word. On the other hand, it informs readers how to create elements of this class of data and how to decide whether some random piece of data is an element of this collection.

Here is a data definition that could be useful for one of our early examples:
; Temperature is a Number.
; interpretation 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 -274C, 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 here. 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 classes of data: Number, String, Image, and Boolean values. With what you know right now, formulating a new data definition means nothing more than introducing a new name for an existing form of data, for example, “temperature” for numbers. Even this limited knowledge, though, suffices to explain the outline of our design process.

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. Express how you wish to represent information as data. A one-line comment suffices, for example,

    ; We use plain numbers to represent temperatures.

    Formulate data definitions, like the one for Temperature above for the classes of data you consider critical for the success of your program.

  2. Write down a signature, a purpose statement, and a function header.

    A function signature (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?

    Every reader of your program should understand what your functions compute without having to read the function itself.

    A multi-function program should also come with a purpose statement. Indeed, good programmers write two purpose statements: one for the reader who may have to modify the code and another one for the person who wishes to use the program but not read it.

    Finally, a header is a simplistic function definition, also called a stub. Pick one parameter for each input data class in the signature; the body of the function can be any piece of data from the output class. The following three function headers match the above three signatures:
    Our parameter names reflect what kind of data the parameter represents. Sometimes, you may wish to use names that suggest the purpose of the parameter.

    When you formulate a purpose statement, it is often useful to employ the parameter names to clarify what is computed. For example,
    ; Number String Image -> Image
    ; adds 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
    ; computes the area of a square whose side is len
    (define (area-of-square len) 0)

    Add the examples between the purpose statement and the function header:

    ; Number -> Number
    ; computes 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 next step is to take inventory,We owe the term “inventory” to Dr. Stephen Bloch. to understand what are the givens and what we 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
    ; computes 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
    ; computes 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
    ; adds 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; 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 results are correct. If so, assume that the mistake is in the function definition. Otherwise, fix the example and then run the tests again. If you are still encountering problems, you may have encountered the third, somewhat rare situation.

3.2 Finger Exercises

The first few of the following exercises are almost copies of previous ones. The difference is that this time they used the word “design” not “define,” meaning you should use the design recipe to create these functions and your solutions should include all relevant pieces. (Skip the template; it is useless here.) Finally, as the title of the section suggests, these exercises are practice exercises to help you internalize the process. Until the steps become second nature, never skip one; that leads to easily avoided errors and unproductive searches for the causes of those flaws. There is plenty of room left in programming for complicated errors; we have no need to waste our time on silly ones.

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

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

Exercise 32. Design the function image-area, which counts the number of pixels in a given image.

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

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

3.3 Domain Knowledge

It is natural to wonder what knowledge it takes to code up the body of a function. A little bit of reflection tells you that this step demands an appropriate grasp of the domain of the program. Indeed, there are two forms of such 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 learn a language as they work through problems with domain experts.

  2. And knowledge about the library functions in the chosen programming language. When your task is to translate a mathematical formula involving the tangent function, you need to know or guess that your chosen language comes with a function such as BSL’s tan. When, however, you need to use BSL to design image-producing functions, you will benefit from understanding the possibilities of the "image" library.

Since you can never predict the area you will be working in, or which programming language you will have to use, it is imperative that you have a solid understanding of the full possibilities of whatever computer languages are around and suitable. Otherwise some domain expert with half-baked programming knowledge will take over your job.

You can recognize problems that demand domain knowledge from the data definitions that you work out. As long as the data definitions use classes that exist in the chosen programming language, the definition of the function body (and program) mostly relies on expertise in the domain. Later, when we introduce complex forms of data, the design of functions demands computer science knowledge.

3.4 From Functions to Programs

Not all programs consist of a single function definition. Some require several functions, many also use constant definitions. No matter what, it is always important to design each function of a program systematically, though both global constants and the presence of auxiliary functions change the design process a bit.

When you have defined global constants, your functions may use those global constants to compute results. To remind yourself of their existence, you may wish to add these constants to your templates; after all, they belong to the inventory of things that may contribute to the function definition.

Multi-function programs come about because interactive programs automatically need functions that handle key and mouse events, functions that render the state as music, and possibly more. Even batch programs may require several different functions because they perform several separate tasks. Sometimes the problem statement itself suggests these tasks; other times you will discover the need for auxiliary functions as you are in the middle of designing some function.

For these reasons, we recommend keeping around a list of needed functions or a wish list.We owe the term “wish list” 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.

3.5 On Testing

Testing quickly becomes a labor-intensive chore. While it is easy to run small programs in the interactions area, doing so requires a lot of mechanical labor and intricate inspections. As programmers grow their systems, they wish to conduct many tests. Soon this labor becomes overwhelming, and programmers start to neglect it. At the same time, testing is the first tool for discovering and preventing basic flaws. Sloppy testing quickly leads to buggy functions—that is, functions with hidden problems—and buggy functions retard projects, often in multiple ways.

Hence, it is critical to mechanize tests instead of performing them manually. Like many programming languages, BSL includes a testing facility, and DrRacket is aware of this facility. 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
; converts 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 computations and three comparisons between two numbers each. You can formulate these tests 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 to 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, for example

(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 computed value, the result of the function call (-40); the expected value (40); and a hyperlink to the text of the failed test case.

; Number -> Number
; converts 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 9: Testing in BSL

You can place check-expect specifications above or below the function definitions 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 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) )
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))
This alternative approach helps you figure out how to express the function body and is therefore preferable.

Because it is so useful to have DrRacket conduct the tests and not to check everything yourself manually, we immediately switch to this style of testing for the rest of the book. This form of testing is dubbed unit testing, and BSL’s unit testing framework is especially tuned for novice programmers. One day you will switch to some other programming language; one of your first tasks will be to figure out its unit testing framework.

3.6 Designing World Programs

While the previous chapter introduces the "universe" library in an ad hoc way, this section demonstrates how the design recipe helps you create world programs systematically. It starts with a brief summary of the "universe" library based on data definitions and function signatures. The second part spells out a design recipe for world programs, and the last one starts a series of exercises that runs through several of the next few chapters.

Figure 10 presents the "universe" library in a schematic and simplified way. The teachpack expects that a programmer develops a data definition that represents the state of the world and a function render that knows how to create an image for every possible state of the world. Depending on the needs of the program, the programmer must then design functions that respond to clock ticks, key strokes, and mouse events. Finally, an interactive program may need to stop when its current world belongs to a sub-class of states; end? recognizes these final states.

; WorldState : a data definition of your choice
; a collection of data that represents the state of the world
 
; render :
;   WorldState -> Image
; big-bang evaluates (render cw) to obtain image of
; current world cw when needed
 
; clock-tick-handler :
;   WorldState -> WorldState
; for each tick of the clock, big-bang evaluates
; (clock-tick-handler cw) for current world cw to obtain
; new world  
 
; key-stroke-handler :
;   WorldState String -> WorldState
; for each key stroke, big-bang evaluates
; (key-stroke-handler cw ke) for current world cw and
; key stroke ke to obtain new world  
 
; mouse-event-handler :
;   WorldState Number Number String -> WorldState
; for each key stroke, big-bang evaluates
; (mouse-event-handler cw x y me) for current world cw,
; coordinates x and y, and mouse event me to
; obtain new world
 
; end? :
;   WorldState -> Boolean
; after an event is processed, big-bang evaluates (end? cw)
; for current world cw to determine whether the program stops

Figure 10: Signatures for interaction functions

Assuming that you understand the rudimentary workings of big-bang, you can focus on the truly important problem of designing world programs. Let’s construct a concrete example for the following design recipe:

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 scenes that illustrate the domain:

In this book, we often refer to the domain of an interactive big-bang program as a “world,” and we speak of designing “world programs.”

The design recipe for world programs, like the one for functions, is a tool for systematically moving from a problem statement to a working program. It consists of three big steps and one small one:
  1. For all those properties of the world that remain the same over time and are needed to render it as an Image, introduce constants. In BSL, we specify such constants via definitions. For the purpose of world programs, we distinguish between two kinds of constants:
    1. “Physical” constants describe general attributes of objects in the world, such as the speed or velocity of an object, its color, its height, its width, its radius, and so forth. Of course these constants don’t really refer to physical facts, but many are analogous to physical aspects of the real world.

      In the context of our sample problem, the radius of the car’s wheels and the distance between the wheels are such “physical” constants:
      (define WIDTH-OF-WORLD 200)
       
      (define WHEEL-RADIUS 5)
      (define WHEEL-DISTANCE (* WHEEL-RADIUS 5))
      Note how the second constant is computed from the first.

    2. Graphical constants are images of objects in the world. The program composes them into images that represent the complete state of the world.

      We suggest you experiment in DrRacket’s interaction area to develop graphical constants.

      Here are graphical constants for wheel images of our sample car:
      (define WHEEL (circle WHEEL-RADIUS "solid" "black"))
      (define SPACE (rectangle ... WHEEL-RADIUS ... "white"))
      (define BOTH-WHEELS (beside WHEEL SPACE WHEEL))
      Graphical constants are usually computed, and the computations tend to involve the physical constants and other graphical images.

  2. Those properties that change over time—in reaction to clock ticks, key strokes, or mouse actions—give rise to the current state of the world. Your task is to develop a data representation for all possible states of the world. The development results in a data definition, which comes with a comment that tells readers how to represent world information as data and how to interpret data as information about the world.

    Choose simple forms of data to represent the state of the world.

    For the running example, it is the car’s distance to the left margin that changes over time. While the distance to the right margin changes, too, it is obvious that we need only one or the other to create an image. A distance is measured in numbers, so the following is an adequate data definition:

    ; WorldState is a Number
    ; interpretation the number of pixels between the left border and the car
    An alternative is to count the number of clock ticks that have passed and to use this number as the state of the world. We leave this design variant as an exercise.

  3. Once you have a data representation for the state of the world, you need to design a number of functions so that you can form a valid big-bang expression.

    To start with, you need a function that maps any given state into an image so that big-bang can render the sequence of states as images:

    ; render

    Next you need to decide which kind of events should change which aspects of the world state. Depending on your decisions, you need to design some or all of the following three functions:
    ; clock-tick-handler
    ; key-stroke-handler
    ; mouse-event-handler
    Finally, if the problem statement suggests that the program should stop if the world has certain properties, you must design

    ; end?

    For the generic signatures and purpose statements of these functions, see figure 10. You should reformulate these generic purpose statements so that you have a better idea of what your functions must compute.

    In short, the desire to design an interactive program automatically creates several initial entries for your wish list. Work them off one by one and you get a complete world program.

    Let us work through this step for the sample program. While big-bang dictates that we must design a rendering function, we still need to figure out whether we want any event handling functions. Since the car is supposed to move from left to right, we definitely need a function that deals with clock ticks. Thus, we get this wish list:
    ; WorldState -> Image
    ; places the image of the car x pixels from the left margin of
    ; the BACKGROUND image
    (define (render x)
      BACKGROUND)
     
    ; WorldState -> WorldState
    ; adds 3 to x to move the car right
    (define (tock x)
      x)
    Note how we tailored the purpose statements to the problem at hand, with an understanding of how big-bang will use these functions.

  4. Finally, you need a main function. Unlike all other functions, a main function for world programs doesn’t demand design. It doesn’t even require testing because its sole reason for existing is that you can launch your world program conveniently from DrRacket’s interaction area.

    The one decision you must make concerns main’s arguments. For our sample problem we opt to apply main to the initial state of the world:
    ; WorldState -> WorldState
    ; launches the program from some initial state
    (define (main ws)
       (big-bang ws
                 [on-tick tock]
                 [to-draw render]))
    Hence, you can launch this interactive program with
    > (main 13)
    to watch the car drive off from 13 pixels to the right of the left margin. It will stop when you close big-bang’s window. Remember that big-bang returns the current state of the world when the evaluation stops.

Naturally, you don’t have to use the name “WorldState” 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 event handling functions. Also, you don’t have to use the names tock, render, or end?. You may 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. Lastly, you may have noticed that you may list the clauses of a big-bang expression in any order as long as you list the initial state first.

Let us now work through the rest of the program design process, using the design recipe for functions and other design concepts spelled out so far.

Exercise 35. Good programmersGood programmers establish a single point of control for all aspects of their programs, not just the graphical constants. Several chapters deal with this issue. ensure that an image such as CAR can be enlarged or reduced via a single change to a constant definition. We started the development of our car image with a single plain definition:

(define WHEEL-RADIUS 5)

The definition of WHEEL-DISTANCE is based on the wheel’s radius. Hence, changing WHEEL-RADIUS from 5 to 10 doubles of the car image. This kind of program organization is dubbed single point of control, and good design employs single point of control as much as possible.

Develop your favorite image of a car so that WHEEL-RADIUS remains the single point of control. Remember to experiment and make sure you can re-size the image easily.

Next we deal with the design of the clock tick handling function on the wish list:
; WorldState -> WorldState
; moves the car by three pixels every time the clock ticks
(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:
; WorldState -> WorldState
; moves the car by three pixels every time the clock ticks
; 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.

Exercise 36. Formulate the examples as BSL tests.

Our second entry on the wish list specifies a function that translates the state of the world into an image:
; WorldState -> Image
; places the car into a scene according to the given world state
(define (render ws)
  BACKGROUND)

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 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 currently empty.

This extended table suggests a pattern for the formula that goes into the body of the render function:
; WorldState -> Image
; places the car into a scene according to the given world state
(define (render ws)
  (place-image CAR ws Y-CAR BACKGROUND))
And that is mostly all there is to designing a simple world program.

Exercise 37. Finish the sample problem and get the program to run. That is, assuming that you have solved exercise 35, define the constants BACKGROUND and Y-CAR. Then assemble all the function definitions, including their tests. 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.

After settling on a first data representation for world states, a careful programmer may have to revisit this fundamental design decision during the rest of the design process. For example, the data definition for the sample problem represents the car as a point. But (the image of) the car isn’t just a mathematical point without width and height. Hence, the interpretation statement—the number of pixels from the left margin—is an ambiguous 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? We ignored this issue here and leave it to BSL’s image primitives to make the decision for us. If you don’t like the result, revisit the data definition above and modify it or its interpretation statement to adjust to your taste.

Exercise 38. Modify the interpretation of the sample data definition so that a state denotes the x coordinate of the right-most edge of the car.

Exercise 39. Let’s work through the same problem statement with a time-based data definition:
; AnimationState is a Number
; interpretation 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?

Use the data definition to design a program that moves the car according to a sine wave. Don’t try to drive like that.

Let us end the section with an illustration of mouse event handling. We also use the example as a first illustration of the advantages that a separation of view and model provide. Suppose we wish to allow people to move the car through hyperspace:

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. If the mouse is clicked anywhere on the canvas, the car is placed at the x coordinate of that point.

The bold part is the addition to the sample problem from above.

When we are confronted with a modified problem, we use the design process to guide us. If used properly, this process naturally determines what we need to add to our existing program to cope with the addition to the problem statement. So here are the four steps applied to this modified problem:
  1. There are no new properties, meaning we do not need new constants.

  2. Since the program is still concerned with only one property that changes over time—the x position of the car—the existing data representation suffices.

  3. The revised problem statement calls for a mouse event handler, without giving up on the clock-based movement of the car. Hence, we state an appropriate wish:
    ; WorldState Number Number String -> WorldState
    ; places the car at the x coordinate if me is "button-down"
    (define (hyper x-position-of-car x-mouse y-mouse me)
      x-position-of-car)

  4. Lastly, we need to modify main to take care of mouse events. All this requires is the addition of an on-mouse clause that defers to the new entry on our wish list:
    (define (main ws)
       (big-bang ws
                 [on-tick tock]
                 [on-mouse hyper]
                 [to-draw render]))
    After all, the modified problem statement calls for dealing with mouse clicks and everything else remains the same.

The rest is a mere matter of designing one more function, and for that we use the design recipe for functions.

An entry on the wish list covers the first two steps of the design recipe for functions. Hence, our next step is to develop some functional examples:
; WorldState Number Number String -> WorldState
; places the car at the x coordinate if me is "button-down"
; given: 21 10 20 "enter"
; wanted: 21
; given: 42 10 20 "button-down"
; wanted: 10
; given: 42 10 20 "move"
; wanted: 42
(define (hyper x-position-of-car x-mouse y-mouse me)
  x-position-of-car)
The examples say that if the string argument is equal to "button-down", the function returns x-mouse; otherwise it returns x-position-of-car.

Exercise 40. Formulate the examples as BSL tests. Click RUN and watch them fail.

To complete the function definition, we must appeal to your fond memories from Prologue: How to Program,In the next chapter, we explain designing with cond in detail. specifically memories about the conditional form. Using cond, hyper is a two-line definition:
; WorldState Number Number String -> WorldState
; places the car at the x coordinate if me is "button-down"
(define (hyper x-position-of-car x-mouse y-mouse me)
  (cond
    [(string=? "button-down" me) x-mouse]
    [else x-position-of-car]))
If you solved exercise 40, re-run the program and watch all tests succeed. Assuming the tests do succeed, evaluate

(main 1)

in DrRacket’s interactions area and transport your car through hyperspace.

You may wonder why this program modification is so straightforward. There are really two reasons. First, this book and its software strictly separate the data that a program tracks—the modeland the image that it shows—the view. In particular, functions that deal with events have nothing to do with how the state is rendered. If we wish to modify how a state is rendered, we can focus on the function specified in a to-draw clause. Second, the design recipes for programs and functions organize programs in the right way. If anything changes in a problem statement, following the design recipe a second time naturally points out where the original problem solution has to change. While this may look obvious for the simple kind of problems we are dealing with now, it is critical for the kind of problems that programmers encounter in the real world.

3.7 A Note on Mice and Characters

Figure 11 displays another program that handles mouse events. Specifically, it is an interactive program that just records where the mouse events occur via small dots.It is acceptable to break the rule of separating data representations and image rendering for such experimental programs, whose sole purpose it is to determine how something works. It ignores what kind of mouse event occurs, and it also ignores the first guideline about the separation of state representation and its image. Instead the program uses images as the state of the world. Specifically, the state of the world is an image that contains red dots where a mouse event occurred. When another event is signaled, the clack function just paints another dot into the current state of the world.

; AllMouseEvts is an element of Image
; interpretation an image with markers for all mouse events
 
; graphical constants
(define MT (empty-scene 100 100))
 
; PositiveNumber -> Image
; records all mouse events for the specified time interval  
(define (main duration)
  (big-bang MT
            [to-draw show]
            [on-tick do-nothing 1 duration]
            [on-mouse clack]))
 
; AllMouseEvts Number Number String -> AllMouseEvts
; adds 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))
 
; AllMouseEvts -> AllMouseEvts
; reveals the current world state (because it is am image)
 
(check-expect (show MT) MT)
 
(define (show ws)
  ws)
 
; AllMouseEvts -> AllMouseEvts
(define (do-nothing ws) ws)

Figure 11: A mouse event recorder

Stop! Check the documentation to find out what an on-tick clause means when it specifies three distinct pieces. All you have seen so far are on-tick clauses that specify a clock-tick handling function.

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

(main 10)

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

Stop! What do you think this image reveals?

Given that we moved the mouse continuously to produce the above image, the scattering of points reveals that an operating system does not track every single point where the mouse appears. Instead it samples mouse events sufficiently often and tells your program about those sample events. Usually these samples suffice for people’s purposes.

; physical constants:
(define WIDTH 100)
(define HEIGHT 30)
 
; graphical constant:
(define MT (empty-scene WIDTH HEIGHT))
 
; AllKeys is a String.
; interpretation the keys pressed since big-bang created the canvas
 
; AllKeys -> AllKeys
(define (main s)
  (big-bang s
            [on-key remember]
            [to-draw show]))
 
 
; AllKeys String -> AllKeys
; adds ke to ak, the state of the world
 
(check-expect (remember "hello" " ") "hello ")
(check-expect (remember "hello " "w") "hello w")
 
(define (remember ak ke)
  (string-append ak ke))
 
; AllKeys -> Image
; renders the string as a text and place it into MT
 
(check-expect (show "hel") (overlay (text "hel" 11 "red") MT))
(check-expect (show "mark") (overlay (text "mark" 11 "red") MT))
 
(define (show ak)
  (overlay (text ak 11 "red") MT))

Figure 12: A key event recorder

Figure 12 is the analogue to figure 11 for key events. The program starts with some basic constant definitions and a data definition that says we are using strings to record the key events we have seen so far. The main function specifies on event handler, namely one for keys. This key event handler, called remember, consumes the key events seen so far and a string that represents the last key pressed; it then appends the latter to the former. As with the previous program, the purpose of this one is to conduct experiments concerning key events.

Experiments are conducted to reveal flaws in our understanding of the world. So run the program and type This opens the world canvas, like this:

enabling you to press keys and see them drawn there. For example, if you choose to press “h” the window displays this image:

And that may surprise you. The letter “h” shows up in the middle of the canvas, not the left margin.

Exercise 41. Look through the functions in the "image" library and find a way to create framed, left-aligned text. Then change the program in figure 12 so that it uses this combination of image primitives to render its state.

Exercise 42. Run the main function again, press some regular keys on your keyboard, and then try the tab key or the delete—also known as rubout—key. The result of these actions is an application of the key event handlers to strings such as "\t" and "\r". Appearances are deceiving, however. These strings consists of a single character and remember therefore adds them to the end of the current world state. Read the documentation of on-key to find out which strings belong to KeyEvent; then use a cond expression inside of remember so that it ignores all key strokes represented by one-character strings.

3.8 Virtual Pet Worlds

This exercise section introduces the first two elements of a virtual pet game. It starts with just a display of a cat that keeps walking across the screen. Of course, all the walking makes the cat unhappy and its unhappiness shows. Like all pets, you can try petting, which helps some, or you can try feeding, which helps a lot more.

So let’s start with an image of our favorite cat:

Copy the cat image and paste it into DrRacket, then give the image a name with define.

Exercise 43. Design a “virtual cat” world program that continuously moves the cat from left to right for a specified time period. Make the cat move three pixels per clock tick. Whenever the cat disappears on the right it should re-appear on the left. You may wish to read up on the modulo function.

Exercise 44. 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, and use a cond expression to select cat images.

Exercise 45. Design a world program that maintains and displays a “happiness gauge” over some specified period of time. With each clock tick, happiness decreases by -0.1, starting with 100, the maximum score; it never falls below 0, the minimum happiness score. Every time the down arrow key is pressed, happiness increases by 1/5; every time the up arrow is pressed, happiness jumps by 1/3.

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.

When you know enough, we will explain how to combine the gauge program with the solution of exercise 43. Then we will be able to help the cat because as long as you ignore it, it becomes less happy. If you pet the cat, it becomes happier. If you feed the cat, it becomes much, much happier. So you can see why you want to know a lot more about designing world programs than these first three chapters can tell you.

4 Intervals, Enumerations, Itemizations

Thus far you have four choices to represent information as data: numbers, strings, images, and Boolean values. For many problems this is enough, but there are many more for which these four collections of data in BSL (or different ones in different programming languages) don’t suffice. Put differently, programming with just the built-in collections of data is often clumsy and therefore error prone.

At a minimum, good programmers must learn to design programs with restrictions on these built-in collections. One way to restrict is to enumerate a bunch of elements from a collection and to say that these are the only ones that are going to be used for some problem. Enumerating elements works only when there is a finite number of them. To accommodate collections with “infinitely” many elements, we introduce intervals, which are collections of elements that satisfy a specific property.

Infinite may just mean “so large that enumerating the elements is entirely impractical.”

Defining enumerations and intervals means distinguishing among different kinds of elements. To distinguish in code requires conditional functions, that is, functions that choose different ways of computing results depending on the value of some argument. Both Many Ways To Compute and Mixing It up with Booleans illustrate with examples how to write such functions. In both, however, there is no design system; all you have is some new construct in your favorite programming language (that’s BSL) and some examples on how to use it.

In this chapter, we introduce enumerations and intervals and discuss a general design strategy for these forms of input data. We start with a second look at the cond expression. Then we go through three different kinds of data descriptions: enumerations, intervals, and itemizations. An enumeration lists every single piece of data that belongs to it, while an interval specifies a range of data in one statement. The last one, itemizations, mixes the clauses of the first two, specifying ranges in one clause of its definition, and specific pieces of data in another. The chapter ends with a section on the general design strategy for such situations.

4.1 Programming with Conditionals

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])
The use of brackets is a convention to make cond lines stand out. It is perfectly acceptable to use ( ... ) in place of [ ... ]. A cond expression starts with (, is marked with a keyword, and ends with ). 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 ].

A cond line is also known as a cond clause.

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 much less suited for multi-situation contexts; they are best used when all we wish to say is “one or the other.” We therefore always use cond for situations when we wish to remind the reader of our code that some distinct situations come directly from data definitions. For other pieces of code, we use whatever construct is most convenient.

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 an error:
> (cond
    [(> x 0) 10]
    [else 20]
    [(< x 10) 30])

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

That is, BSL rejects grammatically incorrect phrases because it makes no sense to figure out what such a phrase might mean.

Imagine designing a function that, as part of a game-playing program, computes some good-bye sentence at the end of the game:
; PositiveNumber is a Number greater or equal to 0.
 
; PositiveNumber -> String
; computes 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"]))
For a line-by-line comparison, this table displays a cond with three full-fledged conditions on the left and with an else clause on the right. 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 the complementof all previous conditions in a cond.

4.2 How 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 go over the idea a bit more precisely for cond expressions. 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—a positive number—and produces a color string.

Just looking at the cond expression you cannot predict which of the three cond clauses is going to be used. And that is the point of a function. The function deals with many different inputs, for example, 2, 3, 7, 18, 29. For each of these inputs, it may have to proceed in a different manner. Differentiating among the different classes of inputs is the purpose of the cond expression.

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:
(reward 3)
= (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 this time, 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 several steps, and so the calculation proceeds to the third cond line. The else tells DrRacket to replace the entire cond expression with the result expression from this clause.

Exercise 46. 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 47. 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]))
Use the stepper to evaluate the 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.

Reformulate create-rocket-scene.v5 to use a nested expression; the resulting function mentions place-image only once.

4.3 Enumerations

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 exiting the canvas.

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, and it is a data representation in which every possibility is listed. It should not come as a surprise that enumerations are common. Here is a simple one:
; A TrafficLight shows one of three colors:
;  "red"
;  "green"
;  "yellow"
; interpretation 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 the 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-case 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
; Determines the next state of the traffic light from the given s
 
(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 48. If you copy and paste the above function definition into the definitions area of DrRacket and click RUN, DrRacket highlights two of the three cond lines. This coloring tells you that your test cases do not cover all possible cases. Add enough tests to make DrRacket happy.

Exercise 49. Design an interactive program that simulates a traffic light for a given duration. The program renders the state of a traffic light as a solid circle of the appropriate color, and it changes state on every clock tick. What is the most appropriate initial state? Ask your engineering friends.

The main idea of an enumeration is that it defines a collection of data as a finite number of pieces of data. Each item explicitly spells out which piece of data belongs to the class of data that we are defining. Usually, the piece of data is just shown as is; on some occasions, the item of an enumeration is an English sentence that describes a finite number of elements of pieces of data with a single phrase.

Here is an important example:
; A 1String is a string of length 1,
; including
;  "\\" (the backslash),
;  " " (the space bar),
;  "\t" (tab),
;  "\r" (return), and
;  "\b" (backspace).
; interpretation represents a single letter or keyboard character
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"
; ...
;  " "
;  "\\"
;  "\t"
;  "\r"
;  "\b"

If you look at your keyboard, you find , , and such notations. Our chosen programming language, BSL, specifically the "universe" library, uses its own data definition to represent this information: Here is an excerpt:You know where to find the full definition.
; 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.

At this point, we can actually design a key event handler systematically. Here is a sketch:
; WorldState KeyEvent -> ...
(define (handle-key-events w ke)
  (cond
    [(= (string-length ke) 1) ...]
    [(string=? "left" ke) ...]
    [(string=? "right" ke) ...]
    [(string=? "up" ke) ...]
    [(string=? "down" ke) ...]
    ...))
This event handling function uses a cond expression, and for each line in the enumeration of the data definition, there is one cond line. The condition in the first cond line identifies the KeyEvents identified in the first line of the enumeration, the second cond clause corresponds to the second data enumeration line, and so on.

; Position is a Number.
; interpretation distance between the left margin and the ball
 
; Position KeyEvent -> Position
; computes the next location of the ball
 
(check-expect (keh 13 "left") 8)
(check-expect (keh 13 "right") 18)
(check-expect (keh 13 "a") 13)
(define (keh p k)
  (cond
    [(= (string-length k) 1)
     p]
    [(string=? "left" k)
     (- p 5)]
    [(string=? "right" k)
     (+ p 5)]
    [else p]))
(define (keh p k)
  (cond
 
 
    [(string=? "left" k)
     (- p 5)]
    [(string=? "right" k)
     (+ p 5)]
    [else p]))

Figure 13: 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" library), 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 a key-event handler that moves a red dot left or right on a horizontal line in response to pressing the left and right arrow keys.

Figure 13 presents two solutions to this problem. The function on the left is organized according to the basic idea of using one cond clause per line in the data definition of the input, KeyEvent. In contrast, the right-hand side displays a version 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.

4.4 Intervals

Imagine yourself responding to the following sample design task:

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

After a bit of thinking, you could come up with a program like the one figure 14. Understand the data definition and the function definitions fully before you read on.

; WorldState is a Number
; interpretation 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
(define (main y0)
  (big-bang y0
            [on-tick nxt]
            [to-draw render]))
 
; WorldState -> WorldState
; computes 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))

Figure 14: UFO, descending

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

Sample Problem: Add a status line that says "descending" when the UFO’s height is above one third of the height of the canvas. It switches to "closing in" below that. And finally, when the UFO has reached the bottom of the canvas, the status notifies the player that the UFO has "landed."

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:

Exercise 50. 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 deals with the end points. In the context of our example, two points on the number line belong to two intervals: CLOSE belongs to both the upper interval and the middle one, while HEIGHT seems to fall into both the middle one and the lowest one. Such overlaps usually cause problems for programs, and they ought to be avoided.

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
; adds a status line to the scene created 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 clause, the ResultExpression uses render (from figure 14) to create the image with the descending UFO and then places an appropriate text at position (10,10) with place-image.

To run this revised animation, you need to change main from figure 14 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 might disturb you, and to clarify why, let us refine the sample problem from above just a tiny bit:

Sample Problem: Add a status line, positioned at (20,20), that says "descending" when the UFO’s height is above one third of the height ...

This could be the response of a client who has watched your animation for a first time.

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 you might recall from early chapters. 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
; adds a status line to the scene create by render  
 
(check-expect (render/status 42)
              (place-image (text "descending" 11 "green")
                           20 20
                           (render 42)))
 
(define (render/status y)
  (place-image
    (cond
      [(<= 0 y CLOSE)
       (text "descending" 11 "green")]
      [(and (< CLOSE y) (<= y HEIGHT))
       (text "closing in" 11 "orange")]
      [(> y HEIGHT)
       (text "landed" 11 "red")])
    20 20
    (render y)))
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 that is placed at position (20,20) into the image created by (render y).

4.5 Itemizations

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, a rewrite of an important example from Enumerations:
; A KeyEvent is one of:
;  1String
;  "left"
;  "right"
;  "up"
;  "down"
;  ...
In this case, the KeyEvent data definition refers to the 1String data definition. Since functions that deal with KeyEvents often deal with 1Strings separately from the rest and do so with auxiliary functions, 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 -> NorF
; converts the given string into a number;
; produces #false if impossible
(define (string->number s) (... s ...))
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
; adds 3 to the given number; 3 otherwise
 
(check-expect (add3 #false) 3)
(check-expect (add3 0.12) 3.12)
 
(define (add3 x)
  (cond
    [(false? x) 3]
    [else (+ x 3)]))
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. The program first displays the rocket sitting at the bottom of the canvas. Once launched, it moves upward at three pixels per clock tick.

This revised version suggests a data definition that represents two classes of states:
; A LR (short for: launching rocket) is one of:
;  "resting"
;  non-negative number
; interpretation "resting" represents a rocket on the ground
; a number denotes the height of 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 could 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 “height.” It is thus slightly more convenient for functions that translate the state of the world into an image, and we therefore choose to interpret the number in that spirit.

To drive home this choice, exercise 55 below asks you to solve the exercises of this section using the first interpretation of “height.”

Exercise 51. 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.

Following the design recipe for world programs from Designing World Programs, we first collect 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"))
The YDELTA constant describes how fast the rocket moves along the y axis, as specified in the problem statement; HEIGHT and WIDTH are arbitrary as is the graphical constant for the rocket.

Next we turn to the development of a data definition. This revision of the problem clearly calls for three distinct sub-classes of states:
; A LRCD (short for: launching rocket count down) is one of:
;  "resting"
;  a number in [-3,-1]
;  a non-negative number
; interpretation a rocket resting on the ground, in count-down mode,
; or the number of pixels from the top i.e. its height
The second, new sub-class of data—three negative numbers—represents the world after the user pressed the space bar and before the rocket lifts off.

At this point, we write down our wish list for a function that renders states as images and for any event-handling functions that we may need:
; LRCD -> Image
; renders the state as a resting or flying rocket
(define (show x)
  BACKG)
 
; LRCD KeyEvent -> LRCD
; starts the count-down when space bar is pressed,
; if the rocket is still resting
(define (launch x ke)
  x)
 
; LRCD -> LRCD
; raises the rocket by YDELTA,
;  if it is moving already
(define (fly x)
  x)
Remember that the design recipe for world programs—specifically, the mandates of the "universe" librarydictates these signatures, though the choice of names for the data collection and the event handlers are ours. Also, we have specialized the purpose statements to fit our problem statement.

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 make one test 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 51 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: one 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) must produce images like the one for (show -2). After all, the rocket still rests on the ground, even if the count down numbers differ.

  • The case for (show HEIGHT) is different. According to our agreement, HEIGHT represents the state when the rocket has just been launched. Pictorially this means the rocket is still resting on the ground. Based on the last test case above, here is the test case that expresses this insight:
    (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))

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

Following the precedents in this chapter, show uses 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 52. Why would it be incorrect to formulate the first condition as (string=? "resting" x)? Conversely, formulate a completely accurate condition, that is, a Boolean expression that evaluates to #true precisely when x belongs to the first subclass of LRCD. Similarly, what is a completely accurate condition for the third clause?

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.

Stop! Do you notice all the occurrences of 10 in the code? It always refers to the x coordinate of the rocket. So go ahead, create a constant definition for this 10. Now read on.

Exercise 53. 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 Prologue: How to Program.

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:
(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. What would you provide as the argument in a call to main1?

; LRCD -> LRCD
; raises 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 15: 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 54. Define main2 so that you can launch the rocket and watch it lift off. Read up on the on-tick clause to determine the length of one tick and how to change it.

If you watch the entire launch, you will notice that once the rocket reaches the top, something curious happens. Explain. Add a stop-when clause to main2 so that the simulation of the lift-off stops gracefully when the rocket is out of sight.

In solving exercise 54 you now have a complete, working program but one that behaves a bit strangely. Experienced programmers tell you that using negative numbers to represent the count-down phase is too “brittle.” The next chapter introduces the means to provide a good data definition for this problem. Before we go there, however, let us reiterate in the following section how to design programs that consume data described by itemizations.

Exercise 55. Recall that the word “height” forced us to choose one of two possible interpretation. Now that you have solved the exercises in this section, solve them again using the first interpretation of the word. Compare and contrast the solutions.

4.6 Designing 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 encounter problems concerning functions that consume itemizations, including enumerations and intervals. To keep the explanation grounded, we illustrate the six design steps with the following, somewhat simplistic 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 less than $1,000, are not taxed. Luxury items, with a price of more than $10,000, are taxed at the rate of eight percent (8.00%). Everything in between comes with a five percent (5%) mark up.

Design a function for a cash register that given the price of an item, computes the sales tax.

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 must use distinct clauses for each different subclasses of data or in some cases just individual pieces of data. Each clause specifies a data representation for a particular subclass of information. The key is that each subclass of data is distinct from every other class so that our function can proceed by analyzing disjoint cases.

    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.
    ; interpretation the price of an item  
    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, you proceed as before.

    Here is the material for our running example:
    ; Price -> Number
    ; computes 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 from each subclass in the data definition. Also, if a subclass is a finite range, be sure to pick examples from the boundaries of the range and from its interior.

    Since our sample 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.

    Stop! Before you read on, try to calculate the tax for each of these prices.

    Here is our first attempt:

    0.00

         

    537.00

         

    1000.00

         

    1282.00

         

    10000.00

         

    12017.00

    0.00

         

    0.00

         

    ????.??

         

    64.10

         

    ?????.??

         

    961.36

    The question marks point out that the problem statement uses the somewhat vague phrase “those costing less than $1,000” and “more than $10,000” to specify the tax table. While a programmer may immediately jump to the conclusion that these words mean “strictly less” or “strictly more,” the lawmakers may have meant to say “less or equal” or “more or equal,” respectively. Being skeptical, we decide here that Tax Land legislators always want more money to spend, so the tax rate for $1,000 is 5% and the rate for $10,000 is 8%. A programmer in a tax company would have to ask the tax-law specialist in the company.

    Now that we have figured out how the boundaries are to be interpreted in the domain, we could refine the data definition. We trust you can do this on your own.

    Before we go, let us turn some of the examples into test cases:
    (check-expect (sales-tax 537) 0)
    (check-expect (sales-tax 1000) (* 0.05 1000))
    (check-expect (sales-tax 12017) (* 0.08 12017))
    Take a close look. Instead of just writing down the expected result, we write down how to compute the expected result. This makes it easier later to formulate the function definition.

    Stop! Write down the remaining test cases. Think about why you may need more test cases than subclasses in the data definition.

  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. First, the function’s body must be a conditional expression with as many clauses as there are distinct subclasses in the data definition. If the data definition mentions three distinct subclasses of input data, you need three cond clauses; if it has seventeen subclasses, the cond expression contains seventeen clauses. Second, you must formulate one condition expression per cond clause. Each expression involves the function parameter and identifies one of the subclasses of data in the data definition.
    ; Price -> Number
    ; computes 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. When you have finished the template, you are ready to define the function. Given that the function body already contains a schematic cond expression, it is natural to start from the various cond lines. For each cond line, you may assume that the input parameter meets the condition and you exploit the corresponding test cases. 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.

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

    What do you do when one of your test cases fails? Review at the end of Designing Functions concerning test failures.

Exercise 56. 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.

4.7 A Bit More about Worlds

Let us exploit our knowledge to create a world that simulates a basic US traffic light. When the light is green and it is time to stop the traffic, the light turns yellow and after that turns red. When the light is red and it is time to get the traffic going, the light switches to green.

Figure 16: How a traffic light functions

Figure 16 summarizes this description as a state transition diagram. Such a diagram consists of states and arrows that connect these states. Each state depicts a traffic light in one particular configuration: red, yellow, or green. Each arrow shows how the world can change, from which state it can transition to another state. Our sample diagram contains three arrows, because there are three possible ways in which the traffic light can change. Labels on the arrows indicate the reason for changes; a traffic light transitions from one state to another as time passes.

In many situations, state transition diagrams have only a finite number of states and arrows. Computer scientists call such diagrams finite state machines or automata, for short: FSA. While FSAs look simple at first glance, they play an important role in computer science.

To create a world program for an FSA, we must first pick a data representation for the possible “states of the world,” which, according to Designing World Programs, represents those aspects of the world that may change in some ways as opposed to those that remain the same. In the case of our traffic light, what changes is the color of the light, that is, which bulb is turned on. The size of the bulbs, their arrangement (horizontal or vertical), and other aspects don’t change. Since there are only three states—red, yellow, and green—we pick three strings, as shown in the data definition of TrafficLight.

Figure 17: How to represent a traffic light

Figure 17 shows how to interpret the three elements of TrafficLight. Like the original figure, it consists of three states, arranged in such a way that it is easy to interpret each data element as a representation of a concrete configuration and to represent any such configuration as a piece of data. Also, the arrows are now labeled with tick to suggest that our world program uses the passing of time as the trigger that changes the state of the traffic light. Alternatively, we could use keystrokes or mouse events to switch the light, which would be especially appropriate if we wanted to simulate the manual operation of a traffic light.

Now that we know how to represent the states of our world, how to go from one to the next, and that the state changes at every tick of the clock, we can write down the signature, a purpose statement, and a stub for the two functions we must design:
; TrafficLight -> TrafficLight
; determines the next state of the traffic light, given current-state
(define (tl-next current-state) current-state)
 
; TrafficLight -> Image
; renders the current state of the traffic light as a image
(define (tl-render current-state) (empty-scene 100 30))
In previous sections, we used the names render and next 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. Because the specific functions have appeared before, we leave them as exercises.

Exercise 57. Finish the design of a world program that simulates the traffic light FSA. Here is the main function:
; TrafficLight -> TrafficLight
; simulates a traffic light that changes with each clock tick
(define (traffic-light-simulation initial-state)
  (big-bang initial-state
            [to-draw tl-render]
            [on-tick tl-next 1]))
The function uses as its argument the initial state for the big-bang expression. It tells DrRacket to re-draw the state of the world with tl-render and to react to clock ticks with tl-next. Also note it informs the computer that the clock should tick once per second (how?).

In short, you have two design tasks to complete: tl-render and tl-design.

Hints (1) Copy the data definition for TrafficLight and the definitions of tl-next and tl-render into DrRacket’s definition area.

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

(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, and so forth. You may find this auxiliary function helpful:
; TrafficLight TrafficLight -> Image
; renders the c colored bulb of the traffic light,
; if on is the current state
(define (bulb on c)
  (if (light=? on c) (circle RAD "solid" c) (circle RAD "outline" c)))

(3) Look up the image primitive place-image; it simplifies the task quite a bit.

Here is another finite state problem that introduces a few additional complications:

Sample Problem: Design a world program that simulates the working of a door with an automatic door closer. If this kind of door is locked, you can unlock it with a key. An unlocked door is closed but someone pushing at the door opens it. Once the person has passed through the door and lets go, the automatic door takes over and closes the door again. When a door is closed, it can be locked again.

To tease out the essential elements, we again draw a transition diagram; see the left-hand side of the figure. Like the traffic light, the door has three distinct states: locked, closed, and open. Locking and unlocking are the activities that cause the door to transition from the locked to the closed state and vice versa. As for opening an unlocked door, we say that one needs to push the door open. The remaining transition is unlike the others, because it doesn’t require any activities by anyone or anything else. Instead, the door closes automatically over time. The corresponding transition arrow is labeled with *time* to emphasize this.

Figure 18: 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" library 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 the space bar " " for pushing it open. The right-hand side diagram expresses these choices graphically; 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 the others, we must design functions that transform 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 our desire to render states as images in our simulation.

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
; simulates the actions on the door via three kinds of key events
(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 information from our drawing with the choices we made about mapping actions to keyboard events. Unlike the table of examples for traffic light, this table is incomplete. Think of some other examples; then consider why our table suffices.

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 the other concerning the given key event.

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
; translates 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
; simulates 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 58. During a door simulation the “open” state is barely visible. Modify door-simulation so that the clock ticks once every three seconds. Re-run the simulation.

; A DoorState is one of:
;  "locked"
;  "closed"
;  "open"
 
; DoorState -> DoorState
; simulates 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)))
 
; 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
; simulates actions on the door via three key events
 
(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
; renders 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"))

Figure 19: A door-simulation program

5 Adding Structure

We could play some mathematical tricks that would “merge” two atomic pieces into a single number such that it is possible to retrieve the original data as needed. But these kinds of tricks just obscure the true intentions behind a program and others will thus find it difficult to understand. Suppose you want to design a world program that simulates a ball rolling back and forth on a plane between two walls. Assume that it always moves two pixels per clock tick. If you follow the design recipe, your first goal is to develop a data representation for what changes over time. Here, the ball’s location and its direction change over time, but that’s two values while big-bang keeps track of just one. Thus 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 wrapped in some plastic. Among other things, it administrates your list of contacts. Each contact comes with a name, a phone number, an email address, and perhaps some other information. When you have lots of contacts, each single contact is best represented as a single piece of data; otherwise the various pieces could get mixed up by accident.

Because of such programming problems, every programming language provides some mechanism for combining several pieces of data into a single piece of compound data. This mechanism comes with means to retrieve the constituent values when needed. BSL supports structure type definitions for this purpose. A structure type definition introduces several functions into the available vocabulary, including one that creates structure instances and others for retrieving the constituent values from instances. The chapter starts with the mechanics of structure type definitions, presents how structure types relate to the entire universe of BSL data, and then moves on to designing with structure.

5.1 Structures

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

Here are the signature, header, and purpose statement:
; Posn -> Number
; computes 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, we 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, we could try to figure out the formula from some basic geometry, or we may recall the formula from your mathematics courses. As you know, this is domain knowledge that you might have but in case you don’t, we supply it; after all, this domain knowledge isn’t computer science. So, here is the distance of a point (x,y) from the origin as a formula:

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 structures as containers from which we can extract other values. BSL provides operations for extracting values from structures. For posn structures, there are two such operations, one per coordinate: posn-x and posn-y. The former operation extracts the x coordinate; the latter extracts the y coordinate.

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 are roughly analogous to the equations that govern addition and subtraction; adding z right after subtracting z from a number yields this original number.

Suppose we have the following in the definitions area of DrRacket:

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

Then we can use these two operations in the interactions area:
> (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. We can extract those with (posn-x a-posn) and (posn-y a-posn). Here is how we put 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 59. Evaluate the following expressions:
by hand. Show all steps. Assume that sqr performs its computation in a single step. Check the results with DrRacket’s stepper.

Exercise 60. 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, one cannot walk a straight path from a point to the origin; instead a person must follow the grid pattern. For a point such as (3,4), a local resident might say “go three blocks this way, turn right, and then go four blocks straight” to provide directions to get to the origin of the grid.

Design the function manhattan-distance, which measures the Manhattan distance of the given posn structure to the origin.

Defining a Structure: Unlike numbers or Boolean values, structures such as posn usually don’t come with a programming language. Only the mechanism to define structure types is provided; the rest is left up to the programmer. This is also true for BSL.

A structure type definition is, as the term indicates, 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 use of brackets is a convention to make the field names stand out. It is perfectly acceptable to use parentheses instead. The keyword define-struct signals to the reader—and to DrRacket—that a structure type is being defined. It is followed by the name of the structure, here posn. The third part of a structure type definition is a sequence of names enclosed in brackets, here [x y]; these names are the fields of the structure type.

Unlike an ordinary 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 area. 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 contacts list like the one in your cell phone:

(define-struct entry [name phone email])

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, "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. We italicize all labels in such pictures. 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 but only for appropriately labeled boxes.

Let 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 61. 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 to represent 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 for computer scientists, the positive direction of the y axis is down.

Exercise 62. 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 “oblique” manner across the screen. Describing both the location and the velocity of a ball moving across a 2-dimensional world canvas demands two numbers: one per direction. For the location part, the two numbers represent the x and y coordinates. Velocity describes the changes in the x and y direction; in other words, these “change numbers” must be added to the respective coordinates to find out where the object is next.

Let us use posn structures to represent locations and let us introduce a vel structure type for velocities:Those of you who know complex numbers may wish to contemplate a data representation that uses complex numbers for both location and velocity. BSL supports those, too.

(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 along only 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 from the top.

Since structures instances are values, it is not surprising that for ball1 we can 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. 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)

(make-vel -10 5)

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

-10

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

posn-x: expects a posn, given (make-vel -10 5)

Applying ball-velocity to ball1 extracts the value of the velocity field, which is an instance of vel. As with numeric arithmetic, we can also evaluate nested expressions, for example, (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 vel signals an error.

Exercise 63. 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 three phone numbers per name: one for a home line, one for the office, and one for a cell phone number. For phone numbers, we wish to include both the area code and the local number. Since this nests the information, the data representation needs to 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 separates the area code from the local phone number.

In sum, nesting information is natural. The best way to represent such information with data is to mirror the nesting with nested structure instances. Doing so makes it easy to interpret the data in the application domain of the program, and it is also straightforward to go from examples of information to data. Of course, it is really the task of data definitions to facilitates this task of going back and forth between information and data. We have not written data definitions so far, but we are going to catch up with this in the next section.

Data in Structures: Until now, data definitions have been rather boring. We have either used built-in collections of data to represent information (numbers, Boolean values, strings) or specified an itemization (interval or enumeration), which restricts an existing collection. The introduction of structures adds complexity to our data definitions.

The purpose of a data definition for structures 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)
; interpretation 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 list, are clearly 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)
; interpretation name, 7-digit phone number, and email address of a contact
In both cases, it is also easy to describe how a reader is to 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)
; interpretation 1 the position from top and the velocity
; interpretation 2 the position from left and the velocity
Whichever one we use in a program, we must stick to it consistently. 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)
; interpretation 2-dimensional position with a 2-dimensional velocity
 
(define-struct vel [deltax deltay])
; A Vel is a structure: (make-vel Number Number)
; interpretation 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 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 definitions, namely, the one for Vel. While all other data definitions have thus far referred to built-in data collections (numbers, Boolean values, strings), it is perfectly acceptable and indeed common that one of your data definition refers to another. Later, when you design programs, such connections provide some guidance for the organization of programs.

At this point, you might be wondering what data definitions really mean. This question, and its answer, is the topic of the next section.

Exercise 64. 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])

Historically, the first three digits make up the area code, the next three the code for the phone switch (exchange) of your neighborhood, and the last four represent the phone with respect to the neighborhood. Describe the content of the three fields as precisely as possible with intervals.

5.2 Programming with Structures

Structures defines distance-to-0, a function that consumed a structure and produced a number. Now we look at a few more such functions before formulating some general principles in the next section.

Sample Problem: Your team is designing a program that keeps track of the last mouse click on a 100 x 100 canvas. Together you chose Posn as the data representation for the x and y coordinates of the mouse click. Design a function that consumes a mouse click and a 100 x 100 scene and adds a circular red spot to the scene where the click occurred.

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 DOT (circle 3 "solid" "red"))
 
; Posn Image -> Image
; adds a red spot to s at p
(define (scene+dot p s)
  s)
The code fragment includes two definitions for graphical constants as inspired by the problem statement, though the radius for the red spot is arbitrary. And the preliminary definition comes with a purpose statement that, as suggested in Designing Functions, uses the function’s parameters to express what the function computes.

Next we work out a couple of examples:
(check-expect (scene+dot (make-posn 10 20) MTS)
              (place-image DOT 10 20 MTS))
(check-expect (scene+dot (make-posn 88 73) (rectangle 100 100 "solid" "blue"))
              (place-image DOT 88 73 (rectangle 100 100 "solid" "blue")))
The second example clarifies that scene+dot does not just add a dot to an empty image; it adds it to the given scene.

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 we see these additional pieces in the body of the function, the rest of the definition is straightforward. Using place-image, the function puts DOT into s at the coordinates contained in p:
(define (scene+dot p s)
  (place-image DOT (posn-x p) (posn-y p) s))

; visual constants
(define MTS (empty-scene 100 100))
(define DOT (circle 3 "solid" "red"))
 
; Posn Image -> Image
; adds a red spot to s at p
 
(check-expect (scene+dot (make-posn 10 20) MTS)
              (place-image DOT 10 20 MTS))
(check-expect (scene+dot (make-posn 88 73) MTS)
              (place-image DOT 88 73 MTS))
 
(define (scene+dot p s)
  (place-image DOT (posn-x p) (posn-y p) s))

Figure 20: 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
; increases 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, and the example all come 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 use it to combine the pieces in the function skeleton:
; Posn -> Posn
; increases 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 adds 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
; updates x coordinate of p 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)))
A neat observation is that we can define x+ using posn-up-x:
; Posn -> Posn
; increases 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-.

Many functions deal with nested structures. We illustrate this point with another small excerpt from a world program.

When you are given a location and a velocity (change in location per time unit), you can find out the location after one time unit by adding the velocity to the location.

Sample Problem: Your team is designing a game program that keeps track of an object that moves across the canvas at changing speed. The chosen data representation requires two data definitions:
(define-struct velocity [dx dy])
; A Velocity is a structure: (make-vel Number Number)
; interpretation (make-vel a b) means that the object moves a steps
; along the horizontal and b steps along the vertical per tick
 
(define-struct ufo [loc vel])
; A UFO is a structure: (make-ufo Posn Velocity)
; interpretation (make-ufo p v) is at location p moving at velocity v
Design the function move1, which moves some given UFO for one clock tick.

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 unlike function definitions, these constant definitions must be ordered in this manner.

Next we write down a signature, a purpose, some examples and a function header:
; UFO -> UFO
; determines where u moves in one clock tick;
; leaves 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 use 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.)

As before, we decide 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 include 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 question whether we need to 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 imagine that we have a function for adding a Velocity to a Posn:
; Posn Velocity -> Posn
; adds v to p
(define (posn+ p v) p)
Writing down the signature, purpose, and header like this is a legitimate way of programming. It is called “making a wish” and is a part of “making a wish list” as described in From Functions to Programs.

The key is to make wishes in such a way that we can complete the function that we are working on. In this manner, we can split difficult programming tasks into different tasks, a technique that helps us solve problems in reasonably small steps. For the sample problem, we get a complete definition for ufo-move:
(define (ufo-move u)
  (make-ufo
    (posn+ (ufo-loc u) (ufo-vel u))
    (ufo-vel u)))
Because ufo-move is a complete definition, we can even click RUN, which checks that DrRacket doesn’t complain about grammatical problems with our work so far.

Now it is time to focus on posn+. In geometry courses, the operation corresponding to posn+ is called a translation. 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)) is to 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. Stop! Check our manual calculations to insure you are following what we are doing.

We are now able to 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, these are simple applications of a selector to a parameter.

If we remind ourselves what these four expressions represent, or if we recall how we computed the desired results from the two structures, our completion of 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.

5.3 The Universe of Data

In mathematics such collections are called sets. Every language comes with a universe of data. This data represents information from and about the external world; it is what programs manipulate. This universe of data is a collection that consists of collections of built-in data but also of classes of data that programs create.

Figure 21: The universe of data

Figure 21 shows one way to imagine the universe of BSL. Since there are an infinitely many numbers and strings, the collection of all data is infinite. We indicate “infinity” in the figure with “...” but a real definition would have to avoid this imprecision.

Neither programs nor individual functions in programs deal with the entire universe of data. It is the purpose of a data definition to describe parts of this universe and to name these parts so that we can refer to them concisely. Put differently, a named data definition is a description of a collection of data, and that name is usable in other data definitions and in function signatures. In a function signature, the name specifies what data a function will deal with and, implicitly, which part of the universe of data it won’t deal with.

Figure 22: The meaning of a data definition

Practically the data definitions of the first four 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 figure 22 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 to BS and which 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 middle bubble in figure 23 depicts the addition of those values, showing things such as (make-posn "hello" 0) and even (make-posn (make-posn 0 1) 2). And yes, even though some of these instances of posn make no sense to us, it is indeed possible to construct all of them in a BSL program.

Figure 23: Adding structure to a universe

The addition of another structure type definition mixes and matches everything, too. Say we add a structure type definition for ball, also with two fields. As the third bubble in figure 23 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 (make-ball "hello" 1) #false)

> (make-posn (make-ball (make-ball (make-posn 1 2) 3) 4) 5)

(posn (make-ball (make-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 24: Imposing a data definition on structures

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

; 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 natural language, data collections defined elsewhere and data constructors. Nothing else should show up in a data definition at the moment.

A data definition for structures specifies a new collection of data made up of those instances to be used by our functions. For example, the data definition for Posns identifies the region shaded with gray stripes in figure 24, 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 the requirement that both fields contain numbers:

(make-posn (make-posn 1 1) "hello")

this structure contains a posn in the x field and a string in the y field.

Exercise 65. Formulate data definitions for the following structure type definitions: