This page has been validated.
Guy L. Steele Jr.
11
"Debunking the "Expensive ..." Myth


E. The Expressive Power of Procedure Calls

Here we shall consider an example of how expressive procedure calls can be when used freely. The example is taken from Yourdon [You75,233]; he implies that the program was an actual one in use. He suggests that, rather than using many flag variables to indicate various conditions within a program, one should use a single variable which encodes the state of the program. The motivation behind this is that one should also draw a state diagram showing the valid transitions between states; the programmer is encouraged to think of his program as a finite-state automaton. In this way one can avoid the common error of producing an invalid combination of flag values. The state diagram for Yourdon's example is reproduced here.

The 128 possible combinations of seven independent flags have been reduced to 23 permissible states and the legal transitions among them.

The program itself is to be implemented using two variables OLD-STATE and NEW-STATE and a computed-GOTO or CASE statement. The main program dispatches to the module designated by NEW-STATE. The module can then check OLD-STATE to be sure the transition was valid. For example, module 14 would ensure that OLD-STATE held 11 or 16. When module 14 is done, it must store 14 into OLD-STATE and set NEW-STATE to the next state, and then branch back to the computed GOTO or CASE. It is assumed, though not stated, that all variables common to several modules are declared in an outer environment accessible to the modules.

We shall modify this set-up slightly to make it more foolproof. The first problem is that every module must contain code to manipulate OLD-STATE and NEW-STATE, and it is easy to forget to include this code. We shall perform this work within the CASE statement itself; this collects the transition information into one place. In order to avoid branching to the CASE statement, we shall embed the CASE statement in a loop. To terminate the loop, we will allow state 0 to represent the exit state. Finally, we shall rename the variables NEW-STATE and OLD-STATE to PROGRAM-COUNTER and OLD-PC. The resulting code looks like this: