I Fixed-Size Data

1 Arithmetic

When a programmer studies a new language, the first item of business is the language’s “arithmetic,” meaning its basic forms of data and the operations that a program can perform on this data. At the same time, we need to learn how to express data and how to express operations on data.

It is not necessary to read and understand the entire chapter in order to make progress. As soon as you sense that this chapter is slowing you down, move on to the next one. Keep in mind, though, that you may wish to return here and find out more about the basic forms of data in BSL when the going gets rough.

The rest of this chapter introduces four forms of data: numbers, strings, images, and Boolean values. It also illustrates how these forms of data are manipulated with primitive operations, often called built-in operations or primitive functions. In many cases, these manipulations involve more than one form of data.

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)

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

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

> (sin 0)

0

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

When it comes to numbers, BSL programs may use natural numbers, integers, rational numbers, real numbers, and complex numbers. We assume that you have heard of the first four. The last one may have been mentioned in your high school. If not, don’t worry; while complex numbers are useful for all kinds of calculations, a novice doesn’t have to know about them.

A truly important distinction concerns the precision of numbers. For now, it is important to understand that BSL distinguishes exact numbers and inexact numbers. When it calculates with exact numbers, BSL preserves this precision whenever possible. For example, (/ 4 6) produces the precise fraction 2/3, which DrRacket can render as a proper fraction, an improper fraction, or as a mixed decimal. Play with your computer’s mouse to find the menu that changes the fraction into decimal expansion and other presentations.

Some of BSL’s numeric operations cannot produce an exact result. For example, using the sqrt operation on 2 produces an irrational number that cannot be described with a finite number of digits. Because computers are of finite size and BSL must somehow fit such numbers into the computer, it chooses an approximation: #i1.4142135623730951. As mentioned in the Prologue, the #i prefix warns novice programmers of this lack of precision. While most programming languages choose to reduce precision in this manner, few advertise it and fewer even warn programmers.

Exercise 1: The direct goal of this exercise is to create an expression that computes the distance of some specific Cartesian point (x,y) from the origin (0,0). The indirect goal is to introduce some basic programming habits, especially the use of the interactions area to develop expressions.

The values for x and y are given as definitions in the definitions area (top half) of DrRacket:

(define x 3)

(define y 4)

The expected result for these values is 5 but your expression should produce the correct result even after you change these definitions.

Just in case you have not taken geometry courses or in case you forgot the formula that you encountered there, the point (x,y) has the distance

from the origin. After all, we are teaching you how to design programs not how to be a geometer.

To develop the desired expression, it is best to hit RUN and to experiment in the interactions area. The RUN action tells DrRacket what the current values of x and y are so that you can experiment with expressions that involve x and y:

> x
3
> y
4
> (+ x 10)
13
> (* x y)
12

Once you have the expression that produces the correct result, copy it from the interactions area to the definitions area, right below the two variable definitions.

To confirm that the expression works properly, change the two definitions so that x represents 12 and y stands for 5. If you click RUN now, the result should be 13.

Your mathematics teacher would say that you defined a distance function in a naive manner. To use the function, you need to open DrRacket, edit the definitions of x and y to the desired coordinates, and click RUN. We will soon show you the right way to define functions. For now, we use this kind of exercise to remind you of the idea and to prepare you for programming with functions.

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 should never (ever) succumb to this thinking.

Programming languages are about calculating with information, and information comes in all shapes and forms. For example, a program may deal with colors, names, business letters, or conversations between people. Even though we could encode this kind of information as numbers, it would be a horrible idea. Just imagine remembering large tables of codes, such as 0 means “red” and 1 means “hello,” etc.

Instead most programming languages provide at least one kind of data that deals with such symbolic information. For now, we use BSL’s strings. Generally speaking, a String is a sequence of the characters that you can enter on the keyboard enclosed in double quotes, plus a few others, about which we aren’t concerned just yet. In Prologue: How to Program, we have seen a number of BSL strings: "hello", "world", "blue", "red", etc. The first two are words that may show up in a conversation or in a letter; the others are names of colors that we may wish to use.

Exercise 2: Add the following two lines to the definitions area:

(define prefix "hello")

(define suffix "world")

Then create an expression using string primitives that concatenates prefix and suffix and adds "_" between them. So the result for these two definitions should be "hello_world".

See exercise 1 for how to create expressions using DrRacket.

1.3 Mixing It Up

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 "2htdp/image" teachpack. Like strings, you used DrRacket to insert images wherever you would insert an expression into your program, because images are values just like numbers and strings.

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

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.

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

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.

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

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

Furthermore, programming languages classify numbers just as mathematics teachers do. In BSL, numbers are classified in two different directions. The first you may know from middle school or high school: integer?, rational?, real?, and complex?, even if you don’t know the last one. Evaluate (sqrt -1) in the interactions area and take a close look at the result. Your mathematics teacher may have told you that one doesn’t compute the square root of negative numbers. Truth is that in mathematics and in BSL, it is acceptable to do so, and the result is a so-called complex number. Don’t worry, though, complex numbers—while useful—play no role in this book. The second direction concerns the degree of exactness that we have mentioned before. There are two predicates: exact? and inexact?, and there are even functions that convert exact numbers into inexact ones, and vice versa. For now, just keep in mind that there are two kinds of numbers. Later, we are going to discuss the nature of numbers in some detail.

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

(define in "hello")

Then create an expression that converts whatever in represents to a number. For a string, it determines how long the string is; for an image, it uses the area; for a number, it decrements the number, unless it is already 0 or negative; for true it uses 10 and for false 20.

See exercise 1 for how to create expressions in DrRacket.

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

2 Functions and Programs

As far as programming is concerned, arithmetic is half the game. The other half is “algebra.” Of course, our notion of “algebra” relates to the school notion of algebra just as much as the notion of “arithmetic” from the preceding chapter relates to the ordinary notion of grade-school arithmetic. What we do mean is that the creation of interesting programs involves variables and—at least abstractly—functions. Once we can deal with functions, writing programs is within reach, though we need to understand that functions, like people, can collaborate (though following mathematics, we don’t call it “collaboration” but composition).

2.1 Functions

From a high-level perspective, a program is a function. A program, like a function in mathematics, consumes inputs, and it produces outputs. In contrast to mathematical functions, programs work with a whole variety of data: numbers, strings, images, and so on. Furthermore, programs may not consume all of the data at once; instead a program may incrementally request more data or not, depending on what the computation needs. Last but not least, programs are triggered by external events. For example, a scheduling program in an operating system may launch a monthly payroll program on the last day of every month. Or, a spreadsheet program may react to certain events on the keyboard with filling some cells with numbers.

Definitions: While many programming languages obscure the relationship between programs and functions, BSL brings it to the fore. Every BSL programs consists of definitions, usually followed by an expression that involves those definitions. There are two kinds of definitions:

• constant definitions, of the same (define AVariable AnExpression), which we encountered in the preceding chapter; and

• function definitions, which come in many flavors, one of which we used in the Prologue.

Before we explain why these examples are silly, we need to explain what function definitions mean. Roughly speaking, a function definition introduces a new operation on data; put differently, it adds an operation to our vocabulary if we think of the primitive operations as the ones that are always available. Like a primitive operation, a defined operation consumes inputs. The number of variables determines how many inputs—also called arguments or parameters—a 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 body—determines 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.

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

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.

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

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

In exercise 1 you developed the right-hand side for this function. All you really need to do is add a function header. Remember this idea in case you are ever stuck with a function. Use the recipe of exercise 1 to develop the expression in the interactions area, and then write down the function definition.

Exercise 14: Define the function cube-volume, which accepts the length of a side of a cube and computes its volume. If you have time, consider defining cube-surface, too.

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

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

Exercise 17: Define the function bool-imply. It consumes two Boolean values, call them b1 and b2. The answer of the function is true if b1 is false or b2 is true. Note: Logicians call this imply and often they use the symbol => for this purpose. While BSL could define a function with this name, we avoid the name because it is too close to the comparison operations for numbers <= and >=, and it would thus easily be confused. See exercise 9.

Exercise 18: Define the function image-area, which computes the area of a given image. Note: The area is also the number of pixels in the picture. See exercise 5 for ideas.

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

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

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

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

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

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

Define one function per task.

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

Exercise 23: Our solution to the sample problem contains several constants in the middle of functions. As One Program, Many Definitions already points out, it is best to give names to such constants so that future readers understand where these numbers come from. Collect all definitions in DrRacket’s definitions area and change them so that all magic numbers are refactored into constant definitions.

Exercise 24: Determine the potential profit for the following ticket prices: $1, $2, $3, $4, and $5. Which price should the owner of the movie theater choose to maximize his profits? Determine the best ticket price down to a dime.

Exercise 25: After studying the costs of a show, the owner discovered several ways of lowering the cost. As a result of his improvements, he no longer has a fixed cost. He now simply pays $1.50 per attendee.

Modify both programs to reflect this change. When the programs are modified, test them again with ticket prices of $3, $4, and $5 and compare the results.

2.3 Programs

In this section we present some simple examples of both batch programs and interactive programs. Before we do so, however, we need one more ingredient: constant definitions.

Batch Programs: As mentioned, a batch program consists of one main function, which performs all the computations. On rare occasions, a program is just this one function. Most of the time, though, the main function employs numerous auxiliary functions, which in turn may also use other functions.

Programs are even more useful if you can retrieve the input from some file on your computer and deliver the output to some other file. The name batch program originates from programs in the early days of computing when a program read an entire file and created some other file, without any other intervention.

This first batch program requires users to actually open DrRacket and to apply the function main to three strings. With read-file, we can do even better, namely we can construct batch programs that do not rely on any DrRacket knowledge from their users.

Let us illustrate the idea with a simple program just to see how things work. Suppose we wish to create a program that converts a temperature measured on the Fahrenheit thermometer into a Celsius temperature. Don’t worry, this question isn’t a test about your physics knowledge (though you should know where to find this kind of knowledge); here is the conversion formula:

Naturally in this formula f is the Fahrenheit temperature and c is the Celsius temperature. Translating this into BSL is straightforward:

(define (f2c f)

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

Recall that 5/9 is a number, a rational fraction to be precise, and more importantly, that c depends on the given f, which is what the function notation expresses.

(define (convert in out)

(write-file out

(number->string

(f2c

(string->number (read-file in))))))

(define (f2c f)

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

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

Figure 6: Converting Fahrenheit temperatures into Celsius

In addition to running the batch program, you should also step through the computation. Make sure that the file "sample.dat" exists and contains just a number, then click the STEP button. Doing so opens another window in which you can peruse the computational process that the call to the main function of a batch program triggers. In this case, the process follows the above outline, and it is quite instructive to see this process in action.

With the choice of a menu entry, DrRacket can also produce a so-called executable, a stand-alone program like DrRacket itself. Specifically, choose the entry Create Executable from the Racket menu, and DrRacket will place a package—labeled convert—into the same folder as your program, which you may then distribute to your friends (who use the same kind of computer). They can install this program and they can run it—without knowing anything about DrRacket, as long as they create a file called "sample.dat" in the same folder where they installed the program. After the program is run, they can find the result in the file "out.dat".

Interactive Programs: No matter how you look at it, batch programs are old-fashioned and somewhat boring. Even if businesses have used them for decades to automate useful tasks, interactive programs are what people are used to and prefer over batch programs. Indeed, in this day and age, people mostly interact with programs via a keyboard and a mouse, that is, events such as key presses or mouse clicks. Furthermore, interactive programs can also react to computer-driven events, e.g., the fact that the clock has ticked or that a message has arrived from some other computer.

Launching interactive programs requires more work than launching a batch program. Specifically, an interactive program designates some function as the one that takes care of keyboard events, another function as the one that presents pictures, a third function for dealing with clock ticks, etc. Put differently, there isn’t a main function that is launched; instead there is an expression that tells the computer how to handle interaction events and the evaluation of this expression starts the program, which then computes in response to user events or computer events.

In BSL, the "universe" teachpack provides the mechanisms for specifying connections between the computer’s devices and the functions you have written. The most important mechanism is the big-bang expression. It consists of one required subexpression, which must evaluate to some piece of data, and a number of optional clauses, which determine which function deals with which event.

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

Copy this definition of render and the third big-bang example into the definitions area of DrRacket Then click RUN, and observe a separate window that counts down from 100 to 0. At that point, the evaluation stops and a 0 appears in the interactions area.

An explanation of this schematic expression must start with is the first, required subexpression. The value of this first expression is installed as a world, specifically the current world. Furthermore, this big-bang expression tells the computer to apply the function tock to the current world whenever the clock ticks. The result of this application—whatever it is—becomes the next current world, a relationship that the following table concisely summarizes:

Each current world is turned into an image with an application of render and this series of images is displayed in a separate window. Finally, the function end? is used to inspect each current world. If the result is true, the evaluation of the big-bang expression is stopped; otherwise it continues.

Coming up with big-bang expressions for interactive programs demands a different skill, namely, the skill of systematically designing a program. Indeed, you may already feel that these first two chapters are somewhat overwhelming and that they introduced just too many new concepts. To overcome this feeling, the next chapter takes a step back and explains how to design programs from scratch, especially interactive programs.

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 understand the vocabulary of the programming language; we need to figure out its grammar; and we must know what “phrases” mean.

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

In his book “The Mythical Man-Month” Fred Brooks describes and contrasts these forms of programming on the first pages. In addition to “garage programming” and a “programming product,” he also recognizes “component programming” and “systems programming.” This book is about the “programming products;” our next two books will cover “components” and “systems” design. All this sounds rather complex and you might wonder why we don’t just muddle our way through, experimenting here and there, and leaving it all alone when the results look decent. This approach to programming, often dubbed “garage programming,” is common and succeeds on many occasions; on some it is even the foundation for a start-up company. Nevertheless, the company cannot sell the results of the “garage effort” because they are usable only by the programmers themselves. These programs are like the first two batch programs we wrote in the preceding chapter.

In practice, a good program must come with a short write-up that explains what it does, what inputs it expects, and what it produces. Ideally, it also comes with some assurance that it actually works. Best of all the program should be connected to the problem statement in such a way that a small change to the problem statement is easy to translate into a small change to the program. Software engineers call this a “programming product.”

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

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

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

In this book, we present a design recipe that integrates a step-by-step process with a way of organizing programs around problem data. For the readers who don’t like to stare at blank screens for a long time, this design recipe offers a way to make progress in a systematic manner. For those of you who teach others to design programs, the design recipe is a device for diagnosing a novice’s difficulties. For yet others, the design recipe may just be something that they can apply to other areas, say medicine, journalism, or engineering, because program design isn’t the right choice for their careers. Then again, for those of you who wish to become real programmers, the design recipe also offers a way to understand and work on existing programs—though not all programmers use a method like the design recipe to come up with programs. The rest of this chapter is dedicated to the first baby steps into the world of the design recipe; all of the following chapters refine the design recipe in one way or another.

3.1 Designing Functions

Information and Data: The purpose of a program is to describe a computation, a process that leads from collection of information to another. In a sense, a program is like the instruction a mathematics teacher gives to grade school students. Unlike a student, however, a program works with more than numbers; it calculates with navigation information, looks up a person’s address, turns on switches, or processes the state of a video game. All this information comes from a part of the real world—often called the program’s domain in computer science—and the results of a program’s computation are turned into information in this domain.

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

For a program to process information, it must turn it into some form of data, i.e., values in the programming language; then it processes the data; and once it is finished, it turns the resulting data into information again. A program may even intermingle these steps, acquiring more information from the world as needed and delivering information in between. You should recall that we apply the adjective “batch” to the plain programs and the others are called “interactive.”

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

BSL and DrRacket cleanly separate these tasks so that you can focus on designing the “core” of programs and, when you have enough expertise with that, you can learn to design the rest. Indeed, real software engineers have come up with the same idea and have a fancy name for it, model-view-control (MVC), meaning a program should separate its information processing view from the data processing model. Of course, if you really wish to make your programs process information, you can always use the "batch-io" teachpack to produce complete batch programs or the "universe" teachpack to produce complete interactive programs. As a matter of fact, to give you a sense of how complete programs are designed, this book and even this chapter provide a design recipe for such programs.

Figure 7: From information to data, and back

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

The word “class” is a popular computer science substitute for the word “set.” In analogy to other set theory mathematics, we also say a value is some element of a class.

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

If you happen to know that the lowest possible temperatures is approximately -274, you may wonder whether it is possible to express this knowledge in a data definition. Since data definitions in BSL are really just English descriptions of classes, you may indeed define the class of temperatures in a much more accurate manner than shown above. In this book, we use a stylized form of English for such data definitions, and the next chapter introduces the style for imposing constraints such as “larger than -274.”

At this point, you have encountered the names of some data: Number, String, Image, and Boolean values. With what you know right now, formulating a new data definition means nothing more than introducing a new name for an existing form of data, e.g., “temperature” for numbers. Even this limited knowledge, though, suffices to explain the outline of our design process.

3.2 Finger Exercises

The first few of the following exercises are almost copies of previous exercise. The difference is that this time they used the word “design” not “define,” meaning you should use the design recipe to create these functions and your solutions should include the relevant pieces. (Skip the template; it is useless here.) Finally, as the title of the section says these exercises are practice exercises that you should solve to internalize the process. Until you internalize the design process, you should never skip a step; it leads to easily-avoided errors and unproductive searches for the causes of errors. There is plenty of room left in programming for complex errors. We have no need to waste our time on silly errors.

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

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

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

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

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

3.3 Domain Knowledge

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

3.4 From Functions to Programs

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

When you have defined global constants, your functions may use those global constants to compute the results from the given data. In some sense, you should add these global constants to your template, because they belong to the inventory of things that may contribute to the definition. Adding global constants to templates, however, can quickly make those templates look messy. In short, keep global constants in mind when you define functions.

The issue with multi-function programs is complex. On one hand, the design of interactive functions automatically demands the design of several functions. On the other hand, even the design of batch programs may require dealing with several different tasks. Sometimes the problem statement itself suggests different tasks; other times you will discover the need for auxiliary functions as you are in the middle of designing some function.

For all cases, we recommend keeping around a list of “desired functions” or a wish list.The term “wish list” in this context is due to Dr. John Stone. Each entry on a wish list should consist of three things: a meaningful name for the function, a signature, and a purpose statement. For the design of a batch program, put the main function on the wish list and start designing it. For the design of an interactive program, you can put the event handlers, the stop-when function, and the scene-rendering function on the list. As long as the list isn’t empty, pick a wish and design the function. If you discover during the design that you need another function, put it on the list. When the list is empty, you are done.

3.5 On Testing

Testing quickly becomes a labor-intensive chore. While it is easy to run tests and discover syntactic errors (clicking the RUN button does this) and run-time errors (the application of a primitive operation to the wrong kind of data), comparing the result of an interaction with the expected result is tiresome. For complex programs, you will tend to write lots of examples and tests and you will have to compare complex (large) values. If you haven’t thought so, you will soon think that this is burdensome and perform sloppy comparisons.

At the same time, testing is a major step to discover flaws in a program. Sloppy testing quickly leads to functions with hidden problems, also known as bugs. Buggy functions then stand in the way of progress on large systems that use these functions, often in multiple ways.

For these reasons—and others to be discussed—it is critical to mechanize tests and not perform them manually in the interactions area. BSL in the DrRacket environment includes a testing facility, as many programming systems do.

; Number -> Number

; convert Fahrenheit temperatures to Celsius temperatures

(check-expect (f2c -40) -40)

(check-expect (f2c 32) 0)

(check-expect (f2c 212) 100)

(define (f2c f)

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

Figure 8: Testing in BSL

You can place check-expect specifications above or below the function definition that they test. When you click RUN, DrRacket collects all check-expect specifications and evaluates them after all function definitions have been added to the “vocabulary” of operations. The above figure shows how to exploit this freedom to combine the example and test step. Instead of writing down the examples as comments, you can translate them directly into tests. When you’re all done with the design of the function, clicking RUN performs the test. And if you ever change the function for some reason—to improve its look or to add a piece of functionality—the next click re-tests the function.

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

3.6 Designing World Programs

The "universe" teachpack supports the construction of some interactive programs. Specifically, you can use the "universe" teachpack to construct so-called world programs, i.e., interactive programs that deal with clock ticks, mouse clicks, and key strokes. In order to interact with people, world programs also create images that DrRacket displays in a graphical canvas.

While the previous chapter introduces the "universe" teachpack in an ad hoc way, this section demonstrates how the design recipe helps you create world programs. The first section provides some basic knowledge about big-bang, the major construct for wiring up world programs. The second section extends this knowledge to deal with mouse clicks and key strokes. Once you have digested this terminology, you are ready to design world programs. The last section is the beginning of a series of exercises, which run through a couple of chapters in this book; take a close look and create your own favorite virtual pet.

Describing Worlds: A raw computer is a nearly useless piece of physical equipment, often called hardware because you can touch it. This equipment becomes useful once you install software, and the first piece of software is usually installed on a computer is an operating system. It has the task of managing the computer for you, including connected devices such as the monitor, the keyboard, the mouse, the speakers, and so on. When you press a key on the keyboard, the operating system runs a function that processes the key stroke. We say that the key stroke is an key event, and the function is an event handler. Similarly, when the clock ticks, the operating system runs an event handler for clock ticks and, when you perform some action with the mouse, the operating system launches the event handler for mouse clicks.

Naturally, different programs have different needs. One program may interpret key strokes as signals to control a nuclear reactor; another passes them to a word processor. To make one and the same computer work on these radically different tasks, programs install event handlers. That is, they tell the operating system to use certain functions for dealing with clock ticks and other functions for dealing with mouse clicks. If a program doesn’t need to handle key strokes, the program says nothing about key events and the operating system ignores them.

The key question is what arguments DrRacket supplies to your event handlers for key strokes, mouse clicks, and clock ticks and what kind of results it expects from these event handlers. Like a real operating system, DrRacket gives these functions access to the current state of the world. For key events and mouse events, DrRacket also supplies information about these events.

The initial state is the value of w0, because our big-bang expression says so. It also is the state that DrRacket hands to the first event handling function that it uses. DrRacket expects that this event handling function produces a new state of the world, call it w1. The point is that DrRacket keeps this result around until the second event happens. Here is a table that describes this relationship among worlds and event handling functions:

In short, the sequence of events determines in which order you traverse the above tables of possible worlds to arrive at the one and only one current world for each time slot. Note that DrRacket does not touch the current world; it merely safeguards it and passes it to event handling functions when needed.

Designing Worlds: Now that you understand how big-bang works, you can focus on the truly important problem of designing world programs. As you might guess, the design starts with the data definition for the states of the “world.” To this end we assume that you have a problem statement and that you are able to imagine what the world program may display in various situations.

A note on names: Naturally, you don’t have to use the name “CarState” for the class of data that represents the states of the world; any name will do as long as you use it consistently for the signatures of the big-bang functions. Also, you don’t have to use the names tock, render, or end?; you can name these functions whatever you like, as long as you use the same names when you write down the clauses of the big-bang expression.

A note on design: Even after settling on the data definition, a careful programmer shouldn’t be completely happy. The image of the car (and a car itself) isn’t just a mathematical point without width and height. Thus, to write “the number of pixels from the left margin” is an ambiguous interpretation statement. Does this statement measure the distance between the left margin and the left end of the car? Its center point? Or even its right end? While this kind of reflection may seem far-fetched, it becomes highly relevant and on occasion life-critical in some programming domains. We ignore this issue for now and leave it to BSL’s image primitives to make the decision for us.

Good programs establish a single point of control for all aspects, not just the graphical constants. Several chapters deal with this issue.

Exercise 32: Good programmers ensure that an image such as CAR can be enlarged or reduced via a single change to a constant definition. We started the development of our car image with a single plain definition:

(define WHEEL-RADIUS 5)

All other dimensions of the car and its pieces are based on the wheel’s radius. Changing WHEEL-RADIUS from 5 to 10 “doubles” the size of the car image, and setting it to 3 reduces it. This kind of program organization is dubbed single point of control, and good design employs single point of control as much as possible.

Now develop your favorite image of a car; name the image CAR. Remember to experiment and make sure you can re-size the image easily.

The rest of this section demonstrates how to apply the third design step to our sample problem. Since the car is supposed to move continuously across the canvas, and since the problem statement doesn’t mention any other action, we have two functions on our wish list: tock for dealing with a clock tick and render for creating an image from the state of the world.

And then, you just need to test, which means evaluating expressions such as (render 50), (render 100), (render 150), and (render 200) and making sure that the resulting image is what you want. Naturally, this is somewhat more difficult than checking that a number is what you want. For now, we and you need to rely on your eyes, which is why doing so is called an eyeball test. In the penultimate subsection, we return to the testing issue in general and the one for images in particular.

Exercise 33: Finish the sample exercise and get the program to run. That is, assuming that you have solved the exercise of creating the image of a car, define the constants Y-CAR and BACKGROUND. Then assemble the appropriate big-bang expression. When your program runs to your satisfaction, add a tree to scenery. We used

(define tree

(underlay/xy (circle 10 'solid 'green)

9 15

(rectangle 2 20 'solid 'brown)))

to create a tree-like shape. Also add a clause to the big-bang expression that stops the animation when the car has disappeared on the right side of the canvas.

Exercise 34: Start with the following data definition:

; AnimationState is a Number

; interp. the number of clock ticks since the animation started

Like the original data definition, this one also equates the states of the world with the class of numbers. Its interpretation, however, explains that the number means something entirely different.

Design functions tock and render and develop a big-bang expression so that you get once again an animation of a car traveling from left to right across the world’s canvas.

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

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

Of Mice and Characters: Before you design world programs that deal with key strokes and mouse events, it is a good idea to practice with small, nearly trivial examples to understand what the event handlers can and cannot compute. We start with a simple problem concerning key strokes:

Sample Problem: Design a program that keeps track of all key strokes. The program should display the accumulated key strokes as a red text in the 11 point font.