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.
Keywords
WarrantProgrammerControl (management)Computer scienceEquivalence (formal languages)Completeness (order theory)EpistemologySpace (punctuation)MathematicsProgramming languagePure mathematicsArtificial intelligencePhilosophyEconomics
Affiliated Institutions
Related Publications
Dataless programming
A programmer using existing programming languages typically codes a problem by (1) defining it, then (2) analyzing the processing requirements, and (3) on the basis of these req...
An investigation of the psychological processes underlying the debugging of computer programs
The primary objective of this thesis is to contribute to a theory of programmer expertise with respect to debugging computer programs. It is important to develop a theory of pro...
An Introduction to Computational Learning Theory
Emphasizing issues of computational efficiency, Michael Kearns and Umesh Vazirani introduce a number of central topics in computational learning theory for researchers and stude...
Computer animation with scripts and actors
A technique and philosophy for controlling computer animation is discussed. Using the Actor/Scriptor Animation System (ASAS) a sequence is described by the animator as a formal ...
Impact of valid selection procedures on work-force productivity.
Decision theoretic equations were used to estimate the impact of a valid test (the Programmer Aptitude Test; PAT) on productivity if it were used to select new computer programm...
Publication Info
- Year
- 1975
- Type
- article
- Volume
- 18
- Issue
- 11
- Pages
- 629-639
- Citations
- 102
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
102
OpenAlex
3
Influential
Cite This
Henry Ledgard,
Michael Marcotty
(1975).
A genealogy of control structures.
Communications of the ACM
, 18
(11)
, 629-639.
https://doi.org/10.1145/361219.361222
Identifiers
- DOI
- 10.1145/361219.361222