Like many of us, Tony Hoare’s career in computing began by accident, though few of us can claim an accident as convoluted as his. Nor can most of us claim a career as distinguished. Great oaks…
It was in 1960 when I first saw an Elliott computer, the 803A, on a stand at a public exhibition of British Scientific Instruments in Moscow. How did I get to be there? That is a story which I could tell you backwards. And what happened afterwards? That is a story I could tell forwards. Both of them are very long stories. I’ll start by going backwards. Then I’ll wind the tape forwards again.
To start with, you have to know that my uncle Sandy was a Captain in the Royal Navy. (I told you it was a long story.) After he retired, he took a job as General Secretary of the British Scientific Instruments Manufacturers Association (SIMA). It was he who organised the exhibition in Moscow; he knew that I was a Russian speaker living in Moscow, and he thought of the idea of inviting me, on behalf of the Association, to act as an interpreter at the exhibition. He offered me £40 to do it, which I thought would be jolly useful when I got back to England.
My duties were indeterminate. I would translate questions and answers at the public lectures given by the exhibitors. I would do the same at an exhibition stand. When one of the exhibitors got appendicitis, and was cast into a Russian hospital with nobody capable of speaking English to him, I was able to give him a little bit of temporary comfort, I’m glad to say, and left my English- Russian Dictionary with him. For these and other services, the organisers gave me another £40 as a bonus when I returned to England.
The reason why Elliotts were at the exhibition was because of the prospect of selling their computer to a Russian customer when the exhibition was over. This was standard practice, no doubt to bypass the administrative barriers (on both sides) which hindered more normal trade across the Iron Curtain. And for the Russians it was a good deal. After a week at an exhibition, the computer became second-hand goods, and could be purchased at a generous 14% discount. Did they realise that this was exactly the amount by which Elliotts had marked up the price of the computer before bringing it to the exhibition?
How did I happen to be in Moscow at the time? I was studying as a graduate student at Moscow State University, on an exchange scheme sponsored by the British Council. I had chosen to study Probability Theory at Moscow State University, in the Department of Professor A.N.Kolmogorov, who was the distinguished founder of the subject. This was because in the previous year I had been studying for a Certificate in Statistics at the University of Oxford. In the two years before that I had learned Russian on National Service in the Royal Navy. In getting accepted by the Navy, it was helpful to have a close relative in the service, and an uncle who was a Captain would do nicely. Only the wildest vagaries of chance could explain the particular combination of circumstances that brought me to my first contact with Elliotts. The only lesson to learn from this long story is that if you want a long and successful career in computing, it helps to start with the right sort of uncle.
I have to confess that I was out of my depth in the mathematical study of probability theory at postgraduate level in Russia. So I was quite happy to be diverted from that subject by a letter that I received in Moscow from the National Physical Laboratory in Teddington. They offered me a post as a Senior Scientific Officer to work on a project just started for automatic translation from scientific Russian into English. They were writing a translation program in machine code for the Pilot ACE computer. My English companion at the University residence, Glyn Harding, was a real scientist, so I consulted him about the offer. He told me that Senior Scientific Officer was a very prestigious post, and I was very lucky to get the offer.
So I started looking into the state of the art in machine translation of languages. I looked as far as the Lenin Library in Moscow, where I first read a work by Chomsky on his context-free grammars; I didn’t understand it at the time, I’m afraid. The Russians too were interested in machine translation. In fact, they had a regular journal called Машинный Перевод — that’s Machine Translation — to which I submitted my first published scientific article. I wrote it in Russian, and I typed it up in Russian on a typewriter borrowed from a friend. It’s not very often attributed to me because my name was transliterated into Russian as “XOAP” with a ‘Ch’ at the beginning rather than an ‘H’ (which does not exist in Russian). When transliterated back into English, the name becomes “Choar” or possibly “Khoar”. So if you want to look up the article in the bibliographies, you’ll have to look under ‘C’ or ‘K’.
The first problem of machine translation that interested me was how to sort the words of each incoming Russian sentence into ascending order. Recall that the main stores of computers of those days were large enough to hold one sentence, but certainly not large enough to hold a dictionary. The dictionary was held on magnetic tape, so to look up a single Russian word would require a spin through the magnetic tape, on average covering half its length. It was clearly a better idea to spin through the tape only once for each whole sentence. This required you to sort the words in the sentence into alphabetical order before you start the tape spinning. I was thinking about this in my little room in Moscow State University, and I tried to write down my thoughts in Mercury Autocode, which I had learnt the previous year at Oxford while I was studying statistics. My first idea I rejected as too slow. It was rapidly followed by my second idea, which later when I got back to England, I wrote up as my second ever published scientific article. Since then, it has become famous under the title “Quicksort”. I believe it is still widely used for sorting.
Well, maybe that’s enough going backwards. I told you it was a long story. How about a little bit of going forwards? At the SIMA exhibition in Moscow, I spent the maximum possible time on the stand at which Elliotts was exhibiting an 803 computer. I met the Managing Director of the Elliott Computing Division, Eddie Nash. He was a very dynamic chap and he suggested two things : one was that I should go to work for him when I came back to England. I don’t know why he thought I would be suitable as an employee. My only qualifications were Russian and Latin and Greek. His second suggestion was that I should travel back in the empty van that had brought the computer to Moscow, and he would give me a lift for free. I could help negotiate in Russian with the hotels and restaurants and deal with the border formalities. And that was very nice because the British Council were happy to reimburse me with the sea fare that they would have had to pay for me to go back to England; that was another forty pounds. I would be rich! So I helped the driver Taffy Griffiths and Arthur Kennedy (production manager of the Computing Division) to take the van back to Britain.
When we had driven some 30 miles out of Moscow, the van suddenly began to slow down, and drew to an unscheduled stop. It had ceased responding to pressure on the accelerator pedal. On inspection it appeared that part of the linkage of the pedal with the carburettor had fallen off. We spent some time looking on the road behind, but in the end, we had to improvise a linkage from a bracket taken from elsewhere off the body of the vehicle. Unfortunately, it turned out that the logic of the linkage had flipped. In order to get the engine to accelerate, you had to release pressure on the pedal; and in order to stop it, you had to press down. After an hour’s driving, the tension in the ankle became intolerable, and short driving shifts were essential. I was spared, because I was not a driver in those days.
But it was possible to acclimatise to the reversal of control, and the main sufferers were pedestrians who made the attempt to step out into the road in front of the van, and were shocked by the roar with which our engine responded, when the driver’s foot moved to the brake pedal. When we reached the coast, we had no difficulty in persuading the ferry officials that we ourselves should drive the van onto the ferry, rather than handing it over, according to the rules, to the ferry drivers to park. On all subsequent trips to Moscow, the Elliott van would carry a full set of spares.
When I arrived back in England I went for an interview at the National Physical Laboratory to find out more about the job that they had offered me. I was a bit disillusioned by what I discovered about the rather primitive delay line architecture of their Pilot Ace computer. But in my studies in Moscow, I had also become disillusioned about the general prospects for machine translation of languages. The problem that worried me was the development and evolution of the dictionary, which would need to contain a very large number of very rare words and an even larger number of rare phrases. The problem would be exacerbated by the rapid evolution of specialist vocabularies of the various branches of Science, where every important discovery generates a whole new vocabulary of concepts and properties.
I got even more disillusioned when I talked with the Personnel Department of the Laboratory — Human Resources, as they would be called nowadays. They informed me that since I didn’t have a science degree I could never be a member of the permanent scientific Civil Service. However, they were willing to employ me as a temporary Civil Servant at the eminent rank of a Technical Officer, which was two or three grades lower than a Senior Scientific Officer; and I could never expect to be promoted. Apparently the Director of the Computing Division of the Laboratory was quite surprised when I declined his diminished offer. I was not surprised five years later when the translation project was closed down in failure.
Of course, I had no hesitation in accepting an offer of employment as programmer from Eddie Nash. He paid me the standard graduate programmer’s salary of those days - eight hundred pounds a year - to which he added an extra hundred pounds a year because of my knowledge of Russian. It was enough to marry on in those days, I’m glad to say. On three subsequent summers (1961, 1962 or 63, and 1964), I was sent with the latest version of the Elliott computers in a van to an exhibition in Moscow, with Taffy Griffiths as driver. On getting there, my job was to exhibit the computer and answer questions from the Russian public, and talk to important people, and eventually to sell the computer at the usual 14% discount to whoever might have been chosen by the Soviet authorities to buy it. The purchasers were from what the Russians called the ‘unnamed institutes’, because they were so secret that they had no name on their front doors.
They were among our best customers. They never complained. In fact, they were so secretive that they never even wrote to us, or told us their address. But in the following years, they watched for whenever we were coming to Moscow for an exhibition, and they would send a small group of experts to talk to our technical people - because in those days every computer needed technical maintenance staff to look after it, if you remember. And at the exhibition stand they described their problems. For example, a particular power transistor kept blowing, or their paper tape punches kept getting blunt. That was easy, the transistor had been replaced by one with a higher rating, and if you want to keep your paper tape punches sharp you should use oiled tape. “Oh ! Where do you get that ? We can’t get that over here.” “Well just write to us and we’ll send you a supply.” Finally they admitted “We can’t write to you. Anyway, you couldn’t send it back.” The only solution was to bring the necessary supplies to the next exhibition, and hand them over in person!
This piece is becoming rather like Lawrence Sterne’s novel Tristram Shandy, a book of 500 pages, published in eight volumes. And towards the middle of volume four Tristram writes : “I have got no further than to my first day’s life”. So far, I’ve dealt with my conception, perhaps even my gestation, and now it is time to proceed to the birth of my computing career in 1960, when I actually started working for Elliotts. I was put under the tutelage of Pat Shackleton, who gave me a little programming puzzle - I’ve forgotten what it was. After a while I came and showed him a solution, a program in Elliott machine code. He looked through it and said “I had no idea you were as good as this! Here’s another problem for you. Write a sorting program, based on a new fast method of sorting which has just recently been invented by Shell.’ It was later called ‘Shellsort’. The method was rather complicated in concept and intricate in detail. In fact, at the time there was no way of calculating how fast it would be.
It was quite a challenging programming job, given all sorts of boundary cases. I really enjoyed the effort of optimising the inner loops. As my new colleague Cedric Dennis said, programming is like solving crossword puzzles, and being paid for it! When I showed the code to Pat, he was again quite appreciative, and the program was published in the 803 library. Rather timidly I said “I think I know a faster way of sorting”, and Pat said “I bet you sixpence you don’t”. So I described to him the method of Quicksort; he thought about it, and after a while he actually programmed it himself for the old 405 computer. It compared favourably with Pat’s own previous sorting program for that machine, because it made more efficient use of the main store held on a drum. I’m not quite sure whether he actually gave me my sixpence or not.
A wonderful bonus of our employment at Elliotts was the friendship that was forged among the programmers and with other staff. Paul King, Bob Brazier, Sheila Quinn, Roger Cook, David Smart and Cedric Dennis were among those who used to meet socially and convivially to play the game of Diplomacy in the (late) evenings. Many of us and our wives still meet occasionally for lunch.
After the sorting routine, my next job was writing magnetic tape device routines for Elliotts’ 35mm magnetic tape drives (the same width as film-stock for the neighbouring Elstree Studios). I thought I knew all about computer tapes, because while I was still an undergraduate reading philosophy at Oxford in the 1950’s, my tutor John Lucas set me the task of reading a famous paper in Mind by Alan Turing on the undecidability problem. His answer was based on the design of a hypothetical computer now known as the Turing Machine. Turing Machines have tapes, so I thought I already knew the relevant theory for computer tapes. But when I looked at the physical characteristics of the tapes that Elliotts were making at that time, I decided that perhaps the gap between theory and practice was too wide for me to bridge. So I wrote the tape routines simply to give random access for reading or writing to the individual words on the tape. A simple idea but very slow to run. To economise on space occupied by the code, my program was terribly complicated, and I suspect that nobody ever understood it afterwards. You could look up my code and its user instructions in the old 803 Library; I have seen it in the old loose-leaf binders that we used to publish our programs in. There was a copy that I saw in the National Museum of Computing at Bletchley Park.
My next task, with all of nine months experience of writing machine code programs, was to design a new programming language. I must have been an expert at that, with all my knowledge of Latin and Greek, don’t you think? Fortunately, in the library of the Computing Division at Borehamwood, I found a copy of a slim 25-page duplicated A5 booklet called “Report on the International Algorithmic Language — Algol 60” written (nominally just edited) by Peter Naur. I looked through that. There were a lot of novel ideas, which I followed with great interest. But some of the features of the language seemed a little bit complicated for our customers and salesmen to understand. Actually, I can now confess, I didn’t quite understand them myself.
So I thought I would design something a little simpler than Algol, and produced a series of draft designs, which were rapidly and happily consigned to oblivion. In the spring of 1961, there was announced a week-long school in Brighton on Algol 60, with teachers Peter Landin, Peter Naur and Edsger Dijkstra. A group of students from Elliotts registered for it, including Paul King, Jill Pym (as she then was), Roger Cook and me.
On the first afternoon of the course, instead of doing the set exercise on the course, I thought it would be interesting if I could program Quicksort in Algol 60. I would try to exploit a surprising feature of its procedures. As it said in the Report, “any other mention of the procedure name, within the procedure body, is a call to the procedure itself”. That is how the Algol 60 report explained recursion. And somehow or other I must have understood it, because I used this recursion very effectively to program my Quicksort method. I had earlier given up my attempt to program it in Mercury Autocode, because the administration of the tasks was too complicated. In Algol 60 all the administration was done behind the scenes by a stack that implemented the recursion. Rather timidly, I went up to the front of the class to show the result of my little exercise to Peter Landin. He looked at it, hmmmm, with increasing wonderment and puzzlement, and finally said: “Peter, come over here! Look at this!” So Peter Naur looked at it, and was appreciative; and that was an encouragement to write up the work for publication in 1962 in the Computer Journal, as my third scientific publication. It made an excellent foundation for my subsequent academic career.
The most important result of our attendance at the School was that coming back home in the car, with Roger Cook driving, we were discussing what we had just learned, and somebody said: “Why don’t we give up our new language and just do Algol 60?” And everybody in the car agreed that would be a good idea. “Can you do it, Tony?” was the next question. I undertook to see if I could work out a way of implementing the language on our 803 architecture. In those days we used to read respectable scientific journals in order to discover how to do things. There was an issue of the Communications of the A.C.M. in January 1961, with a famous picture of the tower of Babel on the front. It was devoted to problems arising in the implementation of Algol 60. It included articles by Cheatham, Perlis, Floyd, Barton and Irons, and an article by Peter Ingerman on thunks. The last of these described what became the standard method of implementing name parameters of procedures in Algol.
On the basis of these articles, I attempted to design the implementation of a cut-down version of Algol 60. It could not be quite the full language, for one good reason. The standard method of implementing the stack for recursion in Algol was to use index registers (B-lines) to point to the workspace of each procedure call. Most of the machines for which Algol 60 was invented and implemented had the option of address modification (indexing) every instruction. The 803 did not. To invoke address modification took two instructions, which would have doubled the length of every program, and halved its speed.
So we used the alternative technique of holding procedure workspace in fixed locations of the computer store, and ‘pushing down’ their content onto a stack whenever we detected that a procedure was being called recursively. And this meant that we couldn’t do procedure parameters. Fortunately, the technique of thunks could be used by programmers to achieve much of the same effect as procedure parameters.
There were lots of other features in the language that I didn’t know how to implement and therefore left out of my original plans. Gradually, over the months that followed, I thought of ways of implementing nearly all of them, so in the end we had a fairly full language implemented.
I was put in charge of the implementation team. The other constant members of the team were Jeff Hillmore and Jill Hoare (as she soon became). I wrote the very first module of the compiler, the lexical analysis routine, and a bit of the run time routines. I also designed the recursive structure of the whole translator, and described it in a sort of ALGOL-like notation. The rest of the team did all the real work. After a while I sort of realised that they were nearly finished. (Remember, in those days we didn’t have deadlines or timescales. We just did what we wanted, and every now and then we produced something useful).
So I wrote a note to the Manager of the Computing Division, saying that I thought that in three to six months time our implementation would be ready for distribution to our customers. At that time, there was concern over imminent loss of a sale. The customer was thinking of cancelling the sale and buying some IBM computer instead. But when the customer heard about this new Algol compiler, he was so impressed that he confirmed the sale, and shortly afterwards we actually delivered the computer. And the Algol compiler continued as a basis of the commercial success of the 803, especially in the academic market. Of course, at Elliotts our team were the heroes of the moment.
I wondered whether this what Eddie Nash meant when he told me, early on in my career at Elliotts, “I think the best thing I ever did for Elliotts was to recruit you.” Of course, I couldn’t believe that; but if I had saved a sale worth £25,000, perhaps it was true. In the end, over 200 803’s were sold worldwide, a large total for those days, and one factor in the success was the Algol compiler.
I’m afraid that what I did next was not so advantageous to Elliotts. I designed and attempted to manage the implementation of the Elliott 503 Mark 2 Programming system. Its failure marked the end of the commercial life of the 503. So the balance of benefit to Elliotts may not be quite as favourable as Eddie expected. But I have no doubt that joining Elliotts was the best thing that I could have done for myself, preparing me well for my subsequent career as an academic computer scientist.