eliminate the outer loop and CASE statement entirely; all that would be needed is GOTO statements at the end of each module, linking them together. This will speed up the program by eliminating the PROGRAM-COUNTER variable, without appreciably altering the structure of the program. Unfortunately, this produces a rat's nest of true GOTO statements, which is not structured.
This points up to some extent the ultimate futility of the Boehm-Jacopini theorem. We can certainly express all programs in a structured form by introducing flag variables, but the preceding series of reasonable transformations merely renders it unstructured again, demonstrating that we had not really made the program structured in nature, but only in form.
There is another way out. Let us not use GOTO statements to jump between modules, and let us not use flag variables to signal what are effectively GOTO statements to an outer control loop. Instead, let us consider what a single module does: it performs its bit of processing, and then invokes or otherwise designates another module to complete processing. Suppose therefore that at the end of every module we had a procedure call to the next module:
PROCEDURE MODULE23;
BEGIN
<do processing>;
IF <testl> THEN PERFORM MODULE10
ELSE IF <test2> THEN PERFORM MODULEl5
ELSE PERFORM MODULE2O;
END;
where we might as well have written "CALL" for "PERFORM".
This will certainly do what we want; if MODULE23 calls MODULE10, then MODULE10 will carry on, calling other modules in the process, and eventually the program will complete. It is also "structured"; the only constructs used are sequencing, possibly conditionals, and procedure calls. It uses no GOTO statements. There is also an additional bonus: if MODULE23 wants to pass some information to MODULE10, it can pass them as parameters rather than having to use global variables. This can help prevent conflicting usages of global variables among disjoint module sets.
From this example we can induce the following theorem:
Any flowchart can be written as a program which uses only sequencing, conditionals, and procedure calls.
This theorem is not new; it appears in McCarthy's 1960 paper. [McC60] It is quite easy to prove. We assume without loss of generality that the boxes of the flowchart are of two sorts: process boxes with one exit, and conditional boxes with two. A process box may contain any single-exit computation whatsoever (which may be built up from sequencing, conditional, and while-do loops, for example). A conditional may contain a predicate which decides which of two exits to take.
For each box in the flowchart we construct a procedure. If a box A is a process box whose exit branch leads to box B, then the procedure for A is:
PROCEDURE A; BEGIN <processing>; CALL B END;If a box C is a conditional box whose exit branches lead to boxes D and E, then the procedure for C is:
PROCEDURE C; IF <predicate> THEN CALL D ELSE CALL E;