To boldly GOTO where no one has gone before…

This content originally appeared on Level Up Coding – Medium and was authored by Alexander Pikovski

Computer programs consist of a list of statements that are executed in a sequential fashion, and a GOTO statement indicates that the execution should jump — i.e., continue at a specified place instead of the next statement. [Functional and logical programming is outside of our discussion.]

Courses on programming usually teach that jumps should be avoided, GOTOs are considered “bad style”. This is taken to the extreme by some programming languages, by omitting the GOTO (or similar) statement in a programming language. Python is the most prominent example of such a language.

The lack of a GOTO statement in Python produces monstrosities like this: (we need to jump out of a nested loop):

class BreakIt(Exception): pass

try:
    for x in range(10):
        for y in range(10):
            print (x*y)
            if x*y > 50:
                raise BreakIt
except BreakIt:
    pass

Languages which do have a GOTO statement include: C++, C#, Fortran, Go, PHP, Visual Basic, various scripting languages as well as machine-level languages. Languages without GOTO include: Java, JavaScript, Matlab, Python, Rust.

Now, programming languages are always evolving and new language features keep being added on a regular basis to Java, Python, etc. Why the stubborn resistance to add a GOTO statement ? And why is a GOTO considered “bad style” ?

To find out what’s going on, we need to understand why people got so annoyed of “spaghetti code” 60 years ago…

Spaghetti code

Photo by Dennis Brekke on Unsplash

Spaghetti code is a name given to computer code which is unnecessary complex and difficult to read, understand, and modify. It is difficult to define this term precisely, but you recognize it when you see it. A computer program without clear structure, with mysterious (often global) data variables. Usually lots of variables with unclear meaning and many jumps.

Here is a modern code snippet (written in Visual Basic), taken from a Reddit post, as an example of spaghetti code:

'PARSE THE SSS STRING INTO PARTS SSS1 SSS2 AND SSS3
line_3350:
    i = InStr(SSS, "  ")
    If i <> 0 Then
        SSS = Left(SSS, i) + Mid(SSS, i + 2)
        GoTo line_3350
    End If    
    i = InStr(SSS, sep)
    SSS1 = SSS + ""
    s1len = Len(SSS1)
    inin = SSS + ""         
    If i = 0 Then
        GoTo line_3400
    End If
...

Perhaps we can say, in short, that spaghetti code produces a headache when you try to figure out what it is supposed to do.

Structured Programming

Photo by Alain Pham on Unsplash

Back in the late 1950s and 1960s, it was realized that convoluted “spaghetti code” is a real practical problem. And computer scientists came up with a solution.

Structured Programming was supposed to end spaghetti code, once for all.

It was stipulated that a “structured program” should consist, essentially, of the following elements:

Single statements: These are either “commands” to execute (variable assignment, calculation, input, output, function call…) or statements which influence the control flow of the program. The only control-flow statements allowed are: conditionals and loops. Conditionals are the well-known IF…THEN…ELSE… . The loops are of two types: FOR (iterates over a fixed range of values) and WHILE/UNTIL (repeats while/until a condition is met).
Blocks of statements: several statements may be combined into a block and are then considered one statement. In modern languages, blocks are delimited e.g. by { … } (C++, Java, JavaScript) or space indentation (Python).
A more recent addition, present in modern languages, is to allow local variables in blocks — this is called “scope”.
Functions (subroutines). They have definite input and output parameters and local variables. They may also be called recursively.

These rules were to be enforced, on the one hand, through the design of programming languages, and on the other hand, by self-discipline of the programmer.

Removing all GOTOs

Photo by Waldemar on Unsplash

The reader will have noticed that Structured Programming, in its strict form presented above, does not contain GOTOs. Is it possible to dispense with jumps?

First, let’s look at another example where GOTOs commonly occur, namely error handling. The following piece of C++ code

result1 = func1();
if (!result1)
  goto err;
result2 = func2();
if (!result2)
  goto err;
...
err:
print_error();

can be re-written without jumps by introducing a flag variable and additional conditionals (the code gets less readable, however):

is_error = false;
result1 = func1();
if (!result1)
  is_error = true;
if (!is_error) {
  result2 = func2();
  if (!result2)
    is_error = true;
}
...
if (isError)
  print_error();

Trying out these and similar “code transformations”, it appears that we can get rid of jumps by introducing additional flags, additional conditionals, and repeating some statements.

Thus, it is natural to ask the general question: Can any computer program be written just with control-flow statements IF/ELSE and loops?

It turns out that the answer is yes.

Here is a recipe how to remove all jumps. Consider a program which contains labels 1 … N and conditional GOTOs (jumps) between them [Conditional jump means a GOTO coupled with an IF condition: IF … THEN GOTO …]. The label 1 should be at the very beginning of the program and label N at the end of the program. The condition to be met when jumping from label i to label j will be written cond(i,j), if there is no condition set cond(i,j)=true. Then we can write a new equivalent program, but without jumps, in the following form:

stage = 1
while (stage < N) {
    /* repeat the following "if" block for all values of i, j */
    if (stage == i && cond(i,j)) {
        /* put here statements which lead form label i to label j */
        stage = j;
    }
    /* ... */
}

This is a general result (given by Böhm and Jacopini, 1966; Cooper 1967).

Of course, nobody said that this resulting code is elegant or practical!

Now, let’s return to the history of events.

Dijkstra vs. Knuth

Photo by Felix Mittermeier on Unsplash

During the 1960s, computer scientists became tired of “spaghetti code”. And they decided to do something about it.

One of them was Edsger W. Dijkstra. During his education as a physicist in the early 1950s in the Netherlands, he became fascinated by computers and made this the focus of his career; he was officially the first person to be employed as “programmer” in the Netherlands in 1952. He is most famous for inventing the algorithm to find the shortest path in a graph.

Dijkstra wrote in 1968 a two-page letter entitled “Go-to statement considered harmful” which starts with:

For a number of years I have been familiar with the observation that the quality of programmers is a decreasing function of the density of GOTO statements in the programs they produce.

and ends with

The GOTO statement as it stands is just too primitive; it is too much an invitation to make a mess of one’s program.

The short paper had a large impact. Other computer scientists joined the movement. The possibility of code transformations to remove all GOTOs — as we discussed above — were started to be called “Structured Programming Theorem” and were used as as an argument to actually get rid of GOTOs in practice. Dijkstra received the prestigious Turing award, sometimes called “Nobel prize of computing”, in 1972.

Not everyone was convinced, however.

Donald E. Knuth, an eminent computer scientist and also recipient of the Turing Award, did not agree. A mathematician by training, he turned his attention to computing and the analysis of algorithms. He is most famous as the author of a fundamental book on algorithms and as the creator of the TeX typesetting system.

Knuth argued in a long paper in 1974 that the GOTO statement is useful, providing many examples, and that it should be included in structured programming.

But the train has left.

The Structured Programming movement took off in the late 1960s and 1970s, textbooks where written, and a new generation of computer scientists and software engineers was trained to follow this principle.

Most people in the field embraced a disdain for GOTOs, and passed this to the younger generation of computer scientists. Some of these got carried away and decided to abolish GOTOs altogether, as soon as they had the chance to design a new programming language.

Conclusion

Photo by John Paul Summers on Unsplash

Structured programming, which tried to abolish GOTOs, was, in hindsight, just the first of the many “waves” of programming styles to come. No need to be carried away in excitement!

It is possible, as discussed above, to eliminate all GOTOs (jumps) in a computer program. However, this does not mean that it is a good idea to do so in practice.

In fact, GOTOs can be helpful on a number of occasions, and one should not be afraid to use them.

So — don’t be afraid to jump ! Engage…

Spaghetti code

Structured Programming

Removing all GOTOs

Dijkstra vs. Knuth

Conclusion

Further reading