Section 4.6
More on Program Design
UNDERSTANDING HOW PROGRAMS WORK IS ONE THING.
Designing a program to perform some particular task is another
thing altogether. In Section 3.2, I
discussed how stepwise refinement can be used to methodically
develop an algorithm. We can now see how subroutines can
fit into the process.
Stepwise refinement is inherently a top-down process,
but the process does have a "bottom," that is,
a point at which you stop refining the pseudocode algorithm
and translate what you have directly into proper programming
language. In the absence of subroutines, the process would
not bottom out until you get down to the level of
assignment statements and very primitive input/output operations.
But if you have subroutines lying around to perform certain useful
tasks, you can stop refining as soon as you've managed to express
your algorithm in terms of those tasks.
This allows you to add a bottom-up element to the top-down
approach of stepwise refinement. Given a problem, you might
start by writing some subroutines that perform tasks relevant
to the problem domain. The subroutines become a toolbox
of ready-made tools that you can integrate into your algorithm
as you develop it. (Alternatively, you might be able to
buy or find a software toolbox written by someone else, containing
subroutines that you can use in your project as black boxes.)
Subroutines can also be helpful even in a strict top-down
approach. As you refine your algorithm, you are free at
any point to take any sub-task in the algorithm and make it
into a subroutine. Developing that subroutine then becomes
a separate problem, which you can work on separately. Your
main algorithm will merely call the subroutine. This, of course,
is just a way of breaking your problem down into separate, smaller
problems. It is still a top-down approach because the
top-down analysis of the problem tells you what subroutines
to write. In the bottom-up approach, you start by writing or
obtaining subroutines that are relevant to the problem domain,
and you build your solution to the problem on top of that
foundation of subroutines.
Preconditions and Postconditions
When working with subroutines as building blocks, it is important to
be clear about how a subroutine interacts with the rest of the program.
This interaction is specified by the contract
of the subroutine, as discussed in Section 1.
A convenient way to express the contract of a subroutine is in terms of
preconditions and postconditions.
The precondition of a subroutine is something that must be true when the
subroutine is called, if the subroutine is to work correctly. For example,
for the built-in function Math.sqrt(x), a precondition is that the
parameter, x, is greater than or equal to zero, since it is not
possible to take the square root of a negative number. In terms of a contract,
a precondition represents an obligation of the caller of the subroutine.
If you call a subroutine without meeting its precondition, then there is no
reason to expect it to work properly. The program might crash or give
incorrect results, but you can only blame yourself, not the subroutine.
A postcondition of a subroutine represents the other side of the contract.
It is something that will be true after the
subroutine has run (assuming that its preconditions were met -- and that there
are no bugs in the subroutine). The postcondition of the function Math.sqrt()
is that the square of the value that is returned by this function is equal to the parameter
that is provided when the subroutine is called.
Of course, this will only be true if the preconditiion -- that the parameter is greater
than or equal to zero -- is met. A postcondition of the built-in subroutine
System.out.print() is that the value of the parameter has been displayed
on the screen.
Preconditions most often give restrictions on the acceptable values
of parameters, as in the example of Math.sqrt(x). However, they can
also refer to global variables that are used in the subroutine. The postcondition
of a subroutine specifies the task that it performs. For a function, the postcondition
should specify the value that the function returns.
Subroutines are often described by comments that explicitly specify their
preconditions and postconditions. When you are given a pre-written subroutine,
a statement of its preconditions and postcondtions tells you how to use it and
what it does. When you are assigned to write a subroutine, the preconditions
and postconditions give you an exact specification of what the subroutine is
expected to do. I will use this approach in the example that constitutes the
rest of this section. I will also use it occasionally later in the book, although
I will generally be less formal in my commenting style.
Preconditions and postconditions will be discussed more thoroughly in
Chapter 9, which deals with techniques for
writing correct and robust programs.
A Design Example
Let's work through an example of program design using subroutines.
In this example, we will both use prewritten subroutines as building
blocks and design new subroutines that we need to complete the project.
Suppose that I
have found an already-written class called Mosaic.
This class allows a program to work with a window that displays little colored
rectangles arranged in rows and columns. The window can be opened, closed,
and otherwise manipulated with static member subroutines defined
in the Mosaic class. Here are some of the available
routines:
void Mosaic.open(int rows, int cols, int w, int h);
Precondition: The parameters rows, cols, w, and h are
greater than zero.
Postcondition: A "mosaic" window is opened on the screen that can
display rows and columns of colored rectangles.
Each rectangle is w pixels wide and h pixels high.
The number of rows is given by the first
parameter and the number of columns by the second.
Initially, all the rectangles are black.
Note: The rows are numbered from 0 to rows - 1, and the columns
are numbered from 0 to cols - 1.
void Mosaic.setColor(int row, int col, int r, int g, int b);
Precondition: row and col are in the valid ranges of row numbers and
column numbers. r, g, and b are in the range 0 to 255.
Also, the mosaic window should be open.
Postcondition: The color of the rectangle in row number row and column
number col has been set to the color specified by
r, g, and b. r gives the amount of red in the color
with 0 representing no red and 255 representing the
maximum possible amount of red. The larger the value
of r, the more red in the color. g and b work
similarly for the green and blue color components.
int Mosaic.getRed(int row, int col);
int Mosaic.getBlue(int row, int col);
int Mosaic.getGreen(int row, int col);
Precondition: row and col are in the valid ranges of row numbers
and column numbers. Also, the mosaic window should
be open.
Postcondition: Returns an int value that represents one of the
three color components of the rectangle in row
number row and column number col. The return value
is in the range 0 to 255. (Mosaic.getRed() returns
the red component of the rectangle, Mosaic.getGreen()
the green component, and Mosaic.getBlue() the blue
component.)
void Mosaic.delay(int milliseconds);
Precondition: milliseconds is a positive integer.
Postcondition: The program has paused for at least the number
of milliseconds given by the parameter, where
one second is equal to 1000 milliseconds.
Note: This can be used to insert a time delay in the program (to
regulate the speed at which the colors are changed, for
example).
boolean Mosaic.isOpen();
Precondition: None.
Postcondition: The return value is true if the mosaic window
is open on the screen, and is false otherwise.
Note: The window will be closed if the user clicks its
close box. It can also be closed programmatically by
calling the subroutine Mosaic.close().
My idea is
to use the Mosaic class as the basis for a neat animation.
I want to fill the window with randomly colored squares,
and then randomly change the colors in a loop that continues as
long as the window is open. "Randomly change the colors"
could mean a lot of different things, but after thinking for a while, I decide
it would be interesting to have a "disturbance" that wanders
randomly around the window, changing the color of each
square that it encounters. Here's an applet that shows what the program will do:
With basic routines for manipulating the window as
a foundation, I can turn to the specific problem at hand.
A basic outline for my program is
Open a Mosaic window
Fill window with random colors;
Move around, changing squares at random.
Filling the
window with random colors seems like a nice coherent task that I
can work on separately, so let's decide to write a separate
subroutine to do it. The third step can be expanded a bit more,
into the steps: Start in the middle of the window, then keep moving to a
new square and changing the color of that square. This should continue
as long as the mosaic window is still open. Thus we can refine the algorithm to:
Open a Mosaic window
Fill window with random colors;
Set the current position to the middle square in the window;
As long as the mosaic window is open:
Randomly change color of current square;
Move current position up, down, left, or right, at random;
I need to represent the current position in some way. That can
be done with two int variables named currentRow
and currentColumn. I'll use 10 rows and 20 columns of
squares in my mosaic, so setting the current position to be in
the center means setting currentRow to 5 and currentColumn
to 10. I already have a subroutine, Mosaic.open(), to open the
window, and I have a function, Mosaic.isOpen(), to test
whether the window is open. To keep the main routine simple,
I decide that I will write two more subroutines of
my own to carry out the two tasks in the while loop.
The algorithm can then be written in Java as:
Mosaic.open(10,20,10,10)
fillWithRandomColors();
currentRow = 5; // Middle row, halfway down the window.
currentColumn = 10; // Middle column.
while ( Mosaic.isOpen() ) {
changeToRandomColor(currentRow, currentColumn);
randomMove();
}
With the proper wrapper, this is essentially the main() routine
of my program. It turns out I have to make one small modification:
To prevent the animation from running too fast, the line
"Mosaic.delay(20);" is added to the while
loop.
The main() routine is taken care of, but to complete the
program, I still have to write the subroutines
fillWithRandomColors(), changeToRandomColor(int,int),
and randomMove(). Writing each of these subroutines is
a separate, small task. The fillWithRandomColors() routine
is defined by the postcondition that "each of the rectangles in
the mosaic has been changed to a random color."
Pseudocode for an algorithm to accomplish this task can be given as:
For each row:
For each column:
set the square in that row and column to a random color
"For each row" and "for each column" can
be implemented as for loops. We've already planned
to write a subroutine changeToRandomColor
that can be used to set the color. (The possibility of
reusing subroutines in several places is one of the big payoffs
of using them!) So, fillWithRandomColors() can be
written in proper Java as:
static void fillWithRandomColors() {
for (int row = 0; row < 10; row++)
for (int column = 0; column < 20; column++)
changeToRandomColor(row,column);
}
Turning to the changeToRandomColor subroutine, we already
have a method, Mosaic.setColor(row,col,r,g,b), that can be
used to change the color of a square. If we want a random color,
we just have to choose random values for r, g,
and b. According to the precondition of the
Mosaic.setColor() subroutine,
these random values must be integers in the
range from 0 to 255. A formula for randomly selecting such an
integer is "(int)(256*Math.random())".
So the random color subroutine becomes:
static void changeToRandomColor(int rowNum, int colNum) {
int red = (int)(256*Math.random());
int green = (int)(256*Math.random());
int blue = (int)(256*Math.random());
mosaic.setColor(rowNum,colNum,red,green,blue);
}
Finally, consider the randomMove subroutine, which is
supposed to randomly move the disturbance up, down, left, or
right. To make a random choice among four directions, we can
choose a random integer in the range 0 to 3. If the integer
is 0, move in one direction; if it is 1, move in another
direction; and so on. The position of the disturbance is given
by the variables currentRow and currentColumn.
To "move up" means to subtract 1 from currentRow.
This leaves open the question of what to do if currentRow
becomes -1, which would put the disturbance above the window.
Rather than let this happen, I decide to move the disturbance
to the opposite edge of the applet by setting currentRow
to 9. (Remember that the 10 rows are numbered from 0 to 9.)
Moving the disturbance down, left, or right
is handled similarly. If we use a switch statement to
decide which direction to move, the code for randomMove
becomes:
int directionNum;
directoinNum = (int)(4*Math.random());
switch (directionNum) {
case 0: // move up
currentRow--;
if (currentRow < 0) // CurrentRow is outside the mosaic;
currentRow = 9; // move it to the opposite edge.
break;
case 1: // move right
currentColumn++;
if (currentColumn >= 20)
currentColumn = 0;
break;
case 2: // move down
currentRow++;
if (currentRow >= 10)
currentRow = 0;
break;
case 3: // move left
currentColumn--;
if (currentColumn < 0)
currentColumn = 19;
break;
}
Putting this all together, we get the following complete
program. The variables currentRow
and currentColumn are defined as static members of the
class, rather than local variables, because each of them is
used in several different subroutines. This program actually
depends on two other classes, Mosaic and
another class called MosaicCanvas that is used
by Mosaic. If you want to compile and run this
program, both of these classes must be available to
the program.
public class RandomMosaicWalk {
/*
This program shows a window full of randomly colored
squares. A "disturbance" moves randomly around
in the window, randomly changing the color of
each square that it visits. The program runs
until the user closes the window.
*/
static int currentRow; // row currently containing the disturbance
static int currentColumn; // column currently containing disturbance
public static void main(String[] args) {
// Main program creates the window, fills it with
// random colors, then moves the disturbance in
// a random walk around the window for as long as
// the window is open.
Mosaic.open(10,20,10,10);
fillWithRandomColors();
currentRow = 5; // start at center of window
currentColumn = 10;
while (Mosaic.isOpen()) {
changeToRandomColor(currentRow, currentColumn);
randomMove();
Mosaic.delay(20);
}
} // end of main()
static void fillWithRandomColors() {
// Precondition: The mosaic window is open.
// Postcondition: Each rectangle has been set to a
// random color
for (int row=0; row < 10; row++) {
for (int column=0; column < 20; column++) {
changeToRandomColor(row, column);
}
}
} // end of fillWithRandomColors()
static void changeToRandomColor(int rowNum, int colNum) {
// Precondition: rowNum and colNum are in the valid range
// of row and column numbers.
// Postcondition: The rectangle in the specified row and
// column has been changed to a random color.
int red = (int)(256*Math.random()); // choose random levels in range
int green = (int)(256*Math.random()); // 0 to 255 for red, green,
int blue = (int)(256*Math.random()); // and blue color components
Mosaic.setColor(rowNum,colNum,red,green,blue);
} // end of changeToRandomColor()
static void randomMove() {
// Precondition: The global variables currentRow and currentColumn
// specify a valid position in the grid.
// Postcondition: currentRow or currentColumn is changed to
// one of the neighboring positions in the grid,
// up, down, left, or right from the previous
// position. If this moves the position outside
// the grid, then it is moved to the opposite edge
// of the window.
int directionNum; // Randomly set to 0, 1, 2, or 3 to choose direction.
directionNum = (int)(4*Math.random());
switch (directionNum) {
case 0: // move up
currentRow--;
if (currentRow < 0)
currentRow = 9;
break;
case 1: // move right
currentColumn++;
if (currentColumn >= 20)
currentColumn = 0;
break;
case 2: // move down
currentRow ++;
if (currentRow >= 10)
currentRow = 0;
break;
case 3: // move left
currentColumn--;
if (currentColumn < 0)
currentColumn = 19;
break;
}
} // end of randomMove()
} // end of class RandomMosaicWalk
