Chapter
4
Stepwise Refinement
To a large extent,
programming is the science
of solving problems by computer. Because problems are often
difficult, solutions—and the programs that
implement those solutions—can be difficult as
well. In order to make
it easier
for you
to develop
those solutions, you need to
adopt a methodology and discipline that reduces the level
of that
complexity to a manageable scale.
In
the early years of programming, the concept of computing as a science was more
or less an experiment in wishful
thinking. No one knew much
about programming in those days, and few
thought of it as an engineering discipline in the conventional sense. As programming matured, however, such a discipline
began to emerge. The cornerstone
of that discipline is the understanding
that programming is done in
a social environment in which
programmers must work together. If you go into industry, you will almost
certainly be one of many programmers
working to develop a large program.
That program,
moreover, is almost
certain to live on and
require maintenance beyond its originally
intended application. Someone will want the
program to include some new
feature or work in some
different way. When that occurs,
a new team of programmers must go in and make the necessary changes in the
programs. If programs are written in an individual style with little or
no commonality,
getting everyone to work together
productively is extremely difficult.
To combat this problem,
programmers began to develop a set
of programming
methodologies that are collectively called software engineering.
Using good software engineering skills not only makes
it easier
for other
programmers to read and understand
your programs, but also makes it easier for you to write those programs
in the first place. One of the most important methodological advances to come out of software
engineering is the strategy of top-down design
or stepwise refinement, which consists of solving problems by
starting with the problem as
a whole. You break the whole
problem down into pieces, and then solve each piece, breaking those down
further if necessary.
An
exercise in stepwise refinement
To
illustrate the concept of stepwise
refinement, let’s teach Karel to
solve a new problem. Imagine that Karel is now living in a world that looks
something like this:7
654
3
2
1 
1 2 3 4 5 6 7 8 9On each of the
avenues, there is a tower of
beepers of an unknown height,
although some avenues (such as 1st, 7th, and 9th in the sample world) may be empty. Karel’s job is
to collect
all the
beepers in each of these
towers, put them back down
on the
easternmost corner of 1st Street, and then return to its starting
position. Thus, when Karel finishes its work
in the
example above, all 21 beepers
currently in the towers should
be stacked on the corner of 9th
Avenue and 1st Street, as follows:765432
1 21 1 2 3 4 5 6 7 8 9
The key to solving
this problem
is to
decompose the program in the
right way. This task is
more complex than the others
you have
seen, which makes choosing appropriate
subproblems more important to obtaining a successful solution.
The principle of top-down design
The key idea
in stepwise
refinement is that you should
start the design of your
program from the top, which
refers to the level of
the program
that is
conceptually highest and most abstract.
At this
level, the beeper tower problem
is clearly
divided into three independent phases. First, Karel
has to
collect all the beepers.
Second, Karel has to deposit them on the last intersection.
Third, Karel has to return to its home position. This conceptual decomposition of the problem suggests that the run method for this program will
have the following structure:
public void run() { collectAllBeepers(); dropAllBeepers();
returnHome();
}
At this level, the problem
is easy
to understand.
Of course,
there are a few details left
over in the form of methods that you have not yet written. Even so, it
is important to look at each level of the decomposition and convince yourself that, as long as you believe that the
methods you are about to
write will solve the subproblems
correctly, you will then have a solution to the problem as a
whole.
Refining the first subproblem
Now that you have
defined the structure for the program as a whole, it is time to move on to the
first subproblem, which consists of
collecting all the beepers. This
task is
itself more complicated than the
simple problems from the preceding
chapters. Collecting all the beepers means that you have to pick up the beepers in every tower until you get to the
final corner. The fact that you need to repeat an operation
for each tower suggests that you
need a while loop
here.
But what does this while loop look like?
First of all, you should think about the conditional test. You want Karel to stop
when it hits the wall at the end of the row. Thus, you want Karel to
keep going as long as
the space
in front
is clear.
Thus, you know that the
collectAllBeepers method will include a while loop that uses the frontIsClear test. At each position, you want Karel to collect all the beepers
in the tower beginning on that corner. If
you give
that operation
a name, which might be something
like collectOneTower,
you can go ahead and write a definition for the collectAllBeepers method even though you haven’t yet
filled in the details.
You do, however, have to be careful. The code for collectAllBeepers does not look
like this:
private void
collectAllBeepers {
while
(frontIsClear()) {
collectOneTower();
move();
}
}
This implementation is buggy
for exactly
the same
reason that the first version
of the
general RoadRepairKarel from the previous chapter failed to do its job. There is a fencepost error in this version of the code, because Karel needs to test for the presence
of a beeper tower on the last avenue. The correct implementation is
private void collectAllBeepers {
while
(frontIsClear()) {
collectOneTower();
move();
}
collectOneTower();
}
Note that this
method has precisely the same
structure as the main program
from the RoadRepairKarel program
presented at the end of the last chapter. The only difference is that this program calls collectOneTower where the other called checkForPothole. These two programs are each examples of a general strategy that
looks like this:
while (frontIsClear()) { Perform some
operation. move();
}
Perform
the same operation for the final corner.
You can use
this strategy whenever you need
to perform
an operation
on every
corner as you move along a path
that ends at a wall. If
you remember
the general
structure of this strategy, you
can use
it whenever
you encounter
a problem that requires such an operation. Reusable
strategies of this sort come
up frequently
in programming
and are
referred to as programming idioms or patterns. The more patterns you know, the easier
it will be for you to find one that fits a particular type of problem.
Coding the next level
Even though the code for the collectAllBeepers method is itself complete, you can’t actually execute the program until you solve the collectOneTower subproblem. When
collectOneTower is called, Karel is either standing at the base of a tower of beepers or standing on an empty corner.
In the
former case, you need to
collect the beepers in the tower.
In the latter, you can simply move on. This situation sounds like an application for the
if statement,
in which you would write something like this:
if (beepersPresent()) {
collectActualTower();
}
Before you add such a statement to the code, you should think
about whether you need to make this test. Often, programs can be made much
simpler by observing that cases that at first
seem to
be special
can be
treated in precisely the same
way as
the more
general situation. In the
current problem, what happens if
you decide
that there
is a tower
of beepers on every avenue but that some of those towers are zero
beepers high? Making use of this insight simplifies the program because you no longer have to test whether there is a
tower on a particular avenue.
The collectOneTower method is still complex enough that an additional level of decomposition is in order. To
collect all the beepers in
a tower, Karel needs to undertake
the following steps:
1. Turn left to face the
beepers in the tower.
2. Collect all the beepers
in the tower, stopping when no more beepers are found.
3. Turn around to face
back toward the bottom of the world.
4. Return to the wall that
represents the ground.
5. Turn left to be ready
to move to the next corner.
Once again, this outline
provides a model for the collectOneTower method, which looks
like this:
private void collectOneTower() { turnLeft();
collectLineOfBeepers(); turnAround();
moveToWall();
turnLeft();
}
Preconditions and postconditions
The turnLeft commands at the beginning and end of the collectOneTower method are both critical to the correctness of this program. When collectOneTower is called, Karel is always
somewhere on 1st Street facing
east. When it completes its
operation, the program as a whole
will work
correctly only if Karel is
again facing east at that
same corner.
Conditions that must be true
before a method is called are
referred to as preconditions;
conditions that must apply after the method finishes are known as postconditions.
When
you define a method, you will get into far less trouble if you write down
exactly what the pre- and postconditions are. Once you have done so, you then
need to make sure that the code
you write
always leaves the postconditions satisfied, assuming that the
preconditions were satisfied
to begin with. For example, think
about what happens if you call collectOneTower when Karel is on 1st Street facing east. The first turnLeft command leaves
Karel facing north, which means
that Karel is properly aligned
with the column of beepers representing the tower. The collectLineOfBeepers method—which
has yet to
be written
but nonetheless
performs a task that you understand
conceptually— simply moves without
turning. Thus, at the end
of the
call to collectLineOfBeepers,
Karel will still be facing north. The turnAround call therefore
leaves Karel facing south.
Like
collectLineOfBeepers, the moveToWall method does not involve any turns but
instead simply moves until
it hits
the boundary
wall. Because Karel is facing
south, this boundary wall will be the one at the bottom of the screen,
just below 1st Street. The final turnLeft command therefore leaves Karel on 1st Street facing east, which satisfies the postcondition.
Finishing up
Although the hard
work has been done, there
are still
several loose ends that need
to be
resolved. The main program calls two methods—dropAllBeepers and returnHome—
that are as yet unwritten.
Similarly, collectOneTower calls collectLineOfBeepers and moveToWall. Fortunately, all four
of these
methods are simple enough to
code without any further decomposition, particularly if you use moveToWall in the definition of returnHome.
The complete implementation appears in Figure 9.
Figure 9. Program to solve the
collect towers of beepers
/*
* File: BeeperCollectingKarel.java
* --------------------------------
* The BeeperCollectingKarel class collects all
the beepers
* in a series of vertical towers and deposits
them at the
* rightmost corner on 1st Street.
*/
import stanford.karel.*;
public class
BeeperCollectingKarel extends SuperKarel {
/**
* Specifies the program entry point.
*/
public void
run() {
collectAllBeepers();
dropAllBeepers();
returnHome();
}
/**
* Collects the beepers from every tower by
moving along 1st
* Street,
calling collectOneTower at every corner. The
* postcondition for this method is that Karel
is in the
* easternmost corner of 1st Street facing
east.
*/
private void collectAllBeepers() {
while
(frontIsClear()) {
collectOneTower();
move();
}
collectOneTower();
}
/**
* Collects the beepers in a single tower. When
collectOneTower
* is called,
Karel must be on 1st Street facing east. The
* postcondition for collectOneTower is that
Karel must again
* be facing east on that same corner.
*/
private void
collectOneTower() {
turnLeft();
collectLineOfBeepers();
turnAround();
moveToWall();
turnLeft();
}
/**
* Collects a consecutive line of beepers. The
end of the beeper
* line is indicated by a corner that contains
no beepers.
*/
private void collectLineOfBeepers() {
while (beepersPresent())
{
pickBeeper();
if (frontIsClear()) {
move();
}
}
}
/**
* Drops all the
beepers on the current corner.
*/
private void
dropAllBeepers() {
while
(beepersInBag()) {
putBeeper();
}
}
/**
* Returns Karel to its initial
position at the corner of 1st
* Avenue and 1st
Street, facing east. The precondition for
this
* method is that Karel must be facing east
somewhere on 1st
* Street, which is true at the conclusion of
collectAllBeepers.
*/
private void returnHome() {
turnAround();
moveToWall();
turnAround();
}
/**
* Moves Karel forward until it is blocked by a
wall.
*/
private void moveToWall()
{
while (frontIsClear()) {
0 comments:
Post a Comment