Eliminating go to's while preserving program structure

ABSTRACT

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 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.

REFERENCES

• 1: Brenda S. Baker, An Algorithm for Structuring Flowgraphs, Journal of the ACM (JACM), v.24 n.1, p.98-120, Jan. 1977 [doi>10.1145/321992.321999]
• 2: Brenda S. Baker , S. Rao Kosaraju, A Comparison of Multilevel break and next Statements, Journal of the ACM (JACM), v.26 n.3, p.555-566, july 1979 [doi>10.1145/322139.322151]
• 3: Corrado Böhm , Giuseppe Jacopini, Flow diagrams, turing machines and languages with only two formation rules, Communications of the ACM, v.9 n.5, p.366-371, May 1966 [doi>10.1145/355592.365646]
• 4: Edsger W. Dijkstra, Letters to the editor: go to statement considered harmful, Communications of the ACM, v.11 n.3, p.147-148, March 1968 [doi>10.1145/362929.362947]
• 5: David Harel, On folk theorems, Communications of the ACM, v.23 n.7, p.379-389, July 1980 [doi>10.1145/358886.358892]
• 6: HECHT, M. S., AND ULLMAN~ J.D. Flow eraph reducibility. SIAM J. Comput. 1, 2 (June 1972), 188-202.
• 7: M. S. Hecht , J. D. Ullman, Characterizations of Reducible Flow Graphs, Journal of the ACM (JACM), v.21 n.3, p.367-375, July 1974 [doi>10.1145/321832.321835]
• 8: K Jensen , N Wirth , A B Mickel , J F Miner, Pascal user manual and report; 3rd ed., Springer-Verlag New York, Inc., New York, NY, 1985
• 9: KEOHANE, J., CHERNIAVSKY, J. C., AND HENDERSON, P.I. On transforming control structures. SIAM J. Comput. 11, 2 (May 1982), 268-286.
• 10: B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
• 11: Donald E. Knuth, Structured Programming with go to Statements, ACM Computing Surveys (CSUR), v.6 n.4, p.261-301, Dec. 1974 [doi>10.1145/356635.356640]
• 12: Donald E. Knuth, The TEXbook, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 13: Donald Ervin Knuth, TEX: The Program, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 14: KNUTH, D. E., AND FLOYD, R.W. Notes on avoiding "go to" statements. InJ? Process. Lett. I, 1 (Feb. 197 l), 23-31 and 177.
• 15: KOSARAJU, S. R. Analysis of structured programs. J. Comput. System Sci. 9, 3 (Dec. 1974), 232-235.
• 16: Henry F. Ledgard , Michael Marcotty, A genealogy of control structures, Communications of the ACM, v.18 n.11, p.629-639, Nov. 1975 [doi>10.1145/361219.361222]
• 17: Mri~CHELL, .l.G., MAYBURY, W., AND SWEET, R. Mesa language manual. Tech. rep. ~aL-/~,-a. Xerox Palo Alto Research Center, Palo Alto, Calif., Apr. 1979.
• 18: PETERSON, W. W., KASAMI, T., AND TOKURA, N. On the capabilities of while, repeat, and exit
• 19: RAMSHAW, L. Problem 83-1, Jr. Algorithms 4, 1 (Mar. 1983), 85-86.
• 20: Henry Ledgard, Reference Manual for the ADA Programming Language, Springer-Verlag New York, Inc., Secaucus, NJ, 1983
• 21: WILLIAMS, M. H., AND CHEN, G. Restructuring Pascal programs containing goto statements. Comput. J. 28, 2 (May 1985), 134-137.
• 22: Niklaus Wirth, Programming in MODULA-2 (3rd corrected ed.), Springer-Verlag New York, Inc., New York, NY, 1985

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Control primitives

General Terms:
Theory, Verification