Common myths about goto’s

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.