1 Prologue: How to Program

When you were a small child, your parents probably taught you to count and later to perform simple calculations with your fingers: “1 + 1 is 2”; “1 + 2 is 3”; and so on. Then they would ask “what’s 3 + 2” and you would count off the fingers of one hand. They programmed, and you computed. And in some way, that’s really all there is to programming and computing.

Start DrRacket and choose “Beginning Student Language” from the “How to Design Programs” submenu in the “Language” menu.

You might be thinking that you’re learning Racket because the software application is called DrRacket. Not true. You are learning a series of teaching languages created for this book, starting with BSL. Once you have mastered these languages though, you can quickly learn all kinds of full-fledged programming languages, including Racket but also JavaScript, Perl, Python, Ruby, and other such scripting languages.

Naturally, when DrRacket calculates for you, it uses the rules that you know and love from math. Like you, it can determine the result of an addition only when all the operands are plain numbers. If an operand is a parenthesized operator expression—something that starts with a “(” and an operation—it determines the result of that nested expression first. Unlike you, it never needs to ponder with which expression to calculate first—because this first rule is the only rule there is to it.

In short, to program is to write down comprehensible, arithmetic expressions, and to compute is to determine their value. With DrRacket, it is easy to explore this kind of programming and computing.

1.1 Arithmetic and Arithmetic

If programming were just about numbers and arithmetic, it would be as boring as mathematics.Just kidding: mathematics is a fascinating subject, but you knew that. You won’t need too much of it for now, though if you want to be a really great programmer, you will need to study some. Fortunately, there is much more to programming than numbers: text, truths, images, and more.

You can do more with strings than append them. You can extract pieces from a string; reverse strings; make all letters uppercase (or lowercase) in a string; strip blanks spaces from the left and right; and so on. And best of all, you don’t have to memorize any of that. If you need to know what you can do with strings, look it up in HelpDesk. Use F1 or the drop-down menu on the right to open HelpDesk, look at the manuals for HtDP languages (BSL) and its section on primitives. It lists all the operations in BSL and especially those that work on strings.

true

true

false

Now try these: (>= 10 10), (<= -1 0), and (string=? "design" "tinker"). This last one is totally different again but don’t worry, you can do it.

produces a solid blue square

Now you know that overlay is more like string-append than +, but it does “add” images just like string-append “adds” strings and + adds numbers.

Do yourself a favor and look up the documentation for overlay/xy in HelpDesk. Then experiment with the function, which is also available through the "2htdp/image" teachpack.

Let’s summarize again. To program is to write down an arithmetic expression, but you’re no longer restricted to boring numbers. With BSL, your arithmetic is the arithmetic of numbers, strings, Boolean values, and even images. To compute though still means to determine the value of the expressions(s) except that this value can be a string, a number, a Boolean, or an image.

And now you’re basically ready to write programs that make rockets fly.

1.2 Inputs and Output

The programs you have written so far are pretty boring. You write down an expression or several expressions; you click RUN; you see some results. If you click RUN again, you see the exact same results. As a matter of fact, you can click RUN as often as you want, and the same results show up. In short, your programs really are like calculations on a pocket calculator, except that DrRacket calculates with all kinds of data not just numbers.

That’s good news and bad news. It is good because programming and computing ought to be a natural generalization of using a calculator. It is bad because the purpose of programming is to deal with lots of data and to get lots of different results, with more or less the same calculations. (It should also compute these results quickly, at least faster than we can.) That is, you need to learn more still before you know how to program. No need to worry though: with all your knowledge about arithmetic of numbers, strings, Boolean values, and images, you’re almost ready to write a program that creates movies, not just some silly program for displaying “hello world” somewhere. And that’s what we’re going to do next.

It turns out that making a movie is no more complicated than completing a table of numbers like that. Indeed, it is all about such tables:

x =	1	2	3	4	5	6
y =						?

To be concrete, your teacher should ask you here to draw the sixth image, the seventh, and the 1273rd one because a movie is just a lot of images, some 20 or 30 of them per second. So you need some 1200 to 1800 of them to make one minute’s worth of it.

This second part means you must supply one value—a number—for x to determine a specific value for y. When you do, DrRacket plugs in the value for x into the expression associated with the function. Here the expression is (* x x). Once x is replaced with a value, say 1, DrRacket can compute the result of the expressions, which is also called the output of the function.

Think of the rocket as an object that is like the disk—though more interesting—in the above table from your mathematics class.

All that’s needed now is to produce lots of these scenes easily and to display all of them in rapid order.

Here is what you learned in this section. Functions are useful because they can process lots of data in a short time. You can launch a function by hand on a few select inputs to ensure it produces the proper outputs. This is called testing a function. Or, DrRacket can launch a function on lots of inputs with the help of some libraries; when you do that, you are running the function. Naturally, DrRacket can launch functions when you press a key on your keyboard or when you manipulate the mouse of your computer. To find out how, keep reading. Whatever triggers a function application isn’t important, but do keep in mind that (simple) programs are just functions.

1.3 Many Ways to Compute

When you run the create-rocket-scene program from the preceding section, the rocket eventually disappears in the ground. That’s plain silly. Rockets in old science fiction movies don’t sink into the ground; they gracefully land on their bottoms, and the movie should end right there.

This idea suggests that computations should proceed differently, depending on the situation. In our example, the create-rocket-scene program should work “as is” while the rocket is in-flight. When the rocket’s bottom touches the bottom of the screen, however, it should stop the rocket from descending any further.

Open a new tab in DrRacket and start with a clean slate.

(define (create-rocket-scene.v2 height)

(cond

[(<= height 100)

(place-image  50 height (empty-scene 100 100))]

[(> height 100)

(place-image  50 100 (empty-scene 100 100))]))

Figure 1: Landing a rocket (version 2)

With this knowledge, you can now change the course of the simulation. The goal is to not let the rocket descend below the ground level of a 100 by 100 scene. Since the create-rocket-scene function consumes the height at which it is to place the rocket in the scene, a simple test comparing the given height to the maximum height appears to suffice.

Landing the rocket half-way under ground is ugly. Then again, you basically know how to fix this aspect of the program. As you learned from the preceding sections, DrRacket knows an arithmetic of images. Images have a center point and, when place-image adds an image to a scene, it uses this center point as if it were the image. This explains why the rocket is half way under ground at the end: DrRacket thinks of the image as if it were a point, but the image has a real height and a real width. As you may recall, you can measure the height of an image with the operation image-height, which is to images like + is to numbers. This function comes in handy here because you really want to fly the rocket only until it bottom touches the ground.

(define (create-rocket-scene.v3 height)

(cond

[(<= height (- 100 (/ (image-height ) 2)))

(place-image  50 height (empty-scene 100 100))]

[(> height (- 100 (/ (image-height ) 2)))

(place-image  50 (- 100 (/ (image-height ) 2))

(empty-scene 100 100))]))

Figure 2: Landing a rocket (version 3)

When you think and experiment along these lines, you eventually get to the program in figure 2. Given some number, which represents the height of the rocket, it first tests whether the rocket’s bottom is above the ground. If it is, it places the rocket into the scene as before. If it isn’t, it places the rocket’s image so that its bottom touches the ground.

1.4 One Program, Many Definitions

Now imagine this. Your manager at your hot game company doesn’t like flight simulations where rockets that sink halfway into the ground. Worse, all of a sudden, this manager requests a version of the game that uses 200 by 400 scenes. This simple request forces you to replace 100 with 400 in five places in the program, which includes the animate line, and to replace 100 with 200 in three other places. Before you read on, try to do just that so that you get an idea of how difficult it is to execute this request for a five-line program. As you read on, keep in mind that real programs consists of 50,000 or 500,000 or 5,000,000 lines of code.

(define (create-rocket-scene.v4 h)

(cond

[(<= h (- HEIGHT (/ (image-height ) 2)))

(place-image  50 h (empty-scene WIDTH HEIGHT))]

[(> h (- HEIGHT (/ (image-height ) 2)))

(place-image  50 (- HEIGHT (/ (image-height ) 2))

(empty-scene WIDTH HEIGHT))]))

(define WIDTH 100)

(define HEIGHT 100)

Figure 3: Landing a rocket (version 4)

The program in figure 3 consists of three definitions: one function definition and two variable definitions. The number 100 occurs only twice: once as the value of WIDTH and once as the value of HEIGHT. The last line starts the simulation, just as in version 3 of the program. You may also have noticed that it uses h instead of height for the function parameter of create-rocket-scene.v4. Strictly speaking, this change isn’t necessary because DrRacket doesn’t confuse height with HEIGHT but we did it to avoid confusing you.

When DrRacket evaluates (animate create-rocket-scene.v4), it replaces HEIGHT with 100 and WIDTH with 100 every time it encounters these variable names. To experience the joys of real programmers, change the 100 next to HEIGHT into a 400 and click RUN. You see a rocket descending and landing in a 100 by 400 scene. One small change did it all.

plus the replacement of every other occurrence of (- 100 (/ (image-height ) 2)) with ROCKET-CENTER-TO-BOTTOM. You might wonder whether the new definition should be placed above or below the definition for HEIGHT. More generally, you should be wondering whether the ordering of definitions matters. The answer is that for variable definitions, the order matters, and for function definitions it doesn’t. As soon as DrRacket encounters a variable definition, it determines the value of the expression and then associates the name with this value. Thus, for example,

; constants

(define WIDTH  100)

(define HEIGHT 100)

(define MTSCN  (empty-scene WIDTH HEIGHT))

(define ROCKET )

(define ROCKET-CENTER-TO-BOTTOM

(- HEIGHT (/ (image-height ROCKET) 2)))

; programs

(define (create-rocket-scene.v5 h)

(cond

[(<= h ROCKET-CENTER-TO-BOTTOM)

(place-image ROCKET 50 h MTSCN)]

[(> h ROCKET-CENTER-TO-BOTTOM)

(place-image ROCKET 50 ROCKET-CENTER-TO-BOTTOM MTSCN)]))

Figure 4: Landing a rocket (version 5)

You may find it surprising, though, that it doesn’t matter whether you first define the variables in your program or the function(s). Indeed, if your program consisted of more than one function, it wouldn’t matter in which order you defined them. Still, it is good to first introduce all the constants, followed by all the important functions and then the less important ones. We know that because you haven’t yet created a program with more than one function definition yet, this discussion is all theory. You will define and enjoy such programs sooner than you know it, however, and then it all becomes practice.

The program also contains two line comments, introduced with semi-colons (“;”). While DrRacket ignores such comments, people who read programs should not because comments are intended for human readers. It is a “back channel” of communication between the author of the program and all of its future readers to convey information about the program—without making DrRacket do anything about it. Once you do all these things, you get the program in figure 4. It consists of one function definition and five variable definitions. In addition to the computation that determines the distance between the rocket’s center and the bottom of the scene, these variable definitions also factor out (as in “refactor”) the image itself as well as the creation of the empty scene.

Before you read on, ponder the following changes to your program:

1.5 One More Definition

Danger ahead! This section introduces one piece of knowledge from physics. If physics scares you, skip this section on a first reading; programming doesn’t require physics knowledge.

Real rockets don’t descend at a constant speed. Real cars don’t stop on the spot. They decelerate, which is the opposite of accelerate. What this really means is that an object first travels at a constant speed and then the driver hits the breaks or the pilot fires some engines. The effect of using the breaks or firing the engines is to change the speed slowly—decelerate in fancy English.

; properties of the “world”

(define WIDTH  100)

(define HEIGHT 100)

; properties of the descending rocket

(define V 20)

(define DECELERATION 1)

; various other constants

(define MTSCN  (empty-scene WIDTH HEIGHT))

(define ROCKET )

(define ROCKET-CENTER-TO-BOTTOM

(- HEIGHT (/ (image-height ROCKET) 2)))

; programs

(define (create-rocket-scene.v6 t)

(cond

[(<= (distance t) ROCKET-CENTER-TO-BOTTOM)

(place-image ROCKET 50 (distance t) MTSCN)]

[(> (distance t) ROCKET-CENTER-TO-BOTTOM)

(place-image ROCKET 50 ROCKET-CENTER-TO-BOTTOM MTSCN)]))

(define (distance t)

(- (* V t) (* 1/2 DECELERATION (sqr t))))

Figure 5: Landing a rocket (version 6)

In comparison to the previous versions of create-rocket-scene, this final version teaches you that a program may consist of more than one function definition and that one function definition (create-rocket-scene.v6) can refer to other function definitions (distance).

In a way, this revelation shouldn’t surprise you. Even the first version of create-rocket-scene used + and / and other functions. It’s just that you think of those as built into DrRacket. While + and / are indeed an intrinsic part of the programming language, some others are not. For example, most of the “image arithmetic” and a good part of the “string arithmetic” are just function definitions that we created a long time ago and that are added to your definitions area when you click RUN.

As you become a true blue programmer you will find out that programs consist of many function definitions and many variable definitions. You will also see that functions refer to each other all the time. What you really need to practice is to organize such collections of definitions so that you can read them easily even months after completion. After all, you or your manager will want to make changes to these programs, and if you don’t know how to read them and if you didn’t organize them well, you will have a difficult time with even the smallest task. Otherwise you mostly know what there is to know and you can program.

1.6 You are a Programmer Now

The claim that you are a programmer may have come as a surprise to you at the end of the preceding section but it is true. You know all the mechanics that there is to know. You know that programming and computing is about arithmetic of numbers, strings, images, and whatever other data your chosen programming languages supports. You know that programs consist of function and variable definitions. You know, because we have told you, that in the end, it’s all about organizing these definitions properly. Last but not least, you know that DrRacket and the teackpacks support lots of other functions and that DrRacket HelpDesk explains what these functions do.

You might think that you still don’t know enough to write programs that react to keystrokes, mouse clicks, and so on. As it turns out, you do. In addition to the animate function, the "universe" teachpack provide other functions that hook up your programs to the keyboard, the mouse, the clock and other moving parts in your computer. Indeed, it even supports writing programs that connect your computer with anybody else’s computer around the world. So this isn’t really a problem.

From a theoretical perspective, you are missing one piece of the puzzle: the ability to define functions that, when called, compute forever. This may sound useless and difficult to achieve. It is neither. Here is how you define such a program:

(define (run ul)

(run 42))

(run 5)

If you click RUN, you get no result. Actually, you should immediately move the mouse to the STOP button, click, hold the mouse button down, and wait for DrRacket to stop your run-away program.

In short, you have seen almost all the mechanics of putting together programs. If you read up on all the functions that are available, you can write programs that play interesting computer games, run simulations, or keep track of business accounts. The question is whether this really means you are a programmer.

Stop! Think! Don’t turn the page yet.

1.7 Not!

When you look at the “programming” book shelves in any random book store of some unnamed book chain not to speak of certain parts of college book stores, you will see loads of books that promise to turn lead into gold, that is, make you a programmer in 21 days or faster. There are also books by cautious authors who think you need to stretch the same or similar material over the entire course of a semester. If you have worked through the first six sections of this book, however, you know that neither of these approaches can create a solid understanding of programming.

Acquiring the mechanical skills of programming—learning how to write instructions or expressions that the computer understand, getting to know what functions are available in the libraries, and similar activities—aren’t helping you much with real programming. To make such claims is like saying that a 10-year old who knows how to dribble can play on a professional soccer (football) team. It is also like claiming that memorizing 1,000 words from the dictionary and a few rules from a grammar book teaches you a foreign language.

Programming is far more than the mechanics of language acquisition. It is about reading problem statements, extracting the important concepts. It is about figuring out what is really wanted. It is about exploring examples to strengthen your intuitive understanding of the problem. It is about organizing knowledge and it is about knowing what you don’t know yet. It is about filling those last few gaps. It is about making sure that you know how and why your code works, and that you and your readers will do so in the future. In short, it is really about solving problems systematically.

The rest of this book is all about these things; very little of the book’s content is about the mechanics of BSL or other HtDP languages. The book shows you how good computer programmers think about problems, and—promise!—you will even learn to see that these ideas of problem solving apply to other situations in life, e.g., the work of doctors and journalists, lawyers and engineers, or car mechanics and photographers.

Oh, and by the way, the rest of the book uses a tone that is appropriate for a serious text.

What the book is not about: Many early books on programming and even some of today’s books teach you a lot about the authors’ favorite application discipline for programming: mathematics, physics, music, accounting, and so on. To some extent that is natural, because programming is useful in those areas. Then again, it forces you to know a lot (or at least something) about those disciplines. This book really focuses on programming and problem solving and what computer science can teach you in this regard. We have made every attempt to minimize the use of knowledge from other areas; for those few occasions when we went too far, we apologize.