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
[ Next Section | Previous Section | Chapter Index | Main Index ]