Analysis of structured programs

ABSTRACT

We investigate various control structures to understand their computational complexity and limitations. It is generally felt that GOTO-less programs constructed from the classical primitives are very restrictive; structured programming languages like BLISS, however, incorporating Repeat-Exit constructs appear to ease this sense of restrictiveness. In this paper we analyze this construct. We answer a conjecture of Knuth and Floyd as a special case of the general theory. We also investigate a general Top-Down Programming construct, which we call the TDn-construct. We structurally characterize the class of GOTO-less programs. We also generalize such an analysis and solve an open problem of Böhm and Jacopini.

REFERENCES

• 1: Ashcroft, E. and Manna, Z., The translation of "go to" Programs, Booklet TA-2, Preprints of the IFIP Congress 1971, Ljubljana, Yugoslavia, August 1971.
• 2: 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]
• 3: J. Bruno , K. Steiglitz, The Expression of Algorithms by Charts, Journal of the ACM (JACM), v.19 n.3, p.517-525, July 1972 [doi>10.1145/321707.321720]
• 4: 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]
• 5: Cooper, D.C., Some transformations and standard forms of graphs, with applications to computer programs. Machine Intelligence 2, 1967, pp. 21-32.
• 6: 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]
• 7: Dijkstra, E. W., Notes on Structured Programming, T.H. Report 70-WSK-03 (Technological University Eindhoven, Netherlands, 1970)
• 8: Matthew S. Hecht , Jeffrey D. Ullman, Flow graph reducibility, Proceedings of the fourth annual ACM symposium on Theory of computing, p.238-250, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804919]
• 9: Knuth, D. E. and Floyd, R. W., Notes on Avoiding "Go To" statements, Report No. CS-148, C.S. Dept., Stanford University, 1970.
• 10: Kosaraju, S. Rao, Analysis of Structured Programs, Tech. Report, Electrical Engineering Department, The Johns Hopkins University, November 1972.
• 11: Mills, H. D., Mathematical Foundations for Structured Programming, FSC 72-6012 (Federal Systems Division, IBM Corp., Gaithersburg, Md. 1972).
• 12: Wulf, W. A., Programming without the Go To, Booklet TA-3, Preprints of the IFIP Congress 71, Ljubljana, Yugoslavia, August 1971

INDEX TERMS

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

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

General Terms:
Theory