wtwolfe@hubcap.UUCP (Bill Wolfe) (01/23/89)
There has been a series of articles from those interested in automatic
translation who wish to target Ada and still retain GOTOs for convenience.
The following abstract, which appears in the current issue of
Communications of the ACM (V32,#1,P140), shows that it is possible
for automatic translators to have their GOTOs and eat them too,
even while retaining the same general control structures.
ELIMINATING GO TO'S WHILE PRESERVING PROGRAM STRUCTURE
Lyle Ramshaw
Suppose we want to eliminate the local GO TO statements of a Pascal
program by replacing them with multilevel loop exit statements. The
standard ground rules for eliminating GO TO's require that we preserve
the flow graph of the program, but they allow us to completely rewrite
the control structures that glue together the program's atomic tests
and actions. The GO TO's can be eliminated from a program under those
ground rules if and only if the flow graph of that program has the
graph-theoretic property named reducibility.
This paper considers a stricter set of ground rules, introduced by
Peterson, Kasami, and Tokura, which demand that we preserve the
program's original control structures, as well as its flow graph,
while we eliminate its GO TO's. In particular, we are allowed to
delete the GO TO statements and the labels that they jump to and to
insert various exit statements and labeled repeat-endloop pairs for
them to jump out of. But we are forbidden to change the rest of the pr
program text in any way. The critical issue that determines whether
GO TO's can be eliminated under these stricter rules turns out to be
the static order of the atomic tests and actions in the program text.
This static order can be encoded in the program's flow graph by
augmenting it with extra edges. It can then be shown that the
reducibility of a program's augmented flow graph, augmenting edges
and all, is a necessary and sufficient condition for the eliminability
of GO TO's from that program under the stricter rules.
For Correspondence: Digital Equipment Corporation Systems Research
Center, 130 Lytton Ave., Palo Alto, CA 94301.
Thus, automatic translators can ensure that the gotos they generate
do not violate the reducibility property with respect to the flow graph,
and then remove the gotos in the final phase of translation. If it is
desirable to leave the control structures of the final code intact,
this paper shows that it is even possible to do that. Therefore, it
seems that automatic translators could survive quite nicely even if
the GOTOs are eliminated in the 9X version of Ada.
Bill Wolfe, wtwolfe@hubcap.clemson.edu