Preface

Everybody engages in problem solving. It is a natural and inevitable part of life.

Historically, the link between problem solving and programming has been less
emphasized. When you write an essay, you are programming—at different levels
many times. You make sure ideas flow and arguments make use of the data you are
analyzing. You write several drafts of the essay. Each draft represents a refinement.
Every paragraph has a point and you avoid repeating yourself. All this is part of
programming, including computer programming. Programmers, people who solve
problems using a computer, go through the exact same steps to write a program.
The same steps are taken by a psychologist analyzing a patient and by a chemist
experimenting in a laboratory. Even a painter engages in programming. No? Does a
painter not want to elicit an outcome or an emotion in you? Indeed, how to achieve
this is a problem that must be solved by the artist. Consider the painting Sorrowing
Old Man (At Eternity’s Gate) by Vincent van Gogh (search for it on the internet).
Can you see the old man’s sorrow? Can you imagine the weight of the years on him?
If so, we can say that the painter successfully solved the problem. This brings us to
another important component of problem solving: testing. It is not only important
to solve a problem. It is equally important to test the solution to make sure it works
and in many cases to make sure that the solution is efficient.
This book is about systematic problem solving or if you like about systematic
reasoning. Unlike most textbooks about programming, this textbook is not about
tinkering with or hacking code. This book is about making a plan to solve a problem
and then implementing the solution. As we shall discover, it turns out that the
solutions to many problems are similar. This should not come as a surprise because
we often solve many problems using similar data. How do you do grocery shopping?
You make a list of items and check them off as you put them in your cart. How do
you manage your chores today? You make a list of chores and check them off as
you get them done. Pretty similar, no? Similarities give rise to abstraction to avoid
repetitions—or reinventing the proverbial wheel. This book, therefore, is also about
abstraction. Thinking abstractly is a powerful tool in problem solving.
In this textbook, all the solutions to problems are expressed as programs. It is
important to be somewhat precise about what a program is. A program is much more
vii
viii Preface

than just code written using a programming language. Remember that a program is
a solution to a problem. Therefore, a program has a design, code, examples of how it
works, and tests. That is, it communicates how the problem is solved and illustrates
that the solution works. If any of the mentioned components are missing, then we
have an incomplete program. Would you believe someone who simply told you that
n2 , where n is a nonnegative integer, is the sum of the first n odd numbers? Many
readers would be skeptical. What if they also provided the following examples:
02 = 0
22 = 1 + 3
42 = 1 + 3 + 5 + 7
It is very likely that most readers would now feel more confident that the claim is
true. It is the same in programming. We cannot simply say that here is a function
that does this or that. We need to explain how the function computes its value, and
we need to have examples that show how it works. The steps taken to design a
program in a systematic manner is called a design recipe. In this textbook, you shall
study many different design recipes. Each design recipe shall become a tool in your
problem-solving toolbox.
There are two problem-solving techniques that are emphasized throughout the
book: divide and conquer and iterative refinement. Divide and conquer is the process
by which a large problem is broken into two or more smaller problems that are easier
to solve and then the solutions for the smaller pieces are combined to create an answer
to the problem. Iterative refinement is the process by which a solution to a problem
is gradually made better—like the drafts of an essay. Mastering these techniques is
essential to becoming a good problem solver and programmer.
Finally, problem solving ought to be fun. To this end, this book promises that by
the end of it you will have designed and implemented a multiplayer video game that
you can play with your friends over the internet. To achieve this, however, there is a
lot about problem solving and programming that you must first learn. The game is
developed using iterative refinement. As we learn about programming, we shall apply
our new knowledge to develop increasingly better versions of the video game. In
fact, every skill you develop for problem solving and program design is transferable
to other (non-programming) domains and to other programming languages.

1 The Languages and the Parts of the Book

The book uses the Racket student languages to write programs. These languages
are chosen for several reasons. The first is that they have an error-messaging system
specifically designed for beginners. This means that unlike common programming
languages the error messages are likely to make sense to beginners. If you do not
understand an error message, do not hesitate to ask your professor or search for
help online. The second is that the syntax is simple and easy to understand. This
is important because the emphasis is always on problem solving and not on how
1 The Languages and the Parts of the Book ix

to correctly write expressions. The third is that the student languages progressively
become richer. At the beginning, you have fewer features at your disposal and,
therefore, the possible errors are fewer. The fourth reason is that the student languages
come with powerful libraries to create graphics, animations, and video games. These
libraries allow students to inject their own personalities in the development of games
and animations. You are strongly encouraged to be creative. Finally, the fifth reason
is that the Racket student languages are likely to put all students on the same playing
field. Most students will be learning the syntax of the programming language together
for the first time.
The book is divided into five parts. Part I focuses on the basics. It starts with
how to write expressions. Once expressions are mastered, the first abstraction lesson
introduces us to functions. In addition, this part introduces you to conditional expres-
sions that allow you to write programs that make decisions. Just this much knowledge
allows us to write interactive programs and puts us on our way to a multiplayer video
game. As you shall discover, decision-making is fundamental to solving problems
that involve information that has many varieties. For example, the whole numbers
may be positive or negative—two varieties—and how a whole number is processed
depends on which variety a given number belongs to. Think about how to compute
the absolute value of a whole number.
Part II introduces you to compound data of finite size. Compound data has multiple
values associated. For example, a point on the Cartesian plane is compound data of
finite size. There are two values: an x coordinate and a y coordinate. Being able to
define compound data of finite size to represent elements in the real or an imaginary
world is a powerful skill to develop.
Part III introduces you to compound data of arbitrary size. This is data that has
multiple values, but the number of values is not fixed. Once again, think about a
grocery list. Sometimes there are no items in the list and at other times there may
be 10, 6, or 17 items in the list. This is where you are introduced to structural
recursion—a powerful data-processing strategy that uses divide and conquer to
process data whose size is not fixed. The types of data that are introduced are lists,
intervals, natural numbers, and binary trees. The knowledge developed is used to
develop a video game that is more challenging for the player.
Part IV delves into abstraction. This section is where we learn how to eliminate
repetitions in our solutions to problems. In fact, we learn how different data can
be processed and different problems can be solved in exactly the same way. You
are introduced to generic programming, which is abstraction over the type of
data processed. This leads to the realization that functions are data and, perhaps
more surprising, that data are functions. In other words, the line between data and
functions is artificial—a fact that is not emphasized enough in Computer Science
textbooks. This realization naturally leads to object-oriented programming—a topic
that you are likely to study extensively.
Part V introduces you to distributed programming—using multiple computers to
solve a problem. This is a topic that until now has never been addressed in a textbook
for beginning programmers. The fact that you develop proficiency in program design
makes it possible for this topic, common in modern computer applications, to be
x Preface

discussed. If you have ever sent a text message or have ever played a game online,
then you have benefitted from and have used a distributed program. It is impossible,
of course, to discuss all the nuances of distributed programming in this textbook.
Nonetheless, you are introduced to a modern trend that is likely to be common
throughout your professional career and beyond.

2 Acknowledgments

This book is the product of over ten years of work at Seton Hall University build-
ing on the shoulders of giants in Computer Science. There are many persons and
groups who deserve credit for informing my work. The Racket community has been
unequivocal in its support for the techniques that I have developed. There is an un-
payable debt of gratitude owed to Matthias Felleisen from Northeastern University
for our discussions over the years about Computer Science education, Liberal Arts
education, and program design. My students and I have greatly benefitted from his
support. Other Racketeers who have deeply influenced me are Shriram Krishna-
murthi, Matthew Flatt, Robert Bruce Findler, and Kathi Fisler. This textbook is a
tribute to our debates and their published work.
I would also like to thank the Trends in Functional Programming (TFP) and
the Trends in Functional Programming in Education (TFPIE) communities. These
communities provided (and continue to provide) a venue to discuss and present
work advancing Computer Science education. I am grateful to many individuals
including Peter Achten, Jurriaan Hage, Pieter Koopman, Simon Thompson, and
Marko van Eekelen. Their insightful feedback has informed much of the material in
this textbook.
Finally, I would like to thank Seton Hall University and its Department of Com-
puter Science for supporting the development of the work presented in this textbook.
In particular, the support of John T. Saccoman, Manfred Minimair, and Daniel Gross
is appreciated. Most of all, I am grateful to all my CS1 students over the past decade
who have informed my Computer Science education efforts. It is likely true that my
students have learned a great deal in my courses, but it is an absolute certainty that
I have learned more from them. They have refined the delivery of every idea found
in this textbook. I am especially grateful to all my undergraduate tutors and teach-
ing assistants, including Shamil Dzhatdoyev, Josie Des Rosiers, Nicholas Olson,
Nicholas Nelson, Lindsey Reams, Craig Pelling, Barbara Mucha, Joshua Schappel,
Sachin Mahashabde, Rositsa Abrasheva, Isabella Felix, and Sena Karsavran. Without
my dedicated students at Seton Hall University and their insight into what students
understood, this textbook would have been impossible.
Contents

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 The Languages and the Parts of the Book . . . . . . . . . . . . . . . . . . . . . viii
2 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x

Part I The Basics of Problem Solving with a Computer

1 The Science of Problem Solving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4 Computing New Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5 Definitions and Interactions Areas Differences . . . . . . . . . . . . . . . . . 11
6 Saving Your Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
7 Error Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
7.1 Grammatical Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
7.2 Type Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
7.3 Runtime Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
8 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 19

2 Expressions and Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

9 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
10 Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
11 Strings and Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
12 Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
13 Booleans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
13.1 Basic Boolean Operators in BSL . . . . . . . . . . . . . . . . . . . . . 32
13.2 Predicates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
14 Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
14.1 Basic Image Constructors . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
14.2 Property Selectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
14.3 Image Composers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

xi
xii Contents

14.4 Empty Scenes and Placing Images . . . . . . . . . . . . . . . . . . . 42

15 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 45

3 The Nature of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

16 The Rise of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
17 General Design Recipe for Functions . . . . . . . . . . . . . . . . . . . . . . . . . 51
17.1 The Design Recipe in Action . . . . . . . . . . . . . . . . . . . . . . . . 53
18 Auxiliary Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
18.1 Bottom-Up Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
19 Top-Down Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
20 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 68

4 Aliens Attack Version 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

21 The Scene for Aliens Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
22 Creating Aliens Attack Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
23 Shot Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
24 Alien Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
25 Rocket Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
25.1 Rocket Window Image Constructor . . . . . . . . . . . . . . . . . . . 82
25.2 Rocket Fuselage Image Constructor . . . . . . . . . . . . . . . . . . 84
25.3 Rocket Single Booster Image Constructor . . . . . . . . . . . . . 85
25.4 Rocket Booster Image Constructor . . . . . . . . . . . . . . . . . . . 87
25.5 Rocket Main Body Image Constructor . . . . . . . . . . . . . . . . 88
25.6 Rocket Nacelle Image Constructor . . . . . . . . . . . . . . . . . . . 90
25.7 Rocket ci Constructor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
26 Drawing Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
27 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 100

5 Making Decisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

28 Conditional Expressions in BSL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
29 Designing Functions to Process Data with Variety . . . . . . . . . . . . . . 104
30 Enumeration Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
31 Interval Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
32 Itemization Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
33 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 125

6 Aliens Attack Version 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

34 The Universe Teachpack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
35 A Video Game Design Recipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
36 Adding the Rocket to Aliens Attack . . . . . . . . . . . . . . . . . . . . . . . . . . 140
37 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 149

Part II Compound Data of Finite Size

Contents xiii

7 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
38 The posn Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
39 Going Beyond the Design Recipe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
40 Revisiting in-Q1? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
41 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 166

8 Defining Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

42 Defining Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
43 Computing Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
44 Structures for the Masses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
45 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 183

9 Aliens Attack Version 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

46 Data Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
47 Function Templates and Sample Instances . . . . . . . . . . . . . . . . . . . . . 187
48 The run Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
49 Drawing the World . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
49.1 The draw-world Refinement . . . . . . . . . . . . . . . . . . . . . . . 191
49.2 Drawing Aliens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
50 The process-key Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
51 Processing Ticks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
51.1 The process-tick Handler . . . . . . . . . . . . . . . . . . . . . . . . 197
51.2 The Design of new-dir-after-tick . . . . . . . . . . . . . . . . 199
51.3 The Design of Auxiliary Functions for
new-dir-after-tick . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
51.4 The Design of move-alien . . . . . . . . . . . . . . . . . . . . . . . . . 206
52 Subtyping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
52.1 Checking Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
53 The game-over? Handler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
54 Computing the Last Scene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
55 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 223

10 Structures and Variety . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225

56 A Bottom-Up Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
57 Code Refactoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
58 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 236

11 Aliens Attack Version 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239

59 Data Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
60 The draw-world Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
61 The process-key Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
62 The process-tick Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
62.1 The Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
62.2 The move-shot Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
63 The game-over? Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
63.1 The hit? Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
xiv Contents

63.2 The draw-last-world Refinement . . . . . . . . . . . . . . . . . . 259

64 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 261

Part III Compound Data of Arbitrary Size

12 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
65 Creating and Accessing Lists in ISL+ . . . . . . . . . . . . . . . . . . . . . . . . 266
66 Shorthand for Building Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
67 Recursive Data Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
68 Generic Data Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
69 Function Templates for Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
70 Designing List-Processing Functions . . . . . . . . . . . . . . . . . . . . . . . . . 277
71 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 279

13 List Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

72 List Summarizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
73 List Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
74 List ORing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288
74.1 Determining If an Alien Is at the Left Edge . . . . . . . . . . . . 288
74.2 Determining If an Alien Is at the Right Edge . . . . . . . . . . . 291
74.3 Determining If an Alien Has Reached Earth . . . . . . . . . . . 292
75 List ANDing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
75.1 All Even in a lon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
75.2 Determining if a lon Is Sorted . . . . . . . . . . . . . . . . . . . . . . 296
76 List Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
76.1 Moving a List of Aliens . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
76.2 Moving a List of Shots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
76.3 Returning a Different List Type . . . . . . . . . . . . . . . . . . . . . . 302
77 List Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
77.1 Extracting Even numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
77.2 Removing Hit Aliens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306
77.3 Removing Shots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
78 List Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314
79 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 318

14 Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

80 Data Definition for a Natural Number . . . . . . . . . . . . . . . . . . . . . . . . 320
81 Computing Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
82 Computing Tetrahedral Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
83 Making Copies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327
84 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 329
Contents xv

15 Interval Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331

85 Interval Data Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
86 Revisiting Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334
87 Creating an Army of Aliens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
88 Largest Prime in an Interval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
89 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 347

16 Aliens Attack Version 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

90 New world Data Definition and Function Template . . . . . . . . . . . . . 349
91 The draw-world Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
92 The process-key Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
93 The process-tick Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
93.1 The new-dir-after-tick Design . . . . . . . . . . . . . . . . . . 361
94 The game-over? Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
94.1 The draw-last-world Refinement . . . . . . . . . . . . . . . . . . 367
95 A Bug Despite Hundreds of Tests Passing . . . . . . . . . . . . . . . . . . . . . 369
96 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 372

17 Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373

97 Binary Tree Data Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
98 Traversing a Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
99 The Maximum of a (btof int) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
100 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382
100.1 A (listof cr) Representation . . . . . . . . . . . . . . . . . . . . . . . . . 383
100.2 A (btof cr) Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 384
100.3 A (bstof cr) Representation . . . . . . . . . . . . . . . . . . . . . . . . . 386
101 Abstract Running Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
102 The Complexity of Searching the Criminal Database . . . . . . . . . . . . 391
103 Balanced (bstof cr) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
103.1 Creating a Balanced Binary Search Tree . . . . . . . . . . . . . . 393
103.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
104 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 398

18 Mutually Recursive Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

105 Designing with Mutually Recursive Data . . . . . . . . . . . . . . . . . . . . . . 403
105.1 Revisiting the Maximum of a (btof int) . . . . . . . . . . . . 403
106 Evaluating Arithmetic Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
107 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
107.1 Creating a Search Tree for Tic Tac Toe . . . . . . . . . . . . . . . . 418
107.2 Can Win Tic Tac Toe? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
108 Project: Tic Tac Toe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426
108.1 Data Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
108.2 Design draw-world . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
108.3 Design process-mouse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
108.4 Design process-tick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
xvi Contents

108.5 Design game-over? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430

109 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 430

19 Processing Multiple Inputs of Arbitrary

Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
110 One Input Has a Dominant Role . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
111 Inputs Must Be Processed Simultaneously . . . . . . . . . . . . . . . . . . . . . 436
112 No Clear Relationship Between the Inputs . . . . . . . . . . . . . . . . . . . . . 438
113 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 442

Part IV Abstraction

20 Functional Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445

114 A Design Recipe for Abstraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
115 Functions as Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
116 Abstraction Over List-Processing Functions . . . . . . . . . . . . . . . . . . . 450
116.1 List Summarizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
116.2 List Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
116.3 List ORing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
116.4 List ANDing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
116.5 List Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
116.6 List Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
116.7 List Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
117 Abstraction over Interval-Processing Functions . . . . . . . . . . . . . . . . 472
118 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 475

21 Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
119 Local-Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
120 Lexical Scoping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
121 Using Local-Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
121.1 Encapsulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
121.2 Readability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
121.3 Furthering Functional Abstraction . . . . . . . . . . . . . . . . . . . . 490
121.4 One-Time Expression Evaluation . . . . . . . . . . . . . . . . . . . . 492
122 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 497

22 Lambda Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499

123 Anonymous Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
124 Revisiting Function Composition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
125 Curried Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
126 Designing Using Existing Abstractions . . . . . . . . . . . . . . . . . . . . . . . 511
126.1 Computing the Value of a Series . . . . . . . . . . . . . . . . . . . . . 511
126.2 Approximating π . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
127 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 516
Contents xvii

23 Aliens Attack Version 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517

128 Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
129 Structure Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
130 Encapsulating and Refactoring Handlers . . . . . . . . . . . . . . . . . . . . . . 522
130.1 The draw-world Handler . . . . . . . . . . . . . . . . . . . . . . . . . . 522
130.2 The process-key Handler . . . . . . . . . . . . . . . . . . . . . . . . . 525
130.3 The process-tick Handler . . . . . . . . . . . . . . . . . . . . . . . . 526
130.4 The game-over? Handler . . . . . . . . . . . . . . . . . . . . . . . . . . 532
130.5 The draw-last-world Handler . . . . . . . . . . . . . . . . . . . . . 533
131 Refactoring run . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534
132 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 535

24 For-Loops and Pattern Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

133 For-Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538
133.1 for-loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 538
133.2 for*-loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542
134 Pattern Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
134.1 Illustrative Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
134.2 Refactoring Using Pattern Matching . . . . . . . . . . . . . . . . . . 549
134.3 Designing Using Pattern Matching . . . . . . . . . . . . . . . . . . . 551
135 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 554

25 Interfaces and Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557

136 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 558
136.1 Improving the Human Interface . . . . . . . . . . . . . . . . . . . . . . 561
136.2 Services that Require More Input . . . . . . . . . . . . . . . . . . . . 561
137 A Design Recipe for Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
138 Interfaces and Union Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566
139 An Abbreviated (listof X) Interface . . . . . . . . . . . . . . . . . . . . . . . . . . 567
139.1 Step 1: Values and Services . . . . . . . . . . . . . . . . . . . . . . . . . 567
139.2 Step 2: Interface and Message Definitions . . . . . . . . . . . . . 568
139.3 Step 3: Class Function Template . . . . . . . . . . . . . . . . . . . . . 568
140 The Empty (listof X) Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
140.1 Step 4: Signature, Purpose, Class Header, and
Message-Passing Function . . . . . . . . . . . . . . . . . . . . . . . . . . 571
140.2 Step 5: Auxiliary Functions . . . . . . . . . . . . . . . . . . . . . . . . . 572
141 The Non-Empty (listof X) Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
141.1 Step 4: Signature, Purpose, Class Header, and
Message-Passing Function . . . . . . . . . . . . . . . . . . . . . . . . . . 573
141.2 Step 5: Auxiliary Functions . . . . . . . . . . . . . . . . . . . . . . . . . 574
142 Step 6: Wrapper Functions and Tests . . . . . . . . . . . . . . . . . . . . . . . . . 575
143 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 579

Part V Distributed Programming

xviii Contents

26 Introduction to Distributed Programming . . . . . . . . . . . . . . . . . . . . . . . . 583

144 A Design Recipe for Distributed Programming . . . . . . . . . . . . . . . . . 585
145 More on the Universe API . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586
146 A Chat Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
146.1 The Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
146.2 Data Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
146.3 Communication Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
146.4 Marshalling and Unmarshalling . . . . . . . . . . . . . . . . . . . . . . 593
146.5 Component Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 593
146.6 Running the Chat Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 600
147 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 601

27 Aliens Attack Version 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603

148 Refining the world Data Definition . . . . . . . . . . . . . . . . . . . . . . . . . . 603
149 The draw-world Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607
150 The process-key Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 610
151 The process-tick Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615
152 The game-over? Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 617
153 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 619

28 Aliens Attack Version 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621

154 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621
155 Data Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622
156 Communication Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623
156.1 Player-Sparked Communication Chains . . . . . . . . . . . . . . . 623
156.2 Server-Sparked Communication Chains . . . . . . . . . . . . . . . 624
156.3 Message Data Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 626
157 Marshalling and Unmarshalling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632
158 Component Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638
158.1 Player Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 638
158.2 Server Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646
159 A Subtle Bug . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
160 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 656

29 Aliens Attack Version 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657

161 The Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657
162 Data Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658
163 Communication Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659
163.1 Player-Sparked Communication Chains . . . . . . . . . . . . . . . 660
163.2 Server-Sparked Communication Chains . . . . . . . . . . . . . . . 661
163.3 Message Data Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 662
164 Marshalling and Unmarshalling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664
165 Component Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
165.1 Player Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666
165.2 Server Component . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 669
Contents xix

166 A Subtle Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683

167 What Have We Learned in This Chapter? . . . . . . . . . . . . . . . . . . . . . 684

Part VI Epilogue

30 Advice for Future Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687

168 Advice for Computer Science Students . . . . . . . . . . . . . . . . . . . . . . . 687
169 Advice for Non-Computer Science Students . . . . . . . . . . . . . . . . . . . 688
 Part I
The Basics of Problem Solving
with a Computer
Chapter 1
The Science of Problem Solving

We all solve problems every day. Have you ever thought about how you go about
problem solving? Do you randomly go about trying potential solutions to a problem
or do you think about how to solve the problem? Most of the time you probably think
about the problem to find a solution. A natural question that arises is how do we think
about a problem to find a solution. In other words, what steps do we take to arrive to
a plausible solution? The solution is plausible until we test it and feel confident that
it works. If it does not work, of course, we go back to thinking about the problem to
obtain a refined solution. Understanding how to think about problems and solutions
is where Computer Science and programming are beneficial to everyone.
Computer Science is not the study of computers just like Chemistry is not the
study of test tubes nor Astronomy is the study of telescopes. So, why is it called
Computer Science? Although there is no clear answer to this question, the best
guess is that Computer Science is an umbrella term for many disciplines whose
primary tool is the computer, such as programming language theory, algorithmics,
software engineering, data mining, robotics, and artificial intelligence. If Computer
Science is not the study of the computer, then what is Computer Science and what do
computer scientists do? Computer scientists solve problems. Unlike biologists who
solve problems in Biology or diplomats who solve problems in Diplomacy, computer
scientists solve problems that are relevant to all fields of study and to all facets of
human life. Stated simply, Computer Science is multidisciplinary. Therefore, the
best way to describe Computer Science is to say that it is the science of problem
solving. Programming is how computer scientists express solutions to problems.
Although Computer Science is a relatively young discipline,1 it has developed many
effective techniques to solve problems. This is why everyone ought to learn to design
programs. Problem solving is an essential skill just like reading, writing, and doing
arithmetic. Your journey through this book will help you learn effective problem
solving techniques.

1
The first Computer Science Program was established in 1953 at the University of Cambridge in
the United Kingdom. The first Computer Science Department in the United States was established
at Purdue University in 1962.
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 3
M. T. Morazán, Animated Problem Solving, Texts in Computer Science,
[Link]
4 1 The Science of Problem Solving

Two of the best-known problem solving techniques are divide and conquer and
iterative refinement. Problem solvers use divide and conquer when a larger problem
is decomposable into smaller problems. Instead of solving an entire problem in one
huge step, the problem is divided into a set of smaller problems. These subproblems
are all solved independently, and then their solutions are combined to formulate the
answer to the large problem. For example, consider computing your quiz average.
You can divide this problem into two smaller problems: sum the quiz grades and
count the number of quizzes. Once these subproblems are solved, the results are
combined by dividing the former by the latter to formulate the quiz average.
Iterative refinement is used to develop a solution in steps. This is particularly
useful to manage the complexity of a problem. Instead of developing a full answer
at once, you solve a simpler version of the problem. Once that is done, you add
complexity to the problem and re-solve it. This process continues until you have
a full answer. For instance, consider the problem of developing a video game like
Pacman. You may first create a game that only has Pacman. Then you create a game
that has Pacman and food. The next version of the game has Pacman, the food, and
one ghost. Finally, the last version of the game has Pacman, the food, and multiple
ghosts.
You have been taught to solve problems most of your life. This means that you have
been taught to compute. For example, you have been taught to compute meaning from
English expressions. You know that Thelma is that pig has a different meaning from
That is Thelma’s pig. Other languages that you have been trained to do computations
with are Arithmetic and Algebra. For example, you know how to compute the value of
the following expression: 5 * (8 + 2). In essence, we use expressions to describe
computations and we evaluate expressions to derive meaning. You may have never
thought explicitly about divide and conquer or about iterative refinement, but you
have been taught to use these techniques. Consider writing an essay. The first step
is to create an outline. This is where you decompose your argument into different
points. Perhaps, every point is implemented as a different section. You combine
the different sections into an essay by making sure that your argument easily flows
from one section to the next. As you can observe, you are using divide and conquer.
Staying with essay development, you first write a rough draft and then repeatedly
make improvements until you are happy with the result. In other words, you are using
iterative refinement.
If we are going to express solutions to problems using a computer, we need to use
a programming language much like we use English to communicate. A programming
language allows us to communicate to the computer what we want it to do. There are
many programming languages. Each has its strengths and weaknesses. You will learn
many programming languages as you explore the world of Computer Science. We
will start with a programming language called Beginning Student Language (BSL).
BSL is a programming language specifically designed to teach beginners like yourself
how to design and implement solutions to problems. A solution to a problem written
in BSL (or any other programming language) is called a program. When a program
is evaluated, we obtain its meaning. That is, we obtain the solution to an instance of
a problem.
3 Getting Started 5

Fig. 1 DrRacket’s language menu

3 Getting Started

In order to write programs, we need a programming development environment.2

A programming development environment is to programs what a text editor is to
essays. Just like you write an essay using a text editor, we write programs using
a programming development environment. There is, however, a major difference
between a programming development environment and a text editor. You can do
more than write programs with a programming development environment. You can
also evaluate programs.
The first step you need to take is to download and install the programming
development environment called DrRacket using the following link:
[Link]
After installing DrRacket, run it and go to the Language menu. Click on Choose
Language... . A pop-up menu will appear and you need to click on Beginning
Student. Figure 1 illustrates what the language menu ought to look like. Click on
OK and then click on the RUN button toward the top right corner of DrRacket.
You are now ready to program! Figure 2 displays DrRacket’s interface (the colors
on your computer may vary). The top half is called the definitions area and the bottom
half is called the interactions area. We type programs in the definitions area and we
interact with our programs in the interactions area. After typing a program in the

2
A programming development environment is commonly called an integrated development envi-
ronment (IDE).
6 1 The Science of Problem Solving

Fig. 2 DrRacket’s interface

definitions area, you may click the RUN button to evaluate your program. Let us try
this out. Type the following string3 in the definitions area:
"Hello World! I am DrRacket."
Now click on RUN. In the interactions window you will see the string printed.
Congratulations! You just wrote your first program. When you clicked on the RUN
button, you told DrRacket to evaluate your program. The value of a string is just
the string itself. Once DrRacket knows the value of a program, it is printed in the
interactions area.

* Ex. 1 — Write and run a program that prints your name.

** Ex. 2 — Write and run a program that prints your age.

** Ex. 3 — Write and run a program that prints your name and your age.

So, what is a program? A program is similar to an essay. In an essay, you express an

argument in favor of or against a point of view. In a program, you express the solution
to a problem. They both have in common the use of expressions. In English, your
expressions are words that may be used to construct larger expressions like sentences
and paragraphs. In programming, your basic expressions are values (for now), like
strings and numbers, that may be used to create larger useful expressions. We will
start by studying expressions and discover how expressions lead us to functions—the
sentences of Algebra and programming.

3
A string is anything inside,"", double quotes.
3 Getting Started 7

Fig. 3 Initial grammar for expressions

expr ::= string
::= number
string::= "<character>*"
number ::= positive
::= negative
positive ::= mag
negative ::= -mag
mag ::= int
::= real
::= fraction
int ::= digit+
digit ::= 0|1|2|3|4|5|6|7|8|9
real ::= digit* .digit+
fraction ::= int/nonzero-int
nonzero-int ::= <1|2|3|4|5|6|7|8|9>int
program ::= expr*

To do so, we need to know how to write valid expressions. That is, we need a
mechanism to describe how to write expressions. We will use a grammar to describe
expressions. A grammar consists of a series of production rules. A production rule
tells a programmer, for example, how to type valid expressions.
Figure 3 displays our initial grammar for expressions. Each production rule con-
sists of three parts. The leftmost part is the syntactic category being defined. If this
is missing, it means that it is the same syntactic category as the production rule
above it. The middle part is always the symbol ::=. The symbol ::= may be read
as is or as may be substituted by. The rightmost part is the definition of the syntactic
category. The first two rules state that an expression, expr, is either a string or a
number. The next rule states that a string starts and ends with ". In between, you
may have 0 or more characters. The * means 0 or more.4 Observe that character
is in a different font and surrounded by < and >. This indicates that it is a syntactic
category we only describe verbally. You may think of a character as anything that is
produced by a keystroke such as letters, spaces, and punctuation marks.5 The next
rule states that a number is either a positive or negative. A positive is a mag
(magnitude) and a negative is a - followed by a mag.
There are three rules for mag. These state that a mag may be an integer, a real, or
a fraction. An int is 1 or more digits (the + means 1 or more and is called Kleene
plus). A digit is an integer in [0..9]. A real is 0 or more digits followed by a .
followed by 1 or more digits. Finally, a fraction is an int followed by a followed
by a nonzero integer. In the grammar, the | means or. Therefore, a nonzero-int is
any digit from 1 to 9 followed by an integer.

4
In a grammar, a * is called Kleene star, named after the American mathematician Stephen Cole
Kleene.
5
Characters inside a computer are represented by an ASCII code. For example, the ASCII code for
a is 97. You will learn more about ASCII codes in a Computer Architecture course.
8 1 The Science of Problem Solving

We are now ready for our initial grammatical definition of a program. The last
rule in Fig. 3 states that a program is 0 or more expressions. Why do we need 0
or more expressions? Given that a program may compute an arbitrary number of
values, a program may have 0 or more expressions.
Let us try to write a new program. To write a new program, open a new tab in
DrRacket by using Ctrl-T. Ctrl-T means pressing the Ctrl and the T keys at the
same time. Now write a program in the definitions area to compute the name of this
textbook, the number one million, and negative 8.7 as follows:
"Program By Design"
1000000
-8.7
The result in the interactions area after clicking RUN is
"Program by Design"
1000000
-8.7

* Ex. 4 — Write and run a program that prints your year of birth and your age.

** Ex. 5 — Write and run a program that prints your favorite color, your lucky
number, and the largest prime number less than 25.

4 Computing New Values

So far, all our programs have computed constant values, that is, values that we wrote
before running the program. In order for programs to be truly useful, we need to
be able to compute new values. That is, we need to be able to combine values to
create new values. Fortunately, BSL provides us with application expressions. An
application expression applies a function to one or more arguments. The function,
in essence, combines its inputs to create a new value and returns this new value.
Therefore, an application expression evaluates to the value returned by the function.
We extend the expr’s production rules in Fig. 3 to include application expressions
as follows:
expr ::= (<function> expr+ )
This production rule states that an application expression starts with an opening
parenthesis, followed by a function (the operator), followed by 1 or more expressions
(the operands), followed by a closing parenthesis. The function and each of its
arguments must be separated from each other by one or more spaces. BSL provides
us with many functions, for example, to combine numbers and to combine strings.
Table 1 lists some of the functions BSL provides along with sample uses.
At this point, you may feel that the syntax notation is a bit awkward. In your
Mathematics textbooks, for example, the basic operations (i.e., +, -, *, and /) are
4 Computing New Values 9

Function Sample application expression Value

+ (+ 1 2 3 4 5) 15
– (– 5 8 2) –5
* (* 39 45 29 2) 101790
/ (/ 20 4 2) 2.5
expt (expt 64 1/2) 8
string-length (string-length "Program By Design") 17
string-append (string-append "Hello " "World") "Hello World"

Table 1: Some numerical and string BSL functions

written using infix notation. This means that the operator is written in the middle
of the operands. For example, the sum of 1, 2, 3, 4, and 5 is written as 1 + 2 +
3 + 4 + 5. A function application, on the other hand, is written operator first and
then in parentheses the operands. For example, applying f to 3 is written as f(3).
In contrast, BSL uses prefix notation. That is, inside parentheses we first write the
operator and then the operands. Observe that the basic operations are functions, and
therefore, BSL treats them no differently than other functions (i.e., they are written
using prefix notation). Thus, the sum of 1, 2, 3, 4, and 5 is written as (+ 1 2 3 4
5) and applying f to 3 is written as (f 3). Always remember that when you want
to apply a function to some arguments, you must put in parentheses the function
first and then the arguments. As you can see, the translation from the syntax used
in Mathematics textbooks to BSL syntax is straightforward. One of the advantages
of BSL syntax is that it may be less typing as is the case for the sum of 1, 2, 3, 4,
and 5. More importantly, however, is that ambiguity cannot arise. For example, in
Mathematics syntax what is the value of 10 + 4 * 5? It depends if you add or you
multiply first. You probably remember operator precedence and believe the correct
value is 30. In BSL, we do not rely on remembering operator precedence. Prefix
notation and the use of parentheses always make it clear what arguments a function
is applied to. If the value of 10 + 4 * 5 is 30, then we write (+ 10 (* 4 5)) in
BSL. Observe that BSL syntax clearly communicates to the readers of our code that
the arguments to * are 4 and 5 and that the arguments to + are 10 and the value of
(* 4 5).
This last example explicitly shows us that application expressions may be nested.
In (+ 10 (* 4 5)), (* 4 5) is nested. There is no limit to the number or the depth
of nested expressions as subtly suggested by the above production rule for application
expressions. Always keep in mind that in an application expression for every opening
parenthesis, there must be a matching closing parenthesis. Furthermore, remember
that a closing parenthesis cannot simply be written anywhere in an application
expression. A closing parenthesis must appear after the last argument to a function.
Otherwise, the meaning of the application expression (i.e., what it evaluates to)
changes. For example, the following two expressions have different meanings:
(* (+ 4 1) 7 (- 15 5)) (* (+ 4 1 7) (- 15 5))
10 1 The Science of Problem Solving

Fig. 4 Accessing DrRacket’s Help Desk

In the first, the last argument to + is 1 and 7 is an argument for *. It evaluates to 25.
In the second, the last argument to + is 7 and 7 is not an argument for *. It evaluates
to 120. As you can see, the meaning of the above expressions is different. Always be
careful about where you close your parentheses.
There is one more thing you may be wondering. Do all functions take as input an
arbitrary number of expressions like + and *? The answer to this is no. It depends
on the function that is being applied. For example, string-length only takes one
input. If you are not sure if a function accepts an arbitrary number of arguments,
you have two options. You can try using it in a program or in the interactions area.
Consider string-append from Table 1. Can we give it more than two arguments?
Let us try it by typing after the prompt, >, in the interactions area the following:
(string-append "Hello" " " "World" "!" " " "I am DrRacket.")
After hitting Enter, the following value is printed:
"Hello World! I am DrRacket."
The answer to our question is that we can give string-append more than two
arguments. Below the output string, you get the DrRacket prompt again. DrRacket
is ready to evaluate another expression for you.
The second option is to consult DrRacket’s Help Desk as illustrated in Fig. 4.
A browser pops up and you can type BSL in the search box. After clicking on BSL,
5 Definitions and Interactions Areas Differences 11

you are taken to the documentation page for the BSL language. On this page a search
for string-append yields
(string-append s t z ...) → string

s : string
t : string
z : string

Concatenates the characters of several strings.

> (string-append "hello" " " "world" " " "good bye")
"hello world good bye"
The . . . means that the function takes as input an arbitrary number of arguments.
The arrow means returns. After the arrow, we find the type of value returned. Further
down, we see the type of each input: all are string type. The types of the inputs and
the type of the output define the signature of the function. It clearly informs anyone
who wishes to use string-append that if they provide strings as input, the function
returns a string as its value. In terms of high school Mathematics, you may think of
the input types as the domain of the function and the return type is the range of the
function. Finally, at the bottom we see a brief description of the function’s purpose
and an example of its use. Whenever you are unsure if BSL has a function or you are
unsure of how to use a BSL function, you may look for it in DrRacket’s Help Desk
to determine if it exists and, if so, the signature tells you the expected inputs and the
expected output.

5 Definitions and Interactions Areas Differences

As you have seen, expressions written in both the definitions and the interactions
areas can be evaluated. In the definitions area you need to click RUN. In the interactions
area you need to hit Enter. So, why are there two areas?
As stated before, the two areas are used for different purposes. In the definitions
area, we write programs. These are solutions to problems that we may save and
run multiple times. In the interactions area, we ask DrRacket to evaluate one-time
expressions, that is, expressions that we are not interested in running multiple times.
The difference may seem subtle, but as you advance through the first few chapters
of this book, the differences will become better delineated.
A good rule of thumb to follow is that if you wish to save the expressions you
write to solve a problem, then you write them in the definitions area. If you only
want to quickly have DrRacket evaluate an expressions for you, then write it in the
interactions window.
12 1 The Science of Problem Solving

Fig. 5 Saving your work

6 Saving Your Work

It is an unfortunate fact that computers may crash. When this happens your unsaved
work is likely to be lost. Therefore, it is important that you regularly save your work.
It is a good idea for you to create a directory for the programs you will develop as
you read this book. You may even want to create subdirectories for each chapter.
This is an effective way to keep your files organized.
To save your work go the File menu. If it is the first time saving your cur-
rent program, click on Save Definitions As... as illustrated in Fig. 5. After
this, find the directory you wish to save your work in and enter a filename. If you
choose the filename Exercise-2-Chapter-4, your work is saved in a file named
[Link]. The .rkt extension is automatically added to indi-
cate that it is a Racket file. In reality, it is a BSL file, but it is saved as a Racket
file given that BSL is a subset of Racket. If it is not the first time saving the current
program, click on Save Definitions inside the File menu. Alternatively, you
may simply use Ctrl+S.

7 Error Messages

Errors are part of the problem solving process and even the most experienced problem
solvers write programs with errors in them. Do not panic when you get an error
message. Remember the famous saying errāre hūmānum est (to err is human6). The
error message is DrRacket’s attempt to help you diagnose the error.

6
The complete saying, coined by Alexander Pope in his Essay on Criticism, is to err is human; to
forgive, divine.
7 Error Messages 13

An important lesson to absorb is that error messages help us diagnose and correct
bugs7 in our programs. An error message itself does not diagnose the bug nor does it
tell us how to fix the bug. That is left to us as program developers, because only the
program developers really know the intended meaning of expressions in a program.
DrRacket approximates where an error occurs, but the programmer must diagnose
and remedy the bug.

7.1 Grammatical Errors

As you now know, essays and programs are both written following the production
rules of a grammar. The English grammar tells you how to write a valid English
expression. Similarly, the BSL grammar tells you how to write valid BSL programs.
When you write a valid BSL program and click on RUN, DrRacket evaluates your
program and prints the answer.
If you fail to write a valid BSL program and click on RUN, DrRacket prints an
error message. When DrRacket detects a grammatical error, an informative error
message is printed in the interactions window. The message details the grammatical
error. For example, type the following in the definitions area:
"Hello World! I am DrRacket.
After clicking RUN, the following error message appears in the interactions window:
read-syntax: expected a closing '"'
The error message states that it was expecting to find a closing double quote. As you
have probably already observed, the opening double quote does not have a matching
closing double quote. Always make sure to read error messages, because they are
usually helpful in determining the cause of errors.
Grammatical errors may also occur writing application expressions. Type the
following program:
(sting-append "I’m done" " " "and going home!")
After clicking RUN, the following error message is displayed:
sting-append: this function is not defined
DrRacket is telling us that it does not know the function sting-append. We can
clearly see that the name of the function is misspelled and we correct it as follows:
(string-append "I’m done" " " "and going home!")

7
The term computer bug stems from a moth found trapped in a computer relay in 1947. The bug was
removed and taped to the log book. The log book along with the moth are part of the Smithsonian
National Museum of American History collection in Washington D.C.
14 1 The Science of Problem Solving

Fig. 6 Grammatical Error

Another common grammatical error is failing to properly write an application

expression with balanced parentheses. For instance, type the following program in
the definitions area to compute (4 * 5) + (50 / 10):
(+ (* 4 5 (/ 50 10))
After clicking RUN, the following error message is displayed:
read-syntax: expected a ‘)‘ to close ‘(‘
DrRacket is informing us that there is a missing closing parenthesis. Observe that in
the definitions window, the opening parenthesis before + is highlighted as displayed
in Fig. 6. DrRacket is letting us know which opening parenthesis it could not match.
If we do not think carefully about the error, we may be tempted to fix the bug by
adding a closing parenthesis at the end as follows:
(+ (* 4 5 (/ 50 10)))
After clicking RUN, the following error message is displayed:
+: expects at least 2 arguments, but found only 1
This is a type error. We will discuss type errors in the next subsection. After some
thought, we realize that we placed the missing closing parenthesis in the wrong place.
DrRacket could not find a closing parenthesis for the first opening parenthesis. The
bug, however, is that the parenthesis before * was not properly closed. We fix the
problem as follows:
(+ (* 4 5) (/ 50 10))
After clicking RUN, the correct value for (4 * 5) + (50 / 10), 25, is printed in
the interactions area.
7 Error Messages 15

Fig. 7 Runtime error

Another common grammatical mistake is to place an expression inside paren-

theses when a function is not applied. This mistake is common among beginners
and it is one you need to be careful about. For instance, consider typing after the
DrRacket’s prompt:
(* (10) (30))
Figure 7 displays the error message after hitting Enter. Observe that 10 is highlighted
in pink. DrRacket is telling us that it did not find a function after the opening
parenthesis for the first operand. Instead, it found 10. 10 is not a function and,
therefore, should not be in the operator position. In fact, 10 is a number and a
number by itself is not written inside parenthesis when it is intended as an argument
to a function.

* Ex. 6 — Type and fix the following buggy expressions:

1.(+ (* 1 2)) 7 (* 5 10))
2.((* 9 6 4))
3.(string-len "Isa and Sena")
4.(sine (/ pi 2))
5.(squareroot (str-length "Yes!"))
16 1 The Science of Problem Solving

7.2 Type Errors

Another kind of error that we may make is called a type error. Type errors mostly
occur in two ways. The first is when the wrong number of arguments are provided
to a function. Let us revisit a program from the previous subsection.
(+ (* 4 5 (/ 50 10)))
After clicking RUN, the following error message is displayed:
+: expects at least 2 arguments, but found only 1
DrRacket is telling us that it believes that we are not correctly using +. We are not
providing the right number of arguments to +. This is a very common mistake done
by beginners and it is important that we keep this in mind as we implement solutions
to problems.
The second is when the wrong type of argument is given to a function. For
example, type the following after the prompt in the interactions area:
(string-append "My lucky number is: " 8)
After clicking RUN, the following error message is displayed:
string-append: expects a string as 2nd argument, given 8
The string-append function expects all its inputs to be strings. In this example,
the second argument is a number. To fix this bug, we must make the second argument
a string as follows:
(string-append "My lucky number is: " "8")
After clicking RUN, the string is printed in the interactions area. It is worth highlight-
ing that "8" is not the same as 8. The former is a string and the latter is a number,
that is, they are different types of data.
Providing a function with the wrong type of input is a very common mistake.
Therefore, type theory is an important and growing discipline within Computer
Science. As we progress through this textbook, we will learn design techniques to
help us avoid type errors. Furthermore, we will learn how to exploit the type of data
being processed to design solutions (and programs) to problems.

* Ex. 7 — Type and fix the following buggy expressions:

1.(string-length 9865)
2.(number->string "7615461")
3.(sqr "20")
4.(add1 (add1 (add1 "7"))))
5.(sub1 (add1 (string->number (string-length "100"))))
6.(string-append ’Animating "Programs" ’Textbook)
7 Error Messages 17

Fig. 8 Runtime error

7.3 Runtime Errors

You need to be aware of a third kind of error called a runtime error. Unlike gram-
matical and type errors, runtime errors are not detected until after an evaluation has
started. For example, type the following program in the definitions area:
(* 5 0)
(+ 5 0)
(/ 5 0)
(- 5 0)
The results after clicking RUN are displayed in Fig. 8. We can observe that the first
two expressions are evaluated and their results are printed. The third expression is
highlighted in pink signalling that an error has been detected during its evaluation.
The error message in the interactions window informs us that there has been an
attempt to divide by 0. The fourth expression is highlighted in black signalling that
it has not been evaluated.
Our programs may also contain runtime errors that do not generate an error
message. For example, write the following program to compute f(4), where f(x)
= 2x2 + 10x + 3:8
(+ (* 2 (sqr 4)) (* 10 4) 4)
After clicking RUN, no error message is generated and 76 is printed in the interactions
window. Observe, however, that 76 is not the value of f(4). These are probably the
hardest errors to fix, because no error message is generated. In this example, the bug
is rather easy to spot. The last 4 in the expression is a typo and should be 3.

8
sqr is a BSL function that squares its input. Look it up in the Help Desk!
18 1 The Science of Problem Solving

Fig. 9 Testing in BSL

To help protect ourselves against this type of error, most programming languages,
including BSL, allow programmers to write unit tests. A unit test validates that two
different expressions evaluate to the same value. In order to write unit tests, we need
to expand our grammar as follows:
program ::= {expr | test}∗
test ::= (check-expect expr expr)
Now, a program is 0 or more expressions or tests. The curly braces are used to
delimit the scope of the Kleene star and should not be typed as part of any program.
In BSL, we write a unit test by typing inside parentheses check-expect and two
expressions. The first expression is the one that we wish to test and it provides what is
called the actual value. The second expression provides what is called the expected
value of the first expression.
We can now rewrite our buggy program as follows:
(+ (* 2 (sqr 4)) (* 10 4) 4)

(check-expect (+ (* 2 (sqr 4)) (* 10 4) 4) 75)

Figure 9a displays DrRacket after clicking run. When tests fail, you get a pop-up
window indicating the number of tests evaluated and the number that passed. For
each failed test, the actual and expected values are displayed. In addition, the line
number of the error in your program is reported.9 In Fig. 9a, we see that 1 test was
evaluated and 0 tests passed. The only failed test is at line 3. We correct our program
as follows:
(+ (* 2 (sqr 4)) (* 10 4) 3)

(check-expect (+ (* 2 (sqr 4)) (* 10 4) 3) 75)

Figure 9b displays the result after pressing RUN. There is no pop-up window with
failed tests and DrRacket in the interactions area indicates that all tests pass.
It may or may not have bothered you that we had to type the same expression
twice. This may be tolerable when you only need to type one expression twice. Most
programmers, however, would find it extremely annoying and, more importantly,

9
You may configure DrRacket to display line numbers in the View menu.
8 What Have We Learned in This Chapter? 19

Fig. 10 Rectangle of width 3 and height 4

error-prone to have to retype multiple expressions multiple times. Furthermore,

evaluating the same expression multiple times (i.e., once for every time it is typed)
may make programs slower. In the next chapter, we will learn techniques to avoid
the repeated typing of the same expression to write tests.

** Ex. 8 — Fix the runtime errors in the following program:

"I have square with a perimeter of 20"
"The length of a side is: "
(/ 20 0)
"The area is:"
(+ 20 20)

(check-expect (* 4 (/ 20 0)) 20)

(check-expect (+ 20 20) (sqr (/ 20 0)))

** Ex. 9 — For a rectangle displayed in Fig. 10, write a program that computes
[Link] rectangle’s area
[Link] rectangle’s perimeter
[Link] rectangle’s diagonal distance from the lower left corner to the top right
corner
Make sure you write unit tests to validate your computed values.

8 What Have We Learned in This Chapter?

The important lessons of Chap. 1 are summarized as follows:

• We write programs using a programming development environment.
20 1 The Science of Problem Solving

Fig. 11 Chapter 1 BSL grammar

program ::= {expr | test}*
test ::= (check-expect expr expr)
expr ::= string
::= number
::= (<function>expr+)
string ::= "<character>*"
number ::= positive
::= negative
positive ::= mag
negative ::= -mag
mag ::= int
::= real
::= fraction
int ::= digit+
digit ::= 0|1|2|3|4|5|6|7|8|9
real::=digit* digit+
fraction ::= int/nonzero-int
nonzero-int ::= <1|2|3|4|5|6|7|8|9> int

• DrRacket is the IDE used in this textbook.

– The definitions area is where programs are written.
– The interactions area is where one-time expressions are evaluated and where
error messages are printed.
– To evaluate a program, click on RUN.
• A programming language is used to write solutions to problems. We call such a
solution a program.
• The syntax of a programming language may be described using a grammar. The
BSL syntax developed so far is displayed in Fig. 11.
– A program is 0 or more expressions.
– An expression can either be a number, a string, or an application expression.
– Strings are written inside double quotes.
– A number is a positive or negative integer, real, or fraction.
– An application expression is used to apply a function to its arguments. In-
side parentheses you first write the function name and then its arguments all
separated by 1 or more spaces.
• Use DrRacket’s Help Desk to determine if a function exists or to learn how to
use a function.
• In order to minimize the danger of loss, frequently save your work.
• Error messages help us determine where a bug occurs but are unable to tell us
how to fix the bug.
• Unit testing helps us find runtime errors by validating that an actual value is the
same as an expected value.
Chapter 2
Expressions and Data Types

You have learned to write expressions using numbers, strings, and applications.
Although this has enabled you to write programs, we need a richer set of data
types to make problem solving easier. This chapter introduces a broader set of data
types that are part of BSL. These are divided into two broad categories: primitive
and compound. A primitive data type is any type of data that is indivisible. For
example, numbers are a primitive data type. A compound data type is one that
contains multiple pieces of data. A piece of compound data can be divided into its
component parts. For example, a coordinate on the two-dimensional Cartesian plane
is compound data. Every coordinate is composed of an x and a y value. The new
data types introduced in this chapter are Boolean, symbol, character, and image. This
chapter also revisits the number and string data types to present them in more detail.
In addition, this chapter introduces how to define constants to avoid having to type
the same expression multiple times in programs.
Consider computing the area and the perimeter of the rectangles in Fig. 12.
Thinking about the problem leads us to conclude that area is computed by multiplying
the width and the length of a rectangle and perimeter is computed by adding the
doubling of the width and the doubling of the length. Based on this analysis, Fig. 13
displays a solution in the form of a program. The first thing you notice is that
comments are used to document a program. Anything after a ; is a comment in
BSL. Specifically, comments are used to document how area and perimeter are
computed. This helps the programmer and anyone else who reads the program to
understand the solution to the problem. Comments are also used to identify the
computation performed for each rectangle. Finally, unit tests are written to make
sure that the computations yield the correct values. Observe that there is one test for
each computation.
The program in Fig. 13 contains many repeated expressions. This is considered
poor programming, because repetitions are boring and lead to errors. Quite frankly,
no one wants to do the same thing over and over again. Therefore, we need a
mechanism to avoid repetitions in our programs. One idea that is promising is to
compute a value once. Instead of (typing and) evaluating each expression multiple

© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 21

M. T. Morazán, Animated Problem Solving, Texts in Computer Science,
[Link]
22 2 Expressions and Data Types

Fig. 12 Three rectangles

(b) Rectangle 2.

(a) Rectangle 1.

(c) Rectangle 3.

4 2

5
2

times, use the value of the expression multiple times. For this we need to learn a
little more BSL syntax to define variables. Variables are used to store the values of
expressions.

9 Definitions

To define and use variables, the BSL syntax is extended as follows:

program ::= {expr | test | def}∗
def ::= (define <variable name> expr)
expr ::= <variable name>
A program consists of 0 or more expressions, tests, and definitions. A definition
starts with an opening parenthesis, followed by the keyword define, followed by a
variable name, followed by an expression, and ends with a closing parenthesis. A
variable name consists of a number of characters without spaces.10 An expression
may be a variable name. This is how variables are used.
A definition binds the variable to the value of the expression. For example, type
the following in the definitions area:
(define DELTA-X 5)

(define i (* 4 25))

10
Some characters are not allowed such as #.
9 Definitions 23

Fig. 13 Version 1 of the area and perimeter program for the rectangles in Fig. 12
;; Area = width * height
;; Perimeter = (2 * width) + (2 * height)

;; Area for rectangle 1

"The area for rectangle 1 is: "
(* 3 4)
(check-expect (* 3 4) 12)

;; Perimeter for rectangle 1

"The perimeter for rectangle 1 is: "
(+ (* 2 3) (* 2 4))
(check-expect (+ (* 2 3) (* 2 4)) 14)

;; Area for rectangle 2

"The area for rectangle 2 is: "
(* 2 5)
(check-expect (* 2 5) 10)

;; Perimeter for rectangle 2

"The perimeter for rectangle 2 is: "
(+ (* 2 2) (* 2 5))
(check-expect (+ (* 2 2) (* 2 5)) 14)

;; Area for rectangle 3

"The area for rectangle 3 is: "
(* 2 2)
(check-expect (* 2 2) 4)

;; Perimeter for rectangle 3

"The perimeter for rectangle 3 is: "
(+ (* 2 2) (* 2 2))
(check-expect (+ (* 2 2) (* 2 2)) 8)

These two definitions bind DELTA-X to 5 and bind i to 100. After clicking RUN, typing
the expression and pressing Enter at the prompt in the interactions area returns 5
and typing the expression i and Enter at the prompt returns 100. Defining variables
is how typing and evaluating the same expression more than once is avoided. They
store the value of an expression allowing programmers to avoid multiple evaluations
of the same expression. Instead, the defined variable is used multiple times.
By convention, two types of variables are distinguished: those whose value may
change and those whose value may not change. The latter are called constants. Both
are defined using the def syntax. The convention in this textbook is to use uppercase
letters for constants and lowercase letters otherwise. In the above example, DELTA-X
is considered a constant and i is not considered a constant. In BSL, there is no such
convention and it is up to the programmers to use this convention.
Armed with the def syntax, the program in Fig. 13 may be rewritten as displayed
in Fig. 14. Observe that for each value computed a constant is defined. Instead of
using generic variable names like x and i, the constants are given names that inform
24 2 Expressions and Data Types

Fig. 14 Version 2 of the area and perimeter program for the rectangles in Fig. 12
;; Area = width * height
;; Perimeter = (2 * width) + (2 * height)

;; Area for rectangle 1

(define AREA1 (* 3 4))

(check-expect AREA1 12)

;; Perimeter for rectangle 1

(define PERIM1 (+ (* 2 3) (* 2 4)))

(check-expect PERIM1 14)

;; Area for rectangle 2

(define AREA2 (* 2 5))

(check-expect AREA2 10)

;; Perimeter for rectangle 2

(define PERIM2 (+ (* 2 2) (* 2 5)))

(check-expect PERIM2 14)

;; Area for rectangle 3

(define AREA3 (* 2 2))

(check-expect AREA3 4)

;; Perimeter for rectangle 3

(define PERIM3 (+ (* 2 2) (* 2 2)))

(check-expect PERIM3 8)

any reader what they represent. This is a good practice and it is a practice that
is followed in this textbook. It is a habit that every programmer is encouraged to
follow. The value of each constant is defined by an expression. Subsequently, the
variable is used to refer to the value of the expression instead of reevaluating the
same expression again. For instance, in the unit tests the constants are used. Observe
also that it is no longer necessary for the program to return each area and perimeter
value, which eliminates the need to clutter the interactions area with printed values.
If a value needs to be examined, type the name of the variable at the prompt and hit
Enter.
Which version of the program is clearer? Most people will argue that the program
in Fig. 14 is clearer. Any interested reader can see what the constants represent.
Furthermore, they can easily see that the tests are there to make sure that the values
of the constants are correct. Admittedly, for this rather small and simple program, it
may not seem significant. Nonetheless, it is important for you to realize now that as
the size of programs grows, it is harder for a programmer (and a reader) to remember
10 Numbers 25

Fig. 15 An error in unit testing using check-expect with real numbers

all the details. Therefore, the goal of a program is twofold. First, a program must
correctly solve a problem. Second, a program must clearly communicate the solution
to the problem. Both of these goals are equally important and you must adhere to
them as responsible problem solvers. It is never acceptable to get the code to work
without documenting the solution to the problem. Think about this carefully. If you
were working on a team programming project, would you trust code that you do not
understand?

10 Numbers

Recall that a number is either an integer, a real, or a fraction. Number is a primitive

type (of data) in BSL. Chapter 1 presented examples of expressions using integers and
how to write unit tests using check-expect. Now, consider writing a program to
compute the circumference of a circle with a radius of 7. Recall that the circumference
of a circle is given by 2πr. Type the following program to solve the problem:
;; The circumference of a circle with radius r is 2 * pi * r

;; The circumference of a circle with radius 7

(define CIRCUM-7 (* 2 pi 7))

(check-expect CIRCUM-7 43.98)

In BSL, pi stores the value of π. Figure 15 displays the failed test message after
clicking RUN. The message is informing us that a real number (called inexact
number in BSL) cannot be checked using check-expect. The reason is that numbers
26 2 Expressions and Data Types

in computer are not exactly the same as numbers in Mathematics. In a computer, a

real number is limited to a finite number, n, of decimal places. Any decimals after
the nth one is discarded. This means that computations using real numbers in BSL
may contain errors. This is why they are called inexact. Examining the value on
CIRCUM-7 at the prompt reveals that it is #i43.982297150257104.
DrRacket is nice enough to print the value prefixed with #i to warn that it
is inexact and, therefore, may contain an error. This problem with real number
computations is common among programming languages. Indicating that a value is
inexact, however, is not common among other programming languages. When the
magnitude of a real number is very small or very large, DrRacket prints it using
scientific notation. For example, #i4.3290784900439874e-010 corresponds to the
inexact number #i4.3290784900439874 x 10-10 .
In order to test computations involving real numbers, the grammar production
rules for test must be expanded as follows:
test ::= (check-within expr expr expr)
As with check-expect, the first two expressions are, respectively, for the value
being tested and the expected value. The third expression defines the error tolerance.
For the test to pass, the actual value must be at most the tolerance away from the
expected value.
The program to compute the circumference of a circle with a radius of 7 is updated
to
;; The circumference of a circle with radius r is 2 * pi * r

;; The circumference of a circle with radius 7

(define CIRCUM-7 (* 2 pi 7))

(check-within CIRCUM-7 43.98 0.01)

The unit test states that the value of CIRCUM-7 may be at most 0.01 away from 43.98
(the expected value). After clicking RUN, the only test passes.
In summary, use check-expect to test integers and fractions and use check-
within to test reals. The example above also demonstrates that bugs do not only
appear in expressions. Bugs may also occur in tests.

* Ex. 10 — In Fig. 14, the expression (* 2 2) appears several times. Rewrite

the program to eliminate its repetition.

** Ex. 11 — A horse riding academy has a rectangular field of 25 meters by

5 meters. They wish to convert it to a horse riding outdoor classroom. In the
middle of the field, they will fence off a 6 meters by 5 meters rectangle for
students to sit and listen to lectures. Write a program to compute the area of
the field left for horse riding. Make sure to write unit tests and document your
solution.
11 Strings and Characters 27

* Ex. 12 — Run the following program:

(define NUM1 #i0.51467e-99)
(define NUM2 #i999999999.42477796076938)
(define NUM3 #i0.8724e-84)

(check-within (* NUM1 NUM2 NUM3) (* NUM3 NUM2 NUM1) 0)

We know from Mathematics courses that multiplication is commutative. Why
does the test fail?

11 Strings and Characters

In Chap. 1, a string is described as anything that is inside double quotes. The word
“anything" suggests that there may be more than one piece of data in a string. In fact,
a string is our first example of a compound data type. Compound data is constructed
using several pieces of data. For example, the string "cat" may be constructed using
the strings: "c", "a", and "t". We build a string by using double quotes. Putting cat
inside double quotes glues together "c", "a", and "t" as a single piece of data. This
is exactly the same as typing (string-append "c" "a" "t"). In other words,
the use of double quotes is simply shorthand for using string-append. Functions
that build compound data, like string-append, are called constructors.
When data is compound, it is possible to access some or all of its components.
Functions that extract a component from an instance of compound data are called
selectors. For strings, we can use the following BSL function to extract substrings:
;; string N [N] → string
;; Purpose: Extract from s the substring starting in
;; position i and ending in position j-1
(substring s i j)
The signature is stating that the function substring requires at least two inputs. The
first is a string and the second is a natural number less than or equal to the length of
s.11 The [] indicates that the third argument is optional. The optional third argument
is a natural number, j, such that 0<=j<=length of s. Think of i and j as defining
the interval [i..j) and substring as extracting the substring from position i to
position j. Not providing the third argument is shorthand for j being the length of the
s. For example, (substring "Wow!" 2) is shorthand for (substring "Wow!"
2 4). Finally, it is important to note that strings’ positions start at 0 (not 1).
The following program illustrates that strings are compound data:

11
A natural number is an integer greater than or equal to 0.
28 2 Expressions and Data Types

(define CAT "cat")

(check-expect CAT (string-append "c" "a" "t"))
(check-expect (substring CAT 0 1) "c")
(check-expect (substring CAT 1 2) "a")
(check-expect (substring CAT 2 3) "t")
(check-expect (substring CAT 3 3) "")
(check-expect (substring CAT 0) CAT)
(check-expect (substring CAT 1) (substring CAT 1 3))
The first test illustrates that "cat" is shorthand for (string-append "c" "a"
"t"). The second, third, and fourth tests, respectively, demonstrate that substrings
of length 1 at the 0th, 1st, and 2nd positions of CAT are "c", "a", and "t". The
fifth test demonstrates that the substring starting at 3 and not including 3 is the empty
string. The sixth test demonstrates that CAT is the same as the substring starting at
0. Finally, the seventh test demonstrates that the substring starting at 1, "at", is the
same as the substring in positions [1..3).
In fact, strings are not really made up of substrings. Every element of a string is a
character (abbreviated as char). Therefore, substring in reality is a function that
converts the selected characters into a string for the programmer. This function was
created to make programming easier.
Expressions may evaluate to characters. Therefore, we need new syntax for char-
acters:
expr ::= \#<character constant>
To denote characters, they are typed by prefixing them with \# followed by a character
constant. For our purposes, a character constant is any single character you can
type using a keyboard. As numbers, characters are primitive data and cannot be
subdivided into components. To actually access the characters of a string, we may
use the following function:
;; string N → char
;; Purpose: Extract the iith char from s
(string-ref s i)
The index i must satisfy 0<=i<=length of s. The following program illustrates the
use of string-ref:
(define DOG "dog")

(check-expect (string-ref DOG 0) \#d)

(check-expect (string-ref DOG 1) \#o)
(check-expect (string-ref DOG 2) \#g)

* Ex. 13 — There are many useful BSL functions to manipulate strings. Be-
come familiar with, for example, string-ith and string-length by looking
them up in DrRacket’s Help Desk. Write a program that appends these 3
11 Strings and Characters 29

string: "Program", "By", and "Design". Include tests to illustrate the follow-
ing:
[Link] appended strings result in "Program By Design".
[Link] length of the appended strings is 17.
3."P" is the substring in positions [0..1].
4.\#P is the first character of the appended strings.
5."By" is the substring in positions [8..10].
[Link] last character of the appended strings is \#n

* Ex. 14 — What happens if we add the following tests to the CAT program
above? Why does each test pass or fail?
(check-expect (substring CAT 3) "")
(check-expect (substring CAT 4) "")
(check-expect (substring CAT 0 3) CAT)
(check-expect (substring CAT 0 4) CAT)
(check-expect (substring CAT -1 1) CAT)
(check-expect (substring CAT 3 1) CAT)

* Ex. 15 — Consider the following program fragment:

(define MARCO "Marco")

(define OCRAM (string-append (substring MARCO . . .)

(substring MARCO . . .)
(substring MARCO . . .)
(substring MARCO . . .)
(substring MARCO . . .)))

(check-expect OCRAM "ocraM")

Complete the program by filling in each . . . with an expression. Make sure the
test passes.

* Ex. 16 — Consider the following program:

(define GREETING1 "hello") ;; lowercase greeting
(define GREETING2 "HELLO") ;; uppercase greeting

(check-expect GREETING1 GREETING2)

The test fails after running the program. Rewrite the test by applying a function
to either GREETING1 or GREETING2. Find a function to change the case of a
string.

* Ex. 17 — Write a program that adds the lengths of "Sena" and "Isa".
30 2 Expressions and Data Types

12 Symbols

Symbols are like strings that are not decomposable. That is, symbol is a primitive
type like number. Symbols are used when we are not interested in manipulating or
accessing the characters as can be done with strings. Symbols require extending the
BSL grammar explored. The following is a new expr production rule for symbols:
expr ::= '<character>+
An expression may be a symbol, which is written as a ' followed by one or more
characters with no spaces.
DrRacket denotes most symbols as a ' followed by the name of the symbol. For
example, entering (string->symbol "Apple") at the prompt returns a symbol
that is printed as 'Apple to the screen. Entering (string->symbol "1024")
returns a symbol, but it is printed differently. Numeric symbols are printed as ',
followed by |, followed by the number, and ending with |. Therefore, the symbol for
"1024" is printed as '|1024|.
Not surprisingly, a symbol is convertible to a string and vice versa. The following
program exemplifies this observation:
;; NAME PROGRAM

(define NAME 'Joshua)

(define NAME2 'Sachin)

(define STR-NAME (symbol->string NAME))

(define STR-NAME2 (symbol->string NAME2))

(check-expect STR-NAME "Joshua")

(check-expect STR-NAME2 "Sachin")

(define JOSH (string->symbol STR-NAME))

(define SACH (string->symbol STR-NAME2))

(check-expect JOSH NAME)

(check-expect SACH NAME2)
In this program two symbols are converted to strings using symbol->string and
then converted back to symbols using string->symbol. Read about these functions
in DrRacket’s Help Desk.
The functions symbol->string and string->symbol are interesting because
they are inverses of each other. Informally, this means that they reverse each other. In
the program above, for example, symbol->string converts 'Josh into "Josh" and
string->symbol converts "Josh" back to 'Josh. More formally, you may recall
from high school Mathematics that two functions are inverses if when composed the
original input is returned. You may recall it from your Mathematics textbook as
(f ◦ g)(x1 ) = x1 = (g ◦ f)(x1 )
13 Booleans 31

Do not panic if you do not remember or recognize function composition and inverses
right now. These will be discussed in more detail later in this book. We mention them
here, because they are important in programming. For example, you may compress
and uncompress your files, encrypt and decrypt your sensitive data, or marshal–
unmarshal your data for computer communication. All of these are achieved by a
pair of functions that are inverses of each other.

** Ex. 18 — Write a program that defines a symbol for your first name and
that computes a symbol that is your first name reversed without the last letter.
Hint: Make a plan for the values that need to be computed to solve this problem.
For example, the program first converts the symbol to a string, then computes a
new string for your reversed name without the last letter, and finally computes
a symbol from that new string.

* Ex. 19 — Explain what happens and why when the following tests are added
to the name program above:
(check-expect NAME STR-NAME)
(check-expect SACH STR-NAME2)

* Ex. 20 — The functions string->number and number->string are in-

verses of each other. Write a program that illustrates this fact.

13 Booleans

Boolean is a primitive type of data. There are only two kinds of Boolean values:
#true and #false. This type of data is important because it allows to perform
computations that depend on whether conditions hold or fail to hold. For example,
in Mathematics you have studied the absolute value function:

x if x ≥ 0
absV alx =
−x otherwise

How do you compute absVal(-100)? You plug in −100 for x, evaluate the condi-
tion, −100 ≥ 0, and determine that it is false. Since this condition is false, the value
of the function is given by −(−100). Evaluating this expression tells you that the
value of absVal(-100) is 100.
Two new expr production rules for Booleans are needed:
expr ::= #true
::= #false
These rules state that a # followed by either true or false represents a Boolean
value in BSL. Nothing else is a Boolean.
32 2 Expressions and Data Types

x y x∧y x∨y ¬x
false false false false true
false true false true true
true false false true false
true true true true false

Table 2: Truth table for the basic Boolean functions

Just like numbers have basic functions (i.e., +, -, *, and /) to create new numbers,
Booleans have the following basic functions: and (also denoted by ∧), or (also
denoted by ∨), and not (also denoted by ¬). A truth table, as the one in Table 2, is
used to illustrate the four basic Boolean functions. From the table, we can infer that
1. and is true when all inputs are true and is false otherwise;
2. or is true when any input is true and is false otherwise;
3. not is true when the input is false and is false otherwise.
The above is a complete description on the basic Boolean functions. It is noteworthy
that it is not always necessary to evaluate all the arguments to and or to or. Consider
the following two expressions:
(and #false (≤ x 20)) (or #true (> i 100))
After evaluating the first argument to and, the other arguments may be ignored,
because the result is known to be false. Similarly, after evaluating the first argument
to or, the other arguments may be ignored, because the result is known to be true.

13.1 Basic Boolean Operators in BSL

BSL takes advantage of the fact that not all arguments to and and or may have to
be evaluated to make them faster. Instead of evaluating all the arguments to and or
or, BSL stops evaluating arguments to and after the first that evaluates to #false.
Similarly, BSL stops evaluating arguments to or after the first that evaluates to #true.
To achieve this, and and or are not functions in BSL. Instead, they are new types
of expressions. The BSL grammar includes the following two production rules for
expr:
expr ::= (and expr expr expr∗ )
::= (or expr expr expr∗ )
These production rules tell us that and and or expect at least two values as input. In
BSL, not is a one-input function.
13 Booleans 33

Fig. 16 Unevaluated expressions in Boolean table validation program

We can now write a program to validate Table 2 as follows:

;; Basic Boolean Functions Validation Program

(define AND-FF (and #false #false))

(define AND-FT (and #false #true))
(define AND-TF (and #true #false))
(define AND-TT (and #true #true))
(define OR-FF (or #false #false))
(define OR-FT (or #false #true))
(define OR-TF (or #true #false))
(define OR-TT (or #true #true))
(define NOT-F (not #false))

(define NOT-T (not #true))

(check-expect AND-FF #false)
(check-expect AND-FT #false)
(check-expect AND-TF #false)
(check-expect AND-TT #true)
(check-expect OR-FF #false)
(check-expect OR-FT #true)
(check-expect OR-TF #true)
(check-expect OR-TT #true)
(check-expect NOT-F #true)
(check-expect NOT-T #false)
34 2 Expressions and Data Types

After running this program, all the tests pass. Observe, as displayed in Fig. 16, that
not all the expressions are evaluated. The expressions that remain unevaluated by
the tests are highlighted in black. These expressions are unevaluated, because their
value is not needed to determine the value of an and or an or expression. In fact,
there is no way to test the unevaluated code. As programmers, this means that, at
best, thorough testing gives us confidence in the program. Testing, however, never
establishes that the program is correct.

** Ex. 21 — Add the following definitions and tests to the basic Boolean func-
tions validation program:
(define AND-FERR (and #false (/ 5 0)))
(define OR-FERR (and #false (string-append "Is this "
"a Boolean?")))

(check-expect AND-FER #false)

(check-expect OR-FERR #true)
What happens with each test? Why?

13.2 Predicates

Functions that return a Boolean are called predicate functions. They are useful to
determine if the input meets some condition. In BSL, built-in types have a predicate to
determine if the input is of that type. These are the predicates for the types presented
in this chapter:
Type Predicate
number number?
string string?
character char?
symbol symbol?
boolean boolean?
image image?
For example, (string? "Hi there!") evaluates to #true and (boolean?
103167) evaluates to #false.
You have used predicates in high school Mathematics. For instance, <, >, ≥, ≤,
and = are all predicates. They are all functions in BSL with the following names: <,
>, >=, <=, and =. These functions all require 1 or more inputs. Typing (< 10) at
the prompt returns #true. Why does this make sense? It turns out that a numerical
predicate returns #true unless one of its input makes it #false. There is nothing
in < 10 that makes it #false, and therefore, this expression evaluates to true.
What does < 10121831 evaluating to #true mean? This is the BSL expression for
10 < 12 < 18 < 31. Remember that BSL expressions use prefix, not infix, notation.
It evaluates to #true, because 10 < 12 ∧ 12 < 18 ∧ 18 < 31 is true.
13 Booleans 35

Strings share an important property with numbers: they are ordinal. This means
that they may be ordered. Strings may be lexicographically ordered (i.e., alphabet-
ically ordered). Therefore, we can ask if one string is less than another or if one
string is greater than or equal to another. We cannot, however, use numerical pred-
icates with strings. The corresponding string predicates are string<?, string>?,
string<=?, string>=?, and string=?. Observe that the ? suggests that a question
is being asked. For example, (string<? "a" "b" "c") is asking if "a" comes
before "b" and "b" comes before "c".
Unlike strings, symbols are not an ordinal type. This means that there are no
functions to compare symbols like > or string<?. There are two predicates to test
symbols. The predicate symbol? tests if its input is a symbol. The predicate eq?
may be used to test if two symbols are equal. In fact, eq? does not exclusively
work with symbols. For example, we can write (eq? 1 1) and (eq? "Alpha
Centauri" "Alpha"). The first evaluates to #true and the second evaluates to
#false. Functions, like eq?, that work for many types of inputs are called generic
functions. We will explore generic functions later in this textbook. For now, we use
=, string=?, and eq?, respectively, to test for numeric, string, and symbol equality.
BSL predicates for Booleans include boolean? and false?. The first tests if its
input is a Boolean. The second tests if its input is #false. You may ask yourself,
why is true? not a predicate in BSL? The answer is that the creators of BSL cannot
possibly implement every conceivable function. Therefore, they must choose what
functions to provide. One criterion that is used to decide is whether or not a value
may be computed using other functions. Can we write expressions to determine if
a variable is #true? To answer this question, we must carefully think about what it
means to be #true. First, the value must be a Boolean. Second, the value must not
be #false. With this insight, we can write an expression to determine if a variable is
true using not, and, and false?. This is a sample program to test our observations:
(define A-STRING "This is not true.")
(define A-SYMBOL 'not-true)
(define A-NUMBER 87)
(define A-BOOL #true)
(define A-BOOL2 #false)

(define IS-TRUE-A-STRING (and (boolean? A-STRING)

(not (false? A-STRING))))
(define IS-TRUE-A-SYMBOL (and (boolean? A-SYMBOL)
(not (false? A-SYMBOL))))
(define IS-TRUE-A-NUMBER (and (boolean? A-NUMBER)
(not (false? A-NUMBER))))
(define IS-TRUE-A-BOOL (and (boolean? A-BOOL)
(not (false? A-BOOL))))
(define IS-TRUE-A-BOOL2 (and (boolean? A-BOOL2)
(not (false? A-BOOL2))))

(check-expect IS-TRUE-A-STRING #false)

(check-expect IS-TRUE-A-SYMBOL #false)
36 2 Expressions and Data Types

(check-expect IS-TRUE-A-NUMBER #false)

(check-expect IS-TRUE-A-BOOL #true)
(check-expect IS-TRUE-A-BOOL2 #false)
Observe that function composition is used to determine if a variable is #true. That
is, the values returned by boolean? and not are inputs to and and the value returned
by false? is input to not. We begin to see that function composition is useful to
design programs.

* Ex. 22 — BSL provides many useful predicates to us. What are the signature
and purpose of the following predicates:
1. odd?
2. even?
3. positive?
4. negative?
5. string-uppercase?
6. string-lowercase?
7. string-numeric?
8. string-alphabetic?
9. string-contains?

* Ex. 23 — Write a program to determine the number of letters in the symbol

'abracadabra.
** Ex. 24 — Logical implication (or simply implies) is important in program
solving. It means that if some condition, ANTECEDENT, is #true, then some
other condition, CONSEQUENT, is #true. Traditionally, implies is denoted by
⇒. This is the truth table for implies:
ANTECEDENT CONSEQUENT ANTECEDENT ⇒ CONSEQUENT
false false true
false true true
true false false
true true true
Write a program to validate the truth table for implies.

*** Ex. 25 — The nand (not and) boolean function has a property called func-
tional completeness. This means that any Boolean expression may be written
only using nand expressions. The truth table for nand is
A B (nand A B)
false false true
false true true
true false true
true true false
The value of nand is given by the expression (not (and A B)). We can
compute (not X) using a nand expression as follows: (not (and X X)).
14 Images 37

Fig. 17 Examples of outline and solid images

 An Outline Rectangle.  A Solid Circle.

Write a program to demonstrate how to compute and and or using only nand
expressions.

* Ex. 26 — Run the following program:

(define NUM1 #i0.51467e-99)

(define NUM2 #i0.8724e-304)

(check-expect (> (* NUM1 NUM2) 0) #true)

Why does the test fail?

14 Images

An image is a visual rectangular type of compound data. Every image consists of

pixels. A pixel is a picture element representing a colored dot. Every image has a
length and a width measured in pixels. In BSL, expressions may evaluate to an image.
This means that we need a new production rule for expr:
expr ::= <image>
Here <image> is a graphic that we either create or copy from elsewhere and paste
it into DrRacket. For images we shall not delve into the manipulation of pixels.
Instead, we shall focus on image manipulation as one whole value.
BSL provides us with a teachpack to create and manipulate images called
2htdp/image. To use the 2htdp/image teachpack, the first line in your program
needs to be:
(require 2htdp/image)
38 2 Expressions and Data Types

This teachpack contains many functions that are split into three broad categories:
Basic Constructors These are functions to create basic images like circles, rectan-
gles, ellipses, stars, and text.
Property Selectors These are functions to extract properties of images such as
width and length.
Image Composers These are functions that combine existing images to create new
images.
It is useful to understand two basic definitions before using the 2htdp/image
teachpack:
mode This refers to how basic geometric shapes are drawn: not filled or filled. Use
'outline or "outline" when an outline of a shape is desired. Use 'solid or
"solid" when a solid shape is desired.
image color This is a string or a symbol representing the desired color. Search for
image-color? in DrRacket’s Help Desk to see the list of predefined colors.
Figure 17 illustrates outline and solid geometric shapes. Figure 17a displays an
outline red rectangle created using the rectangle function. Figure 17b displays a
solid green circle created using the circle function.

14.1 Basic Image Constructors

To illustrate the use of the basic image constructors, consider the program in Fig. 18
to construct the images in Fig. 17. First, constants for the characteristics of the
rectangle and the circle are defined. Next, a constant for each image is defined. The
rectangle is created using the basic constructor rectangle. It requires four inputs: a
width, a height, a mode, and a color. The circle is created using the basic constructor
circle. It requires three inputs: a radius, a mode, and a color. This is followed by
tests. We can write the expected value of a test using a function application or an
image given that both are valid expressions in BSL. The tests that use images require
that the image be created first and then copied and pasted as part of the test.
There are too many basic image constructors to describe them all in this textbook.
Therefore, search for 2htdp/image in the Help Desk to learn about and experiment
with them. Be creative!

14.2 Property Selectors

There are two property selector functions:

image-width Returns the width of an image in pixels.
image-height Returns the height of an image in pixels.
14 Images 39

Fig. 18 Basic constructors in BSL

(require 2htdp/image)

(define RECT-WIDTH 35)

(define RECT-HEIGHT 55)
(define RECT-MODE outline)
(define RECT-COLOR red)

(define CIRC-RADIUS 25)

(define CIRC-MODE solid)
(define CIRC-COLOR green)

(define RED-OUTLINE-RECT (rectangle RECT-WIDTH RECT-HEIGHT

RECT-MODE RECT-COLOR))
(define GREEN-SOLID-CIRCLE (circle CIRC-RADIUS CIRC-MODE CIRC-COLOR))

(check-expect RED-OUTLINE-RECT (rectangle 35 55 outline red))

(check-expect RED-OUTLINE-RECT )
(check-expect GREEN-SOLID-CIRCLE (circle 25 solid green))

(check-expect GREEN-SOLID-CIRCLE )

Consider the problem of computing half the width, half the height, and the number
of pixels for the following images:
(define A-STAR-IMG (radial-star 10 5 35 'outline 'gold))
(define A-RHOMBUS-IMG (rhombus 60 75 'solid 'red))
The first step is to clearly identify what needs to be computed and how it is computed.
We need to compute three values as follows:
Half the Width Divide the image’s width by 2.
Half the Height Divide the image’s height by 2.
Number of Pixels Compute the image’s area.
The next question that arises is how are we to test our computations. We know that
every image is rectangular, but this does not tell us what is the width or the height
of a star image or of a rhombus image. When we do not know what a specific value
ought to be or it is too difficult to write a specific value, we can use property-based
testing to write tests. Instead of testing for the specific value of an expression, we
test properties that the value of the expression ought to have. For our problem, we
40 2 Expressions and Data Types

Fig. 19 Sample program using image selectors and property-based testing

(require 2htdp/image)

(define A-STAR-IMG (radial-star 10 5 35 outline gold))

;; Star computations
(define STAR-W (image-width A-STAR-IMG))
(define STAR-H (image-height A-STAR-IMG))
(define STAR-HALF-W (/ STAR-W 2))
(define STAR-HALF-H (/ STAR-H 2))
(define STAR-PIXELS (* STAR-W STAR-H))

;; Star tests
(check-expect (* 2 STAR-HALF-W) STAR-W)
(check-expect (* 2 STAR-HALF-H) STAR-H)
(check-expect (/ STAR-PIXELS STAR-W) STAR-H)
(check-expect (/ STAR-PIXELS STAR-H) STAR-W)

(define A-RHOMBUS-IMG (rhombus 60 75 solid red))

;; Rhombus computations
(define RHOMBUS-W (image-width A-RHOMBUS-IMG))
(define RHOMBUS-H (image-height A-RHOMBUS-IMG))
(define RHOMBUS-HALF-W (/ RHOMBUS-W 2))
(define RHOMBUS-HALF-H (/ RHOMBUS-H 2))
(define RHOMBUS-PIXELS (* RHOMBUS-W RHOMBUS-H))

;; Rhombus tests
(check-expect (* 2 RHOMBUS-HALF-W) RHOMBUS-W)
(check-expect (* 2 RHOMBUS-HALF-H) RHOMBUS-H)
(check-expect (/ RHOMBUS-PIXELS RHOMBUS-W) RHOMBUS-H)
(check-expect (/ RHOMBUS-PIXELS RHOMBUS-H) RHOMBUS-W)

know that an image is always rectangular. This means that twice half the width ought
to be the width, twice half the height ought to be the height, the number of pixels
divided by the image’s height ought to be the image’s width, and the number of
pixels divided by the image’s width ought to be the image’s height.
Now that we have a game plan, we can proceed to write our program as displayed
in Fig. 19. Observe that related definitions and tests are kept together. First, a data
item is defined like A-RHOMBUS-IMG. Second, the result of computations is defined
like RHOMBUS-HALF-W. Third, tests are written. Organizing code in such a manner
is a good practice because anyone who reads the code (including yourself 6 months
from now) will be able to understand the goals.
14 Images 41

Fig. 20 An image of nested squares

14.3 Image Composers

Image composers are used to create new images from existing images. The image
teachpack provides a myriad of such functions and you ought to experiment with
them as you read the documentation in the Help Desk.
Consider the problem of creating the image in Fig. 20. As always, the first step
is to determine what needs to be computed. The image consists of 6 nested squares.
The largest square is yellow and at the bottom. The smallest square is blue and on
the top. This suggests a divide and conquer strategy. First, compute all the needed
squares. Second, overlay the squares to create the desired image. We can test the
result using property-based testing. A program to implement this strategy is
;; Tests
;; NOTE: SQUARE0 is the largest square.
(check-expect (image-width NESTED-SQS) (image-width SQUARE0))

(check-expect (image-height NESTED-SQS) (image-height SQUARE0))

;; The squares
(define SQUARE0 (square 60 'solid 'yellow)) ;; largest square
(define SQUARE1 (square 50 'solid 'blue))
(define SQUARE2 (square 40 'solid 'yellow))
(define SQUARE3 (square 30 'solid 'blue))
(define SQUARE4 (square 20 'solid 'yellow))
(define SQUARE5 (square 10 'solid 'blue)) ;; smallest square

;; The Nested Squares

(define NESTED-SQS (overlay SQUARE5 SQUARE4 SQUARE3
SQUARE2 SQUARE1 SQUARE0))
The tests check that the dimensions of the resulting image are correct: the dimensions
ought to be the same as the largest square used. The program independently defines
42 2 Expressions and Data Types

the 6 needed squares from largest to smallest. Finally, the needed image is created
by using the function overlay always placing a smaller image over a larger image.
It is natural to wonder how the placing is done. Recall that an image consists of
many pixels. One of these pixels serves as an anchor point around which images
are placed. Unless otherwise specified, image composing functions use the pixel at
the center of the image as the anchor point. This means, for example, that overlay
places all the center points of the images one on top of another. In our program,
the anchor point of SQUARE1 is placed over the anchor point of SQUARE0. Next,
the anchor point of SQUARE2 is placed over the anchor point of the SQUARE1 and
SQUARE0 composed image, and so on until all the squares are overlayed. You may
contrast this behavior with the behavior of the application expression:
(overlay/xy img1 i j img2)
For overlay/xy, the images start aligned with respect to their top-left corner pixel
(not the center pixel). The function overlays img1 over img2 but moves img2 i pixels
to the right and j pixels down. If i is negative, img2 is moved to the left. If y is
negative, img2 is moved up. Experiment with image composers!
Another noteworthy characteristic of our program is that the testing is not very
satisfying. Consider what happens if we mistakenly define NESTED-SQS as follows:
(define NESTED-SQS (overlay SQUARE0 SQUARE1 SQUARE2
SQUARE3 SQUARE4 SQUARE5))
No tests fail when running the program despite that NESTED-SQS is the image of
a yellow square. Clearly, this is not the desired result and this testing shortcoming
ought to be addressed. To remedy such a situation, add unit tests using actual values
that are computed. In this case, first experiment with our program. Once the desired
image is computed, copy and paste it as the expected result for testing NESTED-SQS.
In this manner, any reader of your code can see that both your model and your result
are consistent with expectations. You must be very careful when employing such
a strategy to write tests. If a computed value is wrong, then its use in a test will
make the test pass. Your program, however, still computes the wrong value. It is best
to limit the use of this strategy to test computed images that are easy to visually
validate.

14.4 Empty Scenes and Placing Images

There are two image composing functions that are used extensively to create anima-
tions and video games:
empty-scene Creates an empty image of some given width and height. Option-
ally, the color of the empty image may be provided.
place-image Places the first given image at the given x and y coordinates in the
second given image.
As characters and elements change in a video game, the displayed image must change.
This is done by computing a new image. The empty image is used to create the base
14 Images 43

Fig. 21 Computer graphics coordinate system

0 1 2 3 ...
0
1
2
3
..
.

image of the video game or animation. Think of this base image as the empty canvas
of an artist. The function place-image is used to place elements.
To properly use place-image, a brief description of the computer graphics coor-
dinate system is needed. Figure 21 displays the coordinate system used in computer
graphics. The possible values of x grow from left to right. To place an image further
to the right, the x value is increased. To place an image further to the left the x value
is decreased. The possible values of y grow from top to bottom. To place an image
further down, the y value is increased. To place an image further up, the y value is
decreased. For a given image with dimensions WIDTH x HEIGHT, the valid x values
are in [0..WIDTH-1] and the valid y values are in [0..HEIGHT-1]. If any part of
a placed image falls outside these coordinate ranges, the image is cropped and parts
of the placed image do not appear in the result.
Consider the problem of creating an image with three different alien ships in a
black empty scene. To make the task more manageable, use a divide and conquer
strategy:
• Define the dimensions of the empty scene.
• Compute three different alien ships.
• Compute an image with one alien ship.
• Compute an image with two alien ships.
• Compute an image with three alien ships.
• Write tests.
There are an infinite number of ways a program can be written following this strategy.
Figure 22a displays a proposed partial solution. A black empty scene, 200 x 100,
and 3 different alien ships that differ in color are defined. After this, 3 images are
defined using place-image. Each successive image contains one more ship.
The resulting image with the 3 alien ships is displayed in Fig. 22b. Immediately,
you can see there is a bug in the program. The pink alien ship is cropped and only
part of it appears in the image. This example highlights the value of testing. The
program in Fig. 22a does not contain a test. Although the divide and conquer strategy
is a good one, it is always necessary to perform thorough testing to establish a degree
of confidence in a problem’s solution.
44 2 Expressions and Data Types

Fig. 22 Program for an image with 3 different alien ships in a black empty image
 Program.

(require 2htdp/image)

(define WIDTH 200)

(define HEIGHT 100)

(define E-SCENE (empty-scene WIDTH HEIGHT black))

(define ALIEN-SHIP0 (overlay (circle 7 solid gray)

(rectangle 23 3 solid gray)))

(define ALIEN-SHIP1 (overlay (circle 7 solid pink)

(rectangle 23 3 solid pink)))

(define ALIEN-SHIP2 (overlay (circle 7 solid white)

(rectangle 23 3 solid white)))

(define SCN0 (place-image ALIEN-SHIP0 15 30 E-SCENE))

(define SCN1 (place-image ALIEN-SHIP1 197 80 SCN0))

(define SCN2 (place-image ALIEN-SHIP2 (/ WIDTH 2) (/ HEIGHT 2) SCN1))

 Result Image.

** Ex. 27 — Debug and complete the design of the program in Fig. 22a. Make
sure to test all defined values.
* Ex. 28 — Write a program that creates an image of a banner with your name
on it.
* Ex. 29 — Write a program that creates an image of a triangle that is over an
image of the triangle flipped over the x-axis.

** Ex. 30 — Write a program that creates the image of a smiley face.

15 What Have We Learned in This Chapter? 45

Fig. 23 Sample starry night images

 Starry Night I.

 Starry Night II

*** Ex. 31 — Write a program that creates a starry night image. Your com-
position must have a representation of at least one moon, three stars, and a
stickman. Figure 23aa and 23bb display sample starry night images created by
students. Be creative and have fun!
a
Courtesy of Lindsey M Reams.
b
Courtesy of Shamil Dzhatdoyev.

15 What Have We Learned in This Chapter?

The important lessons of Chap. 2 are summarized as follows:

46 2 Expressions and Data Types

Fig. 24 Chapter 2 BSL grammar

program ::= {expr test def}*
def ::= (define <variable name> expr)
test ::= (check-expect expr expr)
::= (check-within expr expr expr)
expr ::= number string <variable name>
::= \#<character constant>
::= <character+>
::= #true
::= #false
::= <image>
::= (<function> expr+ )
::= (and expr expr expr*)
::= (or expr expr expr*)
string ::= "<character> *"
number ::= positive
::= negative
positive ::= mag
negative ::= -mag
mag ::= int
::= real
::= fraction
int ::= digit+
digit ::= 0|1|2|3|4|5|6|7|8|9
real ::= digit* .digit+
fraction ::= int/nonzero-int
nonzero-int ::= <1|2|3|4|5|6|7|8|9>int

• When solving a problem, outline the values that must be computed to guide the
development of a solution based on divide and conquer.
• In addition to number and string, BSL includes the character, symbol, Boolean,
and image types.
• Primitive type instances, like a Boolean, cannot be decomposed.
• Compound type instances, like a string, can be decomposed.
• The BSL syntax developed so far is displayed in Fig. 24.
– New expressions for characters, symbols, Booleans, and images.
– andand orexpressions are syntax for the Boolean functions and and or.
– not is a Boolean function in BSL.
– | means or. For example, the first production rule for expr states that it can be
a number, a string, or a variable.
• Computations involving numbers and images may contain errors.
• Use check-within to test the computation of a real number.
• Boolean functions are called predicates and allow programmers to determine if
the input satisfies a property.
• Model checking tests properties of a computed value.
• The 2htdp/image teachpack provides functions to create, compose, and extract
properties of images.
Chapter 3
The Nature of Functions

Every high school student has studied functions. What for? Have you ever wondered
where functions come from? Why do they exist? Certainly, many students can state
that a function is a mapping from a domain element to a range element. That,
however, does not tell anyone where functions come from. Perhaps, looking at an
example helps. Consider the following function:
f(x) = x2 + 3x - 10
Certainly, many students can state that x is an input element from the domain and
that the value of f(10) is 120. Now, we know something about functions. We can
use functions to compute values. This is done by "plugging in" 10 for x. That is, all
instances of x are substituted with 10 to obtain
f(10) = 102 + 3·10 - 10
Now, it is all a matter of evaluating function’s body (i.e., the expression to the right of
the equal sign). This is screaming to us that functions are likely to play an important
role in programming. After all, BSL, as well as other programming languages, is
exceptionally good at evaluating expressions. A program in BSL to evaluate f(10)
looks like this:
;; Evaluating f(x) = x^2 + 3x - 10
(define F-X10 (+ (sqr 10) (* 3 10) -10))
(check-expect F-X10 120)
We still, however, do not know where f(x) came from.
This chapter introduces the process of abstraction over expressions that leads to
functions. It also introduces the BSL syntax needed to define functions (like f(x)).
More importantly, it introduces the first design recipe to guide problem solvers in
function development. A design recipe is a series of steps, each with a specific
outcome, that defines a systematic process to implement functions. A design recipe
does not tell you the solution to a problem. That you must figure out. It does, however,
prove useful to take you from a problem statement and a blank IDE to a program that
solves the problem in a manner that is understandable to others.
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 47
M. T. Morazán, Animated Problem Solving, Texts in Computer Science,
[Link]
48 3 The Nature of Functions

Fig. 25 Program for f(x) = x2 + 3x - 10 at x = 10, 0, 1, 20, 100

;; Evaluating f(x) f(x) = x^2 + 3x - 10

(define F-X10 (+ (sqr 10) (* 3 10) -10))

(define F-X0 (+ (sqr 0) (* 3 0) -10))
(define F-X1 (+ (sqr 1) (* 3 1) -10))
(define F-X20 (+ (sqr 20) (* 3 20) -10))
(define F-X100 (+ (sqr 100) (* 3 100) -10))

(check-expect F-X10 120)

(check-expect F-X0 -10)
(check-expect F-X1 -6)
(check-expect F-X20 450)
(check-expect F-X100 10290)

16 The Rise of Functions

Writing a program to compute the value of f(10) has proven rather easy. Now you
are asked to also have your program compute f(0), f(1), f(20), and f(100).
After some thought and a bit of typing, your program looks as displayed in Fig. 25.
A different constant is defined for each value of f(x) obtained from a different value
of x. The tests validate that each value of f(x) has been correctly computed.
Now, you are asked to have your program compute all the values of f(x) for the
integers in [11..19]. This is another 9 different values of x and, frankly speaking,
many are unlikely to want to do a lot of the same typing over and over again. To
avoid this, some may decide to copy, paste, and edit code to account for the changes.
This is dangerous, because it is error-prone. It also means that for a new batch of x
values you will be doing a lot of copying and pasting again. There must be a better
way to get the job done.
Why would anyone decide to cut and paste to write more code? It turns out there
is something interesting about the expressions used to compute the different values
of f(x). Observe that they are almost identical (see Fig. 26). There is only one
difference from one expression to the next: the number plugged in. The elements
that vary among similar expressions are called variables. That is, we can abstract
away the differences among similar expressions by associating each difference with
a variable. For the expressions above, let us call the single difference x (as done in
the mathematical function f(x)). This reduces all the expressions above to a single
expression:
(+ (sqr x) (* 3 x) -10))
In order to exploit such an expression, a mechanism is needed to provide x with a
value.
Let us go back and see how mathematicians provided this mechanism. They chose
the syntax f(x) = e, where e is a mathematical expression. We say that f(x) is
the function header. A function header contains two parts: the name of the function
and the name of the input variables. The input variables are called the function’s
parameters. For f(x), f is the function name and x is the only parameter. We say that
16 The Rise of Functions 49

Fig. 26 Expressions for f(x)

(+ (sqr 10) (* 3 10) -10)
(+ (sqr 0) (* 3 0) -10)
(+ (sqr 1) (* 3 1) -10)
(+ (sqr 20) (* 3 20) -10)
(+ (sqr 100) (* 3 100) -10)

e is the function body. Mathematicians use a mathematical application expression to

bind parameters to values. For example, f(10) binds x to 10. To obtain an expression
that can be evaluated, every parameter is substituted with its binding in the body
of the function. The process of substituting every variable with its binding is called
β-reduction. For f(10), β-reduction substitutes every x with 10 in x2 + 3x - 10
to obtain 102 + 3·10 - 10. Observe that the β-reduction transformation yields an
expression that has no variables and may be evaluated.
BSL allows programmers to write their own functions much like mathematicians
do. To allow programmers to do so, there is a new def production rule:
def ::= (define (<name> <name>+ ) expr)
This production rule states that a function definition is written starting with an
opening parenthesis, the keyword12 define, and inside parenthesis the function
name and the name of 1 or more parameters.13 This is called the BSL function header.
The function header is followed by a BSL expression and a closing parenthesis (to
match the opening parenthesis before define). The expression after the function
header is the body of the BSL function.
Developing a function is not quite enough. It is not reasonable to assume that
anyone will know how to correctly use a function just by looking at it. Any reader
or user of a function needs to know the types of the parameters, the type of the
value returned, and the purpose of the function. In other words, functions need to
be documented with a signature and a purpose statement (just like it is done in
DrRacket’s Help Desk). For our current problem, x’s type is number and the type
returned by the function is number. Therefore, the signature is number → number.
The purpose of the BSL function is to compute the value of f(x).
The program in Fig. 25 can now be updated to compute all the values of f(x)
for the integers in [11..19]. Instead of defining 9 constants for the new function
values, a single BSL function for f(x) is defined and it is used 9 times to compute
the new values. The result of this process is displayed in Fig. 27. Observe that the
new tests use f instead of using a constant for the tested value. Now, the value being
tested is the value returned by f. Further observe that f’s signature and purpose are
written before f’s definition. This helps anyone reading the program to understand
the defined function.
Carefully think about what has been achieved. Ask yourself these questions:
• For the tests, do you prefer to use f or always use defined constants?
• Can this program compute any value of f(x)?
12
A keyword is a word that has a special meaning in a programming language.
13
A name is a symbol written without the '.
50 3 The Nature of Functions

Fig. 27 Program for computing values of f(x) using a BSL function

;; Evaluating f(x) f(x) = x^2 + 3x - 10

(define F-X10 (+ (sqr 10) (* 3 10) -10))

(define F-X0 (+ (sqr 0) (* 3 0) -10))
(define F-X1 (+ (sqr 1) (* 3 1) -10))
(define F-X20 (+ (sqr 20) (* 3 20) -10))
(define F-X100 (+ (sqr 100) (* 3 100) -10))

(check-expect F-X10 120)

(check-expect F-X0 -10)
(check-expect F-X1 -6)
(check-expect F-X20 450)
(check-expect F-X100 10290)
(check-expect (f 11) 144)
(check-expect (f 12) 170)
(check-expect (f 13) 198)
(check-expect (f 14) 228)
(check-expect (f 15) 260)
(check-expect (f 16) 294)
(check-expect (f 17) 330)
(check-expect (f 18) 368)
(check-expect (f 19) 408)

;; number number
;; Purpose: To compute f(x)
(define (f x)
(+ (sqr x) (* 3 x) -10))

• Instead of asking you to modify the program for every value of f(x) needed, can
others use the program to compute these values?
To answer the first question, consider a single test. Most individuals find more
readable and prefer to type
(check-expect (f 11) 144)
over
(check-expect F-X11 144)
(define F-X11 (+ (sqr 11) (* 3 1) -10))
The answer to the second question is yes given enough memory. As a program is
evaluated, memory is allocated to store values. Since memory is finite, it is possible
that a program may be asked to compute a value that requires more memory than
is available. This is something to keep in mind. In practice, however, people around
the world execute programs every day without running out of memory. The answer
to the third question is an unequivocal yes. Anyone running the program only needs
to type the correct application expression at the prompt in the interactions area.
Why were the tests using constants not rewritten to eliminate the need to define
the constants? The answer is that many times it is useful to see how a value is
17 General Design Recipe for Functions 51

Fig. 28 The general design recipe for functions

1. Outline the representation of values and the computation.
2. Define constants for the value of sample expressions.
3. Identify and name the differences among the sample expressions.
4. Write the function’s signature and purpose.
5. Write the function’s header.
6. Write tests.
7. Write the function’s body.
8. Run the tests and, if necessary, redesign.

computed to understand a program. Therefore, you should write both types of tests:
tests that use concrete values (like the last 9 tests) and tests that use defined constants
for expressions that show how a value is computed (like the first 4 tests).

17 General Design Recipe for Functions

Abstraction over expressions led to functions. The question now is how do we

systematically develop functions to solve problems. There are general steps that
ought to be followed to develop every function. Figure 28 presents the steps in the
form of a design recipe. Each step has a specific outcome that guides you to a
problem’s solution.
The first two steps are called problem analysis. Step 1 asks for how values in the
real or an imaginary (like in a video game) world are represented in the program. This
means that we must represent values in the real or imaginary world in a manner that
our programming language can manipulate. Furthermore, this representation must
be invertible. That is, a result must be translatable to the world element it represents.
It is important for the representation to capture the characteristics needed to carry
out the computation. For example, consider the problem of computing the area of
a rectangular field. A field in the real world cannot be processed by a computer.
Therefore, we need a representation of its characteristics that are needed to compute
the area. We can represent the width, length, and area of the field as nonnegative real
numbers. Step 1 also asks for the computation of values to be outlined. Returning to
the area of a rectangular field, we can state that the area is the product of the length
and the width. Step 2 requires the development of sample expressions that illustrate
how the needed value is computed.
Step 3 is the abstraction step. The differences among the sample expressions
must be identified and each is given a unique variable name. These variables are the
parameters of the function. Pick names that identify the value they represent. For
example, if a variable represents a number, then a-number is a better choice than z.
Step 4 requires that the function’s signature be written. To do so, the type of each
parameter and the function’s return type must be written with an arrow between
them. In addition, Step 4 requires a short description of the function’s purpose. This
purpose statement needs to be clear and concise so that others may understand what
52 3 The Nature of Functions

Fig. 29 The basic function template

#|
;; type type
;; Purpose:
(define (f-on-args var)
...)

;; Sample expression definitions for f-on-args

(define CONSTANT-1 expr)
...
(define CONSTANT-N expr)

;; Tests using sample computations for f-on-args

(check-expect (f-on-args expr) CONSTANT-1)
...
(check-expect (f-on-args expr) CONSTANT-N)

;; Tests using sample values for f-on-args

(check-expect (f-on-args expr) value-1)
...
(check-expect (f-on-args expr) value-m)
|#

is computed by the function. The function header is written to satisfy Step 5. Pick a
function name that helps identify the purpose of the function. For example, naming
a cubing function f is a poor choice. A better choice is naming the function cube. In
addition, the parameters from Step 3 must be written in the order that corresponds
to the types in the signature. For Step 6, tests are written using an application of
the function as the tested value and using both the constants from Step 2 and other
values not defined as constants. The body of the function is developed to satisfy
Step 7. β-reduction is performed on any one of the sample expressions. That is, the
differences are substituted with the correct parameter. Finally, Step 8 requires the
running of the tests. If all the tests pass, you may have guarded optimism in having
designed a correct function. If there are any errors, then you need to check your
answers to each step of the design recipe.
The design recipe suggests a function template may be used for function design.
A function template is like a skeleton for functions. It captures the main components
a problem solution needs. Figure 29 displays the basic function template. Every time
a problem is being solved, the template is copied and specialized. When an answer
for a step of the design recipe is formulated, the copied template is edited to reflect
the answer.
17 General Design Recipe for Functions 53

17.1 The Design Recipe in Action

To illustrate the use of the design recipe, consider the problem of creating name
banner images for Craig, Julia (Ohio), Steve, Little Nick, Big Nick, and Jeremy. The
name image should contain only the name in a green 36 size font.
The answers to each step of the design recipe are outlined as follows:
STEP 1
Represent each name as a string. The banner image is computed by applying the
text function to a name, 36, and 'olive.
STEP 2
Three constants for the value of sample expressions are

(define CRAIG (text "Craig" 36 'olive))

(define JULIA (text "Julia (Ohio)" 36 'olive))
(define STEVE (text "Steve" 36 'olive))

STEP 3
The only difference among the three sample expressions is the string representing
the name. The variable for this difference is name.
STEP 4
There is only one difference which is a string and the value computed is an image.
The signature and purpose statement are

;; string → image
;; Purpose: Create a banner for the given name
;; using font 36 and the color olive

STEP 5
The function header contains only one parameter, because a single difference was
identified in Step 3. The name make-banner is suggestive of the purpose of the
function. The function header is
(define (make-banner name)
STEP 6
The tests using the defined constants and sample values are below.

;; Tests using sample computations

(check-expect (make-banner "Craig") CRAIG)
(check-expect (make-banner "Julia (Ohio)") JULIA)
(check-expect (make-banner "Steve") STEVE)
54 3 The Nature of Functions

Fig. 30 Name banners program

(require 2htdp/image)

;; string image
;; Purpose: Create a banner for the give name using
;; font 36 and the color olive
(define (make-banner name)
(text name 36 olive))

; Sample expression definitions for make-banner

(define CRAIG (text "Craig" 36 olive))
(define JULIA (text "Julia (Ohio)" 36 olive))
(define STEVE (text "Steve" 36 olive))

;; Tests using sample computations for make-banner

(check-expect (make-banner "Craig") CRAIG)
(check-expect (make-banner "Julia (Ohio)") JULIA)
(check-expect (make-banner "Steve") STEVE)

;; Tests using sample values for make-banner

(check-expect (make-banner "Little Nick") )

(check-expect (make-banner "Big Nick") )

(check-expect (make-banner "Jeremy") )

;; Tests using sample values

(check-expect (make-banner "Little Nick")

)
(check-expect (make-banner "Big Nick")

)
(check-expect (make-banner "Jeremy")

STEP 7
The body of the function uses name instead of a concrete string:
(text name 36 'olive)
STEP 8
All tests pass.
Figure 30 displays the full program written in BSL inside DrRacket.
18 Auxiliary Functions 55

* Ex. 32 — Follow the steps of the design recipe to write a program to compute
the area of an ellipse.

** Ex. 33 — Follow the steps of the design recipe to write a program to com-
pute the image of a smiley face.

** Ex. 34 — Logical equivalence, denoted A ⇔ B, means that A ⇒ B and

that B ⇒ A. That is, it means that A is true if and only if B is true. The truth
table for logical equivalence is
A B A⇔B
F F T
F T F
T F F
T T F
Follow the steps of the design recipe to write a program to compute the logical
equivalence of two Boolean values.

* Ex. 35 — Follow the steps of the design recipe to write a program to deter-
mine if a string is of even length.

18 Auxiliary Functions

Seldomly, programs only need to compute many instances of a single value as the
program in Fig. 30. It is far more common to have to compute several different values
to solve a problem. A good designer develops a function for each different value.
Such a practice makes it easier for the programmer and for others to understand
the solution to the problem. It also endows programs with modularity. Modularity
enables re-usability of expressions and reduces code duplication. In other words,
modularity is tightly connected to abstraction.
If problem analysis reveals that different kinds of values need to be computed,
consider which values ought to be computed by an auxiliary function. If special
knowledge is required to compute a value or if different instances of the same value
are needed, then designing an auxiliary function is a good choice. On the other hand,
if the expression needed to compute a new value is short, simple, and used only once,
then designing a new function may add little clarity to the solution.
If a programmer determines that several functions are needed, she can follow
two basic strategies: bottom-up or top-down. Bottom-up is a programming style in
which the simplest (usually the smallest) functions are designed first, and then these
functions are used to design more complex functions. Top-down is a programming
style in which the complex functions are designed first, and then simpler functions are
designed. The most commonly used approach is top-down, because a programmer
rarely knows in advance all the simpler functions that are required. Following a top-
down approach allows the programmer to discover, as the design advances, needed
simpler functions.
56 3 The Nature of Functions

Fig. 31 Computing the area of a washer requires two radii

18.1 Bottom-Up Design

To illustrate the bottom-up approach, consider computing the area of a washer as

displayed in Fig. 31. The goal is to compute the area of the green section. This area is
the area difference of the outer circle with radius ro and the inner circle with radius
ri . There are two different values to compute: area and difference. This suggests two
different functions. Given that computing the difference depends on computing the
area, a bottom-up approach starts by designing the area function for circles.
The steps of the design recipe for the area of a circle function may be satisfied as
follows:
STEP 1
The area of a circle is given by the product of π and the square of the circle’s
radius.
STEP 2
Two constants for sample expression values are

(define C-AREA5 (* pi 5))

(define C-AREA18 (* pi 18))

STEP 3
The only difference among the sample expressions is the radius. The variable for
this difference is a-radius.
18 Auxiliary Functions 57

STEP 4
The signature and purpose statement are

;; R>= 0 → R>= 0
;; Purpose: Compute the area of the circle with the given
;; radius.

R>= 0 is any real number greater than or equal to zero.

STEP 5
The function header is
(define (area-circle a-radius)
Observe that the chosen function name suggests the purpose of the function.
STEP 6
The tests using defined constants and sample values are

;; Tests using sample computations

(check-within (area-circle 5) C-AREA5 0.01)
(check-within (area-circle 18) C-AREA18 0.01)

;; Tests using sample values

(check-within (area-circle 0) 0 0.01)
(check-within (area-circle 10) 314.15 0.01)

Observe that the tests include, 0, the lowest possible value for a-radius. It is
always good practice to test border values in the domain of a function.
STEP 7
The body of the function is

(* pi (sqr a-radius))

STEP 8
All tests pass.
With area-circle designed, implemented, and tested, the function for the area
of a washer is designed. The steps of the design recipe may be satisfied as follows:
STEP 1
The area of a washer is given by the area difference of its outer and inner circles.
STEP 2
Three constants for the value of sample expressions are

;; Sample expression definitions for area-washer

(define W-AREA6-3 (- (area-circle 6) (area-circle 3)))
58 3 The Nature of Functions

(define W-AREA15-9 (- (area-circle 15) (area-circle 9)))

(define W-AREA4-1 (- (area-circle 4) (area-circle 1)))

Observe that function composition is used to write the tests. The output of
area-circle is used as input to -. In addition, observe that the constant names
are suggestive of the value they represent.
STEP 3
There are two differences in the sample expressions: the radii of the outer and the
inner circles named, respectively, outer-radius and inner-radius.
STEP 4
The signature and purpose statement are

;; R>= 0 R>= 0 → R>= 0

;; Purpose: Compute the area of the washer with the given
;; radii.
;; ASSUMPTION: outer-radius >= inner-radius

An assumption statement is added to make clear that outer-radius must be greater

than or equal to inner-radius. Such statements help others to correctly use the
function.
STEP 5
The function header is
(define (area-washer outer-radius inner-radius)

The name of the function is suggestive of its purpose. Compare this name choice
with a name like g or area.
STEP 6
The tests using defined constants and sample values are

;; Tests using sample computations for area-washer

(check-within (area-washer 6 3) W-AREA6-3 0.01)
(check-within (area-washer 15 9) W-AREA15-9 0.01)
(check-within (area-washer 4 1) W-AREA4-1 0.01)

;; Tests using sample values for area-washer

(check-within (area-washer 0 0) 0 0.01)
(check-within (area-washer 10 0) 314.15 0.01)
(check-within (area-washer 7 4) 103.67 0.01)
18 Auxiliary Functions 59

Fig. 32 Area of a washer program

;; R > = 0 Real>= 0
;; Purpose: Compute the area of the circle with the given radius.
(define (area-circle a-radius)
(* pi (sqr a-radius)))

;; Sample expression definitions for area-circle

(define C-AREA5 (* pi (sqr 5)))
(define C-AREA18 (* pi (sqr 18)))

;; Tests using sample computations for area-circle

(check-within (area-circle 5) C-AREA5 0.01)
(check-within (area-circle 18) C-AREA18 0.01)

;; Tests using sample values for area-circle

(check-within (area-circle 0) 0 0.01)
(check-within (area-circle 10) 314.15 0.01)

;; R > = 0 R > = 0 Real>= 0

;; Purpose: Compute the area of the washer with the given radii.
;; ASSUMPTION: outer-radius >= inner-radius
(define (area-washer outer-radius inner-radius)
(- (area-circle outer-radius) (area-circle inner-radius)))

;; Sample expression definitions for area-washer

(define W-AREA6-3 (- (area-circle 6) (area-circle 3)))
(define W-AREA15-9 (- (area-circle 15) (area-circle 9)))
(define W-AREA4-1 (- (area-circle 4) (area-circle 1)))

;; Tests using sample computations for area-washer

(check-within (area-washer 6 3) W-AREA6-3 0.01)
(check-within (area-washer 15 9) W-AREA15-9 0.01)
(check-within (area-washer 4 1) W-AREA4-1 0.01)

;; Tests using sample values for area-washer

(check-within (area-washer 0 0) 0 0.01)
(check-within (area-washer 10 0) 314.15 0.01)
(check-within (area-washer 7 4) 103.67 0.01)

STEP 7
The body of the function is
(- (area-circle outer-radius) (area-circle inner-radius))

STEP 8
All tests pass.
The complete program is displayed in Fig. 32. An advantage of bottom-up design
is that functions may be tested as soon as they are implemented. For example, the
area-circle function may be tested as soon as it is written.
60 3 The Nature of Functions

It is possible to design a single function to compute the area of a washer. Such a

function contains repetitions and may look as follows:
;; R>= 0 R>= 0 → R>= 0
;; Purpose: Compute the area of the washer with the given
;; radii.
;; ASSUMPTION: outer-radius >= inner-radius
(define (area-washer outer-radius inner-radius)
(- (* pi (sqr outer-radius)) (* pi (sqr inner-radius))))

;; Sample expression definitions for area-washer

(define W-AREA6-3 (- (* pi (sqr 6)) (* pi (sqr 3))))
(define W-AREA15-9 (- (* pi (sqr 15)) (* pi (sqr 9))))
(define W-AREA4-1 (- (* pi (sqr 4)) (* pi (sqr 1))))

;; Tests using sample computations for area-washer

(check-within (area-washer 6 3) W-AREA6-3 0.01)
(check-within (area-washer 15 9) W-AREA15-9 0.01)
(check-within (area-washer 4 1) W-AREA4-1 0.01)

;; Tests using sample values for area-washer

(check-within (area-washer 0 0) 0 0.01)
(check-within (area-washer 10 0) 314.15 0.01)
(check-within (area-washer 7 4) 103.67 0.01)
This function is obtained by inlining area-circle. Both versions solve the problem.
The question now is which one is clearer? Most people would argue that the version
in Fig. 32 is clearer. In the first version, it is easier to see how the area of a washer
is computed. Even a person who has forgotten the formula for the area of a circle
can discern how the problem is solved. Would that same person as easily discern
how the problem is solved in the second version above? Nonetheless, inlining is an
important optimization done by compilers14 and that you will learn more about in a
Programming Language or a Compilers course.

* Ex. 36 — Use a bottom-up approach following the steps of the design recipe
to write a program to determine if f(a) equals f(b), where f(x) = x2 - 9.

*** Ex. 37 — Use a bottom-up approach, following the steps of the design
recipe, to write a program to implement not, or, and and using only nor (not
or). The truth table for nor is displayed in Fig. 33. For example, (or A B) =
(nor (nor A B) (nor A B)).
* Ex. 38 — Use a bottom-up approach following the steps of the design recipe
to write a program to determine if two strings of length 3 contain a.

14
A compiler is a program that converts programs written in a language like BSL into machine
code that is executable by a computer.
19 Top-Down Design 61

Fig. 33 The truth table for nor

A B (nor A B)
F F T
F T F
T F F
T T F

* Ex. 39 — Use a bottom-up approach following the steps of the design recipe
to design and write a program to compute the flag images of Ghana, Honduras,
Lithuania, Niger, and Syria.

19 Top-Down Design

To illustrate the top-down design process, consider the problem of computing images
like those in Fig. 34. Each image has 4 overlayed squares at a 45◦ angle. Instead of
first trying to figure out how to compute each square in the image composition, start
by writing expressions to compute the image composition. For unknown values,
like the length of a square, use a constant. The definitions of these constants are a
different problem from the problem of creating the desired image. In other words,
use a divide and conquer strategy.
Under this design approach, the steps of the design recipe may be satisfied as
follows:
STEP 1
The image is computed by overlaying squares of alternating colors and differing
lengths. Every other overlayed square, starting with the largest square, is rotated
by 45◦ .
STEP 2
Observe that it is already known that several squares of different colors and lengths
are needed. This immediately suggests that we abstract away the image compu-
tation for squares and design (later) a function for this purpose. Furthermore, we
know that this function requires two arguments (one for each difference): a length
and a color.
Constants for the value of sample expressions may be defined as follows:

(define IMG1 (overlay

(rotate 0 (make-sqr IMG1-LEN4 'brown))
(rotate 45 (make-sqr IMG1-LEN3 'gold))
(rotate 0 (make-sqr IMG1-LEN2 'brown))
(rotate 45 (make-sqr IMG1-LEN1 'gold))))
62 3 The Nature of Functions

Fig. 34 Nested squares at an angle

(define IMG2 (overlay

(rotate 0 (make-sqr IMG2-LEN4 'black))
(rotate 45 (make-sqr IMG2-LEN3 'red))
(rotate 0 (make-sqr IMG2-LEN2 'black))
(rotate 45 (make-sqr IMG2-LEN1 'red))))

Observe that we do not concern ourselves at this point with how make-sqr is
implemented or with how to define the different lengths. We assume that they can
all be defined.
STEP 3
There are 6 differences in the sample expressions: 4 lengths and two colors. We
name the differences: bot-len, len2, len3, top-len, botclr, and topclr.
STEP 4
The signature and purpose statement are

;; R>= 0 R>= 0 R>= 0 R>= 0 color color → image

;; Purpose: Create an image of nested squares at 45
;; degree angles using the given lengths
;; and colors.

STEP 5
The function header is
(define (make-nested-sqs bot-len len2 len3 top-len
botclr topclr)
19 Top-Down Design 63

STEP 6
The tests using defined constants and sample values are

;; Tests using sample computations

(check-expect (make-nested-sqs IMG1-LEN1 IMG1-LEN2
IMG1-LEN3 IMG1-LEN4
'gold 'brown)
IMG1)
(check-expect (make-nested-sqs IMG2-LEN1 IMG2-LEN2
IMG2-LEN3 IMG2-LEN4
'red 'black)
IMG2)

;; Tests using sample values

(check-expect (make-nested-sqs 50 35.35 24.99 17.67 'olive 'yellow)

)
(check-expect (make-nested-sqs 20 14.14 9.99 7.06 'pink 'purple)

STEP 7
The body of the function is

(overlay (rotate 0 (make-sqr top-len topclr))

(rotate 45 (make-sqr len3 botclr))
(rotate 0 (make-sqr len2 topclr))
(rotate 45 (make-sqr bot-len botclr)))

STEP 8
All tests pass.
At this point, we cannot run any tests because make-sqr and the length constants
are undefined. The answer written for Step 8 assumes that the tests pass after all
required functions and constants are defined. If all tests do not pass, then checking
the steps of the design is necessary.
Let us turn our focus now to the design and implementation of make-sqr. We
arrive to this function with some clear ideas about the abstraction. There are two
differences: side length and color. If we were to discover that more values are needed,
64 3 The Nature of Functions

then we have a signal that there is a bug in our abstraction. We proceed assuming
that the function can be designed with the stated differences.
The steps of the design recipe may be satisfied as follows:
STEP 1
The image of a solid square is computed using the square function and the given
side length and color.
STEP 2
Constants for the value of sample expressions may be defined as follows:

(define SQ1 (square 500 'solid 'lightbrown))

(define SQ2 (square 70 'solid 'darkblue))

STEP 3
There are 2 differences in the sample expressions as expected: a length and a
color. We name the differences: side-len and a-color.
STEP 4
The signature and purpose statement are

;; R>= 0 color → image

;; Purpose: Compute the image of a square of the given length and color
degree angles using the given lengths and colors.

STEP 5
The function header is
(define (make-nested-sqs botlen len2 len3 toplen
botclr topclr)

STEP 6
The tests using defined constants and sample values are

;; Tests using sample computations

(check-expect (make-sqr 500 'lightbrown) SQ1)
(check-expect (make-sqr 70 'darkblue) SQ2)

;; Tests using sample values

(check-expect (make-sqr 12 'orange) )

(check-expect (make-sqr 35 'skyblue) )

19 Top-Down Design 65

Fig. 35 The length of the next smaller square is the length of a hypotenuse

STEP 7
The body of the function is

(square side-len 'solid a-color)

STEP 8
All tests pass.
The next task is to define the constants for the lengths. For any image of nested
squares, the length of the largest square is arbitrary. For example, the length of the
largest square can be 100. The length of the next smaller square is not arbitrary as
it depends on the length of the outer square. How do we compute the length of the
next smaller square? The problem must be carefully analyzed. Figure 35 displays the
placement of a smaller square inside a larger square. The length of the outer square
is w. Observe that two adjacent midpoints and the center of the outer square form
a right triangle. The lengths of the sides forming the 90◦ are both w2 . The length of
the inner square is the length of the hypotenuse of the right triangle. We know that
the length of the hypotenuse is given by the Pythagorean theorem:
x2 = ( w2 )2 + ( w2 )2

x = ( w2 )2 + ( w2 )2

= 2 * ( w2 )2

2
= 2 * w4

w2
= 2
66 3 The Nature of Functions

A function can be defined to compute the length of inner squares. The only difference
in computing one inner square length from another is the length of the outer square.
Instead of abstracting over similar expressions, we have developed a mathematical
expression for the length of an inner circle that is easily translated to BSL. Both
approaches to converging on an expression for the body of a function are valid and
ought to be part of any problem solver’s toolbox.
The steps of the design recipe may be satisfied as follows:
STEP 1
The length of the next smallest square is equal to the length of the line between
the two midpoints of two adjacent sides of the
enclosing square of length w. The
2
length of the next smaller square is given by w2 .
STEP 2
Constants for the value of sample expressions may be defined as follows:

(define IMG1-LEN1 100)

(define IMG1-LEN2 (sqrt (/ (sqr IMG1-LEN1) 2)))
(define IMG1-LEN3 (sqrt (/ (sqr IMG1-LEN2) 2)))
(define IMG1-LEN4 (sqrt (/ (sqr IMG1-LEN3) 2)))

STEP 3
There is a single difference in the sample expressions as expected: a length. We
name the difference side-len.
STEP 4
The signature and purpose statement are
;; R>= 0 → R>= 0
;; Purpose: Compute the length of the next smallest square

STEP 5
The function header is
(define (compute-new-sqr-len side-len)

STEP 6
The tests using defined constants and sample values are

;; Tests using sample computations

(check-within (compute-new-sqr-len 100)
IMG1-LEN2
0.01)
(check-within (compute-new-sqr-len IMG1-LEN2)
IMG1-LEN3
0.01)
19 Top-Down Design 67

(check-within (compute-new-sqr-len IMG1-LEN3)

IMG1-LEN4
0.01)

Given that constants for the square lengths for a second image are needed, the
function being designed may be used to compute these. The tests using sample
values based on these constants may be written as follows:
;; Tests using sample values
(define IMG2-LEN1 150)
(define IMG2-LEN2 (compute-new-sqr-len IMG2-LEN1))
(define IMG2-LEN3 (compute-new-sqr-len IMG2-LEN2))
(define IMG2-LEN4 (compute-new-sqr-len IMG2-LEN3))

(check-within IMG2-LEN2 106.06 0.01)

(check-within IMG2-LEN3 75 0.01)
(check-within IMG2-LEN4 53.03 0.01)
(check-within (compute-new-sqr-len 0) 0 0.01)
(check-within (compute-new-sqr-len 8) 5.65 0.01)

STEP 7
The body of the function is

(sqrt (/ (sqr side-len) 2))

STEP 8
All tests pass.
An important point to highlight is when a defined function may be applied in BSL.
A defined function may be applied any time when it is part of a test. All other times,
however, a function must be defined before it is applied to any arguments. That is,
the definition of a function must appear in a program before its first use outside tests.

* Ex. 40 — Implement the nested squares program.

* Ex. 41 — Use a top-down approach following the steps of the design recipe
to write a program to compute the flag images of Armenia, Austria, Bulgaria,
Colombia, and Estonia.

* Ex. 42 — Use a top-down approach following the steps of the design recipe to
write a program to compute f(x) = 4(x3 - 1)3 - 6(x3 -1)2 + 2(x3 -1)
+ 8.
68 3 The Nature of Functions

* Ex. 43 — Use a top-down approach following the steps of the design recipe
to write a program to append two double copies of a string separated by a space.
For example, "abc" results in "abcabc abcabc".

*** Ex. 44 — Use a top-down approach following the steps of the design recipe
to write a program to compute ((a ⇒ b) ∧ (b ⇒ c)) ⇒ (a ⇒ c). i
⇒ j is ¬i ∨ j.

20 What Have We Learned in This Chapter?

The important lessons of Chap. 3 are summarized as follows:

• Functions are abstractions over similar expressions.
– Each difference becomes a function parameter.
– In the body each difference is replaced with the corresponding parameter.
– Functions add modularity and help avoid repetition bugs.
• The BSL syntax explored, displayed in Fig. 36, includes a new def production
rule to define functions.
– Recall that | means or.
– expr ::= #true | #false means an expression may be #true or may be
#false.
• The basic function design recipe is a roadmap for developing and implementing
functions.
• Auxiliary functions are used when specialized knowledge is needed to compute
a needed value or when different instances of the same value are computed.
• There are two general programming development styles.
– Bottom-up: simplest functions are developed first.
– Top-down: complex functions are developed first.
– Regardless of development style, the design recipe guides development.
20 What Have We Learned in This Chapter? 69

Fig. 36 Chapter 3 BSL grammar

program ::= {expr test def}*
def ::= (define <variable name> expr)
::= (define (<name> <name+>) expr)
test ::= (check-expect expr expr)
::= (check-within expr expr expr)
expr ::= number string <variable name>
::= \#<character constant>
::= <character+>
::= #true #false
::= <image>
::= (<function> expr)
::= (and expr expr expr*)
::= (or expr expr expr* )
string ::= "<character> *"
number ::= positive
::= negative
positive ::= mag
negative ::= -mag
mag ::= int
::= real
::= fraction
int ::= digit
digit ::= 0|1|2|3|4|5|6|7|8|9
real ::= digit* .digit+
fraction ::= int/nonzero-int
nonzero-int ::= <1|2|3|4|5|6|7|8|9>int
Chapter 4
Aliens Attack Version 0

It is time to put your newly acquired skills to work. This chapter develops the first
version of a video game that we shall call Aliens Attack. This chapter, however, will
not develop a full video game. You need to learn more about problem solving and
more BSL syntax to write a fully working video game. Therefore, the video game
is developed using the process of iterative refinement. That is, as you learn more
about problem solving and about BSL syntax, a more complete video game shall be
developed. This process culminates with a multiplayer game that you may play with
your friends over the internet. That is a promise. If you work hard and absorb all the
lessons contained in this textbook, then you will acquire enough skills to develop a
multiplayer video game.
Figure 37 displays an image of a single-player version of Aliens Attack. In the
scene there is an army of aliens attacking earth and there is a single rocket defending
earth. There is no placating the aliens and earth must defend itself. The rocket is at
the bottom of the scene over earth and may move left to right without going off the
edge of the image. The rocket may also shoot in an attempt to destroy the aliens.
The army of aliens starts toward the top of the scene. All the aliens move in the
same direction: right, left, or down. The aliens move right one step at a time until
an alien reaches the right edge of the scene. At this point all the aliens move down
a step. After moving down a step, the aliens move left one step at a time until an
alien reaches the left edge of the scene. The aliens then move down a step. This cycle
continues until an alien reaches and conquers earth (the player loses the game) or all
the aliens are destroyed (the player wins the game). Observe that, like the rocket, the
aliens may not go off the scene as they move. When the rocket shoots, a shot starts
at the position of the rocket and moves up until it hits an alien or it goes off the top
each of the scene.
The first version of Aliens Attack is not truly a video game. That is fine because
it will be refined. To start, the focus is on problems that you can solve with the skills
you have already developed. The development of Aliens Attack version 0 focuses on
the creation and placement of images to render the video game as an image. This is
a good starting point because you know the basics of creating and placing images
and of writing functions. The first goal is to design the scene where the images of
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 71
M. T. Morazán, Animated Problem Solving, Texts in Computer Science,
[Link]
72 4 Aliens Attack Version 0

Fig. 37 A sample rendering of a single-player Aliens Attack

the game are rendered. The second goal is to develop functions to create the images
of the rocket, the alien, and the shot. The third goal is to create functions to draw the
elements in a scene.

21 The Scene for Aliens Attack

Recall that graphics are created using a coordinate system in which the x coordinate
grows from left to right and the y coordinate grows from top to bottom. Also recall
that a w1 x h1 empty scene into which images are placed may be created as follows:
(empty-scene w1 h1 )
Creating an empty scene is only part of what is needed. The question that immediately
arises is how do we reason about this empty scene. Figure 38a displays the view of
the empty scene as a grid of pixels. Each square in the grid is a pixel and items, like
the blue square, are placed in the scene using pixel coordinates. The blue square in
Fig. 38a is at pixel coordinate (15, 19). This can work well but seems to mismatch
our goal. Our goal is to place images in a scene, not manipulate pixels. If we choose
a maximum size for each image in the video game, we can reason about the empty
scene as boxes where an image fits. Figure 38b displays this view of the empty scene.
A square is placed using image coordinates, not pixel coordinates. For instance, the
blue square in Fig. 38a is at image coordinate (3,3).
21 The Scene for Aliens Attack 73

So, why should we care about the perspective we adopt? It turns out that data
representation strongly influences how a problem is reasoned about. Consider, for
example, how is an alien hit by a shot is detected. We shall first analyze the problem
using the pixel perspective of the game’s scene. Assume that the image of an alien
has dimensions W x H as illustrated in Fig. 39 and the alien is located at pixel
coordinates (x, y). We define a hit as the shot’s position being inside the alien’s
image. That is, if the shot’s position is any pixel covered by the alien’s image, then
the alien is hit. In Fig. 39, for example, the shots at (xr1 ,yr1 ) and at (xr2 ,yr2 ) have
hit the alien. The shots at (xr3 ,yr3 ) and (xr4 ,yr4 ) have not hit the alien. Now,
how is a hit detected? After thinking about it, you can see that a hit means that the
shot can be at most half the alien’s image width (i.e., W/2) away on the x-axis and
at most half the alien’s image height (i.e., H/2) away on the y-axis from the alien’s
coordinates (i.e., (x, y)). This reasoning leads to a function to detect a hit alien
that looks as follows:
(define HALF-ALIEN-IMG-WIDTH (/ (image-width FUEL-IMG) 2))

(define HALF-ALIEN-IMG-HEIGHT (/ (image-height FUEL-IMG) 2))

(define (alien-hit? x-alien y-alien x-shot y-shot)

(and (<= (abs (- x-alien x-shot)) HALF-ALIEN-IMG-WIDTH)
(<= (abs (- y-alien y-shot)) HALF-ALIEN-IMG-HEIGHT)))
Now, consider solving the same problem using an image perspective of the game’s
scene. Under the image perspective, we do not have to worry about every pixel in
the scene. Images can only be placed in a box with image coordinates x and y. This
means that an alien is hit by a shot if both have the same coordinates. This reasoning
leads to a function to detect a hit alien that looks as follows:
(define (alien-hit? x-alien y-alien x-shot y-shot)
(and (= x-alien x-shot) (= y-alien y-shot)))

Fig. 38 Empty scene perspectives

(a) Pixel Perspective. (b) Image Perspective.
0 1 0 1
0 0

1 1
74 4 Aliens Attack Version 0

Fig. 39 Detecting a hit alien under the pixel perspective

H/2

W/2 (x,y) W/2

H/2

This function is much simpler and easier to understand than the first. The important
lesson here is that different representations, like pixel coordinates versus image
coordinates, may lead to vastly different solutions/programs. It is worth exploring
different representations to determine if any lead to a simpler and easier to understand
solution/program.
Given that we have carefully analyzed how to represent coordinates in the game’s
scene, we may be cautiously confident that using image coordinates leads to simpler
problem solutions. We can also surmise that we need to be careful about defining
the data representation in the program. For this, we need data definitions. A data
definition is written to describe a new type of data. For Aliens Attack, the following
data definitions and constants are used:
;; Character Image Maximum Dimensions
(define IMAGE-WIDTH 30)
(define IMAGE-HEIGHT 30)

;; Video Game Scene Dimensions

(define MAX-CHARS-HORIZONTAL 20)
(define MAX-CHARS-VERTICAL 15)

;; Empty Scene Constants

(define E-SCENE-COLOR ’pink)
(define E-SCENE2-COLOR ’black)
(define E-SCENE-W (* MAX-CHARS-HORIZONTAL IMAGE-WIDTH))
(define E-SCENE-H (* MAX-CHARS-VERTICAL IMAGE-HEIGHT))

#|DATA DEFINITIONS
A character image (ci) is an image which is at most
IMAGE-WIDTH x IMAGE-HEIGHT pixels
21 The Scene for Aliens Attack 75

An image-x is an integer in [0..MAX-CHARS-HORIZONTAL-1]

An image-y is an integer in [0..MAX-CHARS-VERTICAL-1]

A scene is a E-SCENE-W x E-SCENE-H image

A pixel-x is an integer in [0..E-SCENE-W-1]

A pixel-y is an integer in [0..E-SCENE-H-1] |#

;; Sample image-x
(define AN-IMG-X (/ MAX-CHARS-HORIZONTAL 2))
(define MIN-IMG-X 0)
(define MAX-IMG-X (sub1 MAX-CHARS-HORIZONTAL))

;; Sample image-y
(define AN-IMG-Y (/ MAX-CHARS-VERTICAL 2))
(define MIN-IMG-Y 0)
(define MAX-IMG-Y (sub1 MAX-CHARS-VERTICAL))

;; Sample empty scenes

(define E-SCENE (empty-scene E-SCENE-W
E-SCENE-H
E-SCENE-COLOR))
(define E-SCENE2 (empty-scene E-SCENE-W
E-SCENE-H
E-SCENE2-COLOR))
The define constants clearly communicate that for any ci in the game (i.e., rocket,
alien, and shot), the maximum width is 30 pixels and the maximum height is 30 pixels.
The scene fits 20 ci horizontally and 15 ci vertically. This means image coordinates
range from (0,0) to (19, 14). Examples of image-x and image-y values are defined
to make writing tests easier. These include the extrema values: the largest and the
smallest possible values. Pixel coordinates range from (0,0) to ((sub1 E-SCENE-W),
(sub1 E-SCENE-H)). Clearly, we need a mechanism to map image coordinates to
pixel coordinates. We shall return to this new problem after tackling the creation of
character images.
The data definitions clearly describe what is (and what is not) a ci, an
image-x, an image-y, a scene, a pixel-x, and a pixel-y. For example, 2 is
a valid image-x because 2 is in [0..(sub1 MAX-CHARS-HORIZONTAL)]. On
the other hand, 1000 is not a valid image-x because 1000 is not in [0..(sub1
MAX-CHARS-HORIZONTAL)]. These data definitions guide the development of func-
tions for the video game. Furthermore, the newly defined data types may be used in
signatures. That is, the new data types may be used to describe the inputs to and the
output of functions.
76 4 Aliens Attack Version 0

22 Creating Aliens Attack Images

Creating the images needed for Aliens Attack provides the opportunity to practice
the steps of the design recipe. In addition, it provides us with the opportunity to write
an application programming interface (API). An API defines the data formats, the
conventions, and the functions that may be used to create and access data. For Aliens
Attack images, the API is rather simple: the dimensions of any character image must
be 30 x 30 pixels or less and must be created using functions in the image teachpack.
One of the benefits of using or creating an API is information hiding. This means,
for example, that the implementation details of a function are hidden from any
programmer who uses the function. A programmer uses the function independent of
how the function is implemented. To be successful, the signature and the purpose of
the function must be clear. Otherwise, programmers will not know how to properly
use a function.
Observe that according to the data definitions, every ci is an image. Every image,
however, is not a ci. A natural question that arises is determining if an image is a
ci. Testing image values is useless, because everybody’s idea of a shot, an alien, or
a rocket is different. Furthermore, the data definition ci only specifies ci properties
(not values). This is a clear situation where property-based testing is needed. For
this, a predicate to determine if a given image is a ci is needed. Following the steps
of the design recipe, the predicate may be designed as follows:
STEP 1
Determine that both the image width is less than or equal to IMAGE-WIDTH and
that the image height is less than or equal to IMAGE-HEIGHT.
STEP 2
Definitions for the value of sample expressions are

(define IS-CI
(and (<= (image-width (circle 10 'solid 'red))
IMAGE-WIDTH)
(<= (image-height (circle 10 'solid 'red))
IMAGE-HEIGHT)))

(define NOT-CI
(and (<= (image-width (square 40 'solid 'blue))
IMAGE-WIDTH)
(<= (image-height (square 40 'solid 'blue))
IMAGE-HEIGHT)))

(define NOT-CI2
(and (<= (image-width
(rectangle 2 50 'solid 'blue))
IMAGE-WIDTH)
22 Creating Aliens Attack Images 77

(<= (image-height
(rectangle 2 50 'solid 'blue))
IMAGE-HEIGHT)))

Observe that sample expressions are developed for both images that are and that
are not ci.
STEP 3
The only difference among the sample expressions is the image tested. The
variable for this difference is an-img.
STEP 4
The signature and purpose statement are

;; image → Boolean
;; Purpose: To determine if the given image is a ci

STEP 5
The function header is
(define (ci? an-img)
STEP 6
Testing may be satisfied as follows:

;; Tests using sample computations for ci?

(check-expect (ci? (circle 10 'solid 'red)) IS-CI)
(check-expect (ci? (square 40 'solid 'blue)) NOT-CI)
(check-expect (ci? (rectangle 20 40 'solid 'blue)) NOT-CI2)

;; Tests using sample values for ci?

(check-expect (ci? (ellipse 10 22 'outline 'green)) #true)
(check-expect (ci? (rectangle 5 33 'solid 'yellow)) #false)

Observe that both images that are and are not ci are tested.
STEP 7
The body of the function is

(and (<= (image-width an-img) IMAGE-WIDTH)

(<= (image-height an-img) IMAGE-HEIGHT))

STEP 8
All tests pass.

Recall that this step is only satisfied when the tests are executed and pass.
78 4 Aliens Attack Version 0

* Ex. 45 — Design and implement a predicate to determine if an image is a

scene.
* Ex. 46 — Design and implement a predicate to determine if a number is an
image-x.

* Ex. 47 — Design and implement a predicate to determine if a number is an

image-y.

* Ex. 48 — Design and implement a predicate to determine if a number is a

pixel-x.

* Ex. 49 — Design and implement a predicate to determine if a number is a

pixel-y.

** Ex. 50 — A blank pink or black scene is rather dull. Personalize your

empty scene to provide a more interesting and more pleasant background.

Now that ci and non-ci images are distinguishable, attention turns to the con-
struction of cis. There are three image constructors that are needed: one for a shot,
one for an alien, and one for a rocket. The development presented here is only illustra-
tive. This is your video game and you are encouraged to be creative and personalize
the game to your liking. Understand the principles for developing the images and then
design functions for your own images. Remember that, unlike homework problems
in high school Mathematics, there may be many solutions to a problem.

23 Shot Image

The image of the shot is the simplest one in Fig. 37. The shot’s image is a radial
star and the color is orange. These, of course, may be different depending on your
preferences. The goal is to design a constructor for shot images. The steps of the
design recipe may be satisfied as follows:
STEP 1
A shot image is a ci of a radial star created using the function radial-star.
Observe that the data definition of a shot image is described in terms of the type
for character images previously developed.
STEP 2
Definitions for the value of sample expressions are

(define SHOT-COLOR 'orange)

(define SHOT-COLOR2 'skyblue)

23 Shot Image 79

(define SHOT-IMG (radial-star 8

(/ IMAGE-WIDTH 8)
(/ IMAGE-WIDTH 2)
'solid
SHOT-COLOR))

(define SHOT-IMG2 (radial-star 8

(/ IMAGE-WIDTH 8)
(/ IMAGE-WIDTH 2)
'solid
SHOT-COLOR2))

The constants are defined to facilitate changing the color of sample shots. Observe
that the outer diameter of the radial star is IMAGE-WIDTH/2 = 15. Therefore, the
image of a shot is a ci.
STEP 3
The only difference among the sample expressions is the color of the shot. The
variable for this difference is a-color.
STEP 4
The signature and purpose statement are

;; color → image
;; Purpose: Create a shot image of the given color

STEP 5
The function header is
(define (mk-shot-ci a-color)
STEP 6
The tests are below.

;; Tests using sample computations for mk-shot-ci

(check-expect (mk-shot-ci SHOT-COLOR) SHOT-IMG)
(check-expect (mk-shot-ci SHOT-COLOR2) SHOT-IMG2)
(check-expect (ci? SHOT-IMG) #true)
(check-expect (ci? SHOT-IMG2) #true)

;; Tests using sample values for mk-shot-ci

(check-expect (mk-shot-ci 'red) )

(check-expect (mk-shot-ci 'brown) )

(check-expect (ci? (mk-shot-img 'red)) #true)
(check-expect (ci? (mk-shot-img 'brown)) #true)
80 4 Aliens Attack Version 0

Observe that the last two sample computations and sample values tests are
property-based testing. They illustrate that the image returned by mk-shot-img
is a ci.
STEP 7
The body of the function is

(radial-star 8 (/ IMAGE-WIDTH 8) (/ IMAGE-WIDTH 2) 'solid a-color))

STEP 8
All tests pass.

24 Alien Image

The alien image in Fig. 37 is the composition of two images of the same color: an
X and a circle. Specifically, the circle is overlayed over the X. A function to achieve
this uses function composition. The steps of the design recipe may be satisfied as
follows:
STEP 1
The alien image is computed using function composition. The outputs of text
and circle are inputs to overlay. The circle image is overlayed over the X
image. The alien image must be a ci.
STEP 2
Definitions for the value of sample expressions are

(define ALIEN-COLOR 'black)

(define ALIEN-COLOR2 'orange)

(define ALIEN-IMG (overlay (text "X" 25 ALIEN-COLOR)

(circle (/ IMAGE-WIDTH 4)
'solid
ALIEN-COLOR)))

(define ALIEN-IMG2 (overlay (text "X" 25 ALIEN-COLOR2)

(circle (/ IMAGE-WIDTH 4)
'solid
ALIEN-COLOR2)))

Getting the alien images to be at most 30 × 30 pixels requires experimentation.

It is not clear from the code above that the resulting images have this property.
Property-based testing may be used to demonstrate this.
24 Alien Image 81

STEP 3
The only difference among the sample expressions is the color of the alien. The
variable for this difference is a-color.
STEP 4
The signature and purpose statement are

;; color → image
;; Purpose: Create an alien image of the given color

STEP 5
The function header is

(define (mk-alien-ci a-color)

STEP 6
The tests are below.

;; Tests using sample computations for mk-alien-ci

(check-expect (mk-alien-ci ALIEN-COLOR) ALIEN-IMG)
(check-expect (mk-alien-ci ALIEN-COLOR2) ALIEN-IMG2)
(check-expect (ci? ALIEN-IMG) #true)
(check-expect (ci? ALIEN-IMG2) #true)

;; Tests using sample values for mk-alien-ci

(check-expect (mk-alien-ci 'purple) )

(check-expect (mk-alien-ci 'lightbrown) )

(check-expect (ci? (mk-alien-img 'purple)) #true)
(check-expect (ci? (mk-alien-img 'lightbrown)) #true)

STEP 7
The body of the function is

(overlay (text "X" 25 a-color)

(circle (/ IMAGE-WIDTH 4) 'solid a-color))

STEP 8
All tests pass.
82 4 Aliens Attack Version 0

Fig. 40 Components of the rocket image

(a) Rocket Window.

(b) Rocket Fuselage. (c) Rocket Single Booster.

(d) Rocket Booster.

(e) Rocket Nacelle.

(f) Rocket Main Body.

25 Rocket Image

The rocket image is the most complex of the images in Fig. 37. It is composed of the
images displayed in Fig. 40. To design a function to create a rocket image, a divide
and conquer bottom-up strategy is followed. That is, the simplest components are
independently designed first. Then simple components are combined to create more
complex figures.
It is important to keep in mind that creating images for the components of a larger
image requires experimentation. Rarely, if ever, are the dimensions of a component
right after the first attempt. This is another reason why it is important to write sample
expressions. Sample expressions may be repeatedly refined until the desired visual
effect is achieved. The steps of the design recipe presented for each component
below are the final result after several refinements improving the dimensions of each
component. Do not be afraid to experiment. Experimenting with sample expressions
may lead to insights on how to solve a problem.

25.1 Rocket Window Image Constructor

Creating a rocket window image is a simple exercise with which to practice the steps
the design recipe.
STEP 1
A rocket window is a solid vertical oval.
STEP 2
Definitions for the value of sample expressions are
25 Rocket Image 83

(define WINDOW-COLOR 'darkgray)

(define WINDOW2-COLOR 'white)

(define WINDOW (ellipse 3 10 'solid WINDOW-COLOR))

(define WINDOW2 (ellipse 3 10 'solid WINDOW2-COLOR))

STEP 3
The only difference among the sample expressions is the color of the oval. The
variable for this difference is a-color.
STEP 4
The signature and purpose statement are

;; color → image
;; Purpose: Create rocket window image

STEP 5
The function header is

(define (mk-window-img a-color)

STEP 6
Testing may be satisfied as follows:

;; Tests using sample computations for mk-window-img

(check-expect (mk-window-img WINDOW-COLOR) WINDOW)
(check-expect (mk-window-img WINDOW2-COLOR) WINDOW2)

;; Tests using sample values for mk-window-img

(check-expect (mk-window-img 'darkblue) )
(check-expect (mk-window-img 'gray) )

STEP 7
The body of the function is

(ellipse 3 10 'solid a-color)

STEP 8
All tests pass.
84 4 Aliens Attack Version 0

In DrRacket, the code ought to be organized as follows:

;; color → image
;; Purpose: Create rocket window image
(define (mk-window-img a-color)
(ellipse 3 10 'solid a-color))

;; Sample expressions for mk-window-img

(define WINDOW (ellipse 3 10 'solid WINDOW-COLOR))
(define WINDOW2 (ellipse 3 10 'solid WINDOW2-COLOR))

;; Tests using sample computations for mk-window-img

(check-expect (mk-window-img WINDOW-COLOR) WINDOW)
(check-expect (mk-window-img WINDOW2-COLOR) WINDOW2)

;; Tests using sample values for mk-window-img

(check-expect (mk-window-img 'darkblue) )
(check-expect (mk-window-img 'gray) )
Observe that the steps of the design recipe are written in an organized fashion
keeping the function, the sample expressions, and the tests together. The constants
WINDOW-COLOR and WINDOW-COLOR2 ought to be defined in a section dedicated to
constants toward the top of the program.

25.2 Rocket Fuselage Image Constructor

STEP 1
The fuselage is a solid circle.
STEP 2
Definitions for the value of sample expressions are

(define FUSELAGE (circle (* 1/3 IMAGE-HEIGHT)

'solid
FUSELAGE-COLOR))

(define FUSELAGE2 (circle (* 1/3 IMAGE-HEIGHT)

'solid
FUSELAGE2-COLOR))

STEP 3
The only difference among the sample expressions is the color. The variable for
this difference is a-color.
25 Rocket Image 85

STEP 4
The signature and purpose statement are

;; color → image
;; Purpose: Create the fuselage image

STEP 5
The function header is
(define (mk-fuselage-img a-color)
STEP 6
Testing may be satisfied as follows:

;; Test using sample computations for mk-fuselage-img

(check-expect (mk-fuselage-img FUSELAGE-COLOR) FUSELAGE)
(check-expect (mk-fuselage-img FUSELAGE2-COLOR) FUSELAGE2)

;; Test using sample values for mk-fuselage-img

(check-expect (mk-fuselage-img 'olive) )

(check-expect (mk-fuselage-img 'lightgray) )

STEP 7
The body of the function is

(circle (* 1/3 IMAGE-HEIGHT) 'solid a-color))

STEP 8
All tests pass.

25.3 Rocket Single Booster Image Constructor

The single booster image is an equilateral triangle pointing down. Computing this
image requires function composition. The output of triangle is input to rotate.
STEP 1
A rocket single booster is an equilateral triangle image rotated 180◦ .
STEP 2
Definitions for the value of sample expressions are
86 4 Aliens Attack Version 0

(define SINGLE-BOOSTER (rotate 180

(triangle (/ FUSELAGE-W 2)
'solid
NACELLE-COLOR)))
(define SINGLE-BOOSTER2 (rotate 180
(triangle (/ FUSELAGE-W 2)
'solid
NACELLE2-COLOR)))

Observe that in Fig. 40, the single booster image is the same color as the nacelle
image. Therefore, constants NACELLE-COLOR and NACELLE2-COLOR are defined
and used to write sample single booster (and nacelle) expressions.
STEP 3
The only difference among the sample expressions is the color. The variable for
this difference is a-color.
STEP 4
The signature and purpose statement are

;; color → image
;; Purpose: Create single booster image

STEP 5
The function header is
(define (mk-single-booster-img a-color)
STEP 6
Testing may be satisfied as follows:

;; Tests using sample computations for mk-single-booster-img

(check-expect (mk-single-booster-img NACELLE-COLOR) SINGLE-BOOSTER)
(check-expect (mk-single-booster-img NACELLE2-COLOR) SINGLE-BOOSTER2)

;; Tests using sample values for mk-single-booster-img

(check-expect (mk-single-booster-img 'darkred) )
(check-expect (mk-single-booster-img 'gold) )

STEP 7
The body of the function is

(rotate 180 (triangle (/ FUSELAGE-W 2) 'solid a-color)))

STEP 8
All tests pass.
25 Rocket Image 87

25.4 Rocket Booster Image Constructor

Observe that the booster image in Fig. 40d is two copies of a single booster image
side by side. This suggests that a constructor for a booster image needs a single
booster image as input.
STEP 1
A booster image is two copies of a single booster image side by side.
STEP 2
Definitions for the value of sample expressions are

(define BOOSTER (beside SINGLE-BOOSTER SINGLE-BOOSTER))

(define BOOSTER2 (beside SINGLE-BOOSTER2 SINGLE-BOOSTER2))

STEP 3
The only difference among the sample expressions is the single booster image.
The variable for this difference is a-sb-img.
STEP 4
The signature and purpose statement are

;; image → image
;; Purpose: Create booster image

STEP 5
The function header is
(define (mk-booster-img a-sb-img)
STEP 6
Testing may be satisfied as follows:

;; Tests using sample computations for mk-booster-img

(check-expect (mk-booster-img SINGLE-BOOSTER) BOOSTER)
(check-expect (mk-booster-img SINGLE-BOOSTER2) BOOSTER2)

;; Tests using sample values for mk-booster-img

(check-expect (mk-booster-img (mk-single-booster-img 'darkred)) )
(check-expect (mk-booster-img (mk-single-booster-img 'gold)) )

STEP 7
The body of the function is

(beside a-sb-img a-sb-img))

88 4 Aliens Attack Version 0

STEP 8
All tests pass.

25.5 Rocket Main Body Image Constructor

Constructing an image for the rocket’s main body, as displayed in Fig. 40f, requires
three images: a window image, a fuselage image, and a booster image. It also requires
the use of function composition given that the fuselage goes above the booster and
the window goes on the fuselage.
STEP 1
The rocket’s main body is created by placing the fuselage above the booster and
then placing the window one quarter of the way down the height and half away
across the width of the fuselage.
STEP 2
Definitions for the value of sample expressions are

(define ROCKET-MAIN (place-image

WINDOW
(/ (image-width FUSELAGE) 2)
(/ (image-height FUSELAGE) 4)
(above FUSELAGE BOOSTER)))

(define ROCKET-MAIN2 (place-image

WINDOW2
(/ (image-width FUSELAGE2) 2)
(/ (image-height FUSELAGE2) 4)
(above FUSELAGE2 BOOSTER2)))

Observe that previously defined sample images are used to write the sample
expressions.
STEP 3
There are 3 differences among the sample expressions: the window, the fuselage,
and the booster images. The variables for these differences are, respectively,
a-window, a-fuselage, and a-booster.
STEP 4
The signature and purpose statement are

;; image image image → image

;; Purpose: Create the main rocket image
25 Rocket Image 89

STEP 5
The function header is
(define (mk-rocket-main-img a-window a-fuselage a-booster)
STEP 6
Testing may be satisfied as follows:

;; Tests using sample computations for mk-rocket-main-img

(check-expect (mk-rocket-main-img WINDOW FUSELAGE BOOSTER)
ROCKET-MAIN)
(check-expect (mk-rocket-main-img
WINDOW2 FUSELAGE2 BOOSTER2)
ROCKET-MAIN2)

;; Tests using sample computations for mk-rocket-main-img

(check-expect (mk-rocket-main-img
(mk-window-img 'black)
(mk-fuselage-img 'yellow)
(mk-booster-img
(mk-single-booster-img 'yellow)))

(check-expect (mk-rocket-main-img
(mk-window-img 'green)
(mk-fuselage-img 'skyblue)
(mk-booster-img
(mk-single-booster-img 'lightred)))

STEP 7
The body of the function is

(place-image a-window
(/ (image-width a-fuselage) 2)
(/ (image-height a-fuselage) 4)
(above a-fuselage a-booster))

STEP 8
All tests pass.
90 4 Aliens Attack Version 0

Fig. 41 Rocket image

25.6 Rocket Nacelle Image Constructor

The image of the rocket’s nacelle in Fig. 40e is deceptively simple. At first glance,
it looks like an ordinary rectangle. A closer examination of the rocket image, as
displayed in Fig. 41, reveals that the nacelle and the booster are the same color. In
addition, the nacelle must be the same width as the rocket’s main body and about a
quarter of the height of the main body. With these observations, the design of the
constructor for nacelle images follows.
STEP 1
The image of a nacelle is a rectangle that is the same width as the rocket’s main
body and a quarter of the height of the rocket’s main body height. The color of
the nacelle is the same color as the booster in the rocket’s main body.
STEP 2
Definitions for the value of sample expressions are

(define NACELLE (rectangle (image-width ROCKET-MAIN)

(/ (image-height ROCKET-MAIN)
4)
'solid
NACELLE-COLOR))

(define NACELLE2 (rectangle (image-width ROCKET-MAIN2)

(/ (image-height ROCKET-MAIN2)
4)
'solid
NACELLE2-COLOR))

Observe that the same constants used to construct single booster images are used
to construct the corresponding nacelle images.
STEP 3
There are two differences among the sample expressions: the main rocket image
and the color of the nacelle. The variables for these differences are, respectively,
a-rocket-main-img and a-color.
STEP 4
The signature and purpose statement are

;; image color → image

;; Purpose: Create a rocket nacelle image
25 Rocket Image 91

STEP 5
The function header is
(define (mk-nacelle-img a-rocket-main-img a-color)
STEP 6
Testing may be satisfied as follows:

;; Tests using sample computations for mk-nacelle-img

(check-expect (mk-nacelle-img ROCKET-MAIN NACELLE-COLOR)
NACELLE)
(check-expect (mk-nacelle-img ROCKET-MAIN2 NACELLE2-COLOR)
NACELLE2)

;; Tests using sample values for mk-nacelle-img

(check-expect (mk-nacelle-img
(mk-rocket-main-img
(mk-window-img 'blue)
(mk-fuselage-img 'green)
(mk-booster-img
(mk-single-booster-img 'yellow)))
'yellow)
)
(check-expect (mk-nacelle-img
(mk-rocket-main-img
(mk-window-img 'blue)
(mk-fuselage-img 'green)
(mk-booster-img
(mk-single-booster-img 'lightorange)))
'lightorange)
)

STEP 7
The body of the function is

(rectangle (image-width a-rocket-main-img)

(/ (image-height a-rocket-main-img) 4)
'solid
a-color))

STEP 8
All tests pass.
92 4 Aliens Attack Version 0

25.7 Rocket ci Constructor

The final image constructor needed is the rocket image constructor. This constructor
must place the nacelle over the rocket’s main body.
STEP 1
The rocket image is constructed by placing the nacelle image half the way across
the rocket’s main body and 30% from the bottom of the rocket’s main body.
STEP 2
Definitions for the value of sample expressions are

(define ROCKET-IMG (place-image

NACELLE
(/ (image-width ROCKET-MAIN) 2)
(* 0.7 (image-height ROCKET-MAIN))
ROCKET-MAIN))

(define ROCKET-IMG2 (place-image

NACELLE2
(/ (image-width ROCKET-MAIN2) 2)
(* 0.7 (image-height ROCKET-MAIN2))
ROCKET-MAIN2))

Notice that 30% from the bottom is the same as 70% from the top of the rocket’s
main body image. Since y values grow downward in the graphic plane, 70% of
the rocket’s main body image is computed.
STEP 3
There are two differences among the sample expressions: the rocket’s main body
image and the rocket’s nacelle image. The variables for these differences are
a-rocket-main-img and a-nacelle-img.
STEP 4
The signature and purpose statement are

;; image image → ci
;; Purpose: Create a rocket ci

Observe that the signature states that this function returns a ci. This is needed
because the returned image is intended for use in Aliens Attack.
STEP 5
The function header is
(define (mk-rocket-ci a-rocket-main-img a-nacelle-img)
STEP 6
Testing may be satisfied as follows:
25 Rocket Image 93

;; Tests using sample computations for mk-rocket-img

(check-expect (mk-rocket-ci ROCKET-MAIN NACELLE)
ROCKET-IMG)
(check-expect (mk-rocket-ci ROCKET-MAIN2 NACELLE2)
ROCKET-IMG2)
(check-expect (ci? ROCKET-IMG) #true)
(check-expect (ci? ROCKET-IMG2) #true)

;; Tests using sample values for mk-rocket-img

(check-expect (mk-rocket-ci
(mk-rocket-main-img
(mk-window-img
'blue)
(mk-fuselage-img
'green)
(mk-booster-img
(mk-single-booster-img 'yellow)))
(mk-nacelle-img
(mk-rocket-main-img
(mk-window-img
'blue)
(mk-fuselage-img 'green)
(mk-booster-img
(mk-single-booster-img 'yellow)))
'yellow))

Observe that the output of this function must be a character image and, therefore,
ci? is used to test its properties. Furthermore, observe that there is a single
sample value test and that this test contains a significant amount of repetition.
Both of these are considered poor style. Testing ought to be more thorough. The
repetitions make it difficult to read and understand the test.
STEP 7
The body of the function is

(place-image a-nacelle-img
(/ (image-width a-rocket-main-img) 2)
(* 0.7 (image-height a-rocket-main-img))
a-rocket-main-img)
94 4 Aliens Attack Version 0

STEP 8
All tests pass.

** Ex. 51 — Refine the tests using sample values for mk-rocket-ci. Make
sure to eliminate repeated expressions and include more than one test.

*** Ex. 52 — Personalize your game with cis for the shot, the alien, and the
rocket of your own creation.

26 Drawing Functions

In contrast to the development of mk-rocket-img, we shall use a top-down approach

to design the function to draw a ci in a scene. This computation requires a ci, an
image-x, an image-y, and a scene. Note that place-image cannot simply be used
to place a ci at the coordinate formed by the given image-x and image-y. Recall
Fig. 38 and the data definitions for image and pixel coordinates. There are many
more pixel coordinates than image coordinates given that one image point, (xi ,
yi ), covers many pixel points. We must now solve the problem of mapping image
coordinates to pixel coordinates. The design starts with the topmost function, which
draws a ci in a scene.
STEP 1
The given ci is placed in the given scene by translating the given image coordi-
nates to pixel coordinates.
STEP 2
Definitions for the value of sample expressions are

(define ROCKET-Y (sub1 MAX-CHARS-VERTICAL))

(define ROCKET-SCN (place-image

ROCKET-IMG
(image-x->pix-x
(/ MAX-CHARS-HORIZONTAL 2))
(image-y->pix-y ROCKET-Y)
E-SCENE))

(define ALIEN-SCN (place-image ALIEN-IMG

(image-x->pix-x 4)
(image-y->pix-y 7)
E-SCENE2))
26 Drawing Functions 95

(define SHOT-SCN (place-image

SHOT-IMG
(image-x->pix-x 17)
(image-y->pix-y 13)
E-SCENE2))

Observe that the three sample expressions evaluate to a scene because a ci

is placed in a scene. Further notice that two auxiliary functions are needed to
translate the image coordinates. The constant ROCKET-Y stems from thinking
ahead and observing that the rocket’s image-y coordinate is a constant in Aliens
Attack.
STEP 3
There are four differences among the sample expressions: the ci, the image-x and
-y coordinates, and the scene. The variables for these differences are char-img,
an-img-x, an-img-y, and scn.
STEP 4
The signature and purpose statement are

;; ci image-x image-y scene → scene

;; Purpose: Place the given ci in the given scene at the
;; given image coordinates

STEP 5
The function header is
(define (draw-ci char-img an-img-x an-img-y scn)
STEP 6
Testing may be satisfied as follows:

;; Tests using sample computations for draw-ci

(check-expect (draw-ci ROCKET-IMG
(/ MAX-CHARS-HORIZONTAL 2)
ROCKET-Y
E-SCENE)
ROCKET-SCN)
(check-expect (draw-ci ALIEN-IMG 4 7 E-SCENE) ALIEN-SCN)
(check-expect (draw-ci SHOT-IMG 17 13 E-SCENE) SHOT-SCN)

;; Tests using sample values for draw-ci

(check-expect (draw-ci
(square 10 'solid 'green) 8 8 E-SCENE)
96 4 Aliens Attack Version 0

Fig. 42 Top-left box of the scene image perspective

IMAGE-WIDTH/2

IMAGE-HEIGHT/2

(check-expect (draw-ci (ellipse 20 30 'outline 'black)

11 12 E-SCENE)

STEP 7
The body of the function is

(place-image char-img
(image-x->pix-x an-img-x)
(image-y->pix-y an-img-y)
scn)

STEP 8
All tests pass.
The design now focuses on the two auxiliary functions to map image coordinates
to pixel coordinates. Let us first consider mapping the image coordinate pair (0, 0) to
26 Drawing Functions 97

a pixel coordinate pair. This coordinate pair is the top-left box in Fig. 38b. The center
of the image ought to be placed at the center of the box. The dimensions of the box
are IMAGE-WIDTH × IMAGE-HEIGHT. As illustrated in Fig. 42, this means that the
center of this box is at pixel coordinates (IMAGE-WIDTH/2, IMAGE-HEIGHT/2).
What is the pixel coordinate of image coordinate (3, 2)? This pixel coordinate
(IMAGE-WIDTH/2, IMAGE-HEIGHT/2) must be translated 3 boxes to the right and
2 boxes down. Therefore, the pixel coordinate for the box at the image coordinate (3,
2) is:
(3 * IMAGE-WIDTH + IMAGE-WIDTH/2,
2 * IMAGE-HEIGHT + IMAGE-HEIGHT/2)
In general, the image coordinate (x, y) maps to the pixel coordinate:
(x * IMAGE-WIDTH + IMAGE-WIDTH/2,
y * IMAGE-HEIGHT + IMAGE-HEIGHT/2)
Observe that the mapping works for image coordinate pair (0, 0).
The above insight guides the design of the image-coordinate to pixel-coordinate
functions. The steps of the design recipe to transform an image-x may be satisfied
as follows:
STEP 1
For image-x, ix, the corresponding pixel-x is ix * IMAGE-WIDTH
+ IMAGE-WIDTH/2
STEP 2
Definitions for the value of sample expressions are

(define PIX-X5 (+ (* 5 IMAGE-WIDTH) (/ IMAGE-WIDTH 2)))

(define PIX-X12 (+ (* 12 IMAGE-WIDTH) (/ IMAGE-WIDTH 2)))

STEP 3
The only difference among the sample expressions is the image-x value. The
variable for this difference is ix.
STEP 4
The signature and purpose statement are

;; image-x → pixel-x
;; Purpose: To translate the given image-x to a pixel-x

STEP 5
The function header is
(define (image-x->pix-x ix)
98 4 Aliens Attack Version 0

STEP 6

;; Tests using sample computations for x->pix-x

(check-expect (image-x->pix-x 5) PIX-X5)
(check-expect (image-x->pix-x 12) PIX-X12)

;; Tests using sample values for x->pix-x

(check-expect (image-x->pix-x 0) (/ IMAGE-WIDTH 2))
(check-expect (image-x->pix-x (sub1 MAX-CHARS-HORIZONTAL))
585)

Observe that the tests using sample values are written for extrema values. That is,
the minimum and maximum possible values of an image-x are used.
STEP 7
The body of the function is

(+ (* ix IMAGE-WIDTH) (/ IMAGE-WIDTH 2)))

STEP 8
All tests pass.
The design of image-x->pix-x does not reveal the need for any new auxiliary
functions. The only task left is to design a function to translate an image-y to a
pixel-y. The steps of the design recipe may be satisfied as follows:
STEP 1
For image-y, iy, the corresponding pixel-y is iy * IMAGE-HEIGHT +
IMAGE-HEIGHT/2
STEP 2
Definitions for the value of sample expressions are

(define PIX-Y1 (+ (* 1 IMAGE-HEIGHT) (/ IMAGE-HEIGHT 2)))

(define PIX-Y6 (+ (* 6 IMAGE-HEIGHT) (/ IMAGE-HEIGHT 2)))

STEP 3
The only difference among the sample expressions is the image-y value. The
variable for this difference is iy.
STEP 4
The signature and purpose statement are

;; image-y → pixel-y
;; Purpose: To translate the given image-y to a pixel-y
26 Drawing Functions 99

STEP 5

The function header is

(define (image-y->pix-y iy)

STEP 6

;; Tests using sample computations for y->pix-y

(check-expect (image-y->pix-y 1) PIX-Y1)
(check-expect (image-y->pix-y 6) PIX-Y6)

;; Tests using sample values for y->pix-y

(check-expect (image-y->pix-y 0) (/ IMAGE-HEIGHT 2))
(check-expect (image-y->pix-y (sub1 MAX-CHARS-VERTICAL))
435)

Once again, observe that the tests using sample values are written for extrema
values.
STEP 7
The body of the function is

(+ (* iy IMAGE-HEIGHT) (/ IMAGE-HEIGHT 2)))

STEP 8
All tests pass.
The design of image-y->pix-y does not reveal the need for any new auxiliary
functions. This means that all the functions needed to draw a ci have been designed
and implemented.

** Ex. 53 — What happens if draw-ci does not translate image coordinates

to pixel coordinates?

* Ex. 54 — Use draw-ci and function composition to create a possible scene

for Aliens Attack with a rocket, multiple aliens, and multiple shots. Figure 37
is an example of such a scene.
100 4 Aliens Attack Version 0

27 What Have We Learned in This Chapter?

The important lessons of Chap. 6 are summarized as follows:

• The data representation chosen strongly influences how we think about and solve
problems.
• Exploring different data representations may lead to simpler programs.
• Data definitions are written to describe new data types.
• New data types may be used in function signatures.
• An API defines data formats, conventions, constructors, and selectors.
• Signatures and purpose statements make an API’s information hiding useful.
• Property-based testing may be useful in illustrating that the conventions of an
API are met.
Chapter 5
Making Decisions

Making decisions is part of life. For example, while driving on a highway, the driver
monitors the car’s speed. If the speed is too fast, then the driver decreases the speed.
If the speed is too slow, then the driver increases the speed. Otherwise, the driver
does not change the speed. It should not come as a surprise that making decisions is
also part of problem solving. Modern cars are equipped with a cruise control system.
The driver sets the cruise control at a certain speed. If the speed is too fast, then the
cruise control program decreases the speed. If the speed is too slow, then the cruise
control program increases the speed. Otherwise, the cruise control program does not
change the speed.
Regardless of whether it is a driver or a cruise control program, the decision
on how to adjust the speed depends on the car’s current speed. This decision
is may be represented by one of three possible expressions, say, 'increase,
'decrease, or 'steady. Think carefully about what this means. Multiple ex-
pressions for the value of a function means that determining how to adjust the
speed is a compound function. We can, in fact, write a mathematical func-
tion:
⎧
⎪
⎨'decrease if too-fast?(a-speed)
speed-change(a-speed) = 'increase if too-slow?(a-speed)
⎪
⎩
'steady otherwise

Two predicates, too-fast? and too-slow?, are used to evaluate the given speed.
In essence, the above function is stating that there is data variety in the domain of the
function. The input may be in one of three speed intervals indicating that the car is
either traveling too fast, too slow, or neither. In order to determine the speed change
a decision must be made as to which of the 3 expressions needs to be evaluated. This
decision is based on the speed range a-speed belongs to.
It turns out that speed ranges may be used to solve many problems. For example,
a police officer may use the following function to determine a course of action after

© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 101
M. T. Morazán, Animated Problem Solving, Texts in Computer Science,
[Link]
102 5 Making Decisions

measuring the speed of a car:

⎧
⎪
⎨"Issue Ticket" if too-fast?(speed)
police-action(speed) = "Issue Warning" if too-slow?(speed)
⎪
⎩
"Take No Action" otherwise

Observe that this function must also decide which expression to use to provide an
answer for a given speed. Furthermore, observe that the two functions have the same
basic structure. This structural similarity stems from the fact that they process the
same type of data and suggests that a function template may be developed to process
a speed. A function template is like a skeleton for functions. It captures the expected
similarities among function that process the same type of data. For each data type a
problem solver defines a function template is developed.
For example, speed may be defined as follows:
A speed is a number such that either:
1. too-fast?(a-speed) is true
2. too-slow?(a-speed) is true
3. Neither too-fast?(a-speed) nor too-slow?(a-speed) is true
the template for functions that process speed is:
⎧
⎪
⎨. . . if too-fast?(a-speed)
f-on-speed(a-speed) = . . . if too-slow?(a-speed)
⎪
⎩
. . . otherwise
This template may be used to design any function that processes a speed. By providing
the missing expressions and a function name both functions above are obtained.
We can surmise from the examples above that compound functions arise from data
having variety. These functions need to decide which expression to evaluate based
on the variety the input belongs to. All functions that process the same data type with
variety have the same structure. This chapter introduces how to design functions that
make decisions. It introduces new BSL syntax to write conditional expressions which
are used to make decisions. A design recipe for compound functions is presented that
includes the development of data definitions for data with variety and of function
templates to capture structural similarities among functions. Several different types
of data with variety are explored.

28 Conditional Expressions in BSL

In BSL, there is syntax for expressions to make decisions. These new expressions are
called conditional expressions. The new expr production rule is:

expr ::= (cond [expr expr]+

[else expr])
28 Conditional Expressions in BSL 103

This rule states that a conditional expression starts with an opening parenthesis
and the keyword cond. Afterwards, there is 1 or more stanzas delimited by square
brackets. Each stanza contains two expressions. The first expression is a condition
and must evaluate to a Boolean. Think of this expression as a question whose
answer is either true or false. The second expression is called the consequence
and is only evaluated if the corresponding condition evaluates to #true. Think of
this expression as the value of the conditional expression when the answer to the
corresponding question is true. The last stanza in a conditional is called the default
stanza and contains in square brackets the keyword else and a single expression. This
expression represents the default value of the conditional. The default expression is
only evaluated if the conditions in all the other stanzas evaluate to #false.
The mathematical function speed-change(a-speed) is translated into BSL
syntax as follows:
(define (speed-change-bsl a-speed)
(cond [(too-fast? a-speed) 'decrease]
[(too-slow? a-speed) 'increase]
[else 'steady]))
The stanzas of a conditional are evaluated from top to bottom. For each stanza the
condition is evaluated first. If the condition evaluates to #true then the value of the
consequence is the value of the conditional. If the condition evaluates to #false
then evaluation continues with the next stanza. If the default stanza is reached, then
the default expression is evaluated to obtain the value of the conditional expression.
For example, for speed-change-bsl, if too-fast? evaluates to #true then the
value of the conditional is 'decrease. If it evaluates to #false then evaluation
continues with the next stanza. If too-slow? evaluates to #true then the value of
the conditional is 'decrease. If it evaluates to #false then evaluation continues
with the next stanza. The next stanza is the else stanza and, therefore, the default
expression is evaluated making the value of the conditional 'steady.
BSL provides shorthand when there are only two varieties of data. That is, short-
hand may be used when only the default stanza and one other stanza is needed. The
shorthand syntax is called an if-expression:

expr ::= (if expr expr expr)

This rule states that an if-expression is formed by an open parenthesis, three ex-
pressions, and a closing parenthesis. The first expression is called the condition and
must evaluate to a Boolean. If the condition is #true then the second expression is
evaluated to obtain the value of the if-expression. Otherwise, the third expression
is evaluated to obtain the value of the if-expression.
Consider, for example, translating the absolute value mathematical function into
BSL. In mathematical syntax the function is defined as follows:

a-num if a-num >= 0
abs-value(a-num) =
-a-num otherwise
104 5 Making Decisions

Observe that there are only two varieties of numbers for this function: nonnegative
and negative. Only two varieties means that an if-expression may be used to translate
it to BSL syntax:
(define (abs-value-bsl a-num)
(if (>= a-num 0)
a-num
(* -1 a-num)))
If the condition, (>= a-num 0), evaluates to #true then the value of the if-
expression is a-num. If the condition evaluates to #false then the value of the
if-expression is (* -1 a-num).

** Ex. 55 — Write a program to decide the speed change for a car if the
maximum speed is 120 kilometers per hour and the minimum speed is 50
kilometers per hour.

** Ex. 56 — Implement the following mathematical function in BSL:

⎧
⎪
⎨a-num
2 if a-num < 0
f(a-num) = a-num + 5 if anum < 5
⎪
⎩ a-num
e otherwise

29 Designing Functions to Process Data with Variety

When problem analysis reveals that data with variety needs to be processed then a
data definition must be created. Given that there is variety in the data, any function
that processes this type of data requires a conditional expression in its body. A
conditional expression is needed to determine which of the data varieties is being
processed. For each variety an expression for the value of the function needs to be
developed. A problem solver must also develop a function template to capture the
structural similarities among all functions that process the defined data type. Finally,
the number of tests must be greater than or equal to the number of varieties in the
data. In addition to at least one test per variety, it is also good practice to test border
cases that delimit varieties.
Let us examine poem verses as an example. First, we must choose how to rep-
resent a verse. We may, for example, represent a verse as a string. Some poets
feel that it is good practice to limit the length of each verse to 35 characters. A
verse with more than 35 characters is considered too long. A verse with 15 to 35
characters is considered fine. A verse with less than 15 characters is considered
too short. Based on this description, a data definition for a verse is formulated as
29 Designing Functions to Process Data with Variety 105

Fig. 43 Template for functions on a verse

;; verse ... ...
;; Purpose: ...
(define (f-on-verse a-verse ...)
(cond [(> (string-length a-verse) 35) ...]
[(<= 15 (string-length a-verse) 35) ...]
[else ...])

;; Expressions for sample computations

(define VARIETY1-CONSTANT ...)
(define VARIETY2-CONSTANT ...)
(define VARIETY3-CONSTANT ...)

;; Tests using sample computations

(check-expect (f-on-verse ...) VARIETY1-CONSTANT)
(check-expect (f-on-verse ...) VARIETY2-CONSTANT)
(check-expect (f-on-verse ...) VARIETY3-CONSTANT)
..
.

;; Test using sample values

(check-expect (f-on-verse ...) ...) ;; test for verse of length 35
(check-expect (f-on-verse ...) ...) ;; test for verse of length 15
..
.

follows:
;; A verse is either:
;; 1. A string of length greater than 35
;; 2. A string of length 15 to 35
;; 3. A string of length less than 15
The data definition for a verse informs problem solvers that any function that pro-
cesses a verse must have a conditional in its body that determines the variety of the
input verse. In addition, it informs problem solvers that at least 3 tests are needed:
one for each variety. Remember, we say at least because it is always good practice
to test boundary values. In this case, 5 tests are reasonable: one for each variety,
one for length 35, and one for length 15. It is important to note that verse vari-
eties are mutually exclusive. This means that no verse can be part of more than one
variety.
Based on the above data definition, observe that all functions that process a verse
share these features unique to verses:
1. A signature that has at least a verse as an input type.
2. A conditional in the body that determines if the given verse’s length is greater
than 35, between 15 and 34, or less than 15.
3. Sample expressions, if any, for each variety that is used to compute a value.
4. One test for each sample expression
5. Sample value tests including tests for borderline cases of length 35 and 15.
106 5 Making Decisions

This leads to the function template in Fig. 43. Observe that the signature includes a
verse as input and that each stanza in the skeleton’s body has a Boolean expression to
determine the variety of the verse. The default stanza, of course, does not explicitly
state that its Boolean expression is (< (string-length a-verse) 15). This
is unnecessary because verse varieties are mutually exclusive. Mutual exclusion
guarantees that if the first two Boolean expressions are false then the verse’s length
is less than 15. Stated differently:
¬(> (string-length a-verse) 35) ∧
¬(<= 15 (string-length a-verse) 35)
⇒
(< (string-length a-verse) 15)
This logical expression is stating that if the length of a verse is not greater than 35 and
it is not between 15 and 35 then it is less than 15. Finally, observe that the template
suggests 3 sample expressions and sample computation tests (one for each variety)
and 2 sample computation tests (one for each boundary value). The important point
to remember that there must be at least one test for each variety. More tests, of course,
may be added in the interest of clarity.
This function template can be specialized to express the solution to any problem
that requires processing a verse. Consider the problem of computing a string to
describe the length of a verse. To solve the problem, the function must decide
which constant string describing its variety to return: "Too Long", "Fine", or
"Too Short". Given that a verse is not processed to create any of these constant
strings, there are no sample expressions to describe how a verse is used to compute
these strings. If there are no sample expressions, there are also no tests using sample
computations.
The function’s signature, purpose, and header are:
;; verse → string
;; Purpose: Determine if the given verse is too long, fine,
;; or too short
(define (verse-type a-verse)
Observe that the signature uses the type, verse, defined by the data definition above.
Once a type is defined by a data definition it may be used in signatures. Signatures,
therefore, may contain types defined by BSL or by a data definition the programmer
creates. Further observe that the signature only has one input and, therefore, the
function only has one parameter. Finally, observe that the name of the function is
suggestive of its purpose and the name of the parameter is suggestive of the value it
represents.
Given that there are no sample expressions to test (as noted above), the tests using
sample values must be specialized to include a test for each variety of verse and for
each borderline length. Sample tests are:
;; Tests using sample values
(check-expect
(verse-type "Here is a sigh to those who love me,")
"Too Long")
29 Designing Functions to Process Data with Variety 107

Fig. 44 Program to determine verse type

;; A verse is either: 1. A string of length greater than 35
;; 2. A string of length 15 to 35
;; 3. A string of length less than 15
#| Funtion template for verse
;; verse ... --> ...
;; Purpose: ...
(define (f-on-verse a-verse ...)
(cond [(> (string-length a-verse) 35) ...]
[(<= 15 (string-length a-verse) 35) ...]
[else ...]))
;; Expressions for sample computations
(define VARIETY1-CONSTANT ...) (define VARIETY2-CONSTANT ...)
(define VARIETY3-CONSTANT ...)
;; Tests using sample computations
(check-expect (f-on-verse ...) VARIETY1-CONSTANT)
(check-expect (f-on-verse ...) VARIETY2-CONSTANT)
(check-expect (f-on-verse ...) VARIETY3-CONSTANT)
;; Test using sample values
(check-expect (f-on-verse ...) ...) ;; test for verse of length 35
(check-expect (f-on-verse ...) ...) ;; test for verse of length 15 |#

;; verse --> string

;; Purpose: Determine if the given verse is too long, fine, or too short
(define (verse-type a-verse)
(cond [(> (string-length a-verse) 35) "Too Long"]
[(<= 15 (string-length a-verse) 35) "Fine"]
[else "Too Short"]))
;; Tests using sample values
(check-expect (verse-type "Here is a sigh to those who love me,")
"Too Long")
(check-expect (verse-type "And a smile to those who hate") "Fine")
(check-expect (verse-type "Sorry for fate") "Too Short")
(check-expect (verse-type "The Battle of Culloden started now,") "Fine")
(check-expect (verse-type "Flaming heavens") "Fine")

(check-expect
(verse-type "And a smile to those who hate")
"Fine")
(check-expect (verse-type "Sorry for fate") "Too Short")
(check-expect
(verse-type "The Battle of Culloden started now,")
"Fine") ;; verse length 35
(check-expect
(verse-type? "Flaming heavens")
"Fine") ;; verse length 15
108 5 Making Decisions

Fig. 45 The design recipe for decision-making functions

1. Create data definitions with at least one having mutually exclusive varieties.
2. Develop a function template for each data definition.
3. Outline the computation.
4. Define constants for the value of sample expressions for each variety and name the differences.
5. Write the function’s signature and purpose.
6. Write the function’s header.
7. Write tests for each variety.
8. Write the function’s body.
9. Run the tests and, if necessary, redesign.

The next step is to specialize the body of the function in the template. For each
verse variety the proper string needs to be returned. The specialized body is:
(cond [(> (string-length a-verse) 35) "Too Long"]
[(<= 15 (string-length a-verse) 35) "Fine"]
[else "Too Short"]))
The complete program is displayed in Fig. 44. To make Fig. 44 easier to read the
comments including the data definition and the function template are displayed using
an italic font.
The development of verse-type suggests a series of steps that guide the de-
velopment of a decision-making function. Figure 45 displays the design recipe
for decision-making functions. This design recipe is a refinement of the general
design recipe for functions in Fig. 28. Therefore, the steps ought to feel familiar.
Step 1 requires the development of data definitions. Of these, at least one must
have varieties that are mutually exclusive. Step 2 requires the development of a
function template. The function’s body must be a conditional that has a stanza for
each variety. The Boolean expressions to determine the variety of the input are
part of the function’s body in the template. In addition, there must be at least one
test outlined for each data variety. Commonly (but not always), sample expression
tests are used to test each variety and sample value tests are used to test boundary
values. These first two steps are part of what is called data analysis and do not
have to be repeated for every problem being solved using the data type defined.
That is, these steps are performed once and the template may be used multiple
times.
The rest of the steps are taken to solve a specific problem. These are the steps
that need to be repeated for each problem solved. These steps specialize the func-
tion template. Step 3 requires an outline of how the function’s value is computed.
Step 4 requires the specialization of constant definitions for the values of sample
expressions. The sample expression illustrates how an answer is computed by pro-
cessing a given variety. The differences are named and serve as parameters to a
function definition. If a variety is not processed to formulate an answer, then no
sample expression is written. Steps 5 and 6 specialize the signature, the purpose
statement, and the function header. Step 7 requires the specialization of tests. There
must be at least one test for each data variety. Tests ought to also be thorough and,
29 Designing Functions to Process Data with Variety 109

Fig. 46 Function templates for data with variety

;; A vdata is either:
;; 1. Variety 1 ;; A vdata is either:
.. ;; 1. Variety 1
;; . ;; 2. Variety 2
;; N. Variety N
;; vdata . . . ... ;; vdata . . . ...
;; Purpose: . . . ;; Purpose: . . .
(define (f-on-vdata a-vdata . . .) (define (f-on-vdata a-vdata . . .)
(cond [<Variety 1 Test> ...] (if <Variety 1 Test>
.. ...
. ...))
[<Variety N-1 Test> ...]
[else ...])) ;; Sample expressions
;; Sample expressions (define VARIETY1-CONST . . .)
(define VARIETY1-CONST . . .) (define VARIETY2-CONST . . .)
..
.
(define VARIETYN-CONST . . .) ;; Tests using sample computations
;; Tests using sample computations (check-expect
(check-expect (f-on-vdata <variety 1> . . .)
(f-on-vdata <variety 1> . . .) VARIETY1-CONST)
VARIETY1-CONST) (check-expect
.. (f-on-vdata <variety 2> . . .)
. VARIETY2-CONST)
(check-expect
(f-on-vdata <variety N> . . .) ;; Tests using sample values
VARIETYN-CONST) (check-expect
;; Tests using sample values (f-on-vdata <variety i> . . .) . . .)
(check-expect ...
(f-on-vdata <variety i> . . .) . . .)
...

(a) Function Template Using cond (b) Function Template Using if

therefore, test boundary values between varieties. Write tests that use the constants
defined for sample computations and tests that use sample values. Step 8 requires the
specialization of the function’s body. Fill in the expressions for the answer of each
variety one at a time. Step 9, as before, requires running the tests and redesigning if
necessary.
The design recipe for decision-making functions informs us that data variety plays
a central role in problem solving. For example, the number of sample expressions,
of stanzas in a conditional, and of tests is proportional to the number of varieties in
the data. That is, the shape of the data influences the shape of a solution/program.
This suggests the function templates displayed in Fig. 46. Figure 46a displays the
function template for data with more than two varieties. Figure 46b displays the
function template for data with two varieties. In both, the number of constants for
sample expressions, of tests, and of needed expressions in the body of the function
are equal to the number of varieties. It is, of course, reasonable to increase the
110 5 Making Decisions

number of constants and tests for more thorough testing or to add clarity to the
program.
To illustrate the steps of the design recipe we will explore several different types
of data that have variety. It is impossible to outline all imaginable types of data with
variety. The goal here is to illustrate how to solve problems with several common
data type patterns that have variety.

* Ex. 57 — Write a program to compute a verse whose length is in [15..35]

from a given verse. If the given verse is too long, create a new verse by dropping
the letters in excess of 35 at the end of the given verse. If the verse is too short,
create a new verse by padding it with blanks at the end to make its length 15.
Otherwise, return the given verse.

* Ex. 58 — Implement a program to determine if a verse is printable. A verse

is printable if it is not too long. Carefully consider if a conditional is needed.
Do you need a conditional to compute a Boolean function?

30 Enumeration Types

A data definition that lists all possible values is called an enumeration type. To a
programmer this means that the conditional in a function that processes this type of
data only needs to distinguish the cases listed in the data definition. This is done by
checking for equality with the values listed in the data definition. Although this data
type represents the simplest form of variety, it may be cumbersome to use as the
number of varieties grows.
To illustrate the design process using an enumerated type consider creating
an animation for of a traffic light. We design our program for a simplified traf-
fic light that only changes colors from green to yellow to red to green and so
on. That is, the possibilities of a flashing red or a flashing yellow are not in-
cluded the design. Based on this there are only three possible traffic light images,
which may be defined as constants. Each image is created by overlaying the three
lights over a background. For example, the three images may be defined as fol-
lows:
(define BACKGROUND (rectangle 60 180 'solid 'black))

(define R-ON (overlay (above (circle 25 'solid 'red)

(square 10 'solid 'transparent)
(circle 25 'outline 'yellow)
(square 10 'solid 'transparent)
(circle 25 'outline 'green))
BACKGROUND))
30 Enumeration Types 111

(define Y-ON (overlay (above (circle 25 'outline 'red)

(square 10 'solid 'transparent)
(circle 25 'solid 'yellow)
(square 10 'solid 'transparent)
(circle 25 'outline 'green))
BACKGROUND))

(define G-ON (overlay (above (circle 25 'outline 'red)

(square 10 'solid 'transparent)
(circle 25 'outline 'yellow)
(square 10 'solid 'transparent)
(circle 25 'solid 'green))
BACKGROUND))
Each constant for a traffic light has a single light on denoted by a solid circle and
two lights off denoted by outline circles. There is a small space between the lights
obtained by drawing a transparent square.
To create an animation, the animate syntax defined in the universe teachpack
is used. When an animate expression is evaluated a clock is started that ticks 28
times per second. The programmer must write a function that takes as input a tick:
the value of the clock (the number of ticks since the simulation started) and that
returns the image to display. To stop a simulation, click Stop in DrRacket or close
the simulation window. The value of an animate expression is the value of the clock
when the animation is stopped.
Let us use a top-down design strategy given that the needed functions are not
known. What is known, however, is that clock ticks and a traffic light (which is
yet to be defined) must be processed. This is the starting point for the top-down
design strategy. To solve this problem, a programmer may decide that a given clock
tick is first transformed to a number that represents a traffic light. Observe that a
traffic light is not defined as an image. The number representing a traffic light is
then used to select the traffic light image. It is necessary to carefully think about
how a clock tick may be transformed to a traffic light. Given that there are only three
images, we may use three numbers. We need a mechanism to map a tick to one of
the three traffic light numbers. If we use 0, 1, and 2 to represent a traffic light, then
modular arithmetic may be used to map a tick to a traffic light. Observe that the
remainder of any tick by 3 is always 0, 1, or 2. Now, all that is left is developing data
definitions that attach meaning to each of these numbers chosen to represent a traffic
light.
The data analysis steps of the design recipe may be satisfied as follows:
STEP 1
We may define a tick and traffic light as follows:
A tick is an integer greater than or equal to 0.

;; A traffic light (tl) is either

;; 1. 0 --means the green light is on
112 5 Making Decisions

;; 2. 1 --means the yellow light is on

;; 3. 2 --means the red light is on

Observe that if the traffic light is increased by 1 (remainder 3) the next light
is the correct one. For example, increasing from 0 to 1 (remainder 3) means
that the traffic light changes from green to yellow. Similarly, incrementing
2 (remainder 3) results in 0 meaning that the traffic changes from red to
green.
STEP 2
The function template for tick is:
;; tick ... → ...
;; Purpose: ...
(define (f-on-tick a-tick) ...)

;; Sample expressions for f-on-tick

(define TICK-V0 ...)
..
.
(define TICK-VN ...)

;; Tests using sample computations for f-on-tick

(check-expect (f-on-tick ...) TICK-V0)
..
.
(check-expect (f-on-tick ...) TICK-V0)

;; Tests using sample values for f-on-tick

(check-expect (f-on-tick ...) ...)

The function template for tl is:

;; tl ... --> ...
;; Purpose: ...
(define (f-on-tl a-tl)
(cond [(= a-tl 0) ...]
[(= a-tl 1) ...]
[else ...]))

;; Sample expressions for f-on-tl

(define TL-0 ...)
(define TL-1 ...)
(define TL-2 ...)

;; Tests using sample computations for f-on-tl

(check-expect (f-on-tl ...) TL-0)
30 Enumeration Types 113

(check-expect (f-on-tl ...) TL-1)

(check-expect (f-on-tl ...) TL-2)

;; Tests using sample values for f-on-tl

(check-expect (f-on-tl ...) ...)

There is no variety in the data definition for tick. Therefore, f-on-tick does not
have a conditional. No decision needs to be made. The number of tests is also
arbitrary as there are no specific values that must be tested.
On the other hand, the data definition for tl has variety. Observe that there
is a conditional in the body of f-on-tl. There is a stanza for each vari-
ety of tl. The tests for each variety are defined here. The template also sug-
gests writing a sample expression and a corresponding test for each variety of
tl.
Now that the steps for data analysis have been completed, we can start solving
the problem of creating functions for the traffic light animation. We know that a
function to process ticks is needed. This function must return an image of a traffic
light. Starting with Step 3, the following the design recipe yields:
STEP 3
Given a tick, two values need to be computed. From a tick a tl value must be
computed. From a tl value an image must be computed. The computation of these
values is deferred to yet unwritten functions. The function tick->tl converts a
tick to a tl. The function image-of-tl converts a tl into a traffic light image.
STEP 4
To specialize the sample expressions, pick three different tick values such that
each maps to a different traffic light image. Specializing tests in this manner
guarantees to illustrate how a clock tick is mapped to each of the possible images.
Here are some sample expressions:
;; Sample expressions for draw-tick
(define TICK12-IMG (image-of-tl (tick->tl 12)))
(define TICK25-IMG (image-of-tl (tick->tl 25)))
(define TICK32-IMG (image-of-tl (tick->tl 32)))

The only difference among the three sample expressions is the value for tick. The
name for this difference is a-tick.
STEP 5
The signature and purpose statement are specialized as:

;; tick → image
;; Purpose: Compute the traffic light image for the
;; given tick
114 5 Making Decisions

STEP 6
The function header is specialized to:
(define (draw-tick a-tick)

STEP 7
The tests are specialized as follows:

;; Tests using sample expressions for ticks to images

(check-expect (draw-tick 12) TICK12-IMG)
(check-expect (draw-tick 25) TICK25-IMG)
(check-expect (draw-tick 32) TICK32-IMG)

;; Tests using sample values for ticks to images

(check-expect (draw-tick 77) R-ON)
(check-expect (draw-tick 99) G-ON)
(check-expect (draw-tick 241) Y-ON)

The sample value tests illustrate that the function works for more than three
predefined computations.
STEP 8
The body of the function is specialized as follows:
(image-of-tl (tick->tl a-tick))

STEP 9
All tests pass.
The result of Step 9 is expected for now. For the design to be complete all tests
must pass after the auxiliary functions are designed and implemented.
Top-down design has revealed that two auxiliary functions, tick->tl and
image-of-tl, are needed. Each is designed independently of the other. It does
not matter which is designed first. Let us start with tick->tl. Here is an example
of how to satisfy the steps of the design recipe:
STEP 3
Given a tick, the corresponding tl is given by the remainder of the tick and 3.
STEP 4
These are specialized sample expressions to illustrate how each variety of tl is
computed from a tick value:

;; Sample expressions for tick->tl

(define TL-0 (remainder 33 3))
(define TL-1 (remainder 77 3))
(define TL-2 (remainder 152 3))
30 Enumeration Types 115

The only difference among the three sample expressions is the value for tick. The
variable for this difference is a-tick.
STEP 5
The specialized signature and purpose statement are:

;; tick → tl
;; Purpose: Convert the given tick to a tl

STEP 6
The specialized function header is:
(define (tick->tl a-tick)

STEP 7
The specialized tests are:

;; Tests for tick->tl using sample expressions

(check-expect (tick->tl 33) TL-0)
(check-expect (tick->tl 77) TL-1)
(check-expect (tick->tl 152) TL-2)

;; Tests for tick->tl using sample values

(check-expect (tick->tl 0) 0)
(check-expect (tick->tl 451) 1)
(check-expect (tick->tl 182) 2)

STEP 8
The body of the function is:
(remainder a-tick 3)

STEP 9
All tests pass.
The design of tick->tl did not reveal the need for any new auxiliary functions.
Therefore, the only remaining task is the design of image-of-tl. For this function,
the presentation of the design is changed. Instead of outlining the result each step of
the design recipe one at a time, the changes made to the template for functions on tl
is directly presented.
This function converts a given tl to an image. We also observe that a tl is only
used to decide which image to return. Since a tl is not used to compute a value there
are no sample expressions or tests using sample expressions to write. Based on these
observations, the initial template specialization looks as follows:
116 5 Making Decisions

;; tl → image
;; Purpose: Return the traffic light image for the given tl
(define (image-of-tl a-tl . . .)
(cond [(= a-tl 0) . . .]
[(= a-tl 1) . . .]
[else ...]))

;; Tests for image-of-tl using sample values

(check-expect (image-of-tl 0) . . .)
(check-expect (image-of-tl 1) . . .)
(check-expect (image-of-tl 2) . . .)
Observe that despite not having tests using sample computations, there is still at least
one test for every variety of tl.
This rest of the specialization is fairly straight-forward. Our design has already
specified what image corresponds to each instance of tl. The final specialization
yields:
;; tl → image
;; Purpose: Return the traffic light image for the given tl
(define (image-of-tl a-tl)
(cond [(= a-tl 0) G-ON]
[(= a-tl 1) Y-ON]
[else R-ON]))

;; Tests using sample values

(check-expect (image-of-tl 0) G-ON)
(check-expect (image-of-tl 1) Y-ON)
(check-expect (image-of-tl 3) R-ON)

The final step to complete the traffic light simulation program is to require the
universe teachpack and to write the animate expression. Figure 47 displays the
structure of the program. Elements in angle brackets have been omitted from the
figure due to space limitations. It should be clear, however, what needs to be filled in
from all the design steps illustrated above. The second line in the program requires
the universe teachpack. The last line in the program is telling DrRacket to animate
the program using the draw-tick function. Congratulations! You have written your
first animation. Run the program. What do you think?

* Ex. 59 — A domesticated mammal is either a dog, a cat, or a horse. Design

and implement a program to compute the number of mammary glands of a
domesticated mammal.
* Ex. 60 — Design and implement a program that squares even digits and that
doubles odd digits.
30 Enumeration Types 117

Fig. 47 Traffic light animation program

(require 2htdp/image)
(require 2htdp/universe)

<Traffic Light Image Constant Definitions>

<Data Definition and function template for tick>
<Data Definition and function template for tl>

;; tick tl
;; Purpose: Convert the given tick to a tl
(define (tick->tl a-tick) (remainder a-tick 3))

<Sample expressions for ticks->tl>

<Tests for tick->tl>

;; tl image
;; Purpose: To return the traffic light image for the given tl
(define (image-of-tl a-tl)
(cond [(= a-tl 0) G-ON]
[(= a-tl 1) Y-ON]
[else R-ON]))

<Sample expressions for image-of-tl>

<Tests for image-of-tl>

;; tick image
;; Purpose: Compute the traffic light image for the given tick
(define (draw-tick a-tick)
(image-of-tl (tick->tl a-tick)))

<Sample expressions for draw-tick>

<Tests for draw-tick>

(animate draw-tick)

* Ex. 61 — A sequential circuit known as a flip-flop can be on (set) or off

(reset). When the flip-flop is on the next state is off. When the flip-flop is off the
next state is on. Design and implement a program to compute the next state of
a flip-flop.

** Ex. 62 — Design and implement an animation for a pedestrian traffic light.

A pedestrian traffic light displays one of two messages: Walk or Don’t Walk.
118 5 Making Decisions

31 Interval Types

Running the traffic light simulation reveals that the light changes too fast–28 times
per second. The program is well-designed and works from a certain perspective but
needs to be refined. That is, it needs to be improved. This is our first dive into the
process of iterative refinement. It is fairly clear that we need the light to change at a
slower pace so that the human eye can appreciate the changes. Instead of changing
the image 28 times per second, the animation may change the traffic light image, for
example, twice per second. This means that, instead of changing every clock tick,
the image needs to change every 14 clock ticks.
This refinement means that the data definition of tl must be updated. Instead of
defining tl as 0, 1, or 2, tl could define as follows:
;; A traffic light (tl) is either
;; 1. 0 --means the green light is on
;; 2. 1 --means the green light is on
..
.
;; 13. 13 --means the green light is on
;; 14. 14 --means the yellow light is on
..
.
;; 27. 27 --means the yellow light is on
;; 28. 41 --means the red light is on
..
.
;; 41. 41 --means the red light is on
This data definition leads to a function definition whose conditional has 42 stan-
zas. That is quite large and error-prone during development. Sometimes such data
definitions are unavoidable. Observe, however, that there is something special about
this (long) data definition. There is a lot of repetition. This suggests that there is an
abstraction that needs to be defined.
Many consecutive numbers have the same meaning. For example, the values from
0 through 13 all mean that the green light is on. We can borrow an idea from high
school mathematics called an interval. We can say, for example, that when tl is a
member of [0..13] it means that the green light is on. Equivalently, we can say that tl
is a member of [0..14), (-1..13], or (-1..14). Remember that a square bracket means
included and a parenthesis means not included. This leads to the following data
definition:
;; A traffic light (tl) is a member of either
;; 1. [0..13] --means the green light is on
;; 2. [14..27] --means the yellow light is on
;; 3. [28..41] --means the red light is on
This is called an interval type. An interval type defines orderable data by a set of
categories. For example, tl is defined using three intervals. The intervals must be
31 Interval Types 119

Fig. 48 Refined tick->tl for the traffic light animation

#|
;; STEP 3
;; A tl is the remainder of a tick by 42.

STEP 5:
;; tick --> tl
;; Purpose: Convert the given tick to a tl |#

;; STEPS 6 and 8
(define (tick->tl a-tick)
(remainder a-tick 42))

;; STEP 4: Sample expressions for tick->tl

(define TL-0 (remainder 11 42))
(define TL-1 (remainder 60 42))
(define TL-2 (remainder 123 42))

;; STEP 7: TESTS
;;Tests using sample expressions
(check-expect (tick->tl 11) TL-0)
(check-expect (tick->tl 60) TL-1)
(check-expect (tick->tl 123) TL-2)

;; STEP 7: Tests using sample values

(check-expect (tick->tl 0) 0)
(check-expect (tick->tl 325) 31)
(check-expect (tick->tl 650) 20)

mutually exclusive. That is, an instance of the data type must be a member of only
one interval.
Refining a data definition means that the program must also be refined. Any
function that manipulates or creates an instance of the refined data type and its
tests must be updated. To determine which functions to update, a programmer must
look for expressions that manipulate or create an instance of the updated data type.
Functions that are good candidates to be updated are those with signatures that refer
to the refined data type. Examining the signatures in the traffic light simulation
program reveals:
tick->tl: tick → tl Needs to be updated, because it creates an instance of tl.
image-of-tl: tl → image Needs to be updated, because it makes a decision based
on an instance of tl.
draw-tick: tick → image Doest not need to be updated. This function does not
manipulate nor creates an instance of tl.
The refinements necessary involve updating expressions and tests. The tick->tl
function must convert a tick into a tl. Finding the remainder of the given tick by 3
is no longer correct because a tick must be converted to an integer in [0..41].
Modular arithmetic, however, can still be used. Now, the remainder of a tick by 42
must be computed. Figure 48 displays the updated tick->tl function. The sample
120 5 Making Decisions

Fig. 49 Refined image-of-tl for the traffic light animation

#|
STEP 3:
Determine the interval and return the corresponding image

STEP 5:
;; tl --> image
;; Purpose: To return the traffic light image for the given tl
|#

;; STEPS 6 and 8
(define (image-of-tl a-tl)
(cond [(<= 0 a-tl 13) G-ON]
[(<= 14 a-tl 27) Y-ON]
[else R-ON]))

;; STEP 4: There are no sample expressions as a tl is not used to

;; compute a new value. It is only used to make a decision.

;; STEP 7: Tests using sample values

(check-expect (image-of-tl 10) G-ON)
(check-expect (image-of-tl 22) Y-ON)
(check-expect (image-of-tl 37) R-ON)

expressions and the body of the function now use 42 instead of 3. The tests have
been updated in order to have at least one test for each variety of tl using the new
data definition.
Figure 49 displays the refined version of image-of-tl. The image-of-tl func-
tion processes an instance of tl. This means that the conditional expression must
be refined to correspond to the new data definition of tl. Observe that the tests in-
side the conditional now determine what interval contains a-tl. The unit tests for
image-of-tl are also refined to include at least one test for each interval of tl.
An important lesson to absorb is that data in the real or an imaginary world may
be represented in different ways (like tl). Part of the design process is to select a
representation. The representation chosen influences how a problem solver thinks
about a program. Exploring different representation may provide insight into the
problem. It is also important to keep in mind that how data is represented may have
a profound impact on performance.

* Ex. 63 — Design and implement a program to compute the interest rate of a

savings account. The interest rate of a savings account depends on its balance.
For a balance larger than $1,000,000 the interest rate is 1.11%. For a balance
larger than $100,000 the interest rate is 1.05%. For a balance larger than $50,000
the interest rate is 1%. For a balance less than $50,000 the interest rate is 0.5%.
32 Itemization Types 121

* Ex. 64 — Design and implement a program to compute a letter grade on an

exam. Less than 60 points is an F. 60-69 points is a D. 70-79 points is a C. 80-89
points is a B. 90-100 points is an A.

* Ex. 65 — For the traffic light simulation three images are defined: G-ON,
Y-ON, and R-ON. Rewrite the traffic light simulation using the following data
definition:
;; A traffic light (tl) is either
;; 1. G-ON --means the green light is on
;; 2. Y-ON --means the yellow light is on
;; 3. R-ON --means the red light is on

** Ex. 66 — A sequential circuit known as a flip-flop can be on (set) or off

(reset). When the flip-flop is on the next state is off. When the flip-flop is off the
next state is on. Design and implement an animation of a flip-flop that changes
state every second.

*** Ex. 67 — Design and implement an animation for a pedestrian traffic light.
A pedestrian traffic light displays one of two messages: Walk or Don’t Walk.
The Walk message should be displayed for 4 s before it changes. The Don’t Walk
message should be displayed for 2 s before it changes.

32 Itemization Types

Enumeration types capture variety by exhaustively listing all possible values. Interval
types capture variety using a set of intervals to classify orderable data. What is
done if both a listing of values and intervals are needed? As it turns out this is
sometimes needed. To define such data an itemization type is used. An instance of
an itemization type may be a specific value or a member of an interval type. Observe
that an itemization type is a generalization of enumeration and interval type. When
all varieties are specific values an itemization type is called an enumeration type.
When all varieties are intervals an itemization type is called an interval type.
To illustrate how to design a program using an itemization type consider the prob-
lem of doubling or rotating an image using single alphanumeric or arrow keystrokes.
The image is rotated 90, 180, or 270◦ using, respectively, the right, down, and left
arrow keys. The image is doubled using the up arrow key. Nothing is done with the
image on an alphanumeric keystroke.
Before proceeding with the design of the solution it is necessary to know how keys
are represented and compared. In the universe teachpack, all keys are represented
with a string. For example, the z key is represented by "z". The right, down, left, and
up keys are represented, respectively, with the strings "right", "down, "left", and
"up". The key=? function is a predicate used to compare keys for equality. Do not
122 5 Making Decisions

Fig. 50 Data definitions for change image and alphanumeric keystrokes

STEP 1: DATA DEFINITIONS
;; An alphanumeric keystroke (aks) is a member of either:
;; 1. ["a".."z"] --means a letter keystroke
;; 2. ["0".."9"] --means a numeric keystroke

;; A change image keystroke (ciks) is either:

;; 1. "right" --means rotate image 90 degrees clockwise
;; 2. "down" --means rotate image 180 degrees clockwise
;; 3. "left" --means rotate image 270 degrees clockwise
;; 4. "up" --means double image size
;; 5. aks --means do nothing to image

mistake key=? as being the same as string=?. The former only compares strings
that represent keys while the latter compares any two strings.
To facilitate the design, assume that there is a constant ROCKET-IMG whose value
is a rocket image created using the functions in the image teachpack. Figure 50
displays Step 1 of the design recipe. An alphanumeric keystroke is an interval type.
There are two intervals: one for letters and one for numbers. Nothing else is an
alphanumeric keystroke. A change image keystroke is an itemization type. It has
four literal values: one for each arrow. It also has one interval type: an alphanumeric
keystroke. Observe that a data definition may refer to another data definition. The
meaning of each variety is also clearly stated for each variety within each data
definition.
Figures 51 and 52 display Step 2 of the design recipe. In Fig. 51, the template for
ciks has a function skeleton with a conditional that distinguishes the variety of the
value received as input. The template also suggests defining a constant and a test for
the value of a sample expression for each variety of ciks. In addition, it suggests the
definition of a sample value test for each variety of ciks. In Fig. 52, the template for
aks has a function skeleton with a conditional that distinguishes between the varieties
of aks. Two sample expressions along with corresponding test are suggested: one
for a letter keystroke and one for a digit keystroke. In the same manner, two sample
value tests are suggested by the template.
Figure 53 displays Steps 3 through 8 of the design recipe for the function that
processes a ciks. Step 3 explains that the rotate and scale functions are used
to compute new images. Step 4 illustrates how these two functions are used to
compute a new image using the ROCKET-IMG constant. Step 5 results in the spe-
cialized signature and purpose statement. The signature states the function takes
two inputs: an image and a ciks. The purpose statement indicates that the given
image is rotated, doubled, or left untouched. The result of step 6 reflects the re-
quirements stated by the signature. The two parameters are named in a manner that
suggest the type of their value. The name of the function is suggestive of its pur-
pose. Step 7 results in tests using sample computations and using sample values.
The tests with sample computations illustrate that the function computes the same
value as the sample expressions. The tests with sample values use images created
32 Itemization Types 123

Fig. 51 Function template for ciks

;; ciks ... --> ...
;; Purpose: ...
(define (f-on-ciks a-ciks ...)
(cond [(key=? a-ciks "right") ...]
[(key=? a-ciks "down") ...]
[(key=? a-ciks "left") ...]
[(key=? a-ciks "up") ...]
[else ...]))

;; Sample expressions for f-on-ciks

(define CIKS-RIGHT ...)
(define CIKS-DOWN ...)
(define CIKS-LEFT ...)
(define CIKS-UP ...))
(define CIKS-ALPHANUM ...))

;; Tests using sample computations for f-on-ciks

(check-expect (f-on-ciks "right" ...) CIKS-RIGHT)
(check-expect (f-on-ciks "down" ...) CIKS-DOWN)
(check-expect (f-on-ciks "left" ...) CIKS-LEFT)
(check-expect (f-on-ciks "up" ...) CIKS-UP)
(check-expect (f-on-ciks <aks> ...) CIKS-ALPHANUM)

;; Tests using sample values for f-on-ciks

(check-expect (f-on-ciks "left" ...) ...)
(check-expect (f-on-ciks "right" ...) ...)
(check-expect (f-on-ciks "down" ...) ...)
(check-expect (f-on-ciks "up" ...) ...)
(check-expect (f-on-ciks <aks> ...) ...)

Fig. 52 Function template for aks

;; aks ... --> ...
;; Purpose: ...
(define (f-on-aks an-aks ...)
(cond [(string<=? "a" an-aks "b") ...]
[(string<=? "0" an-aks "9") ...]))

;; Sample expressions for f-on-aks

(define AKS-LETTER ...)
(define AKS-NUM ...)

;; Tests using sample computations for f-on-aks

(check-expect (f-on-aks <aks1> ...) AKS-LETTER)
(check-expect (f-on-aks <aks2> ...) AKS-NUM)

;; Tests using sample values for f-on-aks

(check-expect (f-on-aks <aks3> ...) ...)
(check-expect (f-on-aks <aks4> ...) ...)

using functions from the image teachpack. The third test uses flip-vertical.
This test passes because vertically flipping an equilateral triangle results in the
124 5 Making Decisions

Fig. 53 The change image program

;; STEP 3: Use the functions rotate and scale to compute a new image
;; STEP 5: image ciks image
;; Purpose: Rotate 90/180/270 degrees, double or untouch image
;; STEP 6 and 8
(define (change-img an-img a-ciks)
(cond [(key=? a-ciks "right") (rotate 90 an-img)]
[(key=? a-ciks "down") (rotate 180 an-img)]
[(key=? a-ciks "left") (rotate 270 an-img)]
[(key=? a-ciks "up") (scale 2 an-img)]
[else an-img]))
;; STEP 4: Sample expressions for change-img
(define RRIGHT-RCKT (rotate 90 ROCKET-IMG))
(define RDOWN-RCKT (rotate 180 ROCKET-IMG))
(define RLEFT-RCKT (rotate 270 ROCKET-IMG))
(define DOUBLE-RCKT (scale 2 ROCKET-IMG))
;; STEP 7: TESTS
;; Tests using sample computations for change-img
(check-expect (change-img ROCKET-IMG "right") RRIGHT-RCKT)
(check-expect (change-img ROCKET-IMG "down") RDOWN-RCKT)
(check-expect (change-img ROCKET-IMG "left") RLEFT-RCKT)
(check-expect (change-img ROCKET-IMG "up") DOUBLE-RCKT)
(check-expect (change-img ROCKET-IMG "m") ROCKET-IMG)
;; Tests using sample values for change-img
(check-expect (change-img (rectangle 10 30 solid red) "left")
(rectangle 30 10 solid red))
(check-expect (change-img (ellipse 75 35 outline pink) "right")
(ellipse 35 75 outline pink))
(check-expect (change-img (triangle 25 solid gold) "down")
(flip-vertical (triangle 25 solid gold)))
(check-expect (change-img (square 15 outline green) "up")
(square 30 outline green))
(check-expect (change-img (star 10 solid yellow) "y")
(star 10 solid yellow))

same image as rotating the triangle 180◦ . In general, however, this is not true.
For example, vertically flipping a right triangle does not result in the same image
as rotating the triangle 180◦ . Finally, Step 8 specializes the body of the function.
The expressions for the consequence in each stanza of the conditional are based
on the sample expressions and on the last test using a sample value. For the for-
mer, the literal ROCKET-IMG is substituted with, an-img, the image parameter of
the function. For the latter, observe that the input image is the same as the output
image. This means that in the default stanza the value of the parameter must be
returned.
The final noteworthy observation is that the design of change-img did not reveal
the need for auxiliary functions. This means that the template for aks was never used
to design a function. That is fine. Not every problem requires every template to be
specialized. Other problems involving ciks may very well require the specialization
33 What Have We Learned in This Chapter? 125

of the aks function template. Think of the templates developed as different tools in a
toolbox. Sometimes you only need a hammer. Other times you only need a wrench.
Yet other times you need both.

** Ex. 68 — Refine the change image program to flip the given image vertically
for a letter keystroke and to flip the given image horizontally for a number
keystroke. Hint: There is no need to change any data definitions for this problem.

** Ex. 69 — Write a program to provide feedback to a student on their quiz

performance. If their average is 100%, then the feedback is "Excellent
Performance". If their average is greater than or equal to 90%, then the
feedback is "Very Good Performance". If their average is greater than or
equal to 80%, then the feedback is "Good Performance". If their average is
greater than or equal to 71%, then the feedback is "Just OK Performance".
If their average is 70%, then the feedback is "Borderline Performance".
If their average is greater than or equal to 60%, then the feedback is "Poor
Performance". If their average is less than or equal to 59%, then the feedback
is "Failing Performance".

33 What Have We Learned in This Chapter?

The important lessons of Chap. 5 are summarized as follows:

• Compound functions arise from data having variety and having to decide which
expression to evaluate depending on the variety of the input.
• Compound functions in BSL are written with a conditional expression in the body.
• The BSL provides two types of conditional expressions: cond- and if-expressions.
• The BSL syntax explored is displayed in Fig. 54.
– Syntax for data types defined by BSL is omitted.
• Data definitions are needed to describe data that has variety.
• The design recipe for functions that make decisions requires:
– A data definition to describe data that has variety
– A function template for every data definition
– At least one test for every variety of data
• Signatures may use types described by a data definition.
• Function templates are specialized to write functions.
126 5 Making Decisions

Fig. 54 Chapter 5 BSL grammar

program ::= {expr test def}*
def ::= (define <variable name> expr)
::= (define (<name> <name>+) expr)
test ::= (check-expect expr expr)
::= (check-within expr expr expr)
expr ::= number
::= string
::= \#<character constant>
::= <character+>
::= #true
::= #false
::= <image>
::= (<function> expr+)
::= (and expr expr expr* )
::= (or expr expr expr* )
::= (cond [expr expr]+
[else expr])
::= (if expr expr expr)

• There are 3 type categories to describe variety:

– Enumeration types
– Interval types
– Itemization types
Chapter 6
Aliens Attack Version 1

We all know that video games are fun to play. Designing them can also be fun despite
being complex programs. To manage this complexity, video games are developed
using the process of iterative refinement. Adding features to a video game in a
piecemeal manner allows the problem solver to conquer the complexity in small
steps. For example, for Aliens Attack we have already solved the problem of creating
cis (remember, ci is defined as a character image in 4).
Before proceeding, it is a good idea to get a handle on exactly what a video
game is. In many ways, a video game is similar to an animation. For instance,
scenes are flickered fast enough to create the illusion of movement. Video games,
however, allow players to interact with the animation. This interaction may change
the evolution of the game. The evolution of the game changes when a computer
event occurs. A computer event includes any action like pressing a key, the clock
ticking, or clicking the mouse. Players change the evolution of the game through, for
example, key pressing or mouse actions. For instance, in Aliens Attack a player may
use the left arrow and the right arrow keys to move the rocket. Like a simulation, the
evolution of a video game may also change by events not controlled by the player
like a clock tick. In Aliens Attack, for example, the aliens move every time the clock
ticks. It is now clear that functions called event handlers (or simply handlers) are
needed to process computer events.
The ability to design programs that make decisions allows us to implement video
games. Handlers need to make decisions. For example, the handler to process a
keystroke must distinguish what key has been pressed. If the right arrow key is
pressed, then the handler moves the rocket right. If the left arrow key is pressed, then
the handler moves the rocket left. Clearly, data definitions are needed to describe the
keystroke events that change the evolution of the game.
In addition to providing programmers with the ability to write animations, the
universe teachpack provides programmers with the ability to write video games in
BSL. This teachpack is an API. It provides the necessary syntax to associate handlers
with computer events and it defines the signature that these handlers must have.
Using the universe teachpack is an exercise in programming with (the abilities

© The Author(s), under exclusive license to Springer Nature Switzerland AG 2022 127
M. T. Morazán, Animated Problem Solving, Texts in Computer Science,
[Link]
128 6 Aliens Attack Version 1

provided by and the restrictions imposed by) an API. Programming with an API is
a good skill to develop because programming with APIs is standard practice.

34 The Universe Teachpack

The universe teachpack requires the development of a data definition for a world.
A world is all the values that may change during the evolution of the game. Some of
the values may be de displayed when a game image is computed. Other values may
only be needed to advance the evolution of the game. In a fully implemented Aliens
Attack game, for example, the aliens and the direction the aliens travel in are part of
the world. The aliens are displayed in a game image as in Fig. 37. The direction the
aliens travel in, on the other hand, is not displayed in the image.
There is a special expression to run a video game called a big-bang expression
(bb-expr). This expression allows the programmer to provide the initial value of the
world and the handlers needed to advance the evolution of the game. The big-bang
expression syntax is:
bb-expr ::= (big-bang expr bb-clause+)
bb-clause ::= [to-draw function]
[on-key function]
[on-tick function]
[stop-when function]
[name expr]
..
.
A bb-expr has in parenthesis the keyword big-bang followed by an expression
that must evaluate to a world value followed by one or more bb-clauses (big-
bang clauses). A bb-clause associates an event with a handler function to pro-
cess the event. Each bb-clause has in square brackets an event describer (e.g.,
to-draw, on-tick, and stop-when) and a handler for the event. For example,
[to-draw draw-world] states to use draw-world to render the image of the
world, [on-key process-key] states to use process-key to process a key stroke,
[on-tick process-tick] states to use process-tick to process a clock tick,
and [stop-when game-over?] states to use game-over? to detect the end of
the game (or interactive simulation). The only required bb-clause is the to-draw
clause. The only clause that does not follow this scheme is the name clause. This
clause associates a name with the world. The expr in this clause must evaluate to a
string or symbol. The name appears in title of the scene. The vertical dots mean that
there are other varieties of bb-clauses. The big-bang documentation describes all
the possible bb-clauses. An important thing to remember is that a bb-clause may
not be repeated. For example, a bb-expr may only have one to-draw bb-clause.
The universe API also specifies the signature and purpose of the handlers. Each
handler serves a specific purpose like creating a scene, computing the next world
after a clock tick or keystroke, or detecting the end of the game/simulation. For
34 The Universe Teachpack 129

Fig. 55 Fish image

example, the following table displays the signature and purpose for four handlers:
on-draw: world → scene
Purpose: To create the world’s scene
on-key: world key → world
Purpose: To return the world after the given keystroke
on-tick: world → world
Purpose: To return the world after a clock tick
stop-when: world → Boolean
Purpose: To determine if the game/animation has ended
This means that we must write handlers that satisfy the above signatures. To a
programmer this suggest using a top-down design strategy to write a video game. Start
with the functions needed by the big-bang expression. Design auxiliary functions
as their need is revealed.
To illustrate the use of the universe teachpack consider developing an interactive
animation to rotate the image of the fish displayed in Fig. 55. The user may rotate
the image of the fish to point up, down, left, or right using the arrow keys. In Fig. 55
the fish is pointing up. If the user presses the up arrow key, then the image remains
unchanged. If the user presses the right arrow, then the image is rotated to make the
fish point right. A similar action takes place pressing the other arrow keys. If the
user presses any other key, then the fish image remains unchanged regardless of the
direction the fish is pointing in. For example, if the fish is pointing left and the m key
is pressed, then the fish image remains unchanged.
To start, first define the constants that are needed. A scene is needed. A scene is
defined as follows:
A scene is a WIDTH x HEIGHT image
Here WIDTH and HEIGHT are positive integer constants. Presumably, a scene is large
enough to contain the fish image. Otherwise, the fish image is truncated.
The fish image is also a constant. The following code defines all the scene and
fish image constants:
(define WIDTH 200)
(define HEIGHT 200)
(define E-SCENE-COLOR 'black)
(define E-SCENE (empty-scene WIDTH HEIGHT E-SCENE-COLOR))
130 6 Aliens Attack Version 1

(define FISH-W 46)

(define FISH-H 76)
(define FISH-BODY-IMG
(place-image
(ellipse 30 60 'solid 'green)
(/ FISH-W 2)
(/ FISH-H 2)
(rectangle FISH-W FISH-H 'solid E-SCENE-COLOR)))

(define FISH-EYE-IMG (overlay (circle 2 'solid 'lightred)

(circle 4 'solid 'white)))

(define FISH-TAIL-IMG (overlay/xy

(circle 20 'solid 'black)
0
-10
(circle 20 'solid 'green)))

(define FISH-IMG (place-image FISH-EYE-IMG

(- (/ FISH-W 2) 3)
(/ FISH-H 4)
(place-image
FISH-TAIL-IMG
(/ FISH-W 2)
(+ (/ FISH-H 4/3) 15)
FISH-BODY-IMG)))
Observe that the fish image is created using a divide and conquer strategy. First, the
body, eye, and tail images are defined. Second, these three images are combined to
create the fish image.
After defining the first set of constants (others may be needed as the solution
progresses), the design process starts with writing a run function that has a bb-expr
as its body. By convention in this textbook, the run function is used to start a game
or interactive animation and its bb-expr has a name clause. The central question to
start is what computer events need to be processed. For this interactive animation
only keystrokes need to be processed. Therefore, the run function may be written as
follows:
;; string → world
;; Purpose: To run the interactive fish simulation
(define (run a-name)
(big-bang
INIT-WORLD
[on-draw draw-world] ;; world → scene
[on-key process-key] ;; world key → world
[name a-name]))
34 The Universe Teachpack 131

The body of run gives us a starting point for the design process. The initial world,
INIT-WORLD, needs to be defined. For this, a world data definition is needed. The
function handlers draw-world and process-key and any needed auxiliary func-
tions need to be designed. Recall that the signatures of the handlers are defined by
the universe API (noted as comments in run). For the key-processing handler, a
data definition is needed for the keys that affect the evolution of the animation.
We start with the data definition for the keys that affect the evolution of the anima-
tion. Remember that every data definition means the development of a corresponding
function template. A fish keystroke is defined as follows:
A fish keystroke (fks) is either:
1. "up" --means fish in up direction
2. "right" --means fish in right direction
3. "down" --means fish in down direction
4. "left" --means fish in left direction

;; fks . . . → . . .
;; Purpose: . . .
(define (f-on-fks a-fks . . .)
(cond [(string=? a-key "up") . . .]
[(string=? a-key "right") . . .]
[(string=? a-key "down") . . .]
[else . . .]))

;; Sample Expressions for f-on-fks

(define UP-FKS-VAL . . .)
(define RIGHT-FKS-VAL . . .)
(define DOWN-FKS-VAL . . .)
(define LEFT-FKS-VAL . . .)

;; Tests using sample computations for f-on-fks

(check-expect (f-on-fks "up" . . .) UP-FKS-VAL)
(check-expect (f-on-fks "right" . . .) RIGHT-FKS-VAL)
(check-expect (f-on-fks "down" . . .) DOWN-FKS-VAL)
(check-expect (f-on-fks "left" . . .) LEFT-FKS-VAL)

;; Tests using sample values for f-on-fks

(check-expect (f-on-fish-ks . . .) . . .)
...
Observe that an fks is an enumeration type. Further observe that four sample ex-
pressions and four tests using sample computations are needed as required when
designing with data that has variety: one for each variety.
The above data definition now allows for a refinement of the key data definition.
Now, keys may be distinguished between keys that are an fks and those that are not.
The refined data definition is:
132 6 Aliens Attack Version 1

A key is either:
1. fks
2. not an fks

;; key . . . → . . .
;; Purpose: . . .
(define (f-on-key a-key . . .)
(if (fks? a-key)
...
. . .))

;; Sample Expressions for f-on-key

(define FKS-VAL . . .)
(define NON-FKS-VAL . . .)

;; Tests using sample computations for f-on-key

(check-expect (f-on-key . . .) FKS-VAL)
(check-expect (f-on-key . . .) NON-FKS-VAL)
...

;; Tests using sample values for f-on-key

(check-expect (f-on-key . . .) . . .)
...
Observe that key is an itemization type. There is something different, however, in the
formulation of this data definition. The second variety not an fks does not look
like an enumeration nor does it look like an interval. It is, however, an enumeration
type. Specifically, it is the complement of fks. That is, any key that is not an fks is
of the second variety. The use of not is simply shorthand for the large number of
non-fks keys. Given that keys are itemized in two varieties, the body of f-on-key is
an if-expression. This if-expression tests if a given key is an fks using an auxiliary
function that needs to be designed. Finally, observe that the number of sample
expressions and of tests using sample computations matches the number of varieties.
The final data definition we need is for the world. There are many ways to define
the world for this animation. Perhaps, the simplest way to define the world is to make
it an fks as follows:
A world is an fks

;; world . . . → . . .
;; Purpose: . . .
(define (f-on-world a-world)
. . .(f-on-fks a-world). . .)

;; Sample Expressions for f-on-world

(define WORLD-VAL . . .))
34 The Universe Teachpack 133

;; Tests using sample computations for f-on-world

(check-expect (f-on-world . . .) WORLD-VAL)
...

;; Tests using sample values for f-on-world

(check-expect (f-on-world . . .) . . .)
...
Observe that there is no variety in the world data definition. Therefore, the body
of f-on-world is not a conditional expression. This brings to the forefront an
important observation. The world and fks are different. They are different data
definitions. Therefore, at least two functions are needed to process a world: one to
process a world and one to process an fks. This is why there is a call to f-on-fks in
the body of f-on-world. You may ask yourself why two are needed when a world
is the same as fks. Indeed, this is true for this version of the simulation. However,
always design thinking that in the future you or someone else may need to refine
the program. For example, the data definition of the world may be refined. If your
solution already includes separate world-processing and fks-processing functions,
then the process of refinement is easier. A change in the world data definition does
not affect the functions that process an fks and only functions that process a world
need to be refined. On the other hand, if a single data definition is used, then a change
in the world data definition requires refinements to all functions that process a world
and functions for an fks need to be designed.
With the data definitions and function templates completed, the design of the
elements needed by the big-bang expression is next. The first is INIT-WORLD. Ask
yourself what value the initial world needs to be or you want it to be. In this interactive
animation, the initial direction the fish is pointing in is arbitrary. Therefore, the initial
world value may be defined as follows:
(define INIT-WORLD "up")
Next, focus turns to designing draw-world. This function processes a world.
Therefore, we specialize the template for functions on the world. Ask yourself what
this function needs to do. According the universe API, this function needs to
compute a scene. This means that the fish image must be placed in E-SCENE. This is
enough information to start specializing the template as follows:
;; world → scene
;; Purpose: To draw the world in the E-SCENE
(define (draw-world a-world)
. . .(f-on-fks a-world). . .)

;; Sample Expressions for draw-world

(define WORLD-VAL1 (place-image <an up fish image>
(/ WIDTH 2)
(/ HEIGHT 2)
E-SCENE))
134 6 Aliens Attack Version 1

(define WORLD-VAL2 (place-image <a left fish image>

(/ WIDTH 2)
(/ HEIGHT 2)
E-SCENE))

;; Tests using sample computations for draw-world

(check-expect (draw-world . . .) WORLD-VAL)
(check-expect (draw-world . . .) WORLD-VAL2)
...

;; Tests using sample values for draw-world

(check-expect (draw-world . . .) . . .)
...
The template is first specialized by substituting f-on-world with draw-world and
by creating sample expression to place a fish image in E-SCENE. Placing the fish
image in the middle of the empty scene is a reasonable choice. The fish image to
display depends on the fks value the world represents. This is a different type of
value and an auxiliary function is used to compute it. The template can now be
specialized to:
;; world → scene
;; Purpose: To draw the world in the E-SCENE
(define (draw-world a-world)
(place-image (compute-fish-img a-world)
(/ WIDTH 2)
(/ HEIGHT 2)
E-SCENE))

;; Sample Expressions for draw-world

(define WORLD-VAL1 (place-image
(compute-fish-img INIT-WORLD)
(/ WIDTH 2)
(/ HEIGHT 2)
E-SCENE))

(define WORLD-VAL2 (place-image

(compute-fish-img "left")
(/ WIDTH 2)
(/ HEIGHT 2)
E-SCENE))

;; Tests using sample computations for draw-world

(check-expect (draw-world "up") WORLD-VAL1)
(check-expect (draw-world "left") WORLD-VAL2)
34 The Universe Teachpack 135

;; Tests using sample values for draw-world

(check-expect (draw-world "down") )

(check-expect (draw-world "right") )

Observe that the only difference among the sample expressions is the value of the
world. This tells us that draw-world does not need any additional parameters. This
allows the sample expressions and the sample tests using sample computations to
be written. The final specialization step is for the tests using sample values. It is
reasonable to use the untested world values: "up" and "down". Now, all the steps
of the design recipe are satisfied except running the tests.
Focus now turns to the design of compute-fish-img. This function processes
an fks and, therefore, the template to process an fks value is specialized:
;; fks . . . → image
;; Purpose: Compute the fish image for the given fks
(define (compute-fish-img a-fks . . .)
(cond [(string=? a-key "up") . . .]
[(string=? a-key "right") . . .]
[(string=? a-key "down") . . .]
[else . . .]))

;; Sample Expressions for compute-fish-img

(define UP-FKS-VAL FISH-IMG)
(define RIGHT-FKS-VAL (rotate 270 FISH-IMG))
(define DOWN-FKS-VAL (rotate 180 FISH-IMG))
(define LEFT-FKS-VAL (flip-vertical (rotate 90 FISH-IMG)))

;; Tests using sample computations for compute-fish-img

(check-expect (compute-fish-img "up" . . .) UP-FKS-VAL)
(check-expect (compute-fish-img "right" . . .) RIGHT-FKS-VAL)
(check-expect (compute-fish-img "down" . . .) DOWN-FKS-VAL)
(check-expect (compute-fish-img "left" . . .) LEFT-FKS-VAL)

;; Tests using sample values for compute-fish-img

(check-expect (compute-fish-img . . .) . . .)
...
This function returns an image and this is reflected in the signature and the purpose
statement. The sample expressions compute a value for each variety. Observe that
each computes a value for a fish image using only constant values and that the
conditional only needs the value of the given fks. Thus, compute-fish-img does not
require more parameters. Finally, observe that all fks values have a sample expression
136 6 Aliens Attack Version 1

and that all possible returned fish images are produced by these. Therefore, there
is no need for tests using sample values. Based on these observations, the final
specialization step yields:
;; fks → image
;; Purpose: Compute the fish image for the given fks
(define (compute-fish-img a-fks)
(cond [(string=? a-key "up") FISH-IMG]
[(string=? a-key "right") (rotate 270 FISH-IMG)]
[(string=? a-key "down") (rotate 180 FISH-IMG)]
[else (flip-vertical (rotate 90 FISH-IMG))]))

;; Sample Expressions for f-on-fks

(define UP-FKS-VAL FISH-IMG)
(define RIGHT-FKS-VAL (rotate 270 FISH-IMG))
(define DOWN-FKS-VAL (rotate 180 FISH-IMG))
(define LEFT-FKS-VAL (flip-vertical (rotate 90 FISH-IMG)))

;; Tests using sample computations for compute-fish-img

(check-expect (compute-fish-img "up") UP-FKS-VAL)
(check-expect (compute-fish-img "right") RIGHT-FKS-VAL)
(check-expect (compute-fish-img "down") DOWN-FKS-VAL)
(check-expect (compute-fish-img "left") LEFT-FKS-VAL)

Once again, observe that template specialization completes all the steps of the
design recipe except running the tests.
The function process-key, as its name suggests, processes a key. This means
the template for functions on a key must be specialized. This function always takes
as input a world and a key and returns a world according to the universe API. If
the given key is an fks, then the next world is the given key. Otherwise, the world is
unchanged. The initial specialization yields:
;; world key → world
;; Purpose: To return the next world based on the
;; given key
(define (process-key a-world a-key . . .)
(if (fks? a-key)
...
. . .))

;; Sample Expressions for process-key

(define KEY-VAL "down")
(define KEY-VAL2 "left")
(define NON-KEY-VAL "up")

;; Tests using sample computations for process-key

(check-expect (process-key . . .) KEY-VAL)
(check-expect (process-key . . .) KEY-VAL2)
(check-expect (process-key . . .) NON-KEY-VAL)
...
34 The Universe Teachpack 137

;; Tests using sample values for process-key

(check-expect (process-key . . .) . . .)
...
The sample expressions by themselves have an obscured meaning in this case. The
expression for KEY-VAL is for inputs "right" and "down" to process-key. The
expression for KEY-VAL2 is for inputs "up" and "left" to process-key. The
expression for NON-KEY-VAL is for inputs "up" and "j" to process-key. From
these sample expressions we can surmise that if the given key is an fks, then the new
world is the given key. Otherwise, the next world is the value of the given world. The
final specialization is:
;; world key → world
;; Purpose: To return the next world based on the
;; given key
(define (process-key world a-key)
(if (fks? a-key)
a-key
a-world))

;; Sample Expressions for process-key

(define KEY-VAL "down")
(define KEY-VAL2 "left")
(define NON-KEY-VAL "up")

;; Tests using sample computations for process-key

(check-expect (process-key "right" "down") KEY-VAL)
(check-expect (process-key "up" "left") KEY-VAL2)
(check-expect (process-key "up" "j") NON-KEY-VAL)

;; Tests using sample values for process-key

(check-expect (process-key "left" "up") "up")
(check-expect (process-key "left" "right") "right")
(check-expect (process-key "left" "left") "left")
(check-expect (process-key "left" "v") "left")
(check-expect (process-key "right" "x") "right")
The tests using sample values aim to be thorough. The first two test the fks values
not present in the tests using sample computations. The third test shows that if the
given fks is the same as the given world, then the world is unchanged. The last two
tests use two different non-fks values.
The final task is to design fks? Ask yourself how to determine if a key is an fks.
If the key is any fks value, then the answer is true. Otherwise, the answer is false.
Following the steps of the design recipe yields:
138 6 Aliens Attack Version 1

;; key → Boolean
;; Purpose: Determine if the given key is an fks
(define (fks? a-key)
(if (or (key=? a-key "right")
(key=? a-key "down")
(key=? a-key "left")
(key=? a-key "up"))
#true
#false))

;; Sample Expressions for fks?

(define FKS-RVAL #true)
(define NON-FKS-VAL #false)

;; Tests using sample computations for fks?

(check-expect (fks? "right") FKS-RVAL)
(check-expect (fks? "m") NON-FKS-VAL)

;; Tests using sample values for fks?

(check-expect (fks? "up") #true)
(check-expect (fks? "down") #true)
(check-expect (fks? "left") #true)
(check-expect (fks? "q") #false)
(check-expect (fks? "t") #false)
The predicate has the structure suggested by the template. It has an if-expression
in its body. The tests using sample values add thoroughness by making sure all fks
values are tested and more non-fks values are tested. However, fks? is interesting. It
always returns the value of the test. This means that the if-expression is not needed
and fks? may be simplified to:
;; key → Boolean
;; Purpose: Determine if the given key is an fks
(define (fks? a-key)
(or (key=? a-key "right")
(key=? a-key "down")
(key=? a-key "left")
(key=? a-key "up")))
Certainly, this version of fks? is easier to understand and, therefore, a preferable
solution. The important lesson here is that when designing a predicate for data with
variety consider using a Boolean expression instead of a conditional. Remember,
the template is suggestive of the structure of functions. Sometimes the result of
specializing the template can be simplified.
The only step of the design recipe left is to run the tests. Make sure all the tests
pass.
35 A Video Game Design Recipe 139

* Ex. 70 — Why is flip-vertical used in compute-fish-img?

** Ex. 71 — Redesign the fish interactive simulation using the following data
definition for the world:
A world is an image, either:

1.

2.

3.

4.

* Ex. 72 — Consider the following data definition:

A signed integer is either in:
1. (-∞..-1]
2. [1..∞)

Write a predicate to determine if an integer is a signed integer. Simplify the

predicate as much as possible.

*** Ex. 73 — Write an interactive animation that echoes up to 80 lowercase

letter, space, or period keystrokes in a box. The simulation should stop with an
Enter keystroke.

35 A Video Game Design Recipe

This development suggests the design recipe for video game and interactive anima-
tions displayed in Fig. 56. Steps 1–3 are problem and data analysis that are performed
once. Step 1 requires a data definition for the elements that vary in a game. Step 2
140 6 Aliens Attack Version 1

Fig. 56 The design recipe for video game development

1. Create data definitions for the elements that vary.
2. Develop a function template and examples for each data definition.
3. Define the run function with no tests.

For a needed function:

4. Outline the computation.
5. Define constants for the value of sample expressions for each variety and name the differences.
6. Write the function’s signature and purpose.
7. Write the function’s header.
8. Write tests.
9. Write the function’s body.
10. Run the tests and, if necessary, redesign.

requires the development of a function template and of examples for each data def-
inition. If the defined data has variety, then at least one example for each variety is
needed. Step 3 requires the development of the run function. The body must be a
bb-expr. This function serves as a map to guide the top-down development of the
game. Ask yourself what events may affect the evolution of the game. There must be
a clause in the bb-expr for every event that may change the evolution of the game or
interactive simulation. This function is written without tests because it is only used
to initiate the game or simulation. It is not the solution to a problem. In fact, the run
function’s template may be defined as follows:
; string → world
; Purpose: To run the game
(define (run a-name)
(big-bang INIT-WORLD
[on-draw . . .]
[name a-name]
bb-clause∗))
The final clauses, of course, may not contain a repetition of any clause.
Steps 4–10 are performed for each function that is needed. This is done by
specializing the function template for the data being processed. These steps are the
same as those found in previous design recipes.

36 Adding the Rocket to Aliens Attack

The first refinement to Aliens Attack is to add the rocket. Figure 57 displays a scene
of the proposed new version of the video game. Before starting save your Aliens
Attack version 0 to a new file, say Aliens-Attack-v1. It is this new file that is to
be edited with refinements. The version 0 is kept as a safe back-up of work that has
been completed.
36 Adding the Rocket to Aliens Attack 141

Fig. 57 Aliens attack scene with a rocket

Recall that the rocket may move left to right without going off the edges of the
scene. Given that a rocket may exhibit changes as the game evolves, it needs to be
part of the world and, therefore, a data definition for a rocket is needed. Ask yourself
what changes about the rocket as the game advances. The characteristics that change
must be captured in the rocket’s data definition. At this point, it is important to
realize that a rocket is not the same as the image of the rocket. The image of the
rocket does not change as the rocket moves. When the rocket moves left or right the
rocket’s image-x changes. For example, if the image coordinates of the rocket are (5,
ROCKET-Y) and the rocket moves right, then the new image coordinates of the rocket
are (6, ROCKET-Y). That is, the rocket moves to the next image box to the right in
the scene. Observe, as noted in Chap. 6, that the rocket’s image-y is constant. Now
that the rocket’s changing characteristics are identified, the rocket’s data definition,
the template for functions on a rocket, and sample instances (rocket examples) may
be stated as follows:
#| A rocket is an image-x

;; Sample instances of rocket

(define ROCKET1 ...)
...
142 6 Aliens Attack Version 1

;; rocket . . . → . . .
;; Purpose: . . .
(define (f-on-rocket a-rocket . . .)
. . .(f-on-image-x a-rocket . . .) . . .)

;; Sample expressions for f-on-rocket

(define ROCKET1-VAL (f-on-rocket ROCKET1 . . .))
...

;; Tests using sample computations for f-on-rocket

(check-expect (f-on-rocket ROCKET1 . . .) ROCKET-VAL)
...

;; Tests using sample values for f-on-rocket

(check-expect (f-on-rocket . . .) . . .)
... |#

;; Sample instances of rocket

(define ROCKET1 7)
(define INIT-ROCKET (/ MAX-CHARS-HORIZONTAL 2))
Observe that to process a rocket the template suggests calling a function to process
an image-x. This design exhibits separation of concerns. Separation of concerns
reflects that solving a problem for one data type is different from solving a problem
for another data type. In this example, processing a rocket may require processing
an image-x. The processing of an image-x is done by a function to process an
image-x, not a function to process a rocket. Observe that the tests using sample
computations refer to the sample instances of a rocket and the values of sample
expressions. The tests using sample values do not refer to defined sample instances
or defined values for sample expressions. These tests are used to illustrate that a
function works for values not previously computed. Finally, when a data definition is
developed it is good practice to include at least one sample instance. In this example,
two sample instances of a rocket, ROCKET1 and INIT-ROCKET, are defined.
A similar piece of reasoning must be done to define the game’s world. Ask
yourself what may change as the game evolves. In this version of Aliens Attack, the
only characteristic that may change is the rocket. Therefore, the data definition of
the world, its function template, and sample instances may be stated as follows:
#| A world is a rocket

;; Sample instances of world

(define WORLD1 ...)

;; world . . . --> . . .
;; Purpose: . . .
(define (f-on-world a-world . . .)
. . .(f-on-rocket a-world . . .) . . .)
36 Adding the Rocket to Aliens Attack 143

;; Sample expressions for f-on-world

(define WORLD1-VAL . . .)

;; Tests using sample computations for f-on-world

(check-expect (f-on-world WORLD1 . . .) WORLD1-VAL)
...

;; Tests using sample values for f-on-world

(check-expect (f-on-world . . .) . . .)
... |#

;; Sample instances of world

(define WORLD1 ROCKET1)
(define INIT-WORLD INIT-ROCKET)
Observe that despite the world and the rocket being the same in this version of the
game, we use two different data definitions. A good designer always has a different
data definition for every data type. This makes it easier to make future refinements
to the game. We know that the data definition of the world will be expanded to
include, for example, the army of aliens. This expansion will be done without having
to revisit any code developed to manipulate a rocket. If we use a single definition,
then such an expansion would require writing new code for the world, the army of
aliens, and the rocket. Further observe that the template suggests that to process a
world the processing a rocket may be needed. Again, we see separation of concerns
in this design. Observe that, once again, the tests using sample computations refer to
previously defined constants. In contrast, once again, the tests using sample values
do not refer to previously defined constants. The sample worlds are defined using
the sample rockets.
Given that the player moves the rocket using keyboard it is necessary to define
what a key is. In this version of Aliens Attack the rocket is moved using the left and
right arrow keys. This suggests that a key may be defined as an itemization type. This
data definition highlights the keys that change the evolution of the game. The data
definition, function template, and sample instances for keys are defined as follows:
|# A key is either:
1. "right"
2. "left"
3. not "right" or "left"

;; Sample instances of key

(define KEY1 ...)
(define KEY2 ...)
(define KEY3 ...)
144 6 Aliens Attack Version 1

;; key . . . --> . . .
;; Purpose: . . .
(define (f-on-key a-key . . .)
(cond [(key=? a-key "right") . . .]
[(key=? a-key "left") . . .]
[else . . .]))

;; Sample expressions for f-on-key

(define KEY1-VAL . . .KEY1. . .)
(define KEY2-VAL . . .KEY2. . .)
(define KEY3-VAL . . .KEY3. . .)

;; Tests using sample computations for f-on-key

(check-expect (f-on-key KEY1 . . .) KEY1-VAL)
(check-expect (f-on-key KEY2 . . .) KEY2-VAL)
(check-expect (f-on-key KEY3 . . .) KEY3-VAL)
...

;; Tests using sample values for f-on-key

(check-expect (f-on-key . . .) . . .)
... |#

;; Sample instances of key

(define KEY1 "right")
(define KEY2 "left")
(define KEY3 "m")
Shorthand notation for the third key variety is used. The template suggests three
sample instances because there are three key varieties. In the body of f-on-key
there is a cond-expression to distinguish among the key varieties. As expected, the
tests using sample computations use the key sample instances and the values of the
sample expressions. The tests using sample values, on the other hand, do not used
defined values as expected.

* Ex. 74 — Develop function templates for ci, image-x, image-y, pixel-x, pixel-
y, and scene.

After completing steps 1 and 2 of the design recipe, we focus on the run template
specialization to complete step 3. The player moves the rocket using the left and
right arrows keys. This means that an on-key clause is also needed to process key
events. The specialization is as follows:
36 Adding the Rocket to Aliens Attack 145

; string → world
; Purpose: To run the game
(define (run a-name)
(big-bang INIT-WORLD
[on-draw draw-world]
[name a-name]
[on-key process-key]))
This states that the handler to render the game’s scene is draw-world and that the
handler to process key events is process-key.
Let us start by designing draw-world. To draw the world a rocket needs to be
drawn in the empty scene. The steps of the design recipe result in the following
specialization of the template for functions on a world:
;; world → scene
;; Purpose: To draw the world in E-SCENE
(define (draw-world a-world)
(draw-rocket a-world E-SCENE))

;; Sample expressions for draw-world

(define WORLD-SCN1 (draw-rocket INIT-WORLD E-SCENE))
(define WORLD-SCN2 (draw-rocket INIT-WORDLD2 E-SCENE))

;; Tests using sample computations for draw-world

(check-expect (draw-world INIT-WORLD) WORLD-SCN1)
(check-expect (draw-world INIT-WORLD2) WORLD-SCN2)

;; Tests using sample computations for draw-world

(check-expect (draw-world 0) )
(check-expect (draw-world (sub1 MAX-CHARS-HORIZONTAL))

)
146 6 Aliens Attack Version 1

The sample expressions maintain the separation of concerns by calling a rocket-

processing function to create the world’s scene. The only difference in the sample
expressions is the value of a world. Therefore, draw-world indeed only needs one
parameter. The requirement imposed by the universe API is met. The body of
draw-world uses the variable for the single difference instead of using a literal
value like the sample expressions. Observe that the tests using sample computations
use extrema values for the rocket data type. The design of draw-world awaits the
running of the tests.
The design of the auxiliary function draw-rocket is done by specializing the
template for functions on a rocket. This function draws the rocket’s ci in the given
scene using the given rocket as the image-x. Recall that we have already developed
the function draw-ci (see Chap. 6). The specialization of the template for functions
on a rocket yields:
;; rocket scene → scene
;; Purpose: To draw the rocket in the given scene
(define (draw-rocket a-rocket a-scene)
(draw-ci ROCKET-IMG a-rocket ROCKET-Y a-scene))

;; Sample expressions for draw-rocket

(define RSCN3 (draw-ci ROCKET-IMG 3 ROCKET-Y E-SCENE))

(define RSCN12 (draw-ci ROCKET-IMG 12 ROCKET-Y E-SCENE2))

;; Tests using sample computations for draw-rocket

(check-expect (draw-rocket 3 E-SCENE) RSCN3)
(check-expect (draw-rocket 12 E-SCENE2) RSCN12)

;; Tests using sample values for draw-rocket

(check-expect (draw-rocket 0 E-SCENE)

)
(check-expect (draw-rocket (sub1 MAX-CHARS-HORIZONTAL)
E-SCENE)

)
36 Adding the Rocket to Aliens Attack 147

The sample expressions use draw-ci to place the rocket’s ci at image coordinates
(3, ROCKET-Y) and (12, ROCKET-Y) in, respectively, E-SCENE and E-SCENE2.
The two differences among the sample expressions are abstracted and become the
parameters to draw-rocket. The tests using sample values, once again, test rocket
extrema values. There are no new auxiliary functions to design. Therefore, this
concludes the design of draw-world and its auxiliary functions.
The design of process-key is done by specializing the f-on-key template. The
universe API requires that the inputs be a world and a key. If the given key is
"right" or "left", then the next world is created by moving the rocket. Otherwise,
the next world is the given world. The specialization of the template yields:
;; world key → world
;; Purpose: Process a key event to return next world
(define (process-key a-world a-key)
(cond [(key=? a-key "right") (move-rckt-right a-world)]
[(key=? a-key "left") (move-rckt-left a-world)]
[else a-world]))

;; Sample expressions for process-key

(define KEY-RVAL (move-rckt-right INIT-WORLD))
(define KEY-LVAL (move-rckt-left INIT-WORLD))
(define KEY-OVAL INIT-WORLD2)

;; Tests using sample computations for process-key

(check-expect (process-key INIT-WORLD "right") KEY-RVAL)
(check-expect (process-key INIT-WORLD "left") KEY-LVAL)
(check-expect (process-key INIT-WORLD2 "m") KEY-OVAL)

;; Tests using sample values for process-key

(check-expect (process-key (sub1 MAX-CHARS-HORIZONTAL) "right")
(sub1 MAX-CHARS-HORIZONTAL))
(check-expect (process-key 0 "left") 0)
(check-expect (process-key 0 "o") 0)
(check-expect (process-key 11 ";") 11)
Observe that the need for two auxiliary functions is revealed: one to move the rocket
right and one to move the rocket left. Moving a rocket is done in a separate function
because it is a different data type. The sample expressions use the appropriate rocket-
moving function to compute the next world. The third sample expression captures
the idea that a rocket function is not called when the given key is not "right" or
"left" (like "m" in the third test using a sample computation). The first two tests
using sample values are written with extrema values to illustrate that the rocket does
not go off the scene. The last to tests are added for thoroughness.
The design of move-rckt-right requires clearly defining how to move a rocket
right. At a first glance, it may appear that adding 1 to the rocket suffices. Ask yourself,
however, can the rocket always be moved to the right. After designing process-key,
148 6 Aliens Attack Version 1

it is not difficult to see that when the rocket is MAX-CHARS-HORIZONTAL - 1 it

cannot move to the right. Adding 1 to MAX-CHARS-HORIZONTAL - 1 results in an
integer that is not a rocket. This means that a decision must be made to add or not to
add 1 to the given rocket. With this insight, the f-on-rocket template is specialized
as follows:
;; rocket → rocket
;; Purpose: Move the given rocket right
(define (move-rckt-right a-rocket)
(if (< a-rocket (sub1 MAX-CHARS-HORIZONTAL))
(add1 a-rocket)
a-rocket]))

;; Sample expressions for move-rckt-right

(define ROCKET-VAL3 (add1 3))
(define ROCKET-VALMAX (sub1 MAX-CHARS-HORIZONTAL))

;; Tests using sample computations for move-rckt-right

(check-expect (move-rckt-right 3) ROCKET-VAL3)
(check-expect (move-rckt-right (sub1 MAX-CHARS-HORIZONTAL))
ROCKET-VALMAX)

;; Tests using sample values for move-rckt-right

(check-expect (move-rckt-right 0) 1)
(check-expect (move-rckt-right 15) 16)
The sample expressions illustrate how rockets that may and may not move to the
right are computed. In the body of move-rckt-right a new rocket is created by
adding 1 only when the given rocket is not at the right edge of the scene. The tests
using sample values include an untested extrema value, 0, for the rocket type and
add an extra test for thoroughness.
A similar problem analysis leads to concluding that a conditional is needed to
decide when a rocket may be moved to the left. In this case, only when the rocket is
greater than or equal to 0. The template specialization results in:
;; rocket → rocket
;; Purpose: Move the given rocket left
(define (move-rckt-left a-rocket)
(if (> a-rocket 0)
(sub1 a-rocket)
a-rocket))

;; Sample expressions for move-rckt-left

(define ROCKET-VAL7 (sub1 7))
(define ROCKET-VAL0 0)
37 What Have We Learned in This Chapter? 149

;; Tests using sample computations for move-rckt-left

(check-expect (move-rckt-left 7) ROCKET-VAL7)
(check-expect (move-rckt-left 0) 0)

;; Tests using sample values for move-rckt-left

(check-expect (move-rckt-left (sub1 MAX-CHARS-HORIZONTAL))
(- MAX-CHARS-HORIZONTAL 2))
(check-expect (move-rckt-left 14) 13)
Once again, observe that the tests using sample values include an untested extrema
value, (sub1 MAX-CHARS-HORIZONTAL), for the rocket type and add an extra test
for thoroughness.
The final step of the design recipe is to run all the tests. Make sure that you do
not have any syntax errors and that all tests pass. Run the game and try moving the
rocket left and right.

** Ex. 75 — Redesign Aliens Attack version I using the following data defini-
tion for a rocket:
A rocket is an image-x such that it is either:
1. 0
2. (sub1 MAX-CHARS-HORIZONTAL)
3. (0..(sub1 MAX-CHARS-HORIZONTAL))

** Ex. 76 — Write an interactive simulation of a rocket flying down a scene

that stops when it reaches the bottom of the scene. If the user presses "u" the
rocket’s image points up. If the user presses "d" the rocket’s image points down.

*** Ex. 77 — Design an interactive traffic light simulation such that if the
player presses:
1."r" the traffic light goes to flashing red.
2."y" the traffic light goes to flashing yellow.
3."n" the traffic light goes to normal operation.

37 What Have We Learned in This Chapter?

The important lessons of Chap. 6 are summarized as follows:

• Video game and interactive animation programs require functions to process
computer events.
• The universe teachpack provides an API to program video games and interactive
animations.
• Programming with APIs is standard practice in Computer Science.
150 6 Aliens Attack Version 1

• The universe’s big-bang expression is used to run a video game and allows
a programmer to provide the world’s initial value and the handlers needed to
advance the game’s or animation’s evolution.
• Predicates for data types with varieties sometimes may be simplified by using a
Boolean expression instead of a conditional expression.
• The video game design recipe includes steps to:
– Develop data definitions and sample instances for every element that varies as
the game evolves.
– Develop a function template for every data definition.
– Develop a run function.
• Separation of concerns leads to functions that solve a problem for a single data
type and simplifies the process of iterative refinement.
• Developing video games is intellectually stimulating and exciting.