ing sheets, and then they were submitted to a computer maybe the following
day. It would take a long time, if there
were any faults in the program, to find
out where they were.
how did you come to live in Russia?
I did national service, which was compulsory in those days, in the Royal Navy
studying modern military Russian. I
used to know the names of all the parts
of a ship in Russian, even if I didn’t
know what the actual parts of the ship
were. Later I continued my graduate
career as a visiting student at Moscow
State University for a year.
The 1960s were very exciting times
in Russia, especially after the U.S. spy
plane was shot down. I felt quite free,
and no political problems obtruded.
But our Russian friends were very suspicious of each other. We learned quite
early on that you never introduce one
Russian friend to another, because
each of them thinks the other one is
the informer. We knew that our rooms
were bugged, so we would never talk
about Russian friends inside our own
You developed the famous
Quicksort algorithm at
about this time. Why?
The National Physical Laboratory was
starting a project for the automatic
translation of Russian into English,
and they offered me a job. I met several of the people in Moscow who were
working on machine translation, and
I wrote my first published article, in
Russian, in a journal called Machine
In those days the dictionary in
which you had to look up in order to
translate from Russian to English was
stored on a long magnetic tape in alphabetical order. Therefore it paid to
sort the words of the sentence into
the same alphabetical order before
consulting the dictionary, so that you
could look up all the words in the sentence on a single pass of the magnetic
I thought with my knowledge of
Mercury Autocode, I’ll be able to
think up how I would conduct this
preliminary sort. After a few moments
I thought of the obvious algorithm,
which is now called bubble sort, and
rejected that because it was obviously
i think Quicksort
is the only really
that i’ve ever
rather slow. I thought of Quicksort as
the second thing. It didn’t occur to me
that this was anything very difficult. It
was all an interesting exercise in programming. I think Quicksort is the
only really interesting algorithm that
I ever developed.
Where did you work after
returning to england?
I met my future employers in Russia. I
was an interpreter at an exhibition in
Moscow, where Elliott Brothers, which
at that time made small scientific
computers, were exhibiting and selling their computer in Moscow. They
offered me employment when I came
back, with an additional 100 pounds a
year on my salary because I knew Russian. I never had a formal interview.
What did you work on at elliott?
They were embarking on the design of
a new and very much faster computer,
and they thought they would celebrate
by inventing a new language to program it in. As a recent employee, with
six months experience, I was put to
designing the language. Fortunately I
happened to see a copy of the Report on
the Algorithmic Language Algol 60, and
I was able to recommend to the company to implement that, rather than
inventing a language of their own.
That proved a very good commercial
decision. And a good personal one,
because I eventually married Jill, the
other programmer who came to work
on the same project. She had experience writing a compiler before, which
in those days was quite unusual, and
she was a much better-disciplined programmer than I ever was.
Was algol well defined?
The syntax was formally defined. The
grammar of the language was written
up in a way that was, I think, completely unambiguous. The semantics was
a little less formally defined. It used
ordinary English to describe what the
effect of executing a program would
be. But it was very well written by Peter Naur, and it was sufficient to enable us to write a compiler without
ever consulting the original designers
of the language. And it was sufficient
for programmers in the language to
write programs, which in the end actually ran on our compiler, without ever
consulting us or the original designers of the language. It was a really very
remarkable achievement—rather beyond what maybe we can achieve these
days in the design of languages.
Did you collaborate with
other compiler writers?
We didn’t correspond with other people writing compilers, even for Algol,
in those days. We didn’t know each
other. There was no real scientific
community that one could join to talk
over problems with other people who
encountered the same problems. We
worked pretty well on our own.
after moving to Queen’s
university in Belfast in 1968, you
wrote a very important paper
on the axiomatic approach to
computer programming, now
known as “hoare Logic.”
I was interested, as indeed many people were at that time, in making good
the perceived deficiency of the Algol
report: that while the syntax was extremely carefully and formally defined,
the semantics was left a little vaguer.
We were pursuing the goal of trying to
get an equally good formalization of
the semantics of the language, a goal
that I think still is pretty advanced and
maybe beyond our grasp.
I put forward the view that we didn’t
want the specification to be too precise. We didn’t want the specification
of a programming language to concentrate in too much detail on the way in
which the programs were executed,
but rather we should set limits on the
uncertainty of the execution of the programs, to allow different implementations to implement the language in
different ways. In those days the word
lengths and the arithmetic of all of the