Chapter
3
Control Statements in
Karel
The technique of
defining new methods—as useful as
it is—does
not actually
enable Karel to solve any new
problems. Because each method name is merely a shorthand for a specific set of
commands, it is always possible to expand a program written as a series of method calls
into a single main program that
accomplishes the same task, although
the resulting program is likely to
be long
and difficult
to read.
The commands—no
matter whether they are written
as a single program or broken
down into a set of methods—are
still executed in a fixed
order that does not depend
on the
state of Karel’s world. Before
you can solve more
interesting problems, you need to
discover how to write programs
in which this strictly linear, step-by-step
order of operations does not
apply. In particular, you need to
learn several new features of
the Karel
programming language that make it possible
for Karel to examine its world and change its execution pattern accordingly.
Statements that affect the order in which a program executes commands are called
control statements.
Control statements generally fall into the following two
classes:
1. Conditional statements. Conditional statements specify that certain statements in a program
should be executed only if a particular condition
holds. In Karel, you specify
conditional execution using an if
statement.
2. Iterative statements. Iterative statements specify that certain statements in a program should be executed repeatedly, forming what programmers call a loop. Karel supports two different iterative statements: a for statement that is useful when you want to repeat
a set of commands a predetermined number of times and a while statement that is useful when you want to repeat
an operation as long as some condition holds.
This chapter introduces
each of these control statement forms
in the
context of Karel problems that illustrate the need for
each statement type.
Conditional statements
To get a sense of
where conditional statements might come in handy, let’s go back to the fillPothole program presented
at the end of Chapter 2. Before filling the pothole in the
fillPothole method, there are a few conditions that Karel might want to check. For example,
Karel might want to check to see if some other repair crew has already filled
the hole, which means that there is already a beeper on that corner. If so,
Karel does not need to put down a second one. To represent such checks in the
context of a program, you need to use the if statement, which ordinarily appears in the following form:
if (conditional
test) {
statements
to be executed only if the condition is true
}
The conditional test shown in the
first line of this pattern
must be replaced by one
of the
tests Karel can perform on
its environment.
The result
of that
conditional test is either true or false. If the test is true,
Karel executes the statements enclosed in braces; if the test is false, Karel
does nothing.
The tests that
Karel can perform are listed
in Table
1. Note
that each test includes an
empty set of parentheses, which
is used
as a syntactic marker in
Karel’s programming language to show
that
the test is being applied.
Note also that
every condition in the list has
a corresponding opposite.
For example, you can use the frontIsClear condition to check whether the path ahead of Karel is clear or the frontIsBlocked condition to see if
Table 1. Conditions that Karel
can test
Test Opposite What it checks
frontIsClear()
|
frontIsBlocked()
|
Is there a wall in front of Karel?
|
leftIsClear()
|
leftIsBlocked()
|
Is there a wall to Karel’s left?
|
rightIsClear()
|
rightIsBlocked()
|
Is there a wall to Karel’s right?
|
beepersPresent()
|
noBeepersPresent()
|
Are there beepers on this corner?
|
beepersInBag()
|
noBeepersInBag()
|
Any there beepers in Karel’s bag?
|
facingNorth()
|
notFacingNorth()
|
Is Karel facing north?
|
facingEast()
|
notFacingEast()
|
Is Karel facing east?
|
facingSouth()
|
notFacingSouth()
|
Is Karel facing south?
|
facingWest()
|
notFacingWest()
|
Is Karel facing west?
|
there is a wall
blocking the
way. The frontIsClear condition is true whenever frontIsBlocked is
false and vice versa. Choosing the right condition to use in a program requires you
to think
about the logic of the
problem and see which condition
is easiest
to apply.
You can use the if statement to modify the definition
of the fillPothole method so that
Karel puts down a beeper only
if there
is not
already a beeper on that corner.
To do
so, the conditional test you need is noBeepersPresent. If there are
no beepers present on the corner, Karel
should put down a new one.
If there
is already
a beeper there, Karel should do nothing.
The new definition of fillPothole, which checks
to make
sure that there is not already a beeper in the hole, looks like this:
private void fillPothole() {
turnRight();
move();
if (noBeepersPresent()) {
putBeeper();
} turnAround(); move();
turnRight();
}
The if statement in this example
illustrates several features common to all control
statements in Karel. The control
statement begins with a header, which indicates the type of control statement along with any additional information to control the program flow. In
this case, the header is
if (noBeepersPresent())
which shows that the statements
enclosed within the braces should be executed only if the noBeepersPresent test is true. The statements enclosed in braces represent the body of the control statement.
By
convention, the body of any
control statement is indented with
respect to the statements
that surround it. The indentation
makes it much easier to
see exactly which statements will be affected by
the control
statement. Such indentation is particularly
important when
the
body of a control statement
contains other control statements. For example,
you might want to make an additional test to see whether Karel had any beepers before trying
to put
one down.
To do
so, all
you would
need to do is add
a new if
statement
inside the existing one, like this:
if
(noBeepersPresent()) {
if (beepersInBag()) {
putBeeper();
}
}
In this example, the putBeeper command is executed
only if there is no beeper on the
corner and there are
beepers in Karel’s bag. Control
statements that occur inside other
control statements are said to be nested.
The
outcome of a decision in a program
is not
always a matter of whether to
do nothing
or perform
some set of operations. In some cases, you
need to choose between two alternative courses of action. For these cases, the if statement in Karel has an extended form that looks like this:
if (conditional test) {statements to be
executed if the condition is true
} else {
statements to be
executed if the condition is false
}
This form of the if statement is illustrated
by the method invertBeeperState, which picks up a beeper if there is one and
puts down a beeper if the corner is empty.
private void
invertBeeperState() {
if (beepersPresent()) {
pickBeeper();
} else {
putBeeper();
}
}
Iterative
statements
In solving Karel
problems, you will often find
that repetition is a necessary part
of your
solution. If you were
really going to program a robot
to fill
potholes, it would hardly be
worthwhile to have it fill just one. The value of having a robot perform
such a task comes from the fact
that the robot could repeatedly
execute its program to fill
one pothole
after another.
To
see how
repetition can be used in
the context
of a programming problem, consider the following stylized roadway in which the potholes are evenly spaced along 1st Street at
every even-numbered avenue:3
2 11 2 3 4 5 6 7 8 9 1 0 1 1
Your mission
is to write a program
that instructs Karel to fill all the
holes in this
road. Note that the
road reaches
a dead end after 11th Avenue,
which means that you have exactly
five holes to fill.
Since
you know
from this example that there
are exactly
five holes to fill, the
control statement that you need is a for statement, which specifies
that you want to repeat some
operation a predetermined number of times. The structure of the for statement appears complicated
primarily because it is actually
much more
powerful than anything Karel needs.
The only version of the for syntax that
Karel uses is
for (int i = 0; i < count; i++) {
statements to be
repeated
}
where count is an integer indicating the number of repetitions.
For example, if you want to change the fillPothole program so that it solves the more
complex problem of filling five evenly-spaced holes, all you have to do is
change the run method
as follows:
public void
run() {
for (int i = 0; i < 5; i++) {
move();
fillPothole();
move();
}
}
The for statement is useful only when you know in advance the number of repetitions
you need
to perform.
In most
applications, the number of repetitions
is controlled
by the
specific nature of the problem. For example, it seems unlikely that
a pothole-filling robot could always
count on there being exactly five potholes. It would be much better if Karel
could continue to fill holes until it encountered some condition that caused it
to stop, such as reaching the end of the street. Such a program would be more
general in its application and would work
correctly in either of the
following worlds as well as
any other
world in which the potholes were evenly spaced exactly two corners
apart:
3 3
2 1 1
1 2 3
1 2 3 4 5 6 7 8 9
To write a general program that works with any of these worlds, you need to use a
while statement. In Karel, a while statement has the following general form:
while (test)
{
statements to be
repeated
}
The test in
the header
line is chosen from the
set of
conditions listed in Table 1 earlier
in this
chapter. In this case, Karel
needs to check whether the
path in front is clear
by invoking the condition frontIsClear. If you use the frontIsClear condition in a while
loop, Karel will repeatedly
execute the loop until it hits a wall. The while statement therefore makes
it possible
to solve
the more
general problem of repairing a roadway, as long as the
potholes appear at every even-numbered corner and the end of the roadway is marked by a wall. The RoadRepairKarel class that accomplishes this task is shown in Figure
7.
Figure
7. Program to fill regularly spaced potholes in a roadway
/*
/*
* File: RoadRepairKarel.java
* --------------------------
* The RoadRepairKarel class fills a series of regularly
* spaced potholes until it reaches the end of the
roadway.
*/
import stanford.karel.*;
public class RoadRepairKarel extends
SuperKarel {
public void run() {
while (frontIsClear()) {
move();
fillPothole();
move();
}
}
/**
* Fills the hole beneath
Karel's current position by
* placing a beeper in the
hole. For this method to
* work correctly, Karel must be facing east immediately
* above the hole. When execution is complete, Karel
* will have returned to the same square and will again
* be facing east. This version of fillPothole checks to
* see if there is already a beeper present before putting
* a new one down.
*/
private void fillPothole() {
turnRight();
move();
if (noBeepersPresent()) {
putBeeper();
} turnAround(); move();
turnRight();
}
}
Solving
general problems
So far, the
various pothole-filling programs have not
been very
realistic, because they rely on
specific conditions—such as evenly spaced potholes—that are unlikely to be true
in the real world. If you want to write a more general program to fill potholes, it should be
able to work with fewer constraints. In particular,
• The
program should be able to work with
roads of arbitrary
length. It does not
make sense to design a program
that works only for roads
with a predetermined number of corners.
Instead, you want to make
the same
program work for roads of
any length.
Such programs, however, do
need
to know when they have come to the end of
the road, so it makes sense to require
that the end of the roadway is marked by a wall.
• The potholes
may occur
at any
position in the roadway. There should be no
limits on the number of
potholes or any restrictions on their spacing. A pothole
is identified
simply by an opening in the wall representing the road surface.
• Existing potholes
may already
have been repaired. Any of the potholes
may already contain a beeper
left by
a previous repair crew. In such
cases, Karel should not put down
an additional beeper.
To
change the program so that
it solves
this more
general problem requires you to think
about the overall strategy in a different way. Instead of having the loop in
the main program cycle
through each pothole,
you need to have it check each
corner as it goes.
If there is an opening at that corner,
Karel needs to try and fill the
pothole. If there is a wall, Karel can simply move ahead to
the next corner.
This
strategic analysis suggests that the
solution to the general problem
may require
nothing more than making the following change to the run method from
Figure 7:
public void run() {
while (frontIsClear()) {
if (rightIsClear()) {
fillPothole();
}
move();
}
}
However,
as the
bug symbol
off to
the side
suggests, this program is not
quite right. It contains a logical flaw—the
sort of error that programmers call a bug. On the other hand,
the particular
bug in
this example is relatively subtle and would be
easy to miss, even if you tested the
program. For example, the
program works correctly on
the following
world, as shown in the following before-and-after diagrams:
Before
After
4 43 3
2 2
1 1
1 2 3 4 5 6 7
1 2 3 4 5 6 7
From this example,
things look pretty good. If
you ended
your testing here, however, you would never notice that
the program
fails if you change the
world so that there is
a pothole on 7th Avenue. In this case, the before-and-after pictures look like
this:
Before
After
|
|
|||||||||||||
3 3
2 21 1
1 2 3 4 5 6 7
1 2 3 4 5 6 7
Karel stops without
filling the last pothole. In
fact, if you watch the
execution carefully, Karel never even
goes down into that last
pothole to check whether it
needs filling. What’s the problem here?
If you follow through the logic of the program carefully, you’ll discover that the bug lies
in the loop within the run method, which
looks like this:
public void run() {
while (frontIsClear()) {
if (rightIsClear()) {
fillPothole();
}
move();
}
}
As soon as
Karel finishes filling the pothole
on 6th
Avenue, it executes the move command and returns to the top of the while loop. At that point, Karel is standing
at the corner of 7th
Avenue and 2nd street, where
it is
blocked by the boundary wall.
Because the frontIsClear test now fails, the while loop exits without checking
the last segment of the roadway.
The
bug in
this program is an example of a programming
problem called a fencepost error. The name
comes from the fact that
it takes
one more
fence post that you might think
to fence off a particular distance. How many fence posts, for example, do you
need to build a 100-foot
fence if the posts are always positioned 10 feet apart?
The answer is
11, as illustrated by the
following diagram:
100 feet,
11 fenceposts
The situation in
Karel’s world has much the
same structure. In order to
fill potholes in a street that
is seven
corners long, Karel has to
check for seven potholes but
only has
to move
six times.
Because Karel starts and finishes
at an
end of
the roadway,
it needs
to execute one fewer move command than the number of
corners it has to check.
Once you discover it,
fixing this bug is actually
quite easy. Before Karel stops
at the
end of the roadway, all that the program has to do is make a special
check for a pothole at the final intersection, as shown in the program in
Figure 8.
Figure 8. Program to fill
irregularly spaced potholes
/*
/*
* File: RoadRepairKarel.java
* --------------------------
* This version of the RoadRepairKarel class
fills an
* arbitrary sequence of potholes in a roadway.
*/
import stanford.karel.*;
public class RoadRepairKarel
extends SuperKarel {
public void
run() {
while
(frontIsClear()) {
checkForPothole();
move();
}
checkForPothole();
}
/**
* Checks for a pothole immediately beneath
Karel's current
* looking for a
wall to the right. If a pothole exists,
* Karel calls fillPothole to repair it.
*/
private void checkForPothole() {
if (rightIsClear()) {
fillPothole();
}
}
/**
* Fills the pothole beneath Karel's current
position by
* placing a
beeper on that corner. For this method to
* work correctly, Karel must be facing east
immediately
* above the
pothole. When execution is complete,
Karel
* will have returned to the same square and
will again
* be facing
east. This version of fillPothole checks
to
* see if there is already a beeper present
before putting
* a new one down.
*/
private void fillPothole() {
turnRight();
move();
if (noBeepersPresent()) {
putBeeper();
} turnAround();
move(); turnRight();
}
}
0 comments:
Post a Comment