Structured Programming with go to Statements (1974) [pdf]
cs.sjsu.edu
cs.sjsu.edu
"Axiomatics of Jumps
[...]
"Just recently, however, Hoare has shown that there is, in fact, a rather simple way to give an axiomatic definition of go to statements; indeed, he wishes quite frankly that it hadn't been quite so simple. For each label L in a program, the programmer should state a logical assertion α(L) which is to be true whenever we reach L. Then the axioms
{α(L)} go to L {false}
{α(L)} S {P} ⊢ {α(L)} L:S {P}
"Informally, α(L) represents the desired state of affairs at label L; this definition says essentially that a program is correct if α(L) holds at L and before all "go to L" statements, and that control never "falls through" a go to statement to the following text. Stating the assertions α(L) is analogous to formulating loop invariants. Thus, it is not difficult to deal formally with tortuous program structure if it turns out to be necessary; all we need to know is the "meaning" of each label."
(p. 289-290)
Not only does "he wishes quite frankly that it hadn't been quite so simple" make me giggle like a schoolgirl for several minutes every time I see it, but it's also a really beautiful formalism.
Not that anyone would ever do it in practice....
Let's say you want to write the equivalent of this C code:
if (i < 10) {
j = 17;
k = 22;
} else {
j = 42;
k = 69;
}
IF (I .LT. 10) GOTO 100
J = 42
K = 69
GOTO 200
100 J = 17
K = 22
200 CONTINUE-------------------------------------------------------
I should confess that the title of this article was chosen primarily to generate attention. There are doubtless some readers who are convinced that abolition of go to statements is merely a fad, and they may see this title and think, "Aha! Knuth is rehabilitating the go to statement, and we can go back to our old ways of programming again." Another class of readers will see the heretical title and think, "When are diehards like Knuth going to get with it?" I hope that both classes of people will read on and discover that what I am really doing is striving for a reasonably well balanced viewpoint about the proper role of go to statements. I argue for the elimination of go to's in certain cases, and for their introduction in others.
...
[I]t seems that fanatical advocates of the New Programming are going overboard in their strict enforcement of morality and purity in programs. Sooner or later people are going to find that their beautifully-structured programs are running at only half the speed--or worse--of the dirty old programs they used to write, and they will mistakenly blame the structure instead of recognizing what is probably the real culprit--the system overhead caused by typical compiler implementation of Boolean variables and procedure calls.
...
At the present time I think we are on the verge of discovering at last what programming languages should really be like. I look forward to seeing many responsible experiments with language design during the next few years; and my dream is that by 1984 we will see a consensus developing for a really good programming language (or, more likely, a coherent family of languages). Furthermore, I'm guessing that people will become so disenchanted with the languages they are now using--even COBOL and FORTRAN-- that this new language, UTOPIA84, will have a chance to take over. At present we are far from that goal, yet there are indications that such a language is very slowly taking shape.
...
My own programming style has of course changed during the last decade, according to the trends of the times (e.g., I'm not quite so tricky anymore, and I use fewer go to's), but the major change in my style has been due to this inner loop phenomenon. I now look with an extremely jaundiced eye at every operation in a critical inner loop, seeking to modify my program and data structure (as in the change from Example 1 to Example 2) so that some of the operations can be eliminated. The reasons for this approach are that: a) it doesn't take long, since the inner loop is short; b) the payoff is real; and c) I can then afford to be less efficient in the other parts of my programs, which therefore are more readable and more easily written and debugged.
...
There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.
Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail. After working with such tools for seven years, I've become convinced that all compilers written from now on should be designed to provide all programmers with feedback indicating what parts of their programs are costing the most; indeed, this feedback should be supplied automatically unless it has been specifically turned off.
...
For some reason we all (especially me) had a mental block about optimization, namely that we always regarded it as a behind-the-scenes activity, to be done in the machine language, which the programmer isn't supposed to know. This veil was first lifted from my eyes in the Fall of 1973. when I ran across a remark by Hoare that, ideally, a language should be designed so that an optimizing compiler can describe its optimizations in the source language. Of course! Why hadn't I ever thought of it? [...]
The programmer using such a system will write his beautifully-structured, but possibly inefficient, program P; then he will interactively specify transformations that make it efficient. Such a system will be much more powerful and reliable than a completely automatic one. We can also imagine the system manipulating measurement statistics concerning how much of the total running time is spent in each statement, since the programmer will want to know which parts of his program deserve to be optimized, and how much effect an optimization will really have. The original program P should be retained along with the transformation specifications, so that it can be properly understood and maintained as time passes. As I say, this idea certainly isn't my own; it is so exciting I hope that everyone soon becomes aware of its possibilities.
...
The Future
It seems clear that languages somewhat different from those in existence today would enhance the preparation of structured programs. We will perhaps eventually be writing only small modules which are identified by name as they are used to build larger ones, so that devices like indentation, rather than delimiters, might become feasible for expressing local structure in the source language. (See the discussion following Landin's paper [59].) Although our examples don't indicate this, it turns out that a given level of abstraction often involves several related routines and data definitions; for example, when we decide to represent a table in a certain way, we simultaneously want to specify the routines for storing and fetching information from that table. The next generation of languages will probably take into account such related routines.
Program manipulation systems appear to be a promising future tool which will help programmers to improve their programs, and to enjoy doing it. Standard operating procedure nowadays is usually to hand code critical portions of a routine in assembly language. Let us hope such assemblers will die out, and we will see several levels of language instead: At the highest levels we will be able to write abstract programs, while at the lowest levels we will be able to control storage and register allocation, and to suppress subscript range checking, etc. With an integrated system it will be possible to do debugging and analysis of the transformed program using a higher level language for communication. All levels will, of course, exhibit program structure syntactically so that our eyes can grasp it.
...
A great deal of research must be done if we're going to have the desired language by 1984. Control structure is merely one simple issue, compared to questions of abstract data structure. It will be a major problem to keep the total number of language features within tight limits. And we must especially look at problems of input/output and data formatting, in order to provide a viable alternative to COBOL.
Strangley, these often feel more "powerful" to me than the structured languages I use. Especially when writing small programs.