Common myths about goto's
The following article is reprinted from an article I wrote in 1987. It is slightly revised to reflect the passage of time. It is my impression that the level of understanding of the issues among the programming community at large has not improved in the past twenty years.
Some recent contributions about goto's display some misunderstandings about the issues involved. Here are some popular myths that seem to be widely believed: Myth 1: There are algorithms which require goto's. It has been known and proved for over 40 years that all programs can be rewritten in a computationally equivalent form using only the 'while loop' construct. Myth 2: Goto's can be replaced by "while loop" and "if-then-else" conditionals without cost. It has been known and proved for ~30 years that there are programs using goto's (but not function calls) that cannot be rewritten in a computationally equivalent form using only the 'while loop' construct unless either (a) the program size increases by a factor of N or (b) the execution time of the program increases by a factor of log(N) where N is a measure of the program size in the original form. It is further known and has been proved that the following heirarchy of constructs have the property that, for each level, there are programs using the constructs of that level which cannot be rewritten using only constructs of a lower level without paying a penalty either in time or space: 0: While-loop and if-then-else 1: Forever-loop with escape 2: Unconditional goto 3: Procedure invocation and return 4: Computed goto (switch statement in C) Note that the computed goto (transfer to computed address) is the strongest construct available on a Von Neumann machine and that the case (switch) statement of 'structured programming' is equivalent to the computed goto. Myth 3: There are programs which cannot be programmed efficiently unless goto's are used: From the table of strengths we see that goto-less programming has available constructs which are stronger than the unconditional goto. This does not preclude the possibility that there are local optimizations using goto's; only that the gain thereby does not increase indefinitely with program size. Myth 4: Programs cannot be proved correct if goto's are used. The semantics for establishing the correctness of programs using goto's are quite simple -- the essential step is to associate with each transfer label a condition that must hold if a transfer is made to that label. Myth 5: All programs can be effectively decomposed into heirarchical structure. This needs some explication since any program can be converted into a 'structured' program by using a while loop and a gigantic switch statement. Effective decomposition into heirarchical structure means that we can create a tree structure for the program with a reasonably small number of branches at each node. To put it more colorfully, there are problems which are intrinsically 'spaghetti code' problems.
This page was last updated February 1, 2008.