An algorithm for structuring programs (Extended Abstract)

ABSTRACT

Structured programming emphasizes programming language constructs such as while loops, until loops, and if then else statements. Properly used, these constructs make occurrences of loops and branching of control obvious. They are preferable to goto statements, which tend to obscure the flow of control [DDH,DIJ]. This paper describes an algorithm which transforms a flowgraph into a program written using repeat (do forever) and if then else statements. The goal of the algorithm is to produce readable programs, rather than to avoid the use of goto statements entirely. goto statements are generated when there is no better way to describe the flow of control. A number of techniques for eliminating goto statements from programs have been previously published [AM, BJ, BS, COO, KF, KOS, PKT]. However, these techniques do not necessarily produce clear flow of control [KN]. Misuse of control constructs may mislead the reader into expecting patterns of control flow which do not exist in the algorithm. For example, these techniques may use a repeat statement when the contained code cannot be executed more than once or add numerous control variables to avoid goto statements. They also may avoid goto statements by copying segments of code or creating subroutines. The former method results in longer programs and bugs may be introduced when all the identical segments must be modified. The latter method may result in subroutines which appear unnatural.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 2: E. Ashcroft and Z. Manna, Translating program schemas to while-schemas, SIAM J. on Comp. 4,2 (1975), 125-146.
• 3: B. S. Baker, struct, a program which structures fortran, in preparation.
• 4: 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]
• 5: J. Bruno and K. Steiglitz, The expression of algorithms by charts, J. ACM 19 (1966),366-371.
• 6: David C. Cooper, Böhm and Jacopini's reduction of flow charts, Communications of the ACM, v.10 n.8, p.463, Aug. 1967 [doi>10.1145/363534.363539]
• 7: Ole Johan Dahl, Structured Programming, Academic Press, Inc., Orlando, FL, 1972
• 8: 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]
• 9: 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]
• 10: M. S. Hecht and J. D. Ullman, Flow graph reducibility, SIAM J. Comput. 1 (1972), 188-202.
• 11: B. W. Kernighan, ratfor - a preprocessor for a rational fortran, Software Practice and Experience 5,4 (1975), 395-406.
• 12: D. E. Knuth and R. W. Floyd, Notes on avoiding "go to" statements, Infor. Proc. Letters 1 (1971), 23-31.
• 13: 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]
• 14: S.R. Kosaraju, Analysis of structured programs, J. Comp. Sys. Sci. 9,3 (1974), 232-254.
• 15: W. W. Peterson , T. Kasami , N. Tokura, On the capabilities of while, repeat, and exit statements, Communications of the ACM, v.16 n.8, p.503-512, Aug. 1973 [doi>10.1145/355609.362337]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques
          Subjects: Structured programming

General Terms:
Algorithms, Languages, Theory