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 DrScheme and choose the Beginning Student Language with the “Language” menu: see the “How to Design Programs” submenu. Now you’re ready.
You should also have noticed a warning about testing. Don’t ignore it forever but just for this Prologue.

People often say the “computer computes for you” but in reality, raw computers do nothing. A raw computer is pretty useless to most people. It is software that really makes computers useful to them and you, it is just difficult to get used to saying “the software computes for you.”
The top-half of DrScheme is called the definitions area. This area is where you create the programs, which is called editing. As soon as you add a word or change something in the definitions area, the SAVE button shows up in the top-left corner. When you click SAVE for the first time, DrScheme asks you for the name of a file, which is a place on your computer (technically, its disk) where DrScheme stores your program for good. Once your definitions area is associated with a file, clicking SAVE just ensures that the content of the definitions area is stored safely in the file.
Programs consists of expressions. For now, programs are expressions.
You have seen expressions in mathematics. For now, an expression is either a plain number or something that starts with a left parenthesis “(” and ends in a matching right parenthesis “)” – which DrScheme rewards by displaying a gray box.
When you click RUN, DrScheme evaluates an expression at a time and displays the result in the interactions area. Then, DrScheme, your faithful servant, awaits your commands at the prompt and you can enter additional expressions though they disappear next time you hit RUN:
> (+ 1 1) 2
Enter your first program at the prompt, hit the “return” or “enter” key on your keyboard, and watch how DrScheme responds with the result. You can do so as often as you wish:
> (+ 2 2) 4
> (* 3 3) 9
> (- 4 2) 2
> (/ 6 2) 3
> (sqr 3) 9
> (expt 2 3) 8
> (sin 0) 0
> (cos pi) #i-1.0
You might be thinking that you’re learning Scheme because the software application is called DrScheme. Not true, however. You are learning a series of teaching languages created for this book, starting with BSL. These teaching languages are to Scheme what American English is to British English. Once you have mastered these languages though, you can quickly learn all kinds of languages and especially PLT Scheme, a power tool with which you can easily create all kinds of interesting programs.
Or you place the cursor next to the operation and hit F1. This action opens DrScheme’s HelpDesk and searches for the documentation of the operation. Use the results concerning the HtDP teaching languages. As you may have noticed by now, this text is also linked to the documentation in HelpDesk.
In short, to program is to write down arithmetic expressions, and to compute is to determine their value. The place to write down expressions is the definitions area. Clicking RUN makes DrScheme compute the values of these expressions, which it then displays in the interactions area.
1.1 Arithmetic and Arithmetic
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.
| (string-append "hello" "world") |
| (string-append "hello " "world") |
| (string-append "hell" "o world") |
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.
| > (+ (string-length "hello world") 20) |
31 |
| > (number->string 42) |
"42" |
| > (string->number "42") |
42 |
| > (string->number "hello world") |
false |
| > (and true true) |
true |
| > (and true false) |
false |
| > (or true false) |
true |
| > (or false false) |
false |
| > (not false) |
true |
true
true
false
Now try these: (>= 10 10), (<= -1 0), and (<= -1 -1).
| (and (or (= (string-length "hello world") (string->number "11")) |
| (string=? "hello world" "good morning")) |
| (>= (+ (string-length "hello world") 60) 80)) |
To work with images such as this rocket, use the Insert menu, select the “Insert image ...” item, and choose your image via the file system browser. Or, if you’re reading this book on-line, copy-and-paste the image from your browser into DrScheme via right-click.
> 
It’s time to add the "universe" teachpack to DrScheme. Use the “Language” drop-down menu, choose “Add Teachpack ...” and then pick "universe". This library provides primitives for manipulating images and for other fun things.
(* (image-width ) |
(image-height )) |
If you are reading the paper version of the book, though, you only see a gray circle and a gray, outlined rectangle.


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 "universe" teachpack.
| (place-image (circle 5 "solid" "green") |
| 50 80 |
| (empty-scene 100 100)) |
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, booleans, 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 DrScheme 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, booleans, 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.
x =
1
2
3
4
5
6
7
8
9
10
y =
1
4
9
16
25
36
49
64
81
?
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.
Yes, write x2 if you want to be fancy.
If you plug in 1, 2, 3, and so on for x, you get 1, 4, 9, and so on for y – just as the table says. For the sequence of images, you could say something like
y = the image that contains a dot x2 pixels below the top.
The key is that these one-liners are not just expressions but functions.
This second part means you must supply one value – a number – for x to determine a specific value for y. When you do, DrScheme 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, DrScheme can compute the result of the expressions, which is also called the output of the function.
... and in mathematics, too. Your teachers just forgot to tell you.
What all this means for you is that functions provide a rather economic way of computing lots of interesting values with a single expression. Indeed, programs are functions, and once you understand functions well, you know almost everything there is about programming. Given their importance, let’s recap what we know about functions so far. First,
(define (FunctionName InputName) BodyExpression)
is a function definition. You recognize it as such, because it starts with the word “define,” a keyword or marker whose sole purpose is to distinguish a definition from expressions. A function definition consists of three pieces: two names and an expression. The first name is the name of the function; you need it to apply the function as often as you wish. The second name – most programmers call it a parameter – represents the input of the function, which is unknown until you apply the function. The expression, dubbed body computes the output of the function for a specific input. Naturally, the expression may consist of many other expressions, as we have seen in the first two sections.
Second,
(FunctionName ArgumentExpression)
is a function application. The first part tells DrScheme which function you wish to use. The second part is the input to which you wish to apply the function. If you were reading a Windows or Mac manual, it might tell you that this expression “launches” the (software) “application” called FunctionName and that it is going to process ArgumentExpression as the input. Like all expressions, the latter is possibly a plain piece of data (number, string, image, boolean) or a complex, deeply nested expression.


Think of the rocket as an object that is like the disk – though more interesting – in the above table from your mathematics class.
(place-image 50 10 (empty-scene 100 100)) |
(place-image 50 20 (empty-scene 100 100)) |
(place-image 50 30 (empty-scene 100 100)) |



All that’s needed now is to produce lots of these scenes easily and to display all of them in rapid order.
| (define (create-rocket-scene height) |
(place-image 50 height (empty-scene 100 100))) |
| (create-rocket-scene 0) |
| (create-rocket-scene 10) |
| (create-rocket-scene 20) |
| (create-rocket-scene 30) |
When you add this expression at the bottom of the definitions area and click RUN, DrScheme evaluates the expression and does not display a result, not even an interactions prompt (for a while). It does open another window (a canvas) and runs a little “movie” that shows the rocket descending from the top of the screen to the bottom where it then disappears.

You should eventually dismiss this extra window, at which point DrScheme displays a number in the interactions area (the height of the rocket at that point).
Yes, the operand is a function here. Don’t worry for now about using functions as operands. Don’t try this on your on, however, unless we ask you to do it or until we explain what this is all about.
animate starts a clock;
the clock “ticks” many times per second; to be precise, the clock ticks 28 times per second, and you could change this if you wanted to;
every time the clock ticks, animate applies the function create-rocket-scene; and
the scene that this application creates is displayed on the screen.
Indeed, DrScheme can also launch functions when you press a key on your keyboard or when you manipulate the mouse. To find out more, read the documentation for the "universe" teachpack or keep reading this book.
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 DrScheme and start with a clean slate.
| (cond |
| [ConditionExpression1 ResultExpression1] |
| [ConditionExpression2 ResultExpression2] |
| .... |
| [ConditionexpressionN ResultExpressionN]) |
This is a good time to explore what the STEP button does for you. Go ahead, click! And when the new window comes up, keep clicking STEP there.
If the evaluation of ConditionExpression1 yields false, DrScheme drops the first line and moves on to the second line, which is treated just like the first one. In case all condition expressions evaluate to false, DrScheme signals an error.
| (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))])) |
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, DrScheme 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: DrScheme 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.
(place-image 50 (- 100 (image-height )) |
| (empty-scene 100 100)) |
(place-image 50 (- 100 (/ (image-height ) 2)) |
| (empty-scene 100 100)) |
| (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))])) |
1.4 One Program, Many Definitions
Neither you nor the computer should repeat such work because it makes your daily life as a programmer difficult. To understand this remark, imagine yourself working for some hot game company implementing this wonderful “War of the Worlds” game program where rockets from some remote planet system attempt to land on your world and you must defend it. So far, so good. You know how to write at least one part of this game. All of a sudden, though, your manager makes your life miserable with the request of making the game run as a 200 by 400 scene. 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) |
| (animate create-rocket-scene.v4) |
This program 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. 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 DrScheme doesn’t confuse height with HEIGHT but we did it to avoid confusing you.
When DrScheme runs the program above, 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.
In modern parlance, you have just experienced your first program refactoring. Every time you re-organize your program to prepare yourself for likely future change requests, you refactor your program. Put it on your resume. It sounds good and your future manager probably enjoys reading such buzzwords.
| (define ROCKET-CENTER-TO-BOTTOM |
(- 100 (/ (image-height ) 2))) |
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 DrScheme 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 DrScheme do anything about it.
| ; 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)])) |
| (animate create-rocket-scene.v5) |
How would you change the program to create a 200 by 400 scene?
How would you change the program so that it depicts the landing of a green UFO (unidentified flying object)? Drawing the UFO per se is easy:
(overlay (circle 10 "solid" "green") (rectangle 40 4 "solid" "green")) How would you change the program so that the background is always blue?
How would change the program so that the rocket lands on a flat rock bed that is 10 pixels higher than the bottom of the scene? Don’t forget to change the scenery, too.
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.
| (define V 20) |
| (define DECELERATION 1) |
| (define (distance t) |
| (- (* V t) (* 1/2 DECELERATION (sqr t)))) |
| (define (create-rocket-scene t) |
| (cond |
| [(<= t ROCKET-CENTER-TO-BOTTOM) |
| (place-image ROCKET 50 t MTSCN)] |
| [(> t ROCKET-CENTER-TO-BOTTOM) |
| (place-image ROCKET 50 ROCKET-CENTER-TO-BOTTOM |
| MTSCN)])) |
Even if you have never taken a physics course, you know that a time is not a distance. So somehow our program worked by a little bit of an accident. Don’t worry, though; it is all easy to fix. Instead of t, we use (distance t), and we add the above definitions to our program.
| ; 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)))) |
| ; run program run |
| (animate create-rocket-scene.v6) |
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 DrScheme. 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 DrScheme and the teackpacks support lots of other functions and that DrScheme 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) (run)) (run) 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 DrScheme 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 things truly work and 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.










