Section 3.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 2.5, 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, that 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. This 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 relavant to the problem domain, and you build your solution to the problem on top of that foundation of subroutines.
Let's work through an example. Suppose that I have this idea for a neat animation. I am thinking of a window full of little colored squares lined up in rows and columns. The colors of the squares are all random. The animation that I want is to randomly change the colors of squares. This might mean several things, but after thinking for a while, I decide it would be neat to have a "disturbance" that wanders randomly around the window, changing the color of each square that it encounters.
Let's say that I manage to obtain a class, MosaicWindow, for working with windows full of little colored squares. If mosaic is a variable of type MosaicWindow, and if R and C are integers, then the statment
mosaic = new MosaicWindow(R,C);
will create a window object with R rows and C columns of squares, and will set the variable mosaic to refer to that window. ("new MosaicWindow(R,C)" is a special kind of function called a constructor -- a kind of factory for creating objects. For now, you should just accept this constructor, along with the rest of the MosaicWindow class, as a black box. I'll discuss constructors in the next chapter.)
The MosaicWindow class provides a number of subroutines, but the only thing I really need is to be able to set the color of one of the little squares in the window. This can be done with the statement
mosaic.setColor(row,column,r,g,b);
where "row" is an integer giving the number of the row whose color I want to set, "column" is an integer giving the number of the column, and "r", "g", and "b" are of type double and specify the red, blue, and green compontents of the color I want. To use this method correctly, you need to know a few more things: If the window has R rows, the rows are numbered top-to-bottom from 0 to R-1, so the value of the parameter row must be between 0 and R-1. Similarly, columns are numbered from 0 to C-1, where C is the number of columns in the window, so columns must be between 0 and C-1. Each of the numbers r, g, and b must be in the range 0.0 to 1.0. If r has a value of 0.0, then the color contains no red component at all; if r has a value of 1.0, then it contains the maximum possible amount of red; intermediate values give intermediate levels of red. The other two color components work in the same way. All this is part of the contract of the subroutine, that is, the specification of how the subroutine is used and what it does.
With basic routines for manipulating the window in hand as a foundation, I can turn to the specific problem at hand. A basic outline for my program is
Open the window; Fill window with random colors; Move around, changing squares at random.I already have a subroutine to do the first step. Filling the window with random colors seems like a nice coherent task that I can work on separately, so let's decide that I'll 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. Thus we can refine the algorithm to:
Open the window; Fill window with random colors; Set the current position to the middle square in the window; Repeat forever: 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. To open the window, we need to know how many rows and columns there are. Let's represent these quantities with constants named ROWS and COLUMNS. Giving names to the subroutines that I still have to write and using "while (true)" to implement an infinite loop, we get:
mosaic = new MosaicWindow(ROWS, COLUMNS); fillWithRandomColors(); currentRow = ROWS / 2; // middle row, halfway down the window currentColumn = COLUMNS / 2; // middle column while (true) { changeToRandomColor(currentRow, currentColumn); randomMove(); }With the proper wrapper, this is the main() routine of my program. I still have to write the subroutines fillWithRandomColors(), changeToRandomColor(int,int), and randomMove(). Pseudocode for fillWithRandomColors() could be given as:
For each row: For each column: set 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:
for (row = 0; row < ROWS; row++) for (column = 0; column < COLUMNS; column++) changeToRandomColor(row,column);I could go on to discuss the other two subroutines, but you get the idea. Here is the complete program:
public class RandomMosaicWalk { /* 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 in an infinite loop, and so will never end on its own. */ final static int ROWS = 10; // number of rows of squares // (The rows of squares are numbered from 0 to ROWS-1) final static int COLUMNS = 20; // number of columns of squares // (The columns of squares are numbered from 0 to COLUMNS-1) static MosaicWindow mosaic; // the actual 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. MosaicWindow mosaic = new MosaicWindow(ROWS,COLUMNS); fillWithRandomColors(); int currentRow = ROWS / 2; // start at center of window int currentColumn = COLUMNS / 2; while (true) { changeToRandomColor(currentRow, currentColumn); randomMove(); } } // end of main() static void fillWithRandomColors() { // fill every square, in each row and column, // with a random color for (row=0; row < ROWS; row++) { for (column=0; column < COLUMNS; column++) { changeToRandomColor(row, column); } } } // end of fillWithRandomColors() static void changeToRandomColor(int rowNum, int colNum) { // change the square in row number rowNum and // column number colNum to a random color. double red = Math.random(); // choose random levels in range double green = Math.random(); // 0.0 to 1.0 for red, green, double blue = Math.random(); // and blue color components mosaic.setColor(rowNum,colNum,red,green,blue); } // end of changeToRandomColor() static void randomMove() { // randomly move the disturbance in one of // four possible directions: up, down, left, or right; // if this moves the disturbance outside the window, // then move it to the opposite edge of the window. int directionNum = (int)(4*Math.random()); // directionNum is randomly set to 0, 1, 2, or 3 switch (directionNum) { case 0: // move up currentRow--; if (currentRow < 0) currentRow = ROWS - 1; break; case 1: // move right currentColumn++; if (currentColumn >= COLUMNS) currentColumn = 0; break; case 2: // move down currentRow ++; if (currentRow >= ROWS) currentRow = 0; break; case 3: currentColumn--; if (currentColumn < 0) currentColumn = COLUMNS - 1; break; } } // end of randomMove() } // end of class RandomMosaicWalk
End of Chapter 3
[ Next Chapter | Previous Section | Chapter Index | Main Index ]