A genealogy of control structures

ABSTRACT

The issue of program control structures has had a history of heated controversy. To put this issue on a solid footing, this paper reviews numerous theoretical results on control structures and explores their practical implications. The classic result of Böhm and Jacopini on the theoretical completeness of if-then-else and while-do is discussed. Several recent ideas on control structures are then explored. These include a review of various other control structures, results on time/space limitations, and theorems relating the relative power of control structures under several notions of equivalence. In conclusion, the impact of theoretical results on the practicing programmer and the importance of one-in, one-out control structures as operational abstractions are discussed. It is argued further that there is insufficient evidence to warrant more than if-then-else, while-do, and their variants.

REFERENCES

• 1: Allen, F.E., and Cocke, J. A catalogue of optimizing transformations. In Randall Rustin (Ed.), Compiler Optimization. 5tb Courant Computer Science Symposium, Prentice-Hall, Englewood Cliffs, N.J., 1972, (pp. 1-30).
• 2: Edward A. Ashcroft , Z Manna, The translation of ''go to'' programs to ''while'' programs, Stanford University, Stanford, CA, 1971
• 3: G. V. Bochmann, Multiple exits from a loop without the GOTO, Communications of the ACM, v.16 n.7, p.443-444, July 1973 [doi>10.1145/362280.362300]
• 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 , 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]
• 6: Cooper, D.C. Some transformations and standard tbrms of graphs with applications to computer programs. In E. Dale and D. Michie (Eds.), Machine Intelligence 2. American Elsevier, New York, 1968, pp. 21-32.
• 7: Dijkstra, E. W. Notes on structured programming. In Structured Programming. W.J. Dahl, E.W. Dijkstra, and C.A.H. Hoare, Academic Press, New York, 1972, pp. 1-82.
• 8: Daniel P. Friedman , Stuart C. Shapiro, A case for while-until, ACM SIGPLAN Notices, v.9 n.7, p.7-14, July 1974 [doi>10.1145/953224.953225]
• 9: Gross, J.L., and Brainerd, W.S. Fundamental Programming Concepts. Harper and Row, New York, 1972.
• 10: Henderson, P., and Snowdon, R. An experiment in structured programming. BIT 12 (1972), 38-53.
• 11: Hoare, C.A.H., and Wirth, N. An axiomatic definition of the programming language PASCAL. Acta blformatica 2 (1973), 335-355.
• 12: Brian W. Kernighan , P. J. Plauger, The Elements of Programming Style, McGraw-Hill, Inc., New York, NY, 1982
• 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: Knuth, D.E., and Floyd, R.W. Notes on avoiding GO TO statements. Rep. No. CS-148, Comput. Sci. Dep. Stanford U., 1970.
• 15: Kosaraju, R. Analysis of structured programs J. Comput. and Syst. Sci., 9, 3 (Dec. 1974), 232-255. Tech. Rep. No. 72-11, Elect. Eng. Dep., Johns Hopkins U. 1972.
• 16: B. M. Leavenworth, Programming with(out) the GOTO, Proceedings of the ACM annual conference, p.782-786, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800194.805859]
• 17: Ledgard, H. F. Programming Proverbs. Hayden Publishing Co., Rochelle Park, N.J., 1975.
• 18: McKeeman, W.M., Horning, J.J., and Wortman, D.B. A Compiler Generator. Prentice-Hall, Englewood Cliffs, N.J., 1970.
• 19: Mills, H.D. Mathematical foundations for structured programming. FSC 72-6012 Federal System Division, IBM Corp., Gaithersburg, Md., 1972.
• 20: Peter M. Neely, On program control structure, Proceedings of the annual conference, p.119-125, August 27-29, 1973, Atlanta, Georgia, United States [doi>10.1145/800192.805692]
• 21: 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]
• 22: Sites, R.L. Proving tbat computer programs terminate cleanly. Rep. No. STAN-CS-74-418, Comput. Sci. Dep., Stanford U., 1974.
• 23: Wirth, N. The programming language PASCAL. Revised report, Eidgenoessische Technische Hochschule, Zurich, 1972.
• 24: Niklaus Wirth, Program development by stepwise refinement, Communications of the ACM, v.14 n.4, p.221-227, April 1971 [doi>10.1145/362575.362577]
• 25: W. A. Wulf , D. B. Russell , A. N. Habermann, BLISS: a language for systems programming, Communications of the ACM, v.14 n.12, p.780-790, Dec. 1971 [doi>10.1145/362919.362936]
• 26: Zahn, C.T., A conlrol statement for natural top-down structured programming. Sym!b. on Ping. Lang., Paris, 1974.

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
          Subjects: Structured programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Pascal

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Control theory

General Terms:
Languages

Keywords:
PASCAL, control structures, goto statements, language design, structured programming