February 26, 2019
Most of us have heard the (unfortunately) famous quote from Donald E. Knuths
1974 paper “Structured Programming with
go to Statements”. Yes, it’s probably
the one you’re thinking about1. It’s a really good paper with plenty of
interesting ideas that holds up very well especially considering the paper is
over 40 years old and is in great part about optimization. I highly recommend
you to stop reading my blog, and to go and read the paper itself instead.
What follows is a list of other great quotes from the same paper. They are mostly copied straight from the paper, but I’ve occasionally omitted parts in order not to make them too long or filled with irrelevant context. My own edits are written [like this]. Enjoy!
[…] people are now beginning to renounce every feature of programming that
can be considered guilty by virtue of its association with difficulties. Not
go to statements are being questioned; we also hear complaints about
floating-point calculations, global variables, semaphores, pointer variables,
and even assignment statements.
The improvement in speed from Example 2 to Example 2a is only about 12%, and many people would pronounce that insignificant. The conventional wisdom shared by many of today’s software engineers calls for ignoring efficiency in the small; but I believe this is simply an overreaction to the abuses they see being practiced by penny-wise-and-pound-foolish programmers, who can’t debug or maintain their “optimized” programs. In established engineering disciplines a 12% improvement, easily obtained, is never considered marginal; and I believe the same viewpoint should prevail in software engineering. Of course I wouldn’t bother making such optimizations on a one-shot job, but when it’s a question of preparing quality programs, I don’t want to restrict myself to tools that deny me such efficiencies.
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.
He [Tony Hoare] points out quite correctly that the current practice of compiling subscript range checks into the machine code while a program is being tested, then suppressing the check during production runs, is like a sailor who wears his life preserver while training on land but leaves it behind when he sails!
[…] I also know of places where I have myself used a complicated structure
with excessively unrestrained
go to statements, especially the notorious
Algorithm 2.3.3A for multivariate polynomial addition. The original program had
at least three bugs; exercise 2.3.3-14 “Give a formal proof (or disproof) of
the validity of Algorithm A”, was therefore unexpectedly easy.
It is important to keep efficiency in its place, as mentioned above, but when efficiency counts we should also know how to achieve it.
A programmer should create a program P which is readily understood and
well-documented, and then he should optimize it into a program Q which is very
efficient. Program Q may contain
go to statements and other low-level
features, but the transformation from P to Q should be accomplished by
completely reliable and well-documented “mechanical” operations. At this
point many readers will say, “But he should only write P, and an optimizing
compiler will produce Q.” To this I say, “No, the optimizing compiler would
have to be so complicated that it will in fact be unreliable”
We found ourselves always running up against the same problem: the compiler needs to be in a dialog with the programmer; it needs to know properties of the data, and whether certain cases can arise, etc. And we couldn’t think of a good language in which to have such a dialog.
The programmer using such a system will write his beautifully-structure, 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 and a completely automatic one. […] The original program P should be retained along with the transformation specifications, so that it can be properly understood and maintained as time passes.
He [Edsger Dijkstra] went on to say that he looks forward to the day when machines are so fast that we won’t be under pressure to optimize our programs.
Though [a previous code snippet] is slightly cleaner looking that the method in my book, it is noticeable slower, and we have nothing to fear by using a slightly more complicated method once it has been proved correct. Beautiful algorithms are, unfortunately, not always the most useful.
One thing we haven’t spelled out clearly, however, is what makes some
bad and others acceptable. The reason is that we’ve really been directing our
attention to the wrong issue, to the objective question of
go to elimination
instead of the important subjective question of program structure.
We should ordinarily keep efficiency considerations in the background when we formulate our programs. We need to be subconsciously aware of the data processing tools available to us, but we should strive most of all for a program that is easy to understand and almost sure to work.