article

Free access

A genealogy of control structures

Authors:

Henry F. Ledgard,

Michael MarcottyAuthors Info & Claims

Communications of the ACM, Volume 18, Issue 11

Pages 629 - 639

https://doi.org/10.1145/361219.361222

Published: 01 November 1975 Publication History

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]

Ashcroft, E. and Manna, Z. The translation of"GOTO" programs to "WHILE" programs. Rep. No. STAN-CS-71-188, Comput. Sci. Dep., Stanford U., 1971.]]

Digital Library

[3]

Bochmann, G. V. Multiple exits from a loop without the GOTO. Comm. ACM 16, 7 (July, 1973) 443-444.]]

Digital Library

[4]

Bohm, C., and Jacopini, G. Flow diagrams, Turing machines and languages with only two formation rules. Comm. ACM, 9, 5 (May 1966), 366-371.]]

Digital Library

[5]

Bruno, J., and Steiglitz, K. The expression of algorithms by charts. J. ACM, 19, 3 (July 1972), 517-525.]]

Digital Library

[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]

Friedman, D., and Shapiro, S. A case for the while-until. SIGPLAN Notices (ACM newsletter) 9, 7 (July 1974), 7-14.]]

Digital Library

[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]

Kernigham, B.W., and Plauger, P.J. The Elements of Programming Style. McGraw-Hill, New York, 1974.]]

Digital Library

[13]

Knuth, D.E. Structured programming with GOTO statements. Computing Surveys, 6 (Dec. 1974) 261-301.]]

Digital Library

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

Digital Library

[16]

Leavenworth, B. M. Programming with(out) me GOTO. Proc. ACM Nat. Conf., 1972, pp. 782-786.]]

Digital Library

[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]

Neely, P.M. On program control structure. Proc. ACM Nat. Conf. 1973, pp. 119-125.]]

Digital Library

[21]

Peterson, W.W., Kasami, T., and Tokura, N. On the capabilities of while, repeat, and exit statements. Comm. ACM, 16, 8 (Aug. 1973), 503-512.]]

Digital Library

[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]

Wirth, N. Program development by stepwise refinement. Comm. ACM, 14, 4 (Apr. 1971), 221-227.]]

Digital Library

[25]

Wulf, W.A., Russell, D.B., and Habermann, A.N. BLISS: A language for systems programming. Comm. ACM, 14, 12 (Dec. 1971), 780--790.]]

Digital Library

[26]

Zahn, C.T., A conlrol statement for natural top-down structured programming. Sym!b. on Ping. Lang., Paris, 1974.]]

Cited By

Pasarella EVidal MZoltan CRoyo Sales J(2024)A computational framework based on the dynamic pipeline approachJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2024.100966139(100966)Online publication date: Jun-2024
https://doi.org/10.1016/j.jlamp.2024.100966
Blumenthal R(2022)"Teach your children well" value-neutrality and CS202XACM SIGCAS Computers and Society10.1145/3557805.355781550:2(18-18)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1145/3557805.3557815
Wu DOuyang JDai NWu MTan HDeng HFan YWang DJin Z(2022)DeepBrainProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/35503346:3(1-27)Online publication date: 7-Sep-2022
https://dl.acm.org/doi/10.1145/3550334
Show More Cited By

Index Terms

A genealogy of control structures
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
      1. Computational control theory
2. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Software implementation planning
        Software design techniques
    2. Software development techniques
  2. Software notations and tools
    1. General programming languages
      1. Language features
        Control structures
      2. Language types

Recommendations

Control Computations and the Design of Loop Control Structures

The control computation for a loop in a program is that part of the program concerned with the initialization, incrementation, and testing of the variables that determine the flow of control into, through, and out of the loop. The elements of loop ...
On extending Fortran control structures to facilitate structured programming

A number of preprocessors and other extensions of Fortran have been implemented recently, aimed at adding "disciplined" control structures to the language. In spite of wide variations in the details of these dialects, many common features can be ...
Tree-structured programs

With this note I hope to bridge the gap between the adherents of structured programming and the devotees of the unrestricted goto. I describe a style of programming which combines the advantages of structured programming with nearly all the power of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 18, Issue 11

Nov. 1975

54 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/361219

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Copyright © 1975 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1975

Published in CACM Volume 18, Issue 11

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

126
Total Citations
View Citations
983
Total Downloads

Downloads (Last 12 months)153
Downloads (Last 6 weeks)25

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pasarella EVidal MZoltan CRoyo Sales J(2024)A computational framework based on the dynamic pipeline approachJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2024.100966139(100966)Online publication date: Jun-2024
https://doi.org/10.1016/j.jlamp.2024.100966
Blumenthal R(2022)"Teach your children well" value-neutrality and CS202XACM SIGCAS Computers and Society10.1145/3557805.355781550:2(18-18)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1145/3557805.3557815
Wu DOuyang JDai NWu MTan HDeng HFan YWang DJin Z(2022)DeepBrainProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/35503346:3(1-27)Online publication date: 7-Sep-2022
https://dl.acm.org/doi/10.1145/3550334
Ullah MChatterjee SFagundes CLam CNahum-Shani IRehg JWetter DKumar S(2022)mRiskProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/35503086:3(1-29)Online publication date: 7-Sep-2022
https://dl.acm.org/doi/10.1145/3550308
Bartolini C(2017)Software Testing Techniques Revisited for OWL OntologiesModel-Driven Engineering and Software Development10.1007/978-3-319-66302-9_7(132-153)Online publication date: 10-Sep-2017
https://doi.org/10.1007/978-3-319-66302-9_7
Wang FSchewe SWu J(2015)Complexity of node coverage gamesTheoretical Computer Science10.1016/j.tcs.2015.02.002576:C(45-60)Online publication date: 20-Apr-2015
https://dl.acm.org/doi/10.1016/j.tcs.2015.02.002
List MCar D(2011)A polymorphic reference counting implementation in Fortran 2003ACM SIGPLAN Fortran Forum10.1145/2007333.200733430:2(4-27)Online publication date: 21-Mar-2011
https://dl.acm.org/doi/10.1145/2007333.2007334
Arsac J(2011)Emploi de méthodes constructives en programmation. Un dossier : la fonction d'AckermannRAIRO. Informatique théorique10.1051/ita/197711020091111:2(91-112)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1977110200911
Ammann POffutt JXu W(2008)Coverage criteria for state based specificationsFormal methods and testing10.5555/1806209.1806213(118-156)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1806209.1806213
Dearholt DValdés-Fallis G(2008)Toward a probabilistic automata model of some aspects of code-switchingLanguage in Society10.1017/S00474045000058077:3(411-420)Online publication date: 18-Dec-2008
https://doi.org/10.1017/S0047404500005807
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents