Chapter
2
Programming Karel
In its new object-oriented implementation, the simplest style of
Karel program consists of a definition
of a new
Karel class that specifies a sequence of built-in commands
that should
be executed
when the program is run.
A very simple Karel program is
shown in Figure 1.
The program in Figure 1 is composed of several parts. The first part consists of the following lines:
/*
* File: BeeperPickingKarel.java
* -----------------------------
* The BeeperPickingKarel class extends the
basic Karel class
* by defining
a "run" method with three commands. These
* commands cause Karel to move forward one
block, pick up
* a beeper, and then move ahead to the next
corner.
*/
These lines are an example
of a comment, which is simply text designed to explain the operation of the program to human
readers. Comments in both Karel and Java begin with the characters
/* and end with the characters
*/. Here, the comment begins on the first line
and ends several lines later. The stars on the individual lines that make up
the text of the comment are not required, but make it easier for human readers to see the extent of the comment.
In a simple program, extensive comments
may seem
silly because the effect of
the program
is obvious,
but they
are extremely
important as a means of documenting the design of larger, more
complex programs.
The second part of
the program is the line
import stanford.karel.*;
This line requests the inclusion of all definitions from the stanford.karel library. This
Figure 1. Simple Karel example to pick up a single
beeper
/*
* File: BeeperPickingKarel.java
* -----------------------------
* The BeeperPickingKarel class extends the
basic Karel class
* by defining
a "run" method with three commands. These
* commands cause Karel to move forward one
block, pick up
* a beeper, and then move ahead to the next
corner.
*/
import
stanford.karel.*;
public class BeeperPickingKarel
extends Karel {
public void
run() {
move();
pickBeeper();
move();
}
}
library contains the
basic definitions necessary for writing
Karel programs, such as the
definitions of the standard operations
move() and pickBeeper(). Because you always
need access to these operations, every Karel program
you write will
include this import command before you write the actual program.
The final part of the
Karel program consists of the following class definition:
public class BeeperPickingKarel
extends Karel {
public void run()
{
move();
pickBeeper();
move();
}
}
To understand this definition, it is
useful to look more carefully
at its
structure. The definition of the
BeeperPickingKarel class consists of the line beginning
with public class
and encompasses everything between the curly brace at the end of
that line and the corresponding closing
brace on the last line of
the
program. The single
line that introduces the
new class
is called
the header of the definition; the code between the braces
is called the body.
In programming, it is often very
useful to think about a particular definition and
its body as separable ideas. In this example, the definition of BeeperPickingKarel has the following form, where
the entire
body of the definition has been replaced by
a box that you can put out of your mind for the moment:
public class BeeperPickingKarel
extends Karel {
body
of the class definition
}
The header line at the top tells you quite a bit about the BeeperPickingKarel class, even before
you have
looked to see what the
body contains. The key new
concept in the class header is embodied in the word extends,
which is used in both Karel and Java to indicate that a new class
is an
extension of an existing
one. Here, the class
header line indicates that BeeperPickingKarel is an extension of the standard Karel class imported
from the stanford.karel library.
In object-oriented languages, defining a new class
by extension
means that the new class (here, BeeperPickingKarel) builds
on the facilities provided by the existing
class (in this case, Karel). In particular, the fact that it extends Karel guarantees that the new BeeperPickingKarel class will have the
following properties :
1. Any instance of the
class BeeperPickingKarel is also an instance of the class Karel.
Any instance of the class Karel represents a robot that lives in a world of streets,
avenues, beepers, and walls whose state consists of its location, direction, and the
number of beepers in its bag. Because BeeperPickingKarel is an extension of
Karel, you know that an instance of BeeperPickingKarel will also be a robot that
lives in the same type of
world and has the same state properties.
2. Any instance of the BeeperPickingKarel class will automatically respond to the same commands as an instance
of the Karel class. Because every robot in the Karel class knows how to respond to the commands move(), turnLeft(), pickBeeper(),
and putBeeper(), it follows that a instance of BeeperPickingKarel will understand that same set of commands.
In other words, the new BeeperPickingKarel class automatically acquires the state
attributes and the behavior of the Karel class from which it is derived. The process of taking on the structure and behavior of
the parent class is called inheritance.
When a class is defined by extension, the new class is said to be a subclass of the original.
In this example, BeeperPickingKarel is therefore a subclass
of Karel. Symmetrically, Karel
is said to be a superclass of
BeeperPickingKarel. Unfortunately, this terminology can be
confusing for new programmers, who are likely to
make the intuitive inference that
a subclass is somehow less powerful
that its superclass when in fact the opposite is true. A
subclass inherits the behavior of its superclass and can therefore respond
to the
entire set of commands available
to that
superclass. A subclass, however, usually defines
additional commands that are unavailable
to the
superclass. Thus, the typical subclass
actually has more functionality than the class from
which it was derived. This idea is expressed much more clearly by the notion of extension:
a subclass extends its superclass and can therefore add new capabilities to
it.
Now that you have
some idea about what class extension means, it now makes sense to look at the body of the BeeperPickingKarel class. That body consists
of the following
lines:
public void run() { move(); pickBeeper(); move();
}
These lines represent the definition of a new method, which specifies
the sequence
of steps necessary to respond to
a command. As in the case of the
BeeperPickingKarel class itself, the
method definition consists of two
parts that can be considered
separately: The first line constitutes the method header
and the code between the
curly braces is the method
body. If you ignore the body for now, the method definition looks like this:
public void run() {
body
of the method definition
}
The first two words in the method header, public and void, are part of Java’s syntactic
structure, and you
should pretty much feel free
to ignore
them at
this point.
The next
word on the header line
specifies the name of the
new method,
which in this case is
the method run. Defining a method means that
the new
Karel subclass can respond to
a new command with that name. The built-in Karel class responds to the commands move(), turnLeft(), pickBeeper(),
and putBeeper(); a BeeperPickingKarel responds to that same set of commands
plus a new command
called run. The run command plays a
special role in a Karel program.
When you start a Karel program
in the
Eclipse environment, it creates a new
Karel instance of the appropriate
subclass, adds that Karel to a world that you specify, and then issues the run command. The effect of issuing that
command is defined by the body of the run method, which is a sequence of commands
that the robot will execute in order.
For example, the body of the run method for the BeeperPickingKarel class is
move();
pickBeeper(); move();
Thus, if
the initial
state of the world matches
the example
given in Chapter 1, Karel
first moves forward into the
corner containing the beeper,
picks up that beeper, and
finally moves forward to the corner
just before the
wall, as shown in the
following before-and- after
diagram:
Before
After
4 43 3
|
|
||||||||||||||||||||||||
1 1
1 2 3 4 5 6
Solving a more
interesting problem
1 2 3 4 5 6
The BeeperPickingKarel class defined in Figure 1 doesn’t do very much as yet. Let’s try
to make it a little more interesting. Suppose that the goal is not simply to
get Karel to pick up the beeper but to move the beeper from its initial
position on 2nd Avenue and 1st Street to the center of the ledge at 5th Avenue
and 2nd Street. Thus, your next assignment is to define a new Karel subclass
that accomplishes the task illustrated in this diagram:Before
After
4 43 3
|
|
||||||||||||||||||||||||
1 1
1 2 3 4 5 6
1 2 3 4 5 6
The first three commands in the new program—the ones that move forward, pick up the
beeper, and then move up to the ledge—are the same as before:
move();
pickBeeper(); move();
From here, the next step is to turn left to begin climbing the ledge. That operation is easy, because Karel has a turnLeft command in its standard
repertoire. Executing a turnLeft command
at the end of the preceding sequence of commands leaves Karel facing north on the corner of 3rd Avenue and 1st Street. If Karel then executes
a move command, it will move north to reach the following
position:
432
1
1 2 3 4 5 6
From here, the next thing you need to do is get Karel to turn
right so that it is again facing east. While this operation is conceptually just as easy as getting Karel to turn left, there is a slight problem: Karel’s language includes a turnLeft command, but no turnRight command. It’s
as if
you bought
the economy
model and have now discovered
that it
is missing some important features.
At this point, you
have your first opportunity to begin thinking like a programmer. You have one
set of
commands, but not exactly
the set you need.
What can you do? Can
you accomplish the effect of a turnRight command using only the capabilities you have? The answer,
of course,
is yes.
You can
accomplish the effect of turning
right by turning left three times.
After three left turns, Karel
will be facing in the
desired direction. From here, all you
need to do is program Karel to move over to the center of the ledge, drop the beeper
and then
move forward to the final
position. A complete implementation
of a BeeperTotingKarel class that accomplishes
the entire task is shown in Figure 2.
Figure 2. Program to
carry a beeper to the top of a ledge
/*
* File: BeeperTotingKarel.java
* ----------------------------
* The BeeperTotingKarel class extends the
basic Karel class
* so that Karel picks up a beeper from 1st
Street and then
* carries that beeper to the center of a ledge
on 2nd Street.
*/
import
stanford.karel.*;
public class BeeperTotingKarel
extends Karel {
public void
run() {
move();
pickBeeper();
move();
turnLeft();
move();
turnLeft();
turnLeft();
turnLeft();
move();
move();
putBeeper();
move();
}
}
Defining new methods
Even though the BeeperTotingKarel class in Figure 2 demonstrates that it is possible to perform the turnRight operation using only Karel’s built-in commands, the resulting
program is not particularly
clear conceptually. In your mental
design of the program, Karel
turns right when it reaches
the top
of the
ledge. The fact that you
have to use three turnLeft commands to do so is annoying.
It would be much simpler
if you could simply say turnRight and have Karel understand
this command. The resulting program would not
only be shorter and easier to write, but also significantly easier to read.
Fortunately, the Karel programming language makes it possible
to define
new commands
simply by including new method
definitions. Whenever you have a sequence
of Karel commands that performs
some useful task—such as turning
right—you can define a new method that executes that sequence of commands.
The format for defining a new Karel method has much the same as the definition of run in the preceding examples, which is a method definition in
its own right. A typical method definition looks like this:
private void name() {
commands
that make up the body of the method
}
In this pattern, name represents the name you have chosen for the new method. To complete
the definition, all you
have to do is provide
the sequence
of commands
in the
lines between the curly braces. For example, you can define turnRight as follows:
private void turnRight() {
turnLeft();
turnLeft();
turnLeft();
}
Similarly, you could define
a new turnAround method like this:
private void turnAround() {
turnLeft();
turnLeft();
}
You can use the name
of a new method just like any of Karel’s built-in commands. For example, once you have defined turnRight, you could replace the
three turnLeft commands in the BeeperTotingKarel class with a single call to the turnRight method.
A revised implementation of the program that uses turnRight is shown in Figure 3.
There is, of course, one obvious difference
between the definitions of the run and turnRight methods shown in Figure 3: the run method is marked as public in contrast to turnRight, which is marked as private. The difference between these two designations is that public methods
can be
invoked from outside the class,
while private methods cannot. The run method needs to be public because the Karel environment
needs to be able to issue a run command to get things going. By contrast,
turnRight is used only inside the other code appearing within this class.
That definition, therefore, can be private, and
it is
generally good programming practice to
keep definitions private whenever possible.
The reasons for this rule are difficult
to appreciate until you have had
a chance to work with
larger programs, but the basic
idea
is that classes should
try as
much as possible to encapsulate information, which means not only to gather it together
but also to restrict access to that information if possible. Large
programs quickly become very complex in
terms of the volume of
detail that they encompass. If
a class is well designed,
it will seek to reduce that complexity by hiding as much extraneous detail as it
Figure 3. Revised implementation of BeeperTotingKarel that includes a turnRight method
/*
* File: BeeperTotingKarel.java
* ----------------------------
* The BeeperTotingKarel class extends the
basic Karel class
* so that Karel picks up a beeper from 1st
Street and then
* carries that beeper to the center of a ledge
on 2nd Street.
*/
import
stanford.karel.*;
public class BeeperTotingKarel
extends Karel {
public void
run() {
move();
pickBeeper();
move();
turnLeft();
move();
turnRight();
move();
move();
putBeeper();
move();
}
/**
* Turns Karel 90 degrees to the right.
*/
private void turnRight() {
turnLeft();
turnLeft();
turnLeft();
}
}
can. This property
is known as information hiding and is a cornerstone
of the object- oriented
philosophy.
At this point in your
study of programming, you are not
likely to find these arguments about encapsulation particularly convincing. Defining turnRight and turnAround in every program is
certainly a bit of a pain, particularly
in light
of the
fact that they are so useful.
The difficulty, however, in making them more easily available lies in figuring
out where to put those definitions. Declaring turnRight to be public in the definition of BeeperTotingKarel would not be much help. In an object-oriented language, the methods that
specify the behavior of a class
are encapsulated
within that class. The turnRight method that appears within that class knows how to turn an instance of BeeperTotingKarel 90 degrees to the right, but that method cannot be applied to an instance of the Karel class or any its subclasses.
In some sense, what you really want to do is add turnRight and turnAround to the Karel class so that all subclasses
will be able to use these undeniably useful commands.
The problem with that strategy
is that you don’t necessarily have the access to the Karel class necessary
to make such a change. The Karel class is part of the Stanford library, which is used by all
students in this CS106A. If
you were
to go
and make
changes to it, you might end
up breaking
someone else’s program, which would
not endear
you to
the other students. Similarly, if you
at some
point later in the quarter
decide that you really want to add something to one of the standard Java classes, you won’t actually be able to
change that class
because it is under the
control of Sun Microsystems. What you can do, however,
is define a new class that includes your new features as extensions. Thus, if
you want to use turnRight and turnAround in several different Karel programs, you could
define a new class that
included these method definitions and then create your
programs by extending that class. This
technique is illustrated in Figure
4, which
consists of two program files. The first contains a class definition called NewImprovedKarel that
includes the turnRight and turnAround definitions as public methods so that other classes can use them. The second is yet another implementation of
BeeperTotingKarel that extends NewImprovedKarel,
thereby giving itself access to these methods.
The stanford.karel package does not include the NewImprovedKarel class as it
appears here but does include a SuperKarel class that includes the methods turnRight and turnAround along with several other extensions that will make it possible
for you to write much more exciting programs. The examples that follow extend SuperKarel to ensure
that these methods are available. The other extensions are described in Chapter
6.
Decomposition
As a way of
illustrating more of the
power that comes with
being able to define new methods,
it’s useful to have Karel do something a little more practical than move a
beeper from one place to
another. The roadways around Palo
Alto often seem to be in need of
repair, and it
might be fun to see
if Karel
can fill
potholes in its abstract
world. For example, imagine that
Karel is standing on the
“road” shown in the left-hand
figure, one corner to the left
of a pothole in the road.
Karel’s job is to fill
the hole
with a beeper and proceed to
the next corner. The diagram on the right illustrates how the world should look
after the program execution.
Before After
|
|
|||||||||||||||||||||||||||||||
3
2
1
1 2 3 4 5 6
1 2 3 4 5 6
If you are limited
to the four predefined commands,
the run method to solve this problem
would look like this:
public void run() { move(); turnLeft(); turnLeft(); turnLeft();
move(); putBeeper(); turnLeft(); turnLeft(); move(); turnLeft(); turnLeft();
turnLeft(); move();
}
Figure 4. Defining a NewImprovedKarel class that
understands turnRight and turnAround
/*
* File: NewImprovedKarel.java
* ---------------------------
* The NewImprovedKarel class extends the basic
Karel class
* so that any subclasses have access to the
turnRight and
* turnAround
methods. It does not define any run
method
* of its own.
*/
import stanford.karel.*;
public class NewImprovedKarel
extends Karel {
/**
* Turns Karel 90 degrees to the right.
*/
public void
turnRight() {
turnLeft();
turnLeft();
turnLeft();
}
/**
* Turns Karel around 180 degrees.
*/
public void turnAround() {
turnLeft();
turnLeft();
}
}
/*
* File: BeeperTotingKarel.java
* ----------------------------
* The BeeperTotingKarel class extends the
basic Karel class
* so that Karel picks up a beeper from 1st
Street and then
* carries that beeper to the center of a ledge
on 2nd Street.
*/
import
stanford.karel.*;
public class BeeperTotingKarel
extends NewImprovedKarel {
public void
run() {
move();
pickBeeper();
move();
turnLeft();
move();
turnRight();
move();
move();
putBeeper();
move();
}
}
You can, however, make the main program easier to read by extending SuperKarel and then making use of the turnAround and turnRight methods. This version of the program appears in Figure 5.
The initial motivation for defining the turnRight method was that it was cumbersome to keep repeating
three turnLeft commands to accomplish a right turn. Defining new methods has another important purpose
beyond allowing you to avoid repeating the same command sequences every time
you want
to perform
a particular task. The power to
define methods unlocks the
most important strategy in programming—the
process of breaking a large problem down into smaller pieces that are
easier to solve. The process of breaking a program down into smaller pieces is called decomposition, and the component
parts of a large problem are called subproblems.
As
an example, the problem of filling the hole in the roadway can be decomposed
into the following subproblems:
1. Move up to the hole
2. Fill the hole by
dropping a beeper into it
3. Move on to the next
corner
If you think about the
problem in this way, you
can use
method definitions to create a program that reflects your conception of the program structure. The run method would look
like this:
public void run() { move(); fillPothole(); move();
}
Figure 5. Karel program to
fill a single pothole
/*
* File: PotholeFillingKarel.java
* ------------------------------
* The PotholeFillingKarel class puts a beeper
into a pothole
* on 2nd Avenue. This version of the program uses no
* decomposition other than turnRight and
turnAround,
* which are inherited from SuperKarel.
*/
import
stanford.karel.*;
public class
PotholeFillingKarel extends SuperKarel {
public void
run() {
move();
turnRight();
move();
putBeeper();
turnAround();
move();
turnRight();
move();
}
}
The correspondence
with the outline is immediately clear, and everything would be great if only you could get Karel to understand
what you mean by fillPothole. Given the
power to define methods,
implementing fillPothole is extremely simple. All you have to do is define a fillPothole method whose body consists of the commands you have already written to do the job, like
this:
private void fillPothole() {
turnRight();
move();
putBeeper();
turnAround();
move();
turnRight();
}
The complete program is shown in Figure 6.
Figure 6. Program to fill a single pothole using a fillPothole method for decomposition
/*
* File: PotholeFillingKarel.java
* ------------------------------
* The PotholeFillingKarel class puts a beeper
into a pothole
* on 2nd Avenue. This version of the program decomposes
* the problem so that it makes use of a
fillPothole method.
*/
import stanford.karel.*;
public class PotholeFillingKarel
extends SuperKarel {
public void
run() {
move();
fillPothole();
move();
}
/**
* 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.
*/
private void fillPothole() {
turnRight();
move();
putBeeper();
turnAround();
move();
turnRight();
}
}
Choosing the correct
decomposition
There are, however,
other decomposition strategies you might have tried. For example,
you could have written the program as
public void run() { approachAndFillPothole(); move();
}
where the approachAndFillPothole method is simply
private void
approachAndFillPothole() {
move();
turnRight();
move();
putBeeper();
turnAround();
move();
turnRight();
}
Alternatively, you might
have written the program as
public void run() { move(); turnRight(); move();
fillPotholeYouAreStandingIn();
turnAround();
move();
turnRight();
move();
}
where the body of fillPotholeYouAreStandingIn consists of a single putBeeper command. Each of these programs
represents a possible decomposition. Each program
correctly solves the problem.
Given that all three versions
of this
program work, what makes one
choice of breaking up the problem better than another?
In general, deciding how
to decompose
a program is not easy. In
fact, as the problems become more complex, choosing an
appropriate decomposition will turn out to be one of the more difficult aspects
of programming. You can, however, rely to some extent on the following
guidelines:
1. Each subproblem should perform a conceptually simple task. The solution of a subproblem
may require
many commands and may be
quite complex in terms of
its internal operation. Even so, it
should end up accomplishing some conceptual task that is itself easy to
describe. A good indication of whether
you have
succeeded in identifying a reasonable task comes from the name you give to
the method. If you can accurately define its effect with a simple descriptive name, you have probably chosen a
good decomposition. On the other hand, if you
end up with complex names such as approachAndFillPothole,
the decomposition does not seem as promising.
2. Each subproblem
should perform a task that is as general as possible,
so that it can be
used in several different situations. If
one decomposition
results in a program that is only useful in the exact situation
at hand and another would work equally well in a variety of related situations, you
should probably choose the more general one 
0 comments:
Post a Comment