A "non trip report" from E.W.Dijkstra.

        On my last visit to the U.S.A. I found that many regular readers of my trip reports have no picture at all of my daily life when I am not traveling. And, indeed, how should they without further information? This "non trip report" is written with the intention of redressing the balance.

        Tuesday is my day at the Eindhoven University of Technology. It has by now a well-established pattern. In the morning I lecture for two hours and further take care of all "irregular" business (mail, receiving students etc.) The afternoon is reserved for a four-hour discussion with a small group of young computing scientists on whatever subject is brought up.

        Lecturing is great fun. Officially I give only two courses, an introduction to programming in the fall semester and a course on synchronization and communication in the spring semester, but they are no two years the same: the subject matter is so much alive that it is no problem at all to keep these lectures fresh. (I myself find them, as a matter of fact, often quite exciting!) What helps greatly is that of my audience —about 70 people— only half of it is formed by students that have to follow the course, the remaining ones come from other departments or from outside and quite often have already their degree: they come because they are interested, and that makes an inspiring audience.

        The discussion in the afternoon —we are currently with five people: besides me two from within and two from outside the University— takes place in my office at the University and its topics cover in principle a very wide range. It may be an open question that I raised that morning at my lecture, the thesis topic of one of the participants, something that one of us has read somewhere and seemed important to him, something one of us has done or the difficulties he is encountering while trying to do so. (Most of the technical EWD's have in some stage been discussed in this group.) On the average, these Tuesday afternoons are very productive, but it varies as much as the topics: sometimes we just get stuck.

        The other more or less fixed point in my week is Friday which is in principle reserved for working together with a colleague of long standing: we now work together for nearly a quarter of a century! As an experimental physicist he entered the hardware side of our field, while I, a theoretical physicist, entered it as a programmer. The difference in background is still reflected in the nature of our work, but we know each other by now so well that we can appreciate the other's achievements and problems and can often help the other. Besides being very bright and knowledgeable, he is a mature scientist and many things which turned out to become a major topic have been discussed with him in their infancy, when they were still hunches. Because working with him takes "the full mind", it is usually a day of very hard work that leaves me tired and it is a good way to end the week: then we have the weekend to recover and to regroup our forces.

        The other days of the week I am, in principle, a free man, but a few (mostly self-imposed) constraints usually define what has to be done.

        A self-imposed constraint is that all appeals to my assistance in which the professional life of others is at stake, are dealt with promptly. Under this category fall refereeing of papers for symposia and journals, the evaluation of research proposals for funding organizations and of candidates for university posts. (It differs from country to country: my impression is that, for instance, English and American universities seem to rely more heavily on external assessment than the Dutch ones.)

        Besides those constraints I have to observe the deadlines that are the consequence of having committed myself to address an audience. Invitations to do so usually reach me long before the planned date of delivery, so long as a matter of fact, that I usually don't propose to talk about what I have done at the moment of acceptance, but commit myself to talk about the work that I intend to do in the meantime. But I also know myself well enough to know that I work very poorly when under strong pressure, and my desire to have my document ready well in advance of the actual deadline restricts my freedom.

        In my little one-man research establishment, the mail plays of course an important role: to give you some idea, the practical unit for the rate of incoming mail seems to be "pounds/week". Of course I don't need to read it all. Some of it can be thrown away at a glance, most of it I just scan —e.g. lists of abstracts of articles produced by such-and such organization, or encyclopedic works— to keep an overview of what is happening elsewhere. This does not take much of my time. But some of the stuff that is sent to me is very interesting, and then I want to study it, and occasionally it keeps me busy beyond that, either because I start a correspondence with the author or because I don't like the offered solution and try to do better or because the author's attack seems to give a fresh handle on one of my old unsolved problems.

*         *         *

        In a recent paper "The high cost of programming languages", C.A.R. Hoare expresses at the end the "hope that one day we shall learn to design a language which will combine the merits (rather than the features) of its predecessors." After listing such merits, he continues

"But it will not be an easy task to design such a language; like all great engineering breakthroughs, it will require an insight and understanding of the total environment of implementation and use of the product; consideration and rejection of a thousand bright ideas; and a constant appeal to the criteria of low cost and high effectiveness. Furthermore, I believe that it will require an undeviating pursuit of elegance and rigour, which is characteristic of the best tradition of University research. There are few engineering disciplines in which the successful pursuit of academic ideals can pay higher material dividends than in Computer Science."

Although I am not (yet?) engaged in the design of a new programming language, I give the above quotation because I share the opinions expressed —and expressed better than I could formulate them!— and, therefore, gives an apt description of the nature of my work. Indeed: "rejection of a thousand bright ideas" nicely captures its experimental nature.

        From our current mastery of programming to "software engineering" as a discipline worthy of that name, we have still far to go. There is clearly a discipline emerging for the design of little things and for proving their correctness. That is great and encouraging, for these little things are by no means restricted to toy-problems like Euclid's Algorithm for the gcd, they also include difficult and important little things like locking mechanisms and microcode for square-root algorithms down to the bit level. But they are "little" things: it is great, it is encouraging, but not enough! Here, for instance, is an area of research where, to quote Hoare "the successful pursuit of academic ideals can pay high material dividends", at least I believe so. But I know of only one way of discovering why the application of our formal techniques, which is so successful "in the small", is less successful when we try to apply them with greater ambition, and that is "try it!". So that is, for instance, what I have done during the last month. The eventual product (EWD550 in this case) was a 19-page document, but many pages with less successful formalization and proving experiments have disappeared via the wastepaper basket. What I learned from the experience I intend to summarize in a later issue of the EWD-series.

        I mention the exercise because it seems typically to be among the type of things that I should be doing. First of all, the time was not wasted, on the contrary, as it proved to be very difficult to attain in this case the "elegance and rigour, which is characteristic of the best tradition of University research". Whether it would be done at a University, however, remains to be seen: it is —and I have said so explicitly in EWD550— work without any deep thought and, as a result, work without any glamour (and that is what many workers in the academic environment need or think they need). I think that it would be very hard to get funded for it: it is the kind of incremental improvement of which we sometimes need many, one after the other, it is the kind of work that requires hard and quit thinking. I am in the lucky position to be able to do so: that gives its obligations, the more so, because the funding of individual research seems to become more and more impopular. (I quote from a recent issue of the Bulletin of the American Academy of Arts and Sciences:

"Moreover, attitudes toward research have altered. American foundations and government agencies have become reluctant to fund research performed by individuals, preferring instead to help build large institutions and applied research centers, which can assign research priorities according to perceived and immediate economic needs."

The complaint is not new, that the situation seems to get worse is somewhat alarming.) Finally a job like that gives me some sense of achievement, and at regular intervals that is a nice feeling!

        (EWD550 deals with the formal treatment of a modest syntactic analysis. Organisations less enlightened than Burroughs Corporation tolerate such a project only provided it is immediately done on a grandiose scale: IBM allowed its Vienna Laboratory to embark upon the problems of the definition of semantics, provided Vienna formalized the semantics of PL/I, of all languages! Needless to say, the Vienna Lab more or less collapsed under that effort. IBM's dealing with that crew always strikes me as a prime example of industrial mismanagement of research.)

*         *         *

        During the same period of time I wrote EWD554 "A personal summary of the Gries-Owicki theory.", also a project without glamour in the sense that all I have done in those fourteen pages has been to condense the quintessence of the thesis written by Owicki under Gries's supervision: from my side there was no originality involved at all. Again, also EWD554 can be regarded as an experiment, in presentation. Owicki's thesis, I am sorry to say, is on the verge of unreadability. (I lent my copy of her thesis to a student who wanted to do some work in operating systems theory; I never saw him —nor my copy of her thesis— again!) This is a great pity, because hidden beneath the sometimes pompous formalism her method contains the germ of a technique for dealing with a collection of otherwise unmanageable problems. One may raise the question: "Should I spend my time on rephrasing other people's work in an effort to make it more accessible and to show its significance?" I think that sometimes I should. I wrote that text with a dual objective, viz. to offer my students some underlying material and to make a number of people within Burroughs familiar with this work. (I had a third, more selfish objective: I wanted to understand it myself, and in order to be able to do so I had to reduce it to its bare essentials.) In connection with EWD554 I must admit that I treated my students as guinea pigs: I tried my presentation of that theory out on them. The experiment —I am happy to say— gave a positive outcome. I admit "using" my regular audience for such purposes, I am not ashamed of it. There is hardly a point in developing a methodology unless one can transmit it to others, and, therefore, the possibility to transmit it should be tested experimentally.

        I don't regret having written that document. It was a personally rewarding experience because it showed me something the duo Gries-Owicki had not seen yet clearly, viz. a non-operational approach to concurrency. Besides that, who else could have done this? In writing EWD554 I needed all my experience as a teacher to make it palatable, and all my experience as a scientist to make it simple, i.e. to extract "the bare essentials". Again I am grateful for being in the position that I can allow myself to do essential work without glamour!

*         *         *

        This "non trip report" covers about the last month. The plan to write such a report has been with me for some time, the fact that it covers a period of non-glamorous activities is a pure accident. If it had covered the period during which I was engaged in the design of the on-the-fly garbage collection (EWD520) or was lighting a similar piece of firework without burning my fingers too badly, its tone would probably have been quite different. This alternation between spectacular, near reckless intellectual adventure and most definitely non-spectacular (but solid!) work does not disturb me at all, for the progress of science needs both of them.

*         *         *

        This is a good occasion to explain "the missing numbers" in the EWD-series. Some numbers are occupied by documents that I failed to complete; sometimes I start on a document because I hope and expect that I can achieve a result, for instance because I have the exciting feeling of having a new bright idea, but when I then try to use it, it does not work. Furthermore I don't send my Dutch texts to the USA. Each week during term time, for instance, I address at the beginning of my lectures my students with a speech in Dutch commenting on the world we live in: they are traditionally one page long and each speech occupies a new EWD-number. I give these speeches for the enlightening of my students, but probably even more for my own fun and in order to exercise regularly my written Dutch. Like the documents I write in my capacity of Chairman of the Board of Mathematics Inc., they are also linguistic exercises. (With Mathematics Inc., by the way, I am in trouble. No matter how corrupt our commercial practice, no matter how fraudulent our scientific activities, the world around us seems to beat us. In these competitive times itu is bloody hard even to catch up with reality!)


1st of April 1976
Plataanstraat 5
NUENEN - 4565
The Netherlands
prof.dr.Edsger W.Dijkstra
Burroughs Research Fellow

transcribed by Corrado Cantelmi
revised .Mon, 12 Sep 2005