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:
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.