by Edsger W. Dijkstra
We shall do a much better programming job, provided that we approach the task with a full appreciation of its tremendous difficulty — as Very Humble Programmers.
tags: Dijkstra, programming, software, computer science, Turing lecture, languages
The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague.
ACM Turing Award Lecture, 1972. EWD340.
As a result of a long sequence of coincidences I entered the programming profession officially on the first spring morning of 1952 and, as far as I have been able to trace, I was the first Dutchman to do so in my country. In retrospect the most amazing thing was the slowness with which, at least in my part of the world, the programming profession emerged — a slowness which is now hard to believe.
After having programmed for some three years, I had a discussion with A. van Wijngaarden, who was then my boss at the Mathematical Centre in Amsterdam. The point was that I was supposed to study theoretical physics at the University of Leiden simultaneously, and as I found the two activities harder and harder to combine, I had to make up my mind: either to stop programming and become a real, respectable theoretical physicist, or to carry my study of physics to a formal completion only, with a minimum of effort, and to become — yes, what? A programmer? But was that a respectable profession? Where was the sound body of knowledge that could support it as an intellectually respectable discipline? I remember quite vividly how I envied my hardware colleagues, who could at least point out that they knew everything about vacuum tubes, amplifiers and the rest, whereas I felt that, when faced with that question, I would stand empty-handed.
Full of misgivings I knocked on van Wijngaarden's office door. When I left his office a number of hours later, I was another person. For after having listened to my problems patiently, he agreed that up till that moment there was not much of a programming discipline, but then he went on to explain quietly that automatic computers were here to stay, that we were just at the beginning — and could not I be one of the persons called to make programming a respectable discipline in the years to come? This was a turning point in my life. One moral of the above story is, of course, that we must be very careful when we give advice to younger people; sometimes they follow it!
Another two years later, in 1957, I married — and Dutch marriage rites require you to state your profession. I stated that I was a programmer. But the municipal authorities of the town of Amsterdam did not accept it, on the grounds that there was no such profession. And, believe it or not, under the heading "profession" my marriage act shows the ridiculous entry "theoretical physicist"!
Let me try to capture the situation in those old days in a little more detail, in the hope of getting a better understanding of the situation today.
The first automatic electronic computers were all unique, single-copy machines and they were all to be found in an environment with the exciting flavour of an experimental laboratory. One thing is certain: we cannot deny the courage of the groups that decided to try and build such a fantastic piece of equipment. For fantastic pieces of equipment they were: in retrospect one can only wonder that those first machines worked at all, at least sometimes. The preoccupation with the physical aspects of automatic computing is still reflected in the names of the older scientific societies in the field, such as the Association for Computing Machinery or the British Computer Society — names in which explicit reference is made to the physical equipment.
What about the poor programmer? Well, to tell the honest truth: he was hardly noticed. His somewhat invisible work was without any glamour: you could show the machine to visitors, and that was several orders of magnitude more spectacular than some sheets of coding. But most important of all, the programmer himself had a very modest view of his own work: his work derived all its significance from the existence of that wonderful machine. Because it was a unique machine, he knew only too well that his programs had only local significance. And on the one hand, his machine was usually too slow and its memory too small — he was faced with a pinching shoe — while on the other hand its queer order code would cater for the most unexpected constructions. And in those days many a clever programmer derived an immense intellectual satisfaction from the cunning tricks by means of which he contrived to squeeze the impossible into the constraints of his equipment.
Two opinions about programming date from those days. The one opinion was that a really competent programmer should be puzzle-minded and very fond of clever tricks; the other opinion was that programming was nothing more than optimizing the efficiency of the computational process, in one direction or the other. These two misconceptions I shall return to presently.
The latter opinion was the result of the frequent circumstance that, indeed, the available equipment was a painfully pinching shoe, and in those days one often encountered the naive expectation that, once more powerful machines were available, programming would no longer be a problem. But in the next decades something completely different happened: more powerful machines became available, not just an order of magnitude more powerful — even several orders of magnitude more powerful. But instead of finding ourselves in the state of eternal bliss of all programming problems solved, we found ourselves up to our necks in the software crisis! How come?
There is a minor cause: in one or two respects modern machinery is basically more difficult to handle than the old machinery. Firstly, we have got the I/O interrupts, occurring at unpredictable and irreproducible moments; compared with the old sequential machine that pretended to be a fully deterministic automaton, this has been a dramatic change. Secondly, we have got machines equipped with multi-level stores, presenting problems of management strategy that still remain rather elusive. So much for the added complication due to structural changes of the actual machines.
But I called this a minor cause; the major cause is that the machines have become several orders of magnitude more powerful. To put it quite bluntly: as long as there were no machines, programming was no problem at all; when we had a few weak computers, programming became a mild problem; and now we have gigantic computers, programming has become an equally gigantic problem. In this sense the electronic industry has not solved a single problem — it has only created them, it has created the problem of using its products. As the power of available machines grew by a factor of more than a thousand, society's ambition to apply these machines grew in proportion, and it was the poor programmer who found his job in this exploded field of tension between ends and means. Is it a wonder that we found ourselves in a software crisis? No, certainly not — and as you may guess, it was even predicted well in advance; but the trouble with minor prophets, of course, is that it is only five years later that you really know that they had been right.
Then, in the mid-sixties, something terrible happened: the computers of the so-called third generation made their appearance. When these machines were announced and their functional specifications became known, quite a few among us must have become quite miserable; at least I was. It was only reasonable to expect that such machines would flood the computing community, and it was all the more important that their design should be as sound as possible. But the design embodied such serious flaws that I felt that with a single stroke the progress of computing science had been retarded by at least ten years: it was then that I had the blackest week in the whole of my professional life.
Perhaps the most saddening thing now is that, even after all those years of frustrating experience, still so many people honestly believe that some law of nature tells us that machines have to be that way. They silence their doubts by observing how many of these machines have been sold, and derive from that observation the false sense of security that, after all, the design cannot have been that bad. But upon closer inspection, that line of defense has the same convincing strength as the argument that cigarette smoking must be healthy because so many people do it.
The reason I have paid attention to the hardware scene is because I have the feeling that one of the most important aspects of any computing tool is its influence on the thinking habits of those that try to use it — and because I have reasons to believe that that influence is many times stronger than is commonly assumed.
Here the diversity has been so large that I must confine myself to a few stepping stones. I am painfully aware of the arbitrariness of my choice.
EDSAC. In the beginning there was the EDSAC in Cambridge, England, and I think it quite impressive that right from the start the notion of a subroutine library played a central role in the design of that machine and of the way it should be used. We should recognise the closed subroutine as one of the greatest software inventions; it has survived three generations of computers and it will survive a few more, because it caters for the implementation of one of our basic patterns of abstraction.
FORTRAN. The second major development was the birth of FORTRAN. At that time this was a project of great temerity and the people responsible for it deserve our great admiration — it would be absolutely unfair to blame them for shortcomings that only became apparent after a decade of extensive usage. In retrospect we must rate FORTRAN as a successful coding technique, but with very few effective aids to conception. The sooner we can forget that FORTRAN has ever existed, the better, for as a vehicle of thought it is no longer adequate: it wastes our brainpower, is too risky and therefore too expensive to use. FORTRAN's tragic fate has been its wide acceptance, mentally chaining thousands and thousands of programmers to our past mistakes.
LISP. The third project I would not like to leave unmentioned is LISP, a fascinating enterprise of a completely different nature. With a few very basic principles at its foundation, it has shown a remarkable stability.
ALGOL 60. The famous Report on the Algorithmic Language ALGOL 60 is the fruit of a genuine effort to carry abstraction a vital step further and to define a programming language in an implementation-independent way. One could argue that in this respect its authors have been so successful that they have created serious doubts as to whether it could be implemented at all! The report gloriously demonstrated the power of the formal method BNF — now fairly known as Backus-Naur-Form — and the power of carefully phrased English, at least when used by someone as brilliant as Peter Naur. I think that it is fair to say that only very few documents as short as this have had an equally profound influence on the computing community.
PL/1. Finally, although the subject is not a pleasant one, I must mention PL/1, a programming language for which the defining documentation is of a frightening size and complexity. Using PL/1 must be like flying a plane with 7000 buttons, switches and handles to manipulate in the cockpit. I absolutely fail to see how we can keep our growing programs firmly within our intellectual grip when by its sheer baroqueness the programming language — our basic tool, mind you! — already escapes our intellectual control.
I remember from a symposium on higher level programming language a lecture given in defence of PL/1 by a man who described himself as one of its devoted users. But within a one-hour lecture in praise of PL/1 he managed to ask for the addition of about fifty new "features", little supposing that the main source of his problems could very well be that it contained already far too many "features". The speaker displayed all the depressing symptoms of addiction, reduced as he was to the state of mental stagnation in which he could only ask for more, more, more. When FORTRAN has been called an infantile disorder, full PL/1 — with its growth characteristics of a dangerous tumour — could turn out to be a fatal disease.
So much for the past. But there is no point in making mistakes unless thereafter we are able to learn from them. I think that we have learned so much that within a few years programming can be an activity vastly different from what it has been up till now — so different that we had better prepare ourselves for the shock.
The vision is that, well before the seventies have run to completion, we shall be able to design and implement the kind of systems that are now straining our programming ability, at the expense of only a few percent in man-years of what they cost us now — and, besides, these systems will be virtually free of bugs. Those who want really reliable software will discover that they must find means of avoiding the majority of bugs to start with, and as a result the programming process will become cheaper. Both goals point to the same change.
There seem to be three major conditions that must be fulfilled. The world at large must recognize the need for the change; the economic need for it must be sufficiently strong; and the change must be technically feasible. The first two conditions seem, in 1972, already to be satisfied. Now for the third: is it technically feasible? I think it might, and I shall give you six arguments in support of that opinion.
A study of program structure has revealed that programs — even alternative programs for the same task and with the same mathematical content — can differ tremendously in their intellectual manageability. A number of rules have been discovered whose violation will either seriously impair or totally destroy the intellectual manageability of the program. I now suggest that we confine ourselves to the design and implementation of intellectually manageable programs. The class of intellectually manageable programs is still sufficiently rich to contain many very realistic programs for any problem capable of algorithmic solution. The first argument is simply that, as the programmer only needs to consider intellectually manageable programs, the alternatives he is choosing between are much, much easier to cope with.
As soon as we have decided to restrict ourselves to the subset of the intellectually manageable programs, we have achieved, once and for all, a drastic reduction of the solution space to be considered. This argument is distinct from argument one.
The constructive approach to program correctness. Today a usual technique is to make a program and then to test it. But:
One should not first make the program and then prove its correctness, because then the requirement of providing the proof would only increase the poor programmer's burden. On the contrary: the programmer should let correctness proof and program grow hand in hand. If one first asks what the structure of a convincing proof would be and, having found this, then constructs a program satisfying the proof's requirements — then these correctness concerns turn out to be a very effective heuristic guidance.
It has been suggested that there is some kind of law of nature telling us that the amount of intellectual effort needed grows with the square of program length. But, thank goodness, no one has been able to prove this law — and this is because it need not be true. The only mental tool by means of which a very finite piece of reasoning can cover a myriad cases is called "abstraction"; as a result, the effective exploitation of his powers of abstraction must be regarded as one of the most vital activities of a competent programmer. The purpose of abstracting is not to be vague, but to create a new semantic level in which one can be absolutely precise.
It has to do with the influence of the tool we are trying to use upon our own thinking habits. There is a cultural tradition — which in all probability has its roots in the Renaissance — to ignore this influence, to regard the human mind as the supreme and autonomous master of its artefacts. But if I start to analyse the thinking habits of myself and of my fellow human beings, I come, whether I like it or not, to a completely different conclusion: the tools we are trying to use and the language or notation we are using to express or record our thoughts are the major factors determining what we can think or express at all.
The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague. I see a great future for very systematic and very modest programming languages. When I say "modest", I mean that not only ALGOL 60's "for clause" but even FORTRAN's "DO loop" may find themselves thrown out as being too baroque. In one respect one hopes that tomorrow's programming languages will differ greatly from what we are used to now: to a much greater extent than hitherto they should invite us to reflect in the structure of what we write down all abstractions needed to cope conceptually with the complexity of what we are designing.
Until now I have not mentioned the word "hierarchy", but I think that it is fair to say that this is a key concept for all systems embodying a nicely factored solution. I could even go one step further and make an article of faith out of it: that the only problems we can really solve in a satisfactory manner are those that finally admit a nicely factored solution. The best way to learn to live with our limitations is to know them. By the time that we are sufficiently modest to try factored solutions only, because the other efforts escape our intellectual grip, we shall do our utmost best to avoid all those interfaces impairing our ability to factor the system in a helpful way.
There may also be political impediments. Even if we know how to educate tomorrow's professional programmer, it is not certain that the society we are living in will allow us to do so. The first effect of teaching a methodology — rather than disseminating knowledge — is that of enhancing the capacities of the already capable, thus magnifying the difference in intelligence. In a society in which the educational system is used as an instrument for the establishment of a homogenized culture, in which the cream is prevented from rising to the top, the education of competent programmers could be politically unpalatable.
Automatic computers have now been with us for a quarter of a century. They have had a great impact on our society in their capacity of tools, but in that capacity their influence will be but a ripple on the surface of our culture, compared with the much more profound influence they will have in their capacity of intellectual challenge without precedent in the cultural history of mankind.
In computer programming our basic building block has an associated time grain of less than a microsecond, but our program may take hours of computation time. I do not know of any other technology covering a ratio of 10¹⁰ or more: the computer, by virtue of its fantastic speed, seems to be the first to provide us with an environment where highly hierarchical artefacts are both possible and necessary. This challenge — the confrontation with the programming task — is so unique that this novel experience can teach us a lot about ourselves. It should deepen our understanding of the processes of design and creation; it should give us better control over the task of organizing our thoughts. If it did not do so, to my taste we should not deserve the computer at all!
It has already taught us a few lessons, and the one I have chosen to stress in this talk is the following. We shall do a much better programming job, provided that we approach the task with a full appreciation of its tremendous difficulty, provided that we stick to modest and elegant programming languages, provided that we respect the intrinsic limitations of the human mind and approach the task as Very Humble Programmers.
✦ memory · ☽ night · ∞ loops · ❧ margins · ◆ proof
a personal library in perpetual arrangement · MMXXVI