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 primitives. Because of the nature of BSL, this book also refers to primitives as functions though you will need to read the remaining chapters of this first part to understand the reason for this terminology.

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

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

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, that is, 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.

In addition to predicates that distinguish different forms of data, programming languages also come with predicates that distinguish different kinds of numbers. In BSL, numbers are classified in two ways: by construction and by their exactness. Construction refers to the familiar sets of numbers: integer?, rational?, real?, and complex?. You may know these terms from secondary school.Evaluate (sqrt -1) in the interactions area and take a close look at the result. The result you see is the first so-called complex number anyone encounters. While your mathematics teacher may have told you that one doesn’t compute the square root of negative numbers, truth is that real mathematicians and programmers find it acceptable and useful to do so anyway. But don’t worry: understanding complex numbers is not essential to being a programmer. As for exactness, we have mentioned the idea before. For now, experiment with exact? and inexact? to make sure they perform the checks that their names suggest. Later we are going to discuss the nature of numbers in some detail.

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. The creation of real programs involves variables and thus functions, meaning basic notions from algebra. Once we can deal with functions, we can move on to programs, which “compose” functions to achieve their overall purpose.

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 shape (define AVariable AnExpression), which we encountered in the preceding chapter; and

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

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 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 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 Boolean operation implication and often use the symbol =>, pronounced “implies,” for this purpose. While BSL could define a function with this name, we avoid that name because it is too similar to the comparison operations for numbers <= and >=, and it would thus easily be confused. See exercise 9.

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

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

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

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

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

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.

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

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 simple examples of both batch and interactive programs. Before we do so, however, we need one more ingredient: constant definitions.

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.

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

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

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

Exercise 26: Recall the letter program from Composing Functions. We launched this program once, with the inputs "Matthew", "Krishnamurthi", and "Felleisen". Here is how to launch the program and have it write its output to the interactions area:

> (write-file 'stdout (letter "Matthew" "Krishnamurthi" "Felleisen"))

Dear Matthew,   We have discovered that all people with the last name Krishnamurthi have won our lottery. So, Matthew, hurry and pick up your prize.   Sincerely,   Felleisen

'stdout

Of course, programs are useful because you can launch them for many different inputs, and this is true for letter, too. Stop! Run letter on the following three inputs:

• "Robby" "Flatt" "Felleisen"

• "Christopher" "Columbus" "Felleisen"

• "ZC" "Krishnamurthi" "Flatt"

From here it is a short step to a simple batch program that reads names from three files and writes a letter to one:

(define (main in-fst in-lst in-signature out)

(write-file out

(letter (read-file in-fst)

(read-file in-lst)

(read-file in-signature))))

The function consumes four strings: the first three are the names of input files and the last one serves as output file. It uses the first three to read one string each from the three named files, hands these strings to letter, and eventually writes the result of this function call into the file named by out, the fourth argument to main.

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

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

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

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

In BSL, the "universe" teachpack provides this communication mechanisms. For now, the key mechanism is the big-bang expression. It describes to DrRacket how the interactive program deals with clock ticks, key presses, mouse clicks, and so on. A big-bang expression consists of one required subexpression and one required clause. The subexpression evaluates to the initial state of the program, and the required clause tells DrRacket how to render the current state as a program.

With this explanation, you may wish to re-examine Prologue: How to Program because it shows several interactive programs. Like a batch program, an interactive program comes with a main function; unlike a batch program, the main program of an interactive program almost always uses a big-bang expression to install event handling functions, which are defined separately.

In addition to to-draw, on-tick, and stop-when clauses, a world program may also specify on-key and on-mouse clauses. With on-key an interactive program can react to key strokes, and with on-mouse it can treat mouse clicks. For now, all you need to know that on-key needs a function that takes two inputs: the current world and a string, which represents the key stroke.

By now, you may feel that these first two chapters are somewhat overwhelming and that they introduced just too many new concepts. That is correct. To overcome this feeling, the next chapter takes a step back and explains how to design programs systematically from scratch, especially interactive programs. So take a breather and continue when ready.

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.

In his book “The Mythical Man-Month” Fred Brooks describes and contrasts these forms of programming on the first pages. In addition to “garage programming” and a “programming product,” he also recognizes “component programming” and “systems programming.” This book is about the “programming products;” our next two books will cover “components” and “systems” design. All this sounds rather complex and you might wonder why we don’t just muddle our way through, experimenting here and there, leaving well enough alone when the results look decent. This approach to programming, often dubbed “garage programming,” is common and succeeds on many occasions; sometimes it is the launching pad for a start-up company. Nevertheless, the start-up cannot sell the results of the “garage effort” because only the original programmers and their friends can use them.

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

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

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

Exercise 27: 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 refine the 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 one collection of information to another. In a sense, a program is like the instruction a mathematics teacher gives to grade school students. Unlike a student, however, a program works with more than numbers; it calculates with navigation information, looks up a person’s address, turns on switches, or processes the state of a video game. All this information comes from a part of the real world—often called the program’s domain—and 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, also called values, in the programming language; then it processes the data; and once it is finished, it turns the resulting data into information again. An interactive program may even intermingle these steps, acquiring more information from the world as needed and delivering information in between.

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

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

Here we use the "batch-io" and "universe" teachpacks to demonstrate how complete programs are designed. That is, this book—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 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 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.

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

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

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 the relevant pieces. (Skip the template; it is useless here.) Finally, as the title of the section suggests these exercises are practice exercises to help you internalize the process. Until the steps become second nature, never skip one; that leads to easily avoided errors and unproductive searches for the causes of those flaws. There is plenty of room left in programming for complicated errors. We have no need to waste our time on silly mistakes.

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

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

Exercise 30: 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 31: Design the function string-rest, which produces a string like the given one with the first character removed.

Exercise 32: 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 classes that exist in the chosen programming language, the definition of the function body (and program) mostly relies on expertise in the domain. Later, when we introduce complex forms of data, the design of functions demands deep knowledge of computer science.

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. You may wish to add these constants when you create templates as if they were parameters; after all, they belong to the inventory of things that may contribute to the function definition. Adding global constants to templates, however, can quickly make those templates look messy. In short, keep global constants in mind when you define functions.

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

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

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 the flaws in a program. Sloppy testing quickly leads to functions with hidden problems—the bugs. Buggy functions retard progress on large systems, 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 do many programming systems.

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

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

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

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

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

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

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

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, “the number of pixels from the left margin” is ambiguous. Does this statement measure the distance between the left margin and the left end of the car? Its center point? Or even its right end? While this kind of reflection may seem far-fetched, it becomes highly relevant and on occasion life-critical in some programming domains. We ignore this issue for now and leave it to BSL’s image primitives to make the decision for us.

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

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

(define WHEEL-RADIUS 5)

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

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

The rest of this section demonstrates how to apply the third design step—template creation—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 this is called an eyeball test. In the penultimate subsection, we return to the testing issue in general and the one for images in particular.

Exercise 34: Finish the sample problem and get the program to run. That is, assuming that you have solved the exercise of creating the image of a car, define the constants BACKGROUND and Y-CAR. Then assemble the appropriate big-bang expression. When your program runs to your satisfaction, add a tree to scenery. We 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 35: 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 36: 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.