# Why do Java and Python not have goto statements?

(Thanks to Sam Balco, Peter Jipsen, Nikolaus Kurz, Drew Moshier for discussions and contributions.)

(This write-up tries to give a rough introduction to the historical debate surrounding the paradigm of structured programming and some of its ramifications in current popular programming languages ... it is also instructive to read some of the threads on stackexchange on this topic to see that the debate, which started 50 years ago, is still going on. Even if it is not anymore at the cutting edge of programming languages, it still influences how we write code today.)

(Remark on *Critical Thinking:* If I was forced to summarise this lecture in one short sentence, I might still say "Always avoid `goto`'s". Dogmas can be useful. But they are also wrong (all rules have exceptions).[^dogmas] So I recommend to follow up the embedded (and further) references and I would love to hear from you what you are thinking about the issue. Personally, for example, while I think that Dijkstra was essentially right, Knuth's rich and nuanced article is very interesting and shows that one learns more from critical thinking than from repeating dogma.)

[^dogmas]: This is the dogma paradox: Is the dogma "All dogmas are wrong" true or false? On the other hand, there is nothing paradoxical about the rule "All rules have exceptions".

Alternative title:

# On the Origins of Software Engineering

---

This discussion is motivated by the question of how to implement the specification of a state machine [^specifications]. For example, [here](https://github.com/alexhkurz/compiler-construction-2020/blob/master/Sources/abc.pdf) is a statemachine that accepts all words that finish with "abc".

[^specifications]: Such specifications come in many variations and are known under various names such as state machines, automata, transitions system. They play an important role in many areas such as hardware design, control theory, software engineering, compilers, logic, and many more.

In a language with labels and gotos, we can give a nice and direct translation of the picture. For example, in C++, the code translating [the state labelled `q1`](https://github.com/alexhkurz/compiler-construction-2020/blob/master/Sources/abc.pdf) can be written as

q1:
READ_CHAR;
switch (input) {
case 'a': goto q1;
case 'b': goto q2;
default : goto q0;
}

where `READ_CHAR` is a macro that assigns the current character to the variable `input`.

Languages such as Java and Python do not have `goto`. We will discuss later why.

Therefore, we need to use a more mathematical approach. One solution is to think of the specification as a function

$$transition : State \times Char \to State$$

For example, the above C++ code corresponds to the mathematical definition

\begin{align}
transition : State \times Char & \to State\\
transition(q_1,a) &= q_1\\
transition(q_1,b) &= q_2\\
transition(q_1,x) &= q_0 & \rm{if\ x\notin\{a,b\}}\\
\end{align}

Such a function is easy to implement in Java or Python.

**Question:** In the automata theory book, the above function $transition$ has what name?

## "Go To Statement Considered Harmful"

For the remainder of this lecture I want to present some of the history that led to the prohibition of `goto` in many modern programmming language and discuss some of the advantages and disadvantages of using `goto`.

There is some "prehistory", about which you can find out more if you read the articles I refer to. But the starting point of the debate is usually taken to be

[Edgar Dijkstra: "Go To Statement Considered Harmful" (1968)](https://homepages.cwi.nl/~storm/teaching/reader/Dijkstra68.pdf)

The title of the paper, chosen by the editor Niklaus Wirth, himself one of the important figures in the history of compilers, made history itself, see the Wikipedia entry on [Considered harmful](https://en.wikipedia.org/wiki/Considered_harmful) for further references. [^consideredharmful]

[^consideredharmful]: Dijkstra's [reply (1987) ](http://www.cs.utexas.edu/users/EWD/ewd10xx/EWD1009.PDF) to some critics reveals that at the time there apparently was a debate about whether arrays should be indexed starting from `0` or `1` ... we clearly moved on from that. His remark on the "conditional and" is also worth noting.

The most famous quote from the article is probably the opening sentence

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 go to statements in the programs they produce.

Today, of course, we need to ask why, at the time, in 1968, programming without `goto`'s was thought to be impossible.

- One reason for the use of `goto`'s was that machine and assembley code rely on labels and jumps [^jumps] to implement everything from conditionals over loops to functions/procedures/methods. And while, by 1968, modern high level programming languages such as ALGOL had been developed in academia for a decade or so, the associated method of [structured programming](https://en.wikipedia.org/wiki/Structured_programming) had not yet made it into mainstream programming.[^structuredprogramming]

[^jumps]: Jumps and gotos are essentially the same thing, the term "jump" indicates that one is talking about assembly language and "goto" indicates that one is talking about a programming language.

- Another reason, which may be less important nowadays, is that `goto`'s allow the programmer more control to write more efficient code. For more on this see the article by Knuth referenced below.

- Furthermore, at the time more than today, programs were visualised and specified by [flowcharts](https://en.wikipedia.org/wiki/Flowchart) and the obvious way to implement a flowchart is to use labels and `goto`'s, much in the same way as we used them in the sketched C++ implementation of the automaton above. [^flowchart]

[^flowchart]: In fact, [Parnas: On the Criteria To Be Used in Decomposing Systems into Modules (1972)](http://sunnyday.mit.edu/16.355/parnas-criteria.html) which is considered to be one of the founding papers of the discipline of Software Engineering, contains the quote "The flowchart was a useful abstraction for systems with on the order of 5,000-10,000 instructions, but as we move beyond that it does not appear to be sufficient; something additional is needed."

So what happened? Can flowcharts be implemented without `goto`'s? (The theoretical question.) And would that actually improve readability? (The practical question, which is important: Remember that in programming [the reader is always right](https://vimeo.com/14313378#t=10m03s) [^yaronminsky])

The story of the theoretical question starts with [Bohm and Jacopini: "Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules" (1966)](http://www.cs.unibo.it/~martini/PP/bohm-jac.pdf) who showed that every flowchart can be implemented using if-then-else, sequential composition and while-loops. The paper gives a general method to translate every flowchart into a structured program without `goto`'s. [^kozen] As it often happens, the most elegant theoretical results are not directly practical. In this case, the goto-free program obtained from the general method is not necessarily more readable than the one with `goto`'s. On the other hand the Bohm-Jacopini result shows that flowcharts can be implemented by sequential composition, conditionals and loops only.
Improvements on this result also added multi-level breaks out of nested loops (a related addition to the arsenal of structured programming was exceptions).

[^kozen]: A modern accout of the Bohm-Jacopini theorem is given in [Dexter Kozen and Wei-Lung Dustin Tseng: "The Bohm–Jacopini Theorem Is False, Propositionally" (2008)](https://www.cs.cornell.edu/~kozen/Papers/BohmJacopini.pdf) (One shouldn't read the title as saying that the original Bohm–Jacopini Theorem is false, rather the title refers to a technical subtlety which, however, is a crucial point of the paper.)

**Activity:** To illustrate that eliminating goto's does not necessarily improve readability, think about how to replace labels with function definitions and goto's with function calls. [^footnote]

[^footnote]: But, of course, that eliminating `goto`'s may not improve the code, is not an argument for using `goto`'s. The real aim of Structured Programming (and then Software Engineering) was to change the way we design programs in the first place. Structured programming is about much more than avoiding `goto`'s. The aim of structured programming is to align the structure of the program with the logical structure of the specification, which should make the use of `goto`'s unnecessary in the first place (there are no `goto`'s in logic). A possible exception to this arises when the problem is best described by a [state machine](https://github.com/alexhkurz/compiler-construction/blob/master/abc.pdf) because then, indeed, the gotos allow us to directly (and efficiently) implement the specification. On the other hand, our example of a state machine is a very simple one known as a (deterministic) finite automaton. There are many variations of state machines in which states have more structure. In such situations it may be give some real benefit to implement each state by a function.

Nevertheless the theoretical result was hugely important as the knowledge that such a translation is possible in principle gave proponents of structured programming the confidence that they are on the right track. [^moreover] And, as history shows, they largely won the battle.

[^moreover]: Moreover, later improvements of the Bohm-Jacopini result showed that adding multi-level breakd to sequential composition, conditionals and loops produces a much more readable code without gotos (and, indeed, in modern langauges it is common to have multi-level breaks and exceptions).

In spite of all this, we should not forget that readability, and sometimes efficiency, are more important than ideological principles. So while structured programming was certainly an important revolution, this does not imply that all uses of goto should be condemned on principle.

**Activity:** What "hidden" uses of goto's routinely show up in your own programming practice? Which well-known programming constructs are special kind of `goto`'s? So is it legitimate to say that goto's have been eliminated? [^footnote2]

[^footnote2]: `break`, `return`, `try/catch` are special kind of `goto`'s. They are usually considered acceptable programming style, but they do break the single-entry-single-exit paradigm. For example, it is good to ask you whether you can write, without sacrificing readability, your functions using only a single `return` and whether you can avoid using `break` to exit your loops. Often the use of these devices can be avoided by redesigning the code, actually resulting in more readable code.

## "Structured Programming with go to Statements"

**Activity:** Let us put the discussion to test with an example. How readable is the code below? Does the code become more readable after eliminating the goto?

for i = 1 to m
if A[i] = x then goto found
i = m+1
m = i
A[i] = x
B[i] = 0
found: B[i] = B[i] + 1

The example above, which emphasises readability, is from [Knuth, "Structured Programming with go to Statements" (1974)](https://pic.plover.com/knuth-GOTO.pdf). I highly recommend to read this very rich, and sometimes funny, article.

Apart from readability, we also hinted at efficiency.

The paper continues with a discussion on how to optimize loops that are executed millions of times. In such a situation even small improvements can be significant and Knuth shows that the flexibility offered by `goto`'s can be valuable. Of course, today compilers are highly optimizing and it is a question whether we should not just trust our compilers instead of trying to optimize ourselves.

## Summary

While the elimination of `goto`'s might be criticised as being ideological and taking from the programmer a tool that can be useful, it certainly forced programming language designers to invent new powerful language features that make the use of `goto`'s unnecessary. It also forced software developers to come up with new engineering paradigms.

The first examples where conditionals, loops and functions which are all implemented using jumps. [^functions] High level constructs for exception handling are another example.

A similar story, not about `goto`'s but about pointers, could be told about object oriented programming. The best known example is Java, which sacrifices pointers and provides instead objects, classes and garbage collection.

And the quest for new high-level constructs in programming languages continues. Examples include concurrency (with applications to distributed computing), probabilistic programming (with applications to machine learning), quantum computing (many exciting applications anticipated), and homotopy type theory (with applications to theorem proving).

## Further Reading:

- [Real Programmers Don't Use PASCAL](https://www.ee.ryerson.ca/~elf/hack/realmen.html). A well-known, humorous piece against structured programming and in favour of programming in Fortran.

- [The Story of Mel](http://www.catb.org/jargon/html/story-of-mel.html). A well-known, humorous piece against programming in Fortran and in favour of programming in machine code.

- The [software crisis](https://en.wikipedia.org/wiki/Software_crisis) of the 1960ies not only sparked the development of Structured Programming but also led to the creation of the area of [software engineering](https://en.wikipedia.org/wiki/Software_engineering), which received its name from the eponymous conference organised by FL Bauer from the Technical University of Munich in Garmisch-Partenkirchen in 1968, the [proceedings](http://homepages.cs.ncl.ac.uk/brian.randell/NATO/index.html) of which are available online together with more [historical background](http://homepages.cs.ncl.ac.uk/brian.randell/NATO/NATOReports/index.html).

- [GOTO statement considered awesome](https://www.youtube.com/watch?v=D32rpo5TeVg) (Thanks to Michelle Kutsanov for the reference.) I collected some quotes from the video:
- GOTOs are not compositional.
- GOTO is not the enemy. Low-level thinking is.
- Composability always wins.

... to be expanded as time permits ...

[^functions]: And we have seen that functions can be used to implement gotos, even if that incurs a loss of efficiency.

[^structuredprogramming]: One of the important ideas of structured programming is that every block has a single entry and a single exit. The opposite extreme of "single-entry-single-exit" is aptly called [spaghetti code](https://en.wikipedia.org/wiki/Spaghetti_code). Nevertheless, taken to the extreme "single-entry-single-exit" can decrease readability. What examples in your own programming practice violate the single-exit paradigm? Which `goto`-like statements in Java and Python are used expressely to porgram mutiple exits? (The idea of single-entry-single-exit is explained in more detail in Section 7 of [Dijkstra, "Notes on structured programming", 1969](http://www.informatik.uni-bremen.de/agbkb/lehre/programmiersprachen/artikel/EWD-notes-structured.pdf))

[^yaronminsky]: There is lots of other good stuff in the video, eg the discussion about [exhaustion checks](https://vimeo.com/14313378#t=31m51s).