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. 1.A. V. Aho and J. D. Ullman, The Theory of Parsing, Translation, and Compiling, Vol. II - Compiling, Prentice-Hall, Englewood Cliffs, N.J., 1973.
2. 2.E. Ashcroft and Z. Manna, Translating program schemas to while-schemas, SIAM J. on Comp. 4,2 (1975), 125-146.
3. 3.B. S. Baker, struct, a program which structures fortran, in preparation.
4. 4.C. Bohm and G. Jacopini, Flow diagrams, Turing machines and languages with only two formation rules, Comm. ACM 9 (1966), 366-371.
5. 5.J. Bruno and K. Steiglitz, The expression of algorithms by charts, J. ACM 19 (1966),366-371.
6. 6.D. C. Cooper, Bohm and Jacopini's reduction of flow charts, Comm. ACM 10R (1967),463.
7. 7.O.-J. Dahl, E. W. Dijkstra, and C. A. R. Hoare, Structured Programming, Academic Press, New York, 1972.
8. 8.E. W. Dijkstra, Goto statement considered harmful, Comm. ACM 11 (1968), 147-148.
9. 9.M. S. Hecht and J. D. Ullman, Characterizations of reducible flowgraphs, J. ACM 21,3 (1974), 367-375.
10. 10.M. S. Hecht and J. D. Ullman, Flow graph reducibility, SIAM J. Comput. 1 (1972), 188-202.
11. 11.B. W. Kernighan, ratfor - a preprocessor for a rational fortran, Software Practice and Experience 5,4 (1975), 395-406.
12. 12.D. E. Knuth and R. W. Floyd, Notes on avoiding "go to" statements, Infor. Proc. Letters 1 (1971), 23-31.
13. 13.D. E. Knuth, Structured programming with goto statements, ACM Comp. Surveys 6,4 (1974), 261-302.
14. 14.S.R. Kosaraju, Analysis of structured programs, J. Comp. Sys. Sci. 9,3 (1974), 232-254.
15. 15.W.W. Peterson, T. Kasami, and N. Tokura, On the capabilities of while, repeat and exit statements, Comm. ACM 16 (1973), 503-512.

Index Terms

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

• Software and its engineering

  • Software creation and management

    • Designing software

      • Software implementation planning

        • Software design techniques

    • Software development techniques

  • Software notations and tools

    • General programming languages

      • Language features

• Theory of computation

  • Design and analysis of algorithms