Presented by Daniel Silva

Transcribed by Ethan Aubin

In 1968, Dijkstra writes "The quality of programmers is a decreasing function of the density of the goto statements in the programs they produce" and that the Goto statement should be abolished from all higher level languages (except for maybe machine language). He notes that 1) once a program has been made the "making" of the process is delegated to the machine and 2) our intellectual ability is geared towards static relations and our ability of visualize processes which change with time is limited.

We would like to strengthen the correspondence between static programs and their dynamic process. How can we characterize the progress of a process? (In other words, what must we store in order to repeat the process until a specific point?) In a language which is a sequence of assignment statements (possibly with conditional statements), it is sufficient to note the location in the program text. When procedures are included, a sequence of textual locations the same size as dynamic depth of the procedure call is needed. When the presence of repitition clauses, a dynamic index is needed.

Question: Could just stimulate repetitions using procedures?
The audience Dijkstra was addressing at the time used procedures calls sparingly. Procedures might be called, but not commonly call anything else. (Transcription note - Dijkstra says that loops are superfluous for this purpose in EWD215)

Question: Is the information maintained more complete than the current continuation?
Yes. The coordinates specify exactly the information necessary to reproduce the execution of the process.

The value of these indices are outside the control of the programmer. They are genererated either by the write up of his program or by the dynamic evolution of the process.

Why do we need these coordinantes? We can only interprete the values of variables with respect to the progress of the process. For example, say we want to count the number of people in a room (n initially) and a person enters the room. In the moment between the observation of the person entering and the increase of the counter, the value is the number of people in the room minus one.

Goto makes is difficult to find a meaningful set of coordinates to describe the progress of a process. A counter could be used, but is not very helpful.

Dahl, Hoare, Dijkstra published Structured Programming in 1972. Hoare says the structured programming is the systematic use of abstraction to control a mass of detail and a means of documentation which aids program design.

Elsewhere Hoare says:

Pointers are like jumps, leading wildly from one part of the data structure to another. Their introduction into high-level languages has been a step backwards from which we may never recover. - Hints on Programming Language Design 1973

The Elements of Programming Style emphasize abstraction, readability, and the ease of which we can proof equivalency and correctness. Hoare was concerned with teaching data structures and emphasised on testing and communication with other programmers. Repitition constructs, subroutines, and single exits from loops was promoted.

In 1975, Michael Jackson consulted COBOL programmers writing data processing programs. He suggested a style demonstrated by the program:

ENTRY "SUM" USING JOBINF
  GOTO Q1, Q2 DEPENDING ON QS
SUMSEQ

Q1
WRITE HEADLINE
MOVE 0 TO TOTALS
SUMBODYITER
  IF EOF_OUTPUT GOTO SUMBODYEND
  ADD JOBINF TO TOTALS
  MOVE 2 TO QS
  GOBACK

Q2
GOTO SUMBODYITER

SUMBODYEND
CALCULATE AVERAGES
WRITE REPORTLINES
GO BACK
SUMEND

This code is essentially in continuation-passing style. Jackson suggests turning an algebraic datatype into a data diagram (a tree diagram). He tells how to write the code for each node and says to write the program by linearizing that tree. When writing report generating programs, a programmer wants to design based on the output tree. Sometimes you may get a structural clash between the input tree and output tree, so build an intermediate tree which can be viewed by either the left or right. Space was is limited, so it was practical to invert a program so that it can be suspended before invoking the other half when. In other words, he advocated coroutines.

Knuth wrote Structured Programming with the Goto Statement which emphasizes readability and efficiency. We have a running example where given an array A with indexes 1..m, we search for x and if x is found at index i, increase B[i], otherwise add it to A.

A canonical example of where he really does not want to remove a goto is:

  for i := step 1 until m do
      if a[i] = x then goto found

notfound:
  i := m + 1
  m := i
  a[i] := x
  b[i] := 0

found:
  b[i] := b[i] + 1

Here is less readable program without gotos.

i := 1
while (i <= m) && (a[i]!=x) do
    i := i + 1
if i > m then      // An extra comparision
    m  := i
    a[i] := x
    b[i] := 0
b[i] := b[i] + 1

But thats too slow. This is 33 percent faster!

a[n+1] := x
i := 1
while (a[i] != x) do
    i := i + 1
if i > m then
    m := i
    b[i] := 1
else
    b[i] := b[i] + 1

This one is 12 percent faster than the previous one!

i:=1
while i <= m do
    if i > m then
        b[i] := b[i] + 1
    a[m+1] := x
    i := 1
    goto test
loop:
    i := i + 2
test:
    if a[i] == x then goto found
    if a[i+1] != x then
        goto loop
    else
        i := i + 1
found: 
    if i > m then
        b[i] := 1
    else
        b[i] := b[i] + 1

Knuth would say this is an innerloop and this transformation is justifiable.

Procedures calls in PL/I, Algol imposed significant overhead and Knuth did not trust compiliers to eliminate recursion. So given a procedure like:

  procedure treePrint(t)
      if t != 0 then treePrint(left[t])
                     print(value[t])
		     treePrint(right[t])

Is inefficient and the procedure calls should be removed. Rule number 1 to remove procedure calls is:

  • If the last action of a procedure call P before it returns is to call procedure Q simply goto the begining of procedure Q instead.
  • So the treePrint procedure is transformed into the tail-recursive

      procedure treePrint(t)
    loop:
          if t != 0 then treePrint(left[t])
                         print(value[t])
    		     t = right[t]
    		     goto loop
    
    Goto statements can always be elminated by introducing suitable procedures.