How do we tell truths that might hurt? Sometimes we discover unpleasant truths. Whenever we do so, we are in difficulties: suppressing them is scientifically dishonest, so we must tell them, but telling them, however, will fire back on us. If the truths are sufficiently impalatable, our audience is psychically incapable of accepting them and we will be written off as totally unrealistic, hopelessly idealistic, dangerously revolutionary, foolishly gullible or what have you. (Besides that, telling such truths is a sure way of making oneself unpopular in many circles, and, as such, it is an act that, in general, is not without personal risks. Vide Galileo Galilei.....) Computing Science seems to suffer severely from this conflict. On the whole, it remains silent and tries to escape this conflict by shifting its attention. (For instance: with respect to COBOL you can really do only one of two things: fight the disease or pretend that it does not exist. Most Computer Science Departments have opted for the latter easy way out.) But, Brethern, I ask you: is this honest? Is not our prolonged silence fretting away Computing Science's intellectual integrity? Are we decent by remaining silent? If not, how do we speak up? To give you some idea of the scope of the problem I have listed a number of such truths. (Nearly all computing scientists I know well will agree without hesitation to nearly all of them. Yet we allow the world to behave as if we did not know them....) * * * Programming is one of the most difficult branches of applied mathematics; the poorer mathematicians had better remain pure mathematicians. The easiest machine applications are the technical/scientific computations. The tools we use have a profound (and devious!) influence on our thinking habits, and, therefore, on our thinking abilities. FORTRAN --"the infantile disorder"--, by now nearly 20 years old, is hopelessly inadequate for whatever computer application you have in mind today: it is now too _clumsy_, too _risky_, and too _expensive_ to use. PL/I --"the fatal disease"-- belongs more to the problem set than to the solution set. It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration. The use of COBOL cripples the mind; its teaching should, therefore, be regarded as a criminal offence. APL is a mistake, carried through to perfection. It is the language of the future for the programming techniques of the past: it creates a new generation of coding bums. The problems of business administration in general and data base management in particular are much too difficult for people that think in IBMerese, compounded with sloppy English. About the use of language: it is impossible to sharpen a pencil with a blunt axe. It is equally vain to try to do it with ten blunt axes instead. Besides a mathematical inclination, an exceptionally good mastery of one's native tongue is the most vital asset of a competent programmer. Many companies that have made themselves dependent on IBM-equipment (and in doing so have sold their soul to the devil) will collapse under the sheer weight of the unmastered complexity of their data processing systems. (Simplicity is prerequisite for reliability.) We can found no scientific discipline, nor a hearty profession on the technical mistakes of the Department of Defense and, mainly, one computer manufacturer. The use of anthropomorphic terminology when dealing with computing systems is a symptom of professional immaturity. By claiming that they can contribute to software engineering, the soft scientists make themselves even more ridiculous. (Not less dangerous, alas!) In spite of its name, software engineering requires (cruelly) hard science for its support. In the good old days physicists repeated each other's experiments, just to be sure. Today they stick to FORTRAN, so that they can share each other's programs, bugs included. Projects promoting programming in "natural language" are intrinsically doomed to fail. * * * Isn't this list enough to make us uncomfortable? What are we going to do? Return to the order of the day, presumably....... PS. If the conjecture "You would rather that I had not disturbed you by sending you this." is correct, you may add it to the list of uncomfortable truths. * * * That was EWD498, dated 18 June 1975. That document has been in wide circulation since 1982, when it was included in a collection of Dijkstra's writings published by Springer. That selection of documents is really very good, and accurately reflects the spread of Dijkstra's work over the preceding thirty years. But about two years ago an archive of those and many more documents has been made available on the world wide web; I included the URL in the announcement. What's exciting about this is that now we can all see how these and other classic papers came about: the circumstances in which they were written, and in a number of cases, how they developed through a series of revisions. Some people have been on Dijkstra's mailing list for many years - but not I. So it has been an eye-opener. Befor continuing I'd like to mention what this talk is and why I'm giving it. Well, what this talk isn't. I could presume to claim that because I have never met Dijkstra that my picture of him is more objective than that of some of you, who have. But that would be quite misleading. I've looked at over three hundred documents from the archive. I'm biased - I am in _awe_ of this man. So although I do claim some objectivity - in that I'm not making all this up - what I choose to say in this talk _is_ based on a personal response and my own selections from the archive. It _is_ only a small selection, and I should say now that you won't leave here with anything like the full picture. For that, you'll have to go to the archive yourself and start reading, which is, of course, what I hope you leave here feeling encouraged to do. And I won't hesistate to offer my _own_ views. Why this talk? It seems to me a shame that in general we don't celebrate achievement nearly often enough - it tends to happen at prize ceremonies, in Festschriften, and obituaries. If there is anyone alive today whose work needs to be rediscovered and appropriated by every generation of programmers, computing scientists, and software engineers, it must surely be Edsger Dijkstra. His influence is so broad and it runs so deep as to be inescapable, and if we understand just _how_ broad and deep it is then celebration is the only reasonable response. Now Dijkstra himself has said that he doesn't mind if you learn something of his work without his name attached. But I think it is important to give credit where credit is due. We tend to think we are now "grown up" - isn't Dijkstra's work of historical interest only? To that, I would answer: of course, it's of _enormous_ historical interest, but I hope to offer some evidence that shows how we need to keep listening to what he says. I am reminded of the current television advertisement for wearing seatbelts. We see a driver having his face slapped repeatedly -- about once a second -- and we hear a voice saying "wear a seatbelt, wear a seatbelt, wear a seatbelt". It would appear that there are a lot of extremely foolish drivers out there who just don't get it. If your reaction to Dijkstra is that he's a bit like a broken record, I would suggest instead that he has met a very large number of fools over the years. This talk is also a sort of "work in progress report". Two years ago I started reading some of these documents to my own students. I teach the fundamentals of concurrency, and Dijkstra had a lot to say in this area, so you'd think that was natural. But I haven't restricted myself to that one area. I've also chosen to read some of his shorter essays - you might call them mini-sermons - that he used at the beginning of his own lectures, in which he talks about the state of the discipline and of industry, often with predictions of the future. I have to tell you that without exception his analyses have stood the test of the time and his predictions have come true time and time again. Who is Edsger Dijkstra? The 1972 Turing Award citation reads as follows: Edsger Dijkstra was a principal contributor in the late 1950's to the development of ALGOL, a high level programming language which has become a model of clarity and mathematical rigor. He is one of the principal exponents of the science and art of programming languages in general, and has greatly contributed to our understanding of their structure, representation, and implementation. His fifteen years of publications extend from theoretical articles on graph theory to basic manuals, expository texts, and philosophical contemplations in the field of programming languages. That was 1972. Until that time, he had been on the staff of the Mathematical Center in Amsterdam, and a professor of mathematics at Eindhoven University of Technology. From 1973 until 1984 he was paid by Burroughs to do his own thing, and in 1984 he moved to Austin, Texas to take up the endowed chair he held until 1999. In case you're wondering, he was born in 1930, so you can see that some institutions have some time ago dispensed with the idea of forced retirement at age 65. Let us now dispense with some of the more ridiculous objections. I am grateful to a colleague (who shall remain nameless), who only last week provided an excellent example of the sort of nonsense that surrounds Dijkstra. This colleague remarked that Dijkstra was pompous for writing his title as `professor doctor'. Well, I had to point out that that _is_ his title - it's absolutely typical for a professor from that part of the world. In fact, he's being modest, since he's entitled to call himself `professor doctor doctor'. The other classic one that comes to mind is his most famous operating system - _THE_ operating system - surely it is the height of presumption to use the definite article in this way. Well, it _isn't_ the definite article, it's the acronym of the Eindhoven University of Technology (in Dutch, of course). And isn't it `quaint' that he does his work using fountain pen and paper instead of a computer? Luca Cardelli even scanned a sample of his handwriting and turned it into a font that you can download and use on your computer. Well, the truth is not really all that glamorous. More than half of the documents in the archive were typed on various typewriters, some of which had mathematical symbols - less than, greater than, and so on. He wore out at least one typewriter! And when at last these typewriters were no longer available, why would he use a computer system that had fewer features than his typewriter? So he reverted to pen and paper, and he has never seen a need to use anything else. He still types some documents -- most recently in April 2000. And anyway, for Dijkstra, doing his work with only pen and paper has not been `quaint' - it has been an _incredibly_ productive way of working. And _I_ think it's an intellectual discipline that we should try to reclaim for ourselves. It strikes me that few other great computer scientists have had such a bad deal as Dijkstra. Think about Tony Hoare and Don Knuth, for instance, whose work overlaps with Dijkstra's most closely. The word _controversial_ does not come to mind. Yet this is what Tony Hoare says of Dijkstra: "Edsger has been the source and inspiration of all my research into the theory of programming. And the prospect of his reading of my work has been a constant incentive to sharpen the clarity of my thinking and my presentation." And Knuth has said that Dijkstra has had a "profound influence on all the computer programs he has written since about 1970". I concede that Dijkstra hasn't helped his own reputation - he has very firm views and he doesn't mind expressing them. What seems not to have been appreciated is how much of this is cultural. Maybe you don't know many Dutch people; the ones _I_ know are very strong-minded too. Many of Dijkstra's one liners, such as the ones I read at the beginning, have become classics. And if that's all there was to them - just cute little sayings - we'd be right to dismiss his strong views as just opinions. But what the EWD archive reveals is that there's much more to them. Each of these one liners is a summary of an argument worked out in detail in one or more of the documents - in some cases these views developed over a period of years. And it's clear that on some issues he changed his mind - most notably on the value of the `goto' statement. But more on that later. A good example of the distortion that arises from taking his one liners out of context is provided by David Patterson in his list of commandments for how to give a bad talk. Number seven is "Thou shalt not illustrate" and reads: Confucius says "A picture = 10K words," but Dijkstra says "Pictures are for weak minds." Who are you going to believe? Wisdom from the ages or the person who first counted goto's? The EWD archive enables -- and, I would say, compels us -- to check out what Dijkstra really said and what he meant. Patterson's comments are not simply a cheap shot, they're a total misrepresentation. My own personal experience began with my finding the book, `A Method of Programming', in the Co-Op Bookshop. It had just been published - that was 1989 - and I devoured a large part of it. I came back to it recently - I had assumed that I hadn't read it - and I discovered that I had made a number of corrections of typographical errors, so I must have read it! By the way, I have compared the book with the original Dutch manuscript - it was a set of lecture notes and it's available in the archive as manuscript NN832 - and, of course, I found that the errors are not Dijkstra's. Still, the translator has done a very good job. I was also pleased to hear that the book is now back in print - as a `print on demand' edition - though I haven't yet been able to find it in any online catalogue. So what's in the archive? (I should mention that not all of them are a part of the EWD series; there are a number of technical reports that belong to some other numbering schemes. But the EWD series constitutes about 95% of the archive.) There are technical reports about working with real machines and real programming languages - in general, they're not in the EWD series. There are book reviews, reviews of computers (especially machines produced by IBM), exam questions, travel reports, speeches, lectures, course handouts, project proposals, personal letters, open letters, problem statements and solutions, autobiographical notes, essays about mathematical method, notes about the origin of some of the EWD documents, and essays on the role of the university, the state of the computing discipline, and industry. And of course there's what most consider the "meat": the hard-core computing science. I now propose to take us on a tour of the archive, mostly in chronological order. We'll stop at various places along the way to smell the flowers, and at other places we'll sit down and take in the scenery. In large part I will let Dijkstra speak for himself. ============================================================ ============================================================ ============================================================ ============================================================ MR12.PDF 1953 Functionele Beschrijving van de ARRA MR34.PDF On the Design of Machine Independent Programming Languages October 1961 MR35.PDF ALGOL-60 Translation (An ALGOL 60 Translator for the X1) Translated from German by M. Woodger, October 1961 November 1961 ============================================================ ZW1957-002.PDF 26 January 1957 A method to investigate primality (implemented on the ARMAC) an example returned to frequently ============================================================ CR1957-009.PDF November 1957 T. J. Dekker, E. W. Dijkstra, Prof. Dr. Ir A. van Wijngaarden Course notes for programming the ARMAC CR1970-013.PDF (MR 33) Course in programming in Algol 60, 11th edition 68 pages ============================================================ PhDthesis.PDF 28 October 1959 Communication with an automatic computer (in English) X1 ============================================================ NN832.PDF August 1982 Programmeren 1 en 2 236 handwritten pages ============================================================ EWD28.PDF January 1962 Substitution processes (similar to MR46) EWD37.PDF January 1963 A review of the IBM 1620 Data Processing System EWD84.PDF 15 May 1964 numbered from page 0 EWD117.PDF circa 1965 Programming Considered as a Human Activity questions the use of the goto - gives an argument against, based on difficulty of proving termination EWD123.PDF 1968? Must be circa 1965-6! Cooperating sequential processes (lecture notes), preliminary version binary and general semaphore; superfluity of general semaphores sleeping barber bounded buffer deadly embrace Banker's algorithm EWD158.PDF April 1966 Exam question `Cooperating Sequential Processes' Dining philosophers (but not called so; 5 processes in a cycle) EWD196.PDF The structure of the `THE'-multiprogramming system as published in CACM 1968 system hierarchy: levels 0 - 4, level 5 the operator! EWD209.PDF August 1967 A Constructive Approach to the Problem of Program Correctness producer-consumer, semaphores proof of correctness of bounded buffer implementation page 0 (beginning) Summary. As an alternative to methods by which the correctness of given programs can be established a posteriori, this paper proposes to control the process of program generation such as to produce a priori correct programs. An example is treated to show the form that such a control then might take. This example comes from the field of parallel programming; the way in which it is treated is representative for the way in which a whole multiprogramming system has actually been constructed. page 8 (conclusions) Firstly, one can remark that I have not done much more than to make explicit what the sure and competent programmer has already done for years, be it mostly intuitively and unconsciously. I admit so, but without any shame: making his behaviour conscious and explicit seems a relevant step in the process of transforming the Art of Programming into the Science of Programming. My point is that this reasoning can and should be done explicitly. Secondly, I should like to stress that by using the verb "to derive" I do not intend to suggest any form of automatism, nor to underestimate the amount of mathematical invention involved in all non-trivial programming. (On the contrary!) But I do suggest the constructive approach sketched in this paper as an accompanying justification of his inventions, as a tool to check during the process of invention that he is not lead astray, as a reliable and inspiring guide. Thirdly, I am fully aware that the style of reasoning I have applied, though possibly appealing to some, might easily appal others. For this difference in taste I blame them as little as they should blame me. I can only hope that they will find a way to follow the constructive approach in a style satisfactory to them. Finally, I should like to point out that the constructive approach to program correctness sheds some new light on the debugging problem. Personally I cannot refrain from feeling that many debugging aids that are en vogue now are invented as a compensation for the shortcomings of a programming technique that will be denounced as obsolete within the near future. EWD241.PDF Towards correct programs Problem re producing all possible bit patterns that meet certain criteria Different versions of programs Note at end: (This paper has been produced in relation to a talk given at the University of Grenoble in December 1967.) Among the mental aids available I should like to mention three explicitly: 1) Enumeration 2) Mathematical Induction 3) Abstraction EWD245.PDF One of two working papers presented at 1968 NATO Software Engineering Conference in Garmisch, 7-11 October 1968 On useful structuring The purpose of this minor contribution is to stress the urgency to make a conscious effort at exploiting "structure" as a useful thinking aid. Furthermore it gives some of the conclusions such an effort has led me to so far. To start with, I take for granted that all of us acknowledge that the software failure is an undisputable fact: this recognition was why this conference on software engineering was organized, its acknowledgement is why we have accepted to participate. Hardware is rushing ahead of our programming ability and unless something drastic happens the situation will only get worse and worse. For: with more and more powerful machines becoming generally available society will be more ambitious in these applications and will be demanding more from the poor programmer who finds his tasks in the field of tension between the things to be done and the available tools. The scope of his task is just exploding. At face value our main shortcoming is that we have let ourselves be lured into constructing elaborate mechanisms, the actual behaviour of which has grown far beyond our mental grasp or even worse: the misbehaviour of which is well beyond our control. As a professional community we play the Sorcerer's Apprentice over and over again. Closer scrutiny reveals the current source of the trouble: viz. unstructured multitude and bigness, insufficiently organised complexity with its bastards such as Chaos, Unreliability, Unadaptability and the like. To regain control over what we are doing and what we are making constitutes for me the main challenge of software engineering. Now, closer to the problem at hand. It would be helpful if all of us recognised that although the programmer only makes programs, the true subject matter of his trade are the possible computations evoked by them. In actual fact: the computation is the happening that has to effectuate the desired effect or in other words, when a programmer claims that his program is correct, he actually makes a statement about the computations! Trivial as this remark may seem I must state that it has had a profound influence on my thinking and my programming. Once I was really aware of my mind's task to bridge the conceptual gap between the static program and the dynamic computation, I have restricted myself to the most straightforward sequencing clauses, finding myself in general unable to cope with programs containing go to statements. I will return to sequencing control later on, at present we note that here is an element of structure greatly assisting me in understandability of what we are making. After long and, I must admit, rather painful struggles, I came to the following conclusion: doing something and knowing what you have done implies that your act is presented as a choice from what you could have done. In particular: making a program implies taking a whole class of programs into account: alternative programs for the same job or for related jobs, and programs on various levels of detail. In doing so I made the following observations which may inspire you: they seemed relevant in the light of my experience. 1. Different members of the program class can only share their correctness proof to the extent that they enjoy the same structure. In other words: comparing programs with the aim of comparing the corresponding computations is only a fruitful activity to the extent that they exhibit the same sequencing. 2. A flowchart need not be regarded as a vague sketch of what we are going to do, a sketch that only makes sense when the details have been filled in. On the contrary: at the appropriate level of abstraction it can be regarded as a program existing in its own right. 3. It may very well be that certain aspects of the original problem statement are only reflected at the lower levels of greater detail: this just means that at the higher level one has a program solving a generalised problem. 4. I tend to think of the program consisting of a set of hierarchical layers, performing in steps the transition from what we have got into what we should like to have. The right of existence of these separate layers is that in each layer an independent abstraction is implemented: an identified choice is condensed in its coding. One of the trickiest kind of alternatives to compare turned out to be analagous to the design decision whether something shall be done by software or by a machine instruction. This observation is, I think, encouraging. Finally, to ride another little pet horse of mine: experience has given me a strong indication that provided the software is properly constructed its correctness can be claimed much more convincingly by a convincing proof of its correctness than can ever be achieved by the all too common procedure of testing and debugging. I know that the truth of this statement is doubted by many, but always by those who did not try to apply the method. ============================================================ NATO 1968 conference (not in the archive) Dijkstra's paper: Complexity controlled by hierarchical ordering of function and variability gave rise to several remarks. Next you said that you missed in my description something which you described as, how does one solve a problem. Well, as you, I am engaged in the education business. If I look for someone with a position analogous to the way in which I experience my own position, I can think of the teacher of composition at a school of music. When you have got a class of 30 pupils at a school of music, you cannot turn the crank and produce 30 gifted composers after one year. The best thing you can do is to make them, well, say, sensitive to the pleasing aspects of harmony. What I can do as a teacher is to try to make them sensitive to, well, say, useful aspects of structure as a thinking aid, and the rest they have to do themselves. Communication and management in design I have a point with respect to the fact that people are willing to write programs and fail to make the documentation afterwards. I had a student who was orally examined to show that he could program. He had to program a loop, and programmed the body of it and had to fill in the Boolean condition used to stop the repetition. I did not say a thing, and actually saw him, reading, following line by line with his finger, five times the whole interior part of his coding. Only then did he decide to fill in the Boolean condition and made it wrong. Apparently the poor boy spent ten minutes to discover what was meant by what he had written down. I then covered up the whole thing and asked him, what was it supposed to do, and forced out of him a sentence describing what it had to do, regardless of how it had been worked out. When this formulation had been given, then one line of reasoning was sufficient to fill in the condition. The conclusion is that making the predocumentation at the proper moment, and using it, will improve the efficiency with which you construct your whole thing incredibly. One may wonder, if this is so obvious, why doesn't it happen? I would suggest that the reason why many programmers experience the making of predocumentation as an additional burden, instead of a tool, is that whatever predocumentation he produces can never be used mechanically. Only if we provide him with more profitable means, preferably mechanical, for using predocumentation, only then will the spiritual barrier be crossed. Alan Perlis: The point that Dijkstra just made is an extremely important one, and will probably be one of the major advantages of conversational languages over non-conversational ones. However, there is another reason why people don't do predocumentation: They don't have a good language for it since we have no way of writing predicates describing the state of a computation. Acceptance testing Testing is a very inefficient way of convincing oneself of the correctness of a program. Education To the question of how one can get experience when working in a university I have two answers: (1) If you undertake something at a university it has to be one of your main concerns to organize your activity in such a way that you get exactly the experience you need. This again must be the main concern in the choice of projects. (2) We have a Dutch proverb: One learns from experience, suggesting that it happens automatically. Well, this is a lie. Otherwise everyone would be very, very wise. Consequently in a university with limited resources, from the experience one has got one should try, consciously, to learn as much as possible. ============================================================ back to the archive for: EWD249.PDF August 1969 (when finished? original must be started late 1968) Second edition, April 1970 Notes on structured programming Composing a program as stringing pearls together into a necklace On our inability to do much Making assumptions explicit - floating-poing representations Prime number generator Plotting a function Layers of abstract machines Successive refinement of programs EWD268.PDF August 1969 Structured Programming Presented as a working paper at 1969 NATO Software Engineering Techniques, Rome, 21-31 October 1969 ============================================================ 1969 NATO conference (not in the archive) Ian Sharp: I believe that a lot of what we construe as being theory and practice is in fact architecture and engineering; you can have theoretical or practical architects: you can have theoretical or practical engineers. I don't believe for instance that the majority of what Dijkstra does is theory -- I believe that in time we will probably refer to the Dijkstra School of Architecture. I would like to comment on the distinction that has been made between practical and theoretical people. I must stress that I feel this distinction to be obsolete, worn out, inadequate and fruitless. It is just no good, if you want to do anything reasonable, to think that you can work with such simple notions. Its inadequacy, amongst other things, is shown by the fact that I absolutely refuse to regard myself as either impractical or not theoretical. [E. E.] David expressed the idea that "We can make case studies in industry, and then you can study the results. You can do these analyses." A probable effect of the distinction is that if such a study is made, the output of it can be regarded as theory and therefore ignored. What is actually happening, I am afraid, is that we all tell each other and ourselves that software engineering techniques should be improved considerably, because there is a crisis. But there are a few boundary conditions which apparently have to be satisfied. I will list them for you: 1 We may not change our thinking habits. 2 We may not change our programming tools. 3 We may not change our hardware. 4 We may not change our tasks. 5 We may not change the organizational setup in which the work has to be done. Now under these five immutable boundary conditions, we have to try to improve matters. This is utterly ridiculous. Thank you. (Applause) Software Quality/ Correctness Testing shows the presence, not the absence of bugs. Debugging M. E. Hopkins: Programmers call their errors bugs to preserve their sanity; that number of mistakes would not be psychologically acceptable! I think that the higher level the language used in programming the better. This was clearly understood by Shakespeare who was against assembly language coding: Bloody instructions which being learned, return to plague the inventor (Macbeth). Programming languages should have structure. The user must be helped to write in a proper style which will improve the standard of the resulting program. Machines don't have side effects; neither should languages. Dijkstra: I would like to applaud Hopkins' remarks! Software engineering education A Dutch definition of a university professor is someone who casts false pearls before real swine! Otherwise my position differs greatly from that which Perlis describes. I am engaged in teaching, at graduate level, in producing one variety of mathematical engineer. The most powerful test that I know of for an applicant to be one of my students is that they have an absolute mastery of their native tongue: you just need to listen to them. I find it difficult to find worthwhile research subjects and think it wrong to teach material which I know will be obsolete in a few years. What finally remains isn't so much. You have to teach a grasp of method, a sense of quality and style. Sometimes you are successful. This cannot be all of computer science or software engineering. It may well be that it is a rather small subject but it may take very good people to work in it. A neglected part of software engineering is the area of hardware design. If a software engineer cannot specify hardware design, who can? ============================================================ back to the archive for: EWD273.PDF The Programming task Considered as an Intellectual Challenge Speech/lecture, report of October 1969 NATO conference December 1969 EWD279.PDF (no date) The programming laboratory project Secondly I would like to do away with the off-line preparation of paper tapes or cards as part of the activity of program composition. This points to having the complete system documentation inside the machine, as readable as source text. EWD287.PDF Sans titre (but most definitely a predecessor to {EWD316}, `A short introduction into the art of programming') 93 pages problem of finding `good' sequences of numbers using the digits 1, 2, 3. shortest spanning subtree of a graph towers of Hanoi eight queens pivot part of Quicksort EWD316.PDF August 1971 A Short Introduction to the Art of Programming Nice version of EWD287 EWD288.PDF July 1970 Concern for Correctness as a Guiding Principle for Program Composition EWD302.PDF Design considerations in more detail. Preceding sections -- in particular `A first example of step-wise program composition' have evoked the criticism that I have oversimplified the design process almost to the extent of dishonesty; I don't think this criticism fully unjustified and to remedy the situation I shall treat two examples in greater detail. (two problems from EWD287) EWD310.PDF Hierarchical Ordering of Sequential Processes 29 pages published in Acta Informatica 1971 `Five Dining Philosophers' EWD340.PDF The humble programmer published in CACM 1972 Turing award acceptance speech EWD367.PDF 29 April 1973 On the axiomatic definition of semantics (The following is heavily influenced by the work of C.A.R.Hoare.) `predicate transformers' EWD418.PDF 26 June 1974 Guarded commands, non-determinacy and a calculus for the derivation of programs. EWD470.PDF 22 January 1975 Letter to the referees of EWD418 5 pages EWD472.PDF CACM 1975 version of EWD418 EWD447.PDF 30 August 1974 On the role of scientific thought (Springer) (page 2) Another separation of concerns that is very commonly neglected is the one between correctness and desirability of a software system. Over the last years I have lectured for all sorts of audiences about the techniques that may assist us in designing programs such that one can prove a priori that they meet their specifications. One of the standard objections raised from the floor is along the following lines: "What you have shown is very nice for the little mathematical examples with which you illustrated the techniques, but we are afraid that they are not applicable in the world of business data processing, where the problems are much harder, because there one always has to work with imperfect and ambiguous specifications." From a logical point of view, this objection is nonsense: if your specifications are contradictory, life is very easy, for then you know that no program will satisfy them, so, make "no progress"; if your specifications are ambiguous, the greater the ambiguity, the easier the specifications are to satisfy (if the specifications are absolutely ambiguous, every program will satisfy them!). Pointing that out, however, seldom satisfies the man who raised the objection. What he meant, of course, was something different. He meant something along the following lines: "We make something with the best of intentions in the hope of satisfying a need as we understand it, but when our product has been put into action, it does not perform satisfactorily and how are we to discover whether we have correctly made the wrong thing or whether there is just a silly bug somewhere?". The point is that that this question is empty as long as the specifications do not define -- are not accepted to define by definition -- what the system is supposed to do. It is like asking the judge to settle a business dispute caused by the absence of a contract stating the mutual rights and obligations. It is the sole purpose of the specifications to act as the interface between the system's users and the system's builders. The task of "making a thing satisfying our needs" as a single responsibility is split into two parts " stating the properties of a thing, by virtue of which it would satisfy our needs" and "making a thing guaranteed to have the stated properties". Business data processing systems are sufficiently complicated to require such a separation of concerns and the suggestion that in part of the computing world "scientific thought is a non-applicable luxury" puts the cart before the horse: the mess they are in has been caused by too much unscientific thought. But from the above, please don't conclude that unscientific thought is restricted to the business world! In Departments of Computing Science, one of the most common confusions is the one between a program and its execution, between a programming language and its implementation. I always find this very amazing: the whole vocabulary to make the distinction is generally available, and also, the very similar confusion between and computer and its order code, remarkably enough, is quite rare. But it is a deep confusion of long standing. One of the oldest examples is presented by the LISP 1.5 Manual: halfway through their description of the programming language LISP, its authors give up and from then onwards try to complement their incomplete language definition by an equally incomplete sketch of a specific implementation. Needless to say, I have not been able to learn LISP from that booklet! I would not worry, if the confusion were restricted to old documents, but, regretfully enough, the confusion is still very popular. At an international summer school in 1973, a very well-known professor of Computing Science made the statement that "ALGOL 60 was a very inefficient language", while what he really meant was that with the equipment available to him, he and his people had not been able to implement ALGOL 60 efficiently. (That is what he meant, he did not mean to say it!) Another fairly well-known professor of computing science has repeatedly argued in public that there is no point in proving the correctness of one's programs written in a higher-level language "because, how do you know that its compiler is correct?". In the motivation of a recent research proposal doubt is case upon the adequacy of "the axiomatic semantics approach" as it may lead to deductive systems that are "undesirable in that they may not accurately reflect the actual executions of programs". It is like casting doubt on Peano's Axiomatization of the Natural Numbers on the ground that some people make mistakes when they try to do an addition! (compare this with Niklaus Wirth, "Programming Language: what to demand and how to assess them", March 1976, cited at EWD571-3: "I believe that there will be no real progress until programmers learn to distinguish clearly between a language (definition) and its implementation in terms of compiler and computer. The former must be understood without knowledge of the latter. And we can only expect programmers to understand this vital distinction, if language designers take the lead [...]. Hence we conclude that the first criterion that any future programming language must satisfy, and that customers must ask for, is a complete definition without reference to compiler or computer.") (page 5) In view of the preceding it becomes quite obvious why many earlier efforts to concoct Computing Science Curricula at our universities have been such dismal failures. They were just cocktails! For lack of other ingredients, they tried to combine scraps of knowledge from the most diverse fields that seemed to have some relation to the phenomen Computer. That the ingredients of the cocktail did not mix into a coherent whole, is not surprising; that the cocktial did not tast too well, is not surprising either. In those early days, the only alternative was waiting, as for instance still in 1969 urged by Strachey: "I am quite convinced that in fact computing will become a very important science. But at the moment we are in a very primitive state of development; we don't know the basic principles yet and we must learn them first. If universities spend their time teaching the state of the art, they will not discover these principles and that, surely, is what academics should be doing." I could not agree more. EWD469.PDF Programming methodologies, their objectives and their nature. Years ago I gave a talk at a large software house, showing what techniques we had at our disposal for proving the correctness of programs. The talk was a disaster. My audience rejected the topic for what they regarded as sound business reasons: from a business point of view, correctness was their last goal: it was much more important to make a customer dependent on a software product so poorly documented and still so full of bugs, that its maintenance contract fell into your hands as well. But not only the managers of the firm rejected my topic, so did the programmers in my audience: they felt that I was tampering with the magic of their craft. While I had urged that a programmer should continue to understand what he is doing, it transpired during the discussion that many a professional programmer derives his intellectural excitement from _not_ quite understanding what he is doing, from the daring risks he takes in his irresponsibility. They wanted the magic of their craft to remain black magic.... I mention this story because their reaction took me by surprise. He goes on to give two reasons. First, the attraction of magic. Second, the modelling of the professions on the guilds. But he argues that this is not what universities should be about. EWD473.PDF 13 February 1975 On the teaching of programming, i.e. on the teaching of thinking lecture EWD485.PDF 16 March 1975 Marketing Questionnaire "A Discipline of Programming" 5. Teaching and learning aids in the book The book does not contain the usual type of confusing diagrams (it contains, as a matter of fact, hardly any illustrations). Compares his book with Conway & Gries and Wirth. EWD492.PDF 2 April 1975 On-the-fly garbage collection: an exercise in multiprocessing EWD496A.PDF On-the-fly garbage collection: an exercise in cooperation by Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten, E. F. M. Steffens EWD496B.PDF On-the-fly garbage collection: an exercise in cooperation EWD520.PDF 20 October 1975 On-the-fly garbage collection: an exercise in cooperation EWD595.PDF 5 January 1977 On-the-fly garbage collection: an exercise in cooperation EWD630.PDF 1977 On-the-fly garbage collection: an exercise in cooperation as published in CACM 1978 EWD498.PDF How do we tell truths that might hurt? (Springer) EWD501.PDF 5 July 1975 Variations on a theme: an open letter to C. A. R. Hoare (Springer) Comments on Hoare's monitor paper EWD514.PDF 17 September 1975 On a language proposal for the Department of Defense comments on "strawman" EWD533.PDF Homo cogitans: A Small Study of the Art of Thinking orders of magnitude difference in the difficulty of programming EWD544.PDF 30 December 1975 An open letter to Ross Honsberger Handwritten (first one? I have checked the three preceding ones; they are all typed; 547 is typed) EWD564.PDF A superficial book "Techniques of Program Structure and Design.", Edward Yourdon, Prentice Hall, 1975 EWD574.PDF A letter to Professor Zohar Manna, 26 July 1976 EWD581.PDF A somewhat open letter to Professor John McCarthy including McCarthy's letter of 18 August 1976 about Dijkstra's letter to Manna (EWD574) EWD613.PDF Trip report, Australia, 16 February 1977--21 March 1977 (Springer) The trip to "downunder" was terrible. Still remembering my forced stay in the International Departure Hall of New Delhi--with the cockroaches on the carpet--I refused to fly again via the Eastern Hemisphere and had arranged my itinerary via Los Angeles. The IATA tariff rules -- imposed by QANTAS, the Australian airline company -- are such that you may have one stopover during the whole trip. Having the choice between arriving in Australia or returning home as a bodily and nervous wreck, I had chosen the first. and later: Life is not easy for Australian scientists. A look through the papers gives you the impression that Australian spiritual life extends from labour conflicts at the one hand and cricket at the other hand, with very little in between. Listening to the conversations one discovers that there is bushwalking -- with snob value -- and that there are horse races -- definitely without it-- . There is, of course, much more, but that is definitely much less prominent, under the surface, so to speak. I found many of my colleagues a little bit sad. They feel very much cut off from the rest of the world, and to a large extent they are. Scientific journals are sent by surface mail, and thus arrive late and irregularly. Worse, of course, is that they are cut off from the old boys network and pick up so little from the grapevine. They are very much aware of this isolation and try to compensate for it. They do this in their personal lives. I found in several homes impressive record collections; I also looked at the bookshelves, and, again, I was often impressed. They also try to do this in their organisations. There were many foreigners and most of the Australian staff members seemed to have been either in Europe or in the USA or both, either for many visits or for extended periods of time. The net result was that at many places -- but particularly at ANU -- the whole atmosphere was quite cosmopolitan. and later: a description of staying at University House and environs. On one of the last days, one of the staff members dropped in. He was genuinely worried and puzzled, and asked "Why did yo ucome? You did not get anything from this visit." I could answer that I had come, firstly because I had been invited, and secondly, because the way in which the invitation from dr.Robin B.Stanton had been phrased had given me the impression that he had sound reasons for being very keen that I should accept the invitation. Shortly after my arrival I began to understand what Stanton hoped that I would do, and I think that I have done it to the extent that can be achieved in a one-month visit. It was hard work, I had to be alert continuously. The greatest compliment for my hosts in general and for Stanton's care and initiative in particular is probably Ria's remark when she entered my office a page ago: "I am glad you went." To which I could only add "I am also glad to be home again." EWD637.PDF (Springer) The Three Golden Rules for Successful Scientific Research Raise your quality standards Scientific soundness over social relevance Don't tackle problems that others are better at EWD683.PDF 4 October 1978 To a new member of The Tuesday Afternoon Club EWD696.PDF 20 December 1978 Written in anger On (not) using diagrams as a proof technique EWD716.PDF 1 October 1979 A short talk to my students about money. software engineering education about the cost of things as a design influence EWD717.PDF 3 October 1979 An exercise in exposition handwritten EWD718.PDF typed EWD719.PDF 29 October 1979 typed until half-way through EWD719-7, the rest handwritten EWD720.PDF 18 November 1979 typed game with white and black balls EWD723.PDF 29 December 1979 handwritten EWD724E.PDF typed EWD726.PDF 9 January 1980 handwritten EWD731.PDF 27 February 1980 handwritten EWD732.PDF handwritten EWD738.PDF typed EWD739.PDF typed EWD748.PDF 17 September 1980 handwritten EWD831.PDF 11 August 1982 Why numbering should start at zero EWD841a.PDF Remarks about the genesis of the paper "A Note on Two Problems in Connexion with Graphs" typed EWD847.PDF 14 February 1983 Trip report, Australia, 19 Jan. 1983 -- 12 Feb. 1983 typed First Wollongong Summer School on The Science of Programming, Perisher Valley. On Friday morning 7:10 we left in a minibus for Canberra, where Tony was to give a lecture at the Australian National University, either at the end of the morning or at the beginning of the afternoon, no one was quite sure. (It turned out to be at 14:00.) The journey to Canberra was not a pleasant one: it became very, very hot in the minibus and its driver -- Dromey -- absent-mindedly indluged in a technical discussion for which he would have preferred to use both hands. After a depressing exposure to the results of the Australian drought we arrived in Canberra, well in time had Tony had to perform in the morning. After lunch, Tony gave his talk, but he was clearly not in the mood. In the evening the Department of Computer Science took us out for dinner; I enjoyed both the food and the company. Then our ways separated for almost two days. The others continued the next day their journey to Perisher Valley, while Ria and I stayed for a long weekend with Robin and Kate Stanton. (Robin had been my host in 1977, when I stayed for a month at ANU.) On Saturday we went to the Botanic Garden (whose trees give surprisingly little shade), to the High Court and the (new) National Gallery, on Sunday to Tidbinbilla Nature Reserve, where we saw many emus, kangaroos (both from quit close) and -- we were very fortunate! -- one koala: a really charming animal! Both evenings Kate had guests for dinner. It was a pleasant weekend, but very hot: 34 degrees C. in the living room seemed standard. I wrote some, but not much. On Monday afternoon Robin drove with Brian Molinari and us in Kate's car to Perisher Valley, where, in Sponar's Chalet, the Summer School would start the next morning. and later: On Tuesday evening we had a very nice string quartet (Mozart, Shostakovich, and Meldelssohn again; I liked Mozart most): Richard Tognetti (17) and Karen Segal (18), violins, Debbie Lander (17), viola, and Rita Woolhouse (21), 'cello. They played very well and had not the handicap of an unwilling keyboard instrument. EWD889.PDF 28 May 1984 User-friendly mathematics EWD927.PDF 29 August 1985 The ATAC (= Austin Tuesday Afternoon Club) EWD947.PDF A letter to a typewriter manufacturer handwritten EWD952.PDF typed EWD962.PDF June 1986 Introducing a course on mathematical methodology (page 0) To put it bluntly, a major part of my educational duty is to be an un-American activity become flesh. (page 7) Just as a professor at a conservatory represents a musical style (to the extent that it is often possible to identify the master by listening to his pupils), I represent a mathematical style. It is up to you to decide later to what degree to adopt and to improve it. One thing, however, you are not allowed to do, viz. to reject it offhand for the sole reason that it does not reflect the way of doing mathematics you are used to. Of course it doesn't! That is precisely why you are here. EWD977.PDF 14 September 1986 An address to my students (16.9.1986) "a certain editing/type-setting system" EWD1000.PDF 11 January 1987 Twenty-eight years Twenty-eight years ago I wrote EWD0. typewriters My degradation from esteemed colleague to dangerous competitor caused me to suffer from a depression that lasted more than half a year. EWD249 marked my recovery. Was an expert typist, but preferred writing (noisy typewriter) I am reasonably pleased with life, about as pleased as we poor mortals may be allowed to be, and in this contentment the EWD-series plays a major role. If there is one "scientific" discovery I am proud of, it is the discovery of the habit of writing without publication in mind. I experience it as a liberating habit: writhout it, doing the work becomes one thing and writing it down becomes another one, which is often viewed as an unpleasant burden. When working and writing have merged, that burden has been taken away. EWD1009.PDF 25 May 1987 On a somewhat disappointing correspondence on Frank Rubin's letter to CACM and the replies EWD1036.PDF 2 December 1988 On the cruelty of really teaching computing science radical novelties: (1) orders of magnitude (2) automatic computer is our first large-scale digital device proposal for freshman course in introductory programming EWD1058.PDF In reply to comments reply to responses to EWD1036 as published in CACM EWD1055A.PDF List of points for researchers (as on my door) EWD1068.PDF On the quality criteria for mathematical writing Assume your audience to be * large * ignorant of the jargon and tacit assumptions that are specific to your topic * sympathetic, curious, intelligent and demanding EWD1166.PDF 29 November 1993 "From my Life" typed autobiography EWD1175.PDF 9 February 1994 The strengths of the academic enterprise typed (page 1) My third remark introduces you to the Buxton Index, so named after its inventor, Professor John Buxton, at the time at Warwick University. The Buxton Index of an entity, i.e. person or organization, is defined as the length of the period, measured in years, over which the entity makes its plans. For the little grocery shop around the corner it is about 1/2, for the true Christian it is infinity, and formost other entities it is in between: about 4 for the average politician who aims at his re-election, slightly more for most industries, but much less for the managers who have to write quarterly reports. The Buxton Index is an important concept because close co-operation between entities with very different Buxton Indices invariably fails and leads to moral complaints about the partner. The party with the smaller Buxton Index is accused of being superficial and short-sighted, while the party with the larger Buxton Index is accused of neglect of duty, of backing out of its responsibility, of freewheeling, etc. In addition, each party accuses the other one of being stupid. The great advantage of the Buxton Index is that, as a simple numerical notion, it is morally neutral and lifts the difference above the plane of moral concerns. The Buxton Index is important to bear in mind when considering academic/industrial co-operation. EWD1179.PDF 1 May 1994 A sorry parade about the use of OHPs "Parade of the Faculty Candidates" EWD1283.PDF 21 February 1999 How "they" try to corrupt "us" At my former university it was a firm principle of the informatics group that we would _not_ teach our students how to use industrial products. The main reasons at the time were * the quality of industrial products was never up to academic standards, and * the market being as fickle as it is, the industrial product was of volatile significance only Later I learned how much the purposes of the University and those of industry can diverge. Universities, believe it or not, are interested in education, but I learned of industries that were not interested in education at all, neither in an educated work force, nor in an educated customer base. On the contrary, they preferred a docile, brainwashed work force and undemanding customers hooked on their products. Another remark is that it is the task of a "leading University" to lead. In particular this means for us that we should give society not what it asks for, but what it needs. This issue is particularly acute for CS because their society asks for snake oil, for more of the same, though we all know that it hardly works. * * * The above was triggered by a letter we received from one of our colleagues. I quote from it -- "MS" presumably stands for "Microsoft" -- : "We had a good meeting with MS representatives [...]. They were open to the possibility of giving us a *significant* number of graduate fellowships [...]. A key thing that MS wants in return is that our students have experience in programming in NT environments; they and other companies want such students. [...]" Well, that was a revealing meeting! For the record I quote from the following paragraph of that letter: "I believe a key to the MS support for our department will be clear evidence that we are using NT (or related software, e.g. CE). I need to collect information about your use of NT (or intended use of MS software) as part of our proposal." Since I do not want MS to sue me, I won't tell you how much I appreciate their offer. You must guess. For more detail I refer to the communications of the Chairman of the Board of "Mathematics Inc.", as published in "Selected Writings on Computing". For dominance of the Universities, see EWD 539 in particular. [Gives ref and bibliography instead of naming the book inline.] EWD1285.PDF 30 April 1999 To Cambridge by mistake (13--April 1999) "EDSAC 99" Of course it did not help that, when I left on Tuesday afternoon, I was upset and rather depressed. In the morning I had listened to a faculty candidate, and that had been a pretty awful experience. You see, a few years ago graduate students believed that the use of LATEX was enough to write a scientific article; these days faculty candidates seem to think that they can give a scientific lecture provided they have played enough with Powerpoint. EWD1298.PDF 22 April 2000 typed EWD1303.PDF October 2000/April 2001 My recollections of operating system design EWD1305.PDF 28 November 2000 Answers to questions from students of Software Engineering EWD1308.PDF 10 June 2001 What led to "Notes on Structured Programming" EWD1309a.PDF 25 June 2001 ============================================================ ============================================================ ============================================================ ============================================================ I would like to conclude by showing you the end of the video, which was made in 1990. You'll see him argue that we should call `bugs' `errors'. So what? I hope I have shown that these few words spoken by what looks like a very strange old man are much more than what they appear. They are a summary of decades of calling programmers to account for their work. He is not saying this here for the first time. We are only now beginning to teach ethics to our students as an essential part of the curriculum. In this respect, have we been like the driver in the ad who has to be told to wear a seatbelt? (play tape) Do you have any questions or comments?