Structured programming in Basic; part 3: an application. Arthur Luehrmann.
As pointed out in last month's article, the real payoff of using the tools of structured programming comes when you are faced with a big job. Small programming tasks usually yield to a brute force attack, but as the job gets bigger it gets disproportionately harder to get the program to work.
An hour or so of trial-and-error patching and debugging is multiplied into weeks or months when the number of program lines goes from 100 to 1000. Many programmers hit their "wall" on these long programs. Structured programming methods promise to change all that and bring the difficulty of the job back into proportion with the size of the program that will result.
Unfortunately, it is not practical in these few pages to present a truly big programming job and show how to solve it. That would take too much space and time. So, although we are forced to pick a smallish example for now, keep in mind that it is a stand-in for any programming problem you may face. The methods shown here are exactly the same ones to use on a program of 1000 lines or 5000 lines.
The programming example we have chosen is a simple word game. We want to have the computer play the game with a user of the program. Here is an informal description of the game as two people might play it together:
The game starts when Susan thinks of a secret word. After that, Bill tries again to guess the word. Each time, Susan tells Bill whether the secret word is earlier or later in the dictionary than the one Bill guessed. As soon as Bill guesses correctly, Susan says "You got it!" and the ends.
Our goal will be to write a program that tells the computer precisely how to play Susan's part in the game. Though this task is simple enough to handle by almost any method, let's see how the structured approach works. Top-down Planning
The wrong thing to do at this point isto go the computer and begin entering Basic statements. Instead, let's recall the steps of the top-down method of planning any program. Here they are:
1. Always start by planning a simple main routine. Use English phrases to describe the major tasks to be done. Avoid thinking about details.
2. Translate each English phrase into one or two Basic statements. If more are needed, use a GOSUB statement to refer to a subroutine that will contain the details.
3. Write skeleton versions of the subroutines, including PRINT statements for debugging. Run the program and check that things are done in the right order.
4. Fill in the details of each subroutine. Use these same four steps with each subroutine. If new, more detailed subroutines are created in the process, do the same four steps with them.
5. After the program is working according to the original plan, undertake any refinements you think necessary or desirable.
We begin with step 1: planning the main routine. A good starting point for such a plan is an ordinary outline written in English. Here is possible way to describe the game in outline form:
1. Susan thinks of a secret word.
2. Bill guesses again and again, and Susan gives hints until he gets it right.
3. Susan congratulates him. Now it is easy how to convert the steps of the outline into the main routine of our program. Here is the first stage of the conversion, partly in Basic and partly still in English: 100 PROGRAM GUESSING GAME 110 get secret word 120 guess words 130 wrap up game 140 END
Note that the outline gives no details. How does the computer get the secret word? How does the user guess words? How does the computer wrap up the game? At this stage, it makes no difference how the computer does these things. In fact, these details are exactly the wrong things to think about now. Details will come later, when we write the subroutines that tell the computer what these "top level" instructions mean.
Now we go on to step 2 of the top-down method: converting the main routine completely into Basic statements. There are no simple Basic statements that you can substitute for the English phrases. That means we should use a GOSUB for each one: 100 'PROGRAM GUESSING GAME 110 GOSUB 200 'SECRET WORD 120 GOSUB 400 'GUESS WORDS 130 GOSUB 600 'WRAP UP 140 END
Note that we have used the apostrophe (') abbreviation for REM and :REM, as several current versions of Basic allow. To improve readability, we have indented the body of the main routine. In some versions of Basic, one must use colons to get indentation.
Now that the main routine is finished (and we will never return to it!), it is time to go on to step 3: writing skeleton subroutines, entering the program, and checking for errors. Each skeleton subroutine should have a PRINT statement saying which routine it is. The purpose here is to allow us to verify that the overall structure of the program is correct before going on. Here is the program with skeleton subroutines: 100 'PROGRAM GUESSING GAME 110 GOSUB 200 'SECRET WORD 120 GOSUB 400 'GUESS WORDS 130 GOSUB 600 'WRAP UP 140 END 190 ' 200 'SUB SECRET WORD 210 PRINT "SECRET WORD SUBROUTINE" 380 RETURN 390 ' 400 'SUB GUESS WORDS 410 PRINT "GUESS WORDS SUBROUTINE" 580 RETURN 590 ' 600 'SUB WRAP UP 610 PRINT "WRAP UP SUBROUTINE" 780 RETURN Now we have a complete Basic program that can be entered into the computer and run. It won't play the game yet, but as soon as the computer prints SECRET WORD SUBROUTINE GUESS WORDS SUBROUTINE WRAP UP SUBROUTINE we will be certain that the structure of the program is correct and that all the GOSUB and RETURNS are in good working order. Then we will have a strong framework that will allow us to concentrate on each block of the program without worrying about the others.
Next we go on to step 4 of the top-down process: Filling in the details of each subroutine body. We begin with the SECRET WORD routine. What must it tell the computer to do? Remember that the purpose of this routine is to have the computer do what Susan did when she "thought of a secret word." Unfortunately, computers don't know many English words, so this part looks hard. We'll take the easy way out and have the computer ask someone other than the player to enter a secret word.
To fill in the body of the subroutine, we follow exactly the same rules we used for the main routine: (1) make an outline in English , (2) convert it to Basic, and (3) write more skeleton subroutines if necessary. Here is an outline version of SECRET WORD: 200 'SUB SECRET WORD 210 clear the screen 220 ask for secret word 230 input secret word 380 RETURN
Lines 200 and 380 are holdovers from the skeleton version. The next step is to replace each English phrase with one or two Basic statements to carry out the task described, or else to use a GOSUB to a new subroutine. Here is the result: 200 'SUB SECRET WORD 210 CLS 220 PRINT "WHAT'S THE SECRET WORD"; 230 INPUT S$ 380 RETURN
Line 210 might be different in different versions of Basic. In Applesoft, for example, the statement is spelled HOME. Note that each English phrase was easily convertible into one Basic statement, so no new GOSUBS were necessary.
The last step for this subroutine is to enter these new body statements into the computer and check for errors. Checking is best done in the immediate mode (if available) by typing GOSUB 200. If all is in order, the screen should be erased, the prompt message should be printed, and the computer should wait for input. Entering any word should cause a return from the subroutine. Then, entering PRINT S$ in immediate mode will confirm that the word was correctly assigned to S$. Using Control Blocks
We can now turn to the GUESS WORDS subroutine, which is the heart of the entire program. Its job is to tell the computer to accept guess after guess from the user, give hints if the guess is wrong, and stop asking for more guesses if the guess is right. Obviously, there are many details to worry about here.
The trick is not to get bogged down ing details. Instead, think about the structure of the problem. Recall how two people play the game. Once Susan thinks of a secret word, Bill guesses again and again, getting hints along the way, until he guesses the right word. What kind of program structure tells the computer to do something "again and again until" some condition becomes true?
If the answers doesn't jump to mind, remember the Boehm and JAcopini theorem from last month's article:
Theorem: Any program logic, no matter how complex, can be resolved into only three kinds of blocks: actions, loops, and branches.
Action blocks are just straight sequences of action statements, such as INPUT, LET, and PRINT, which are to be performed one after the other. Loop blocks contain statements that are to be performed again and again until some exit condition becomes true. Branch blocks contain two groups of statements only one of which is to be performed.
Now we come back to our question: Which kind of program block will be needed to tell the computer to accept guesses again and again until the guess is correct? A loop block, of course. The exit condition from the loop is that the guess matches the secret word.
Now we can get started on the body of the GUESS WORDS subroutine. The first step is to write a bare-bones outline of the loop block and put it inside GUESS WORDS. Here it is, with the loop in lines 410 through 500: 400 'SUB GUESS WORDS 410 'LOOP -- DO SOMETHING -- If exit-condition THEN 500 -- do something 490 GOTO 410 500 'END LOOP 580 RETURN
The next step is to figure out what the two "do somethings" and the "exit-condition" are. The first "do something" has to ask for the user's guess and accept it as input. The "exit-condition" is that the guess is correct. The second "do something" has to give the user a helpful hint. Here is a more detailed outline of the loop block: 400 'SUB GUESS WORDS 410 'LOOP -- ask for guess -- input guess -- IF guess is correct THEN 500 -- give a hint 490 GOTO 410 500 'END LOOP 580 RETURN
We can easily replace the first two phrases with Basic statements. We need a Basic condition in the IF statement to test whether the guess is correct. If the guess is incorrect, the computer must "give a hint." It will take more than one or two Basic statements to give a hint, so we use a GOSUB and bury details in a new subroutine. Here is the complete version of GUESS WORDS: 400 'SUB GUESS WORDS 410 'LOOP 420 PRINT "WHAT'S YOUR GUESS"; 430 INPUT G$ 440 IF G$ = S$ THEN 500 450 GOSUB 800 'HINT 490 GOTO 410 500 'END LOOP 580 RETURN
To test this subroutine, we need a skeleton version of the HINT subroutine. Here it is: 800 'SUB HINT 810 PRINT "HINT SUBROUTINE" 980 RETURN
Now we can do our testing of GUESS WORDS. We first enter all the new body statements in lines 410 through 500, plus the skeleton version of HINT. Next we enter LET S$ = "CAT" in immediate mode to establish a value for the secret word. Then we enter GOSUB 400 in immediate mode. After that, we can test the loop by replying to the input prompts with a series of words, such as DOG, RAT, BAT, CAT. The computer should stay in the loop, printing HINT SUBROUTINE after each reply until the reply is CAT. After that, the return should occur.
It is tempting now to plunge in finish work on subroutine HINT. that, however, is a detail that is best put off until we finish with the last of the three original subroutines, WRAP UP. Its job is to have the computer print a final message saying that the game is over and the word was guessed. So little planning is needed for this routine that we can write it directly in Basic and test it in the immediate mode, like the others. Here it is: 600 'SUB WRAP UP 610 PRINT "YOU GOT IT!!!" 620 PRINT "THE WORD WAS"; S$ 780 RETURN Another Control Block
We have now completed the main routine and all three subroutines it calls. But the job is not over. Subroutine GUESS WORDS has a GOSUB 800 to a subroutine named HINT. HINT exists only in skeletal form. What should we write for the body of HINT?
The trick, once again, is not to get bogged down in details. Instead, think about th structure of the problem. Recall how people play the game. After each wrong guess, Susan tells Bill that the secret word is either earlier or later in the dictionary than Bill's guess. What kind of program structure tells the computer to do either one thing or another?
The answer is the branch block. (IF there are any doubts, just go through the three possibilities allowed by Messrs. Boehm and Jacopini.) Knowing that, the next step is easy: writing a bare-bones outline of the branch block as the body of the HINT subroutine. Here it is: 800 'SUB HINT 810 IF condition THEN 850 -- 'FALSE -- do something -- GOTO 870 850 'TRUE -- do something 870 'END IF 980 RETURN Lines 810 through 870 contain the outline of any brance block. Our job is to convert "condition" and the two "do somethings" into the right Basic for the job that HINT must do, which is to print one of two possible prompting messages. For example, if the secret word (S$) is CAT and the guess (g$) is BAT, then the computer should print LATER THAN BAT.
If the guess is RAT, the computer should print EARLIER THAN RAT. Here is a more specific outline of the branch block: 800 'SUB HINT 810 IF secret earlier than guess THEN 850 -- 'FALSE -- give "later" hint -- GOTO 870 850 'TRUE -- give "earlier" hint 870 'END IF 980 RETURN
It is easy now to translate this outline from English directly into Basic. Here is the final version of HINT: 800 'SUB HINT 810 IF S$ < G$ THEN 850 820 'FALSE 830 PRINT "LATER THAN"; G$ 840 GOTO 870 850 'TRUE 860 PRINT "EARLIER THAN"; G$ 870 'END IF 980 RETURN
Like the other subroutines, this one can also be tested in the immediate mode. Entering the statements, LET S$ = "CAT", LET G$ = "DOG", and GOSUB 800, should produce the hint EARLIER THAN DOG. After that, entering the statements LET G$ = "BEE" and GOSUB 800, should yield the hint LATER THAN BEE. The Complete Program
Now all the routines have been planned, written, entered into the computer, and fully tested independently of one another. The only thing left is to confirm that all the parts work together correctly. We do that by typing RUN, entering a secret word, and then trying a sequence of guess words. Since all the parts have been tested, we expect the whole to work. It does. Here it is: 100 'PROGRAM GUESSING GAME 110 GOSUB 200 'SECRET WORD 120 GOSUB 400 'GUESS WORDS 130 GOSUB 600 'WRAP UP 140 END 190 ' 200 'SUB SECRET WORD 210 CLS 220 PRINT "WHAT'S THE SECRET WORD"; 230 INPUT S$ 380 RETURN 390 ' 400 'SUB GUESS WORDS 410 'LOOP 420 PRINT "WHAT'S YOUR GUESS"; 430 INPUT G$ 440 IF G$ = S$ THEN 500 450 GOSUB 800 'HINT 490 GOTO 410 500 'END LOOP 580 RETURN 590 ' 600 'SUB WRAP UP 610 PRINT "YOU GOT IT!!!" 620 PRINT "THE WORD WAS"; S$ 780 RETURN 790 ' 800 'SUB HINT 810 IF S$ < G$ THEN 850 820 'FALSE 830 PRINT "LATER THAN"; G$ 840 GOTO 870 850 'TRUE 860 PRINT "EARLIER THAN"; G$ 870 'END IF 980 RETURN
There are a few noteworthy things about programs written in this structured form. First of all, they are practically self-documenting. The only remark statements used are there for structural reasons: to mark the beginnings of routines, the beginnings and endings of control blocks, and the TRUE and FALSE cases in the branch block. Copious explanatory remarks are missing because they are not needed.
Second, programs in this form are especially easy to work with on a CRT display. Limited screen size makes it impossible to see the entire listing of a long program. But if you need to find something in the listing of a long structured program, there is a simple and straight forward method. Begin by listing the first dozen or so lines, which contain the main routine. In the listing, each GOSUB contains a tail remark describing the purpose of the subroutine, and contains the line number at which the routine begins. Therefore, you can use the main routine as a "table of contents" for the whole program. And, by keeping each routine under 20 lines or so, you can list all its statements on your screen.
Most important of all, structured programs are easy to understand
and, for that reason easy to modify and to maintain. That is the
topic we turn to next. Making Refinements
Step 5 of the top-down method is to make refinements to the program. No matter how much care and planning go into a program, it seems always true that as soon as the program runs successfully, we discover changes and revisions that need to be made. In that sense, writing a program is like writing a paper or report: when we see the whole draft for the first time, we feel the need to revise and improve.
Structured programs lend themselves to easy revision, modification, and refinement. This fact becomes truly clear only when you see an example. Therefore, let's look at our GUESSING GAME program with a jaundiced eye and see what is wrong with the way it currently works. Here are a few problems that need fixing:
1. After someone enters the secret word, it stays on the screen. The game isn't much of a challenge if the player can look on the screen and see the answer.
2. If someone typed ANTIDISESTABLISHMENTARIANISM as the secret word, it might take a while for the player to guess it.
3. The guessing will go on forever if the player cannot find the secret word. Also, it might be more challenging to allow only a given number of guesses.
Let's see how to attack these problems. The first is easy: making the secret word disappear from the screen after it is entered.
We begin by finding the place in the listing to make the change. When deciding what part of a structured program to look at or change, use the main routine as a directory. Here it is: 100 'PROGRAM GUESSING GAME 110 GOSUB 200 'SECRET WORD 120 GOSUB 400 'GUESS WORDS 130 GOSUB 600 'WRAP UP 140 END
You can see the subroutines GUESS WORDS and WRAP UP have nothing to do with getting the secret word. But subroutine SECRET WORD obviously does. Here is how it looks now: 200 'SUB SECRET WORD 210 CLS 220 PRINT "WHAT'S THE SECRET WORD"; 230 INPUT S$ 380 RETURN
When someone replies to the INPUT statement, the secret word stays on the screen. Getting rid of it easy: Just put another clear-the-screen statement as line 240. The player must look away while the secret word is being typed, but afterward the word will disappear from the screen.
The second problem we need to solve is limiting the length of the secret word. Once again, we need to change subroutine SECRET WORD, and we can ignore the rest of the program. Here is how the routine now looks: 200 'SUB SECRET WORD 210 CLS 220 PRINT "WHAT'S THE SECRET WORD"; 230 INPUT S$ 240 CLS 380 RETURN
Let's change the subroutines so that if a secret word longer than three characters is entered, the computer will reject the word and ask for a shorter word. If the secret word is three or fewer characters, the game should begin.
As before, the wrong way to start is to plunge in with a patchwork of Basic statements. The right approach is to ask "What kind of block do I need to use? Is it an action, a loop, or a branch?" The clue lies in the fact that if one keeps entering words longer than three characters, the computer should keep asking for another word. As soon as the length is okay, the computer should stop asking. So we need a loop block.
The loop should begin after the first CLS statement and end before the second. Here is a bare-bones outline: 200 'SUB SECRET WORD 210 CLS 215 'LOOP -- do something -- IF exit-condition THEN 238 -- do something 236 GOTO 215 238 'END LOOP 240 CLS 380 RETURN
The next step is to decide what the "do somethings" and the "exit-condition" should be. The first "do something" is easy: It is just an action block consisting of the present lines 220 and 230, which prompt for input and assign the input to S$. The "exit-condition" is that the length of S$ be three or less. The second "do something" needs to be a PRINT statement to prompt for a shorter secret word. Here is the final version of the loop: 200 'SUB SECRET WORD 210 CLS 215 'LOOP 220 PRINT "WHAT'S THE SECRET WORD"; 230 INPUT S$ 232 IF LEN (S$) [is less than or =] 3 THEN 238 234 PRINT "TOO LONG" 236 GOTO 215 238 'END LOOP 240 CLS 380 RETURN
If the secret word has three characters or fewer, the computer now leaves the loop. If not, the computer goes on to line 234, and prints the TOO LONG prompt. Then the computer returns to the beginning of the loop.
Here is an important point to note: When we first planned subroutine SECRET WORD, it contained only an action block. With the improvement we just made, the subroutine now contains a loop with action blocks inside the loop. More often than not, program revisions mean fundamental changes in block structure. Thinking hard about block structure is the best way to avoid having a program end up looking like a patchwork quilt.
Now we can start thinking about the third problem: how to limit the number of guesses. First, we have to decide which program block should be changed. It certainly cannot be the SECRET WORD subroutine or the WRAP UP subroutine. That leaves only the GUESS WORDS subroutine. Here is how it now stands: 400 'SUB GUESS WORDS 410 'LOOP 420 PRINT "WHAT'S YOUR GUESS"; 430 INPUT G$ 440 IF G$ = S$ THEN 500 450 GOSUB 800 'HINT 490 GOTO 410 500 'END LOOP 580 RETURN
At present, the computer stops looping only when the guess is correct. We want the loop to stop when the guess is correct or when the player uses up the allowed number of guesses, so we need a compound condition in the IF statement. Let's use the variable C to count the number of guesses and agree to limit the guesses to 10. Then the exit-condition needs to be changed to this: G$ = S$ OR C = 10
With this change, the IF statement now says to end the loop if C equals 10. But how does the computer know where to start counting? And how does it keep track of the number of guesses? We need two new statements. First, we must set the value of C to 1 (for the first guess) outside the loop. Second, we must have the computer add 1 to C each time through the loop. Here is the subroutine with the new IF statement and the statements that define and keep track of C. 400 'SUB GUESS WORDS 405 LET C = 1 410 'LOOP 420 PRINT "WHAT'S YOUR GUESS"; 430 INPUT G$ 440 IF G$ = S$ OR C = 10 THEN 500 450 GOSUB 800 'HINT 460 LET C = C + 1 490 GOTO 410 500 'END LOOP 580 RETURN
Here is another important thing to note: Even though the above loop depends on a counter that increases in steps of 1, it cannot be replaced by the FOR/NEXT shortcut. This is true because the exit-condition depends on two things: the value of the counter and the value of G$. Trying to use a FOR/NEXT loop here would force us to use either a wild jump out of the loop or tricky manipulation of the loop variable. Using the general form of the loop block avoids these unstructured tactics and improves readability.
That might seem to wrap up the three changes we set out to make. However, the last change has created a new problem: subroutine WRAP UP gives a winning message whether or not the word was guessed. Here is how it reads now: 600 'SUB WRAP UP 610 PRINT "YOU GOT IT!!!" 620 PRINT "THE WORD WAS"; S$ 780 RETURN
The body of the subroutine is now a single action block. What kind of block is needed to print either a winning message or a losing message? The branch block will do the job, and so we must change the basic structure from an action block to a branch block. Here is the WRAP UP subroutine with a bare-bones branch outline in lines 601 through 615: 600 'SUB WRAP UP 601 IF condition THEN 605 -- 'FALSE -- do something -- GOTO 615 605 'TRUE 610 PRINT "YOU GOT IT!!!" 615 'END IF 620 PRINT "THE WORD WAS"; S$ 780 RETURN
Note that we have preserved lines 610 and 620 intact, but 610 is now inside the branch block. Now we must decide on the "condition" and the FALSE "do something." Since line 610 is the TRUE "do something," we want to get the congratulatory message when the "condition" is true. So the "condition" must be G$ = S$. Furthermore, the FALSE "do something" needs to be a YOU LOSE message. Here is the complete branch: 600 'SUB WRAP UP 601 IF G$ = S$ THEN 605 602 'FALSE 603 PRINT "YOU LOSE" 604 GOTO 615 605 'TRUE 610 PRINT "YOU GOT IT!!!" 615 'END IF 620 PRINT "THE WORD WAS"; S$ 780 RETURN
Now the branch block tells the computer to print YOU GOT IT!!! if G$ = S$; that is, if the guess is correct. If G$ < > S$, the computer prints the message YOU LOSE. Either way, the computer prints the secret word on the screen.
We have now finished planning, implementing, and refining the GUESSING GAME program. When in the planning stage, we used the top-down method to break the task into small, meaningful units. When handling any problem in program logic, we needed to use only three formal control blocks: actions, loops, and branches. By adhering strictly to these principles of structured programming, we were able to produce a program that worked, that was easy to read, and that was easy to change. Without ever using the crutch of detailed flowcharts or hours budgeted for brute-force patching and debugging, we got results.
The programming task we set ourselves here was a very simple one, of course. It was picked to be a practical size for an article such as this, but also to exemplify a general approach to program development that will work for a task of any size. The method is easy to learn, easy to use, and easy to teach to others. Why and how it has been so successfully kept a secret from the community of Basic programmers for the past decade is hard to fathom. Coming Next Month
The first three articles in this four-part series have introduced structured programming methods in a language with which most people are familiar: Basic as implemented on today's microcomputers. In these Basics, subroutines, loop blocks, and branch blocks need to be built up from scratch, using very primitive statements: GOSUB, RETURN, IF, and GOTO. Better Basics exist today, and still better ones are on the way, thanks mainly to the efforts of Committee X3J2 of the American National Standards Institute, whose task it is to propose a national standard for a modern version of Basic. In ANSI Basic, the full set of structured programming methods is built into the language. Next month's article will show how to write these fundamental structures in ANSI Basic.