EWD802 - 0

Trip report E.W.Dijkstra, Scotland, Newcastle 31 Aug-15 Sep 1981

Sunday morning 7:10, Femke (who had just got her driver's licence) took me to the Eindhoven railway station. Well in time for the 10:55 flight to Edinburgh. I arrived at Schiphol, not knowing yet that my flight would be delayed for almost three hours. The plane, a Fokker Friendship, arrived in time but, while landing, the pilot had jammed its nose wheel. The plane having been manufactured ten miles from where we were, I thought in my innocence that it would be fixed quickly, but Air UK preferred to fly in the spare part from Norwich, England. In the course of the afternoon I arrived in Edinburgh, where I was collected by Mr. Hannah (of Burroughs) and his wife. They drove me to The Marine Hotel in North Berwick, where I would give a seminar the next week for people from various Burroughs plants in Europe.

I had hoped to address an audience of about 25, but found a list of only 14 names. The two men from France were at the last minute replaced by one other man and the two participants from Croydon just did not show up. So I started with 11. I ended with 10 because, on Wednesday morning before breakfast, Jim Wilson (from Cumbernauld, Scotland) was found unconscious on the beach. (After 24 hours for observation in the Royal Infirmary in Edinburgh, his wife was allowed to take him home. He seemed all right; he had been jogging.)

EWD802 - 1

The rather small size of the audience, I am happy to say, was more than compensated by its quality. They were bright. The majority was not very experienced and certainly not knowledgeable, but the combination of ignorance and intellect makes quite a pleasant audience: there was a lot I had to show them but I could show it to them! I lectured for five successive days, between 6 and 7 hours per day. The first two days were largely devoted to standard material (with on the first morning the standard surprise from the audience that universal quantification over the empty set yields true). One afternoon was largely spent on the development and explanation of heapsort (something I had never done before); I did this when I discovered that I was the only one in the room who knew that algorithm. Another afternoon was quite unexpectedly spent on multiprogramming. (I derived the implementation of the conditional critical region using a split binary semaphore.) For two of the three Walloons the language barrier was severe; they did not know a single word of Dutch.

On Friday afternoon at 17:00, Mrs. Joan Suggett of The Marine Hotel took me to the station of Drem, where I should catch the train to Newcastle-upon-Tyne. I was early and the train was late. The "station" of Drem is just two platforms at either side of the track; it was unmanned and the result was that for 45 minutes I was waiting alone in the middle of nowhere; the

EWD802 - 2

Scottish wind had begun to blow and I was relieved when the train at last arrived. Around 20:00 I arrived in Newcastle.

The next 9 days I stayed with the Randells. Brian's wife was at the station; half an hour earlier she had collected a French girl - the new teaching assistant for French - who stayed with them as well until she had found accommodation. This made the house somewhat crowded and, the weather being unusually mild, the two eldest children decided to sleep in a tent in the garden.

On Saturday afternoon Brian took Françoise - such was quite appropriately the French girl's name - and me to Warkworth Castle - that is, to what has remained of it, but that was impressive enough - and to the "Hermitage" nearby, a pre-medieval chapel hewn out in the rocks. A so-called unique experience. The next afternoon, Brian went with Françoise and some of his sons to a rugby match; I stayed home and wrote. On Monday I joined Brian on his walk to and from the University, where I spent the day talking and reading (in "The Mathematical Experience" by Philip J. Davis and Reuben Hersh (Birkhäuser), a new book, but too philosophical for me).

At the home of Harry Whitfield we had that evening the first social event of the 14th, Joint International

EWD802 - 3

Seminar on the Teaching of Computing Science, this time devoted to Very Large Scale Integration. The next morning the seminar started in real earnest.

We started with the obligatory IBM speaker, this time Dr. V.L. Rideout, and when he started with the usual slide show, I feared the worst. But, apart from the fact that he showed too much and spoke mostly in acronyms, he was an excellent speaker who gave an instructive survey of the technological difficulties of chip fabrication. (Later in the week, other American speakers would refer to the "fab line".) He gave 2 lectures. The third IBM lecture was given by Dr. J. Rivierre, who made it quite clear - he talked about test pattern generation - that for chips quality control is a profoundly unsolved problem. I appreciated his choice of topic, for too many in that field are only too happy to ignore this unfortunate circumstance. (I remember Noice's comment along the lines "From a technological point of view it is not attractive, but it does not matter too much for our competitors cannot do better.") His was a slide show too.

Dr. J. Gray (University of Edinburgh) gave two lectures on "Structured Design". What he told he told convincingly, viz. that design discipline made most of the elaborate "CAD tools" (CAD for Computer Aided Design) superfluous. In contrast to the previous speakers, Gray told perhaps too little. Besides the

EWD802 - 4

unavoidable slides he showed transparencies.

Prof. Dr. M. Rem used the blackboard. He gave 2 lectures illustrating a design discipline, the first one on a notation for restoring logic circuitry, the second one on partially ordered computations. In his first lecture he hesitated too much, his second lecture was much better. Amazingly enough, M. Wells (Leeds) almost exploded when he was half-way, complaining that Rem was not concrete enough and did not give a "picture to show what he was talking about". I can only fear that Wells has not followed what C.A.R. Hoare has been writing about during the last four years. (More in the audience seemed flabbergasted by the fact that so much can be said independently of the distinction between input and output. The inability not to make that distinction seems a further price to be paid for a very operational approach.)

Prof. H.T. Kung (Carnegie-Mellon University) gave 3 lectures on his high-performance special purpose designs, which are very original. (They are fun.) He had given these lectures - transparency shows - many times before, but delivered them with an almost contagious enthusiasm. The combination of a severe stammer and a strong Chinese accent made him not too easy to understand. The most amazing thing is that he did it all by hand-waving

EWD802 - 5

and seemed to have never considered a decent notation for and a more rigorous treatment of his highly concurrent computations.

(The above was written on the evening of Friday 11 Sept. 1981, while Brian Randell and his wife were to the opera; they had invited me to join them but, disliking opera, I had declined their invitation whole-heartedly.)

We were exposed to 3 presentations given by Prof. C.H. Sequin (University of California, Berkeley). Underlying his topic was the Mead/Conway design methodology "requiring virtually no specific knowledge about the physics of silicon devices", and that sounds very sensible. But his description of the course in which this way of designing chips was taught gave me the impression of something rather silly. He spoke much more like a manager than as a scientist, and I found him unpleasant to listen to. His students seemed to learn how to make the best of a set of dubious "design tools"; the gap between intentions and actual practice seemed very wide.

Finally we had 3 presentations by Prof. J. Allen (MIT) but he used such loose language ("multiple levels of process representation") that I found it impossible to figure out what he was talking about. One thing, however, was clear: his unshakable faith

EWD802 - 6

in "logic simulators". One of the "CAD tools" - Sequin had mentioned it too - tried to reconstruct the circuitry from the raster description of the masks! The amount of pattern recognition involved made it a very expensive (and not too reliable) tool, and Allen seriously proposed to design a special machine for this purpose. In his summary of what we had learned, Prof. C.A.R. Hoare compared it with the future software design tool that, by analysing the object code on the bit level, would perform the type checking for Ada programs "since, of course, you cannot trust the compiler". It was a great pity that, by that time, Allen had left.

Much of the design process as shown to us seemed engineering in the worst possible sense of the word, viz. essentially by trial and error. (In this connection, Sequin's insistence on the quick turn-around from the "fab line" was very telling: evidently the chip itself was a component in a major feedback loop in the design process.) A large part of the design costs seems due to ignoring that errors are the more expensive, the later you catch them. I could not help remembering that for certain types of artefacts such an experimental design strategy is fundamentally inadequate, e.g. a mathematical proof. You can only get a proof right by not making a mistake, and discrete designs share that property. The VLSI community as a whole does not seem to

EWD802 - 7

have learned that lesson yet.

On Saturday afternoon, Brian took me to a waterfowl park nearby, on Sunday I helped his daughter with her mathematics homework before I was off to Glasgow, where I arrived at 18:00 for a visit to the Department of Computer Science of the University. Dinner and part of the evening were pleasantly spent in the company of my host, Dr. J. Cavouras. The next morning was spent at the department, that afternoon, from 14:15 until 16:30, I gave a (new) talk on the presentation of programs for an audience of about 100 people. Immediately afterwards I left for Edinburgh, where I would spend a similar day at Heriot-Watt University. My host, Dr. H. Davis, was again most pleasant; I gave the same talk (be it compressed: from 14:30 until 15:45) for about 75 people. Air UK was on time, and at 23:00 that evening I was home again.

I found the two departments very different. Glasgow was not much more than a teaching establishment; it may amount to something in numerical analysis - Prof. D. Gilles was away, examining in St. Andrews - computing science seemed to have been replaced by the art of living with an ICL system. From incompatible character sets the discussion drifted to the question which campus facilities charged VAT

EWD802 - 8

(= Value Added Tax) for their refreshments. At Heriot-Watt, however, the range of scientific topics raised by my hosts seemed unbounded (the structure of termination proofs in connection with transfinite induction, Polya, early work of Hoare, and a few new monographs - including one which, by now, should be available in the U.S.A. but has not reached Europe yet -; the preceding enumeration is far from exhaustive).

The delivery of my own lecture, however, pleased me more in Glasgow than in Edinburgh. Perhaps my second audience was more demanding; perhaps I suffered in Edinburgh from lack of time (I had prepared the blackboard, which could have been a mistake). Perhaps it was because my preceding night in the Edinburgh Facility Club had been sleepless. At breakfast I heard that one of the young women serving at the Faculty Club had fallen under a train that night.

In Eindhover, Femke and Ria (my wife) were at the station; Femke drove.

Plataanstraat 5
The Netherlands
15 September 1981
prof.dr.Edsger W. Dijkstra
Burroughs Research Fellow

Transcribed by Mikhail Esteves

Last revised on Tue, 14 Oct 2003.