Structured Programming with go to Statements DONALD E. KNUTH Stanford University, Stanford, California 9~S05 A consideration of several different examples sheds new light on the problem of ereat- ing reliable, well-structured programs that behave efficiently. This study focuses largely on two issues: (a) improved syntax for iterations and error exits, making it possible to write a larger class of programs clearly and efficiently without go to state- ments; (b) a methodology of program design, beginning with readable and correct, but possibly inefficient programs that are systematically transformed if necessary into efficient and correct, but possibly less readable code. The discussion brings out op- posing points of view about whether or not go to statements should be abolished; some merit is found on both sides of this question. Fina!ly, an attempt is made to define the true nature of structured programming, and to recommend fruitful direc- tions for further study. Keywords and phrases: structured programming, go to statements, language design, event indicators, recursion, Boolean variables, iteration, optimization of programs, program transformations, program manipulation systems searching, Quieksort, efficiency CR categories: 4.0, 4.10, 4.20, 5.20, 5.5, 6.1 (5.23, 5.24, 5.25, 5.27) You may go when you will go, And I will stay behind. --Edna St. Vincent Millay [66] Most likely you go your way and I'll go mine. --Song title by Bob Dylan [33] Do you suffer from painful elimination? --Advertisement, J. B. Williams Co. INTRODUCTION A revolution is taking place in the way we write programs and teach programming, be- cause we are beginning to understand the associated mental processes more deeply. It is impossible to read the recent book Struc- tured programming [17; 55] without having it This research was supported in part by the Na- tional Science Foundation under grant number GJ 36473X, and by IBM Corporation. change your life. The reasons for this revolu- tion and its future prospects have been aptly described by E. W. Dijkstra in his 1972 Tur- ing Award Lecture, "The Humble Program- mer" [27l. As we experience this revolution, each of us naturally is developing strong feelings one way or the other, as we agree or disagree with the revolutionary leaders. I must admit to being a nomhumble programmer, egotisti- Copyright (~) 1974, Association for Computing Machinery, Inc. General permission to republish, but not for profit, all or part of this material is granted, provided that ACM's copyright notice is given and that reference is made to this publication, to its date of issue, and to the fact that reprint- ing privileges were granted by permission of the Association for Computing Machinery. Computing Surveys, V?L 6, No. 4, Dee, ember 1974262 , Donald E. Knuth CONTENTS INTRODUCTION 1. ELIMINATION OF so to STATEMENTS Historical Background A Searching Example Efficiency Error Exits Subscript Checking Hash Coding Text Scanning A Confession Tree Searching Systematic Elimination Event Indicators Comparison of Features Simple Iterations 2. INTRODUCTION OF so to STATEMENTS Recursion Elimination Program Manipulation Systems Reeursion vs. Iteration Boolean Variable Elimination Coroutines Quicksort : A Digression Axiomatics of Jumps Reduction of Complication 3. CONCLUSIONS Structured Programming With go to Statements Efficiency The Future ACKNOWLEDGMENTS APPENDIX BIBLIOGRAPHY eal enough to believe that my own opinions of the current treads are not a waste of the reader's time. Therefore I want to express in this article several i of the things that struck me most forcefully as I have been thinking about structured programming during the last year; several of my blind spots were re- moved as I ivas learning these things, and I hope I can convey some of my excitement to the reader. Hardly any of the ideas I will discuss are my own; they are nearly all the work of others, but perhaps I may be pre- senting them in a new light. I write this article in the first person to emphasize the fact that what I'm saying is just one man's opinion; I don't expect to persuade everyone that my present views are correct. Before beginning a more technical discus- sion. I should confess that the title of this article was chosen primarily to generate attention. There are doubtless some readers who are convinced that abolition of go to statements is merely a fad. and they may see this title and think, "Aha! Knuth is rehabili- tating the go to statement, and we can go back to our old ways of programming again." Another class of readers will see the heretical title and think, "When are die- hards like Knuth going to get with it?" I hope that both classes of people will read on and discover that what I am really doing is striving for a reasonably well balanced view- point about the proper role of go to state- ments. I argue for the elimination of go to's in certain cases, and for their introduction in others. I believe that by presenting such a view I am not in fact disagreeing sharply with Dijkstra's ideas, since he recently wrote the following: "Please don't fall into the trap of believing that I am terribly dogmatical about [the go to statement]. I have the uncomfortable feeling that others are making a religion out of it, as if the conceptual problems of programming could be solved by a single trick, by a simple form of coding discipline!" [29]. In other words, it, seems that fanatical advocates of the New Pro- gramming are going overboard in their strict enforcement of morality and purity in programs. Sooner or later people are going to find that their beautifully-structured Computing Surveys, Vol. 6, No. 4, December 1974Structured Programming with go to Sta~ment~ ! programs are running at only half the speed --or worse--of the dirty old programs they used to write, and they will mistakenly blame the structure instead of recognizing what is probably the real culprit--the system over- head caused by typical compiler implementa- tion of Boolean variables and procedure calls. Then we'll have an unfortunate counter- revolution, something like the current rejec- tion of the "New Mathematics" in reaction to its over-zealous reforms. It may be helpful to consider a