Hoare studied Classics and Philosophy in college. This did expose h...
**Shellsort** could be understood as a variation on **insertion sor...
Nowadays most high-level languages implement bounds checking (aka i...
“Although my method was very difficult to explain, he finally a...
ALGOL 60 (short for **ALGO**rithmic **L**anguage 1960) was a prog...
Hoare intruducing *Quicksort* in Communications of the ACM (July 19...
The bug that (at least in part) caused the Mariner 1 probe to fail ...
Again, a pretty astute insight by Hoare. GO TO statements were st...
Invention of the case statement!
What are 'code or data overlays'? Are these patches that do not ov...
> I believe our customers were fortunate that hardware limitat...
> A lack of clarity in specification is one of the surest signs of...
Here is [the link to the paper](https://www.cs.cmu.edu/~crary/819-f...
Is there a source of the flow diagram that Tony used here?
Christopher Strachey (and R. E. Milne) would later refine this appr...
One of the most memorable quotes from this paper.
I think it was Tony Hoare who said, of the Algol 60 Report, “it was...
This is a reference to *"The Emperor's New Clothes”* a short tale w...
The 1980 ACM Turing Award Lecture
Delivered at ACM '80, Nashville, Tennessee, October 27, 1980
The 1980 ACM Turing Award was presented to Charles Antony Richard Hoare,
Professor of Computation at the University of Oxford, England, by Walter Carlson,
Chairman of the Awards committee, at the ACM Annual Conference in Nashville,
Tennessee, October 27, 1980.
Professor Hoare was selected by the General Technical Achievement Award
Committee for his fundamental contributions to the definition and design of program-
ming languages. His work is characterized by an unusual combination of insight,
originality, elegance, and impact. He is best known for his work on axiomatic
definitions of programming languages through the use of techniques popularly
referred to as axiomatic semantics. He developed ingenious algorithms such as
Quicksort and was responsible for inventing and promulgating advanced data struc-
turing techniques in scientific programming languages. He has also made important
contributions to operating systems through the study of monitors. His most recent
work is on communicating sequential processes.
C.A.R. I-Ioare Prior to his appointment to the University of Oxford in 1977, Professor Hoare was
Professor of Computer Science at The Queen's University in Belfast, Ireland from
1968 to 1977 and was a Visiting Professor at Stanford University in 1973. From 1960
to 1968 he held a number of positions with Elliot Brothers, Ltd., England.
Professor Hoare has published extensively and is on the editorial boards of a number of the world's foremost
computer science journals. In 1973 he received the ACM Programming Systems and Languages Paper Award.
Professor Hoare became a Distinguished Fellow of the British Computer Society in 1978 and was awarded the degree
of Doctor of Science Honoris Causa by the University of Southern California in 1979.
The Turing Award is the Association for Computing Machinery's highest award for technical contributions to the
computing community. It is presented each year in commemoration of Dr. A. M. Turing, an English mathematician
who made many important contributions to the computing sciences.
The Emperor's Old Clothes
Charles Antony Richard Hoare
Oxford University, England
The author recounts his experiences in the implemen-
tation, design, and standardization of computer program-
ruing languages, and issues a warning for the future.
Key Words and Phrases: programming languages,
history of programming languages, lessons for the future
CR Categories: 1.2, 2.11, 4.2
Permission to copy without fee all or part of this material is
granted provided that the copies are not made or distributed for
direct
publication and its date appear, and notice is given that copying is by
permission of the Association for Computing Machinery. To copy
otherwise, or to republish, requires a fee and/or specific permission.
Author's
Oxford OX2 6PE, England.
75
My first and most pleasant duty in this lecture is to
express my profound gratitude to the Association for
Computing Machinery for the great honor which they
have bestowed on me and for this opportunity to address
you on a topic of my choice. What a difficult choice it is!
My scientific achievements, so amply recognized by this
award, have already been amply described in the scien-
tific literature. Instead of repeating the abstruse techni-
myself, my personal experiences, my hopes and fears,
my modest successes, and my rather less modest failures.
I have learned more from my failures than can ever be
revealed in the cold print of a scientific article and now
I would like you to learn from them, too. Besides, failures
Communications February 1981
of Volume 24
the ACM Number 2
are much more fun to hear about afterwards; they are
not so funny at the time.
I start my story in August 1960, when I became a
programmer with a small computer manufacturer, a
division of Elliott Brothers (London) Ltd., where in the
next eight years I was to receive my primary education
in computer science. My first task was to implement for
the new Elliot 803 computer, a library subroutine for a
new fast method of internal sorting just invented by
Shell. I greatly enjoyed the challenge of maximizing
efficiency in the simple decimal-addressed machine code
of those days. My boss and tutor, Pat Shackleton, was
very pleased with my completed program. I then said
timidly that I thought I had invented a sorting method
that would usually run faster than SHELLSORX, without
taking much extra store. He bet me sixpence that I had
not. Although my method was very difficult to explain,
he finally agreed that I had won my bet.
I wrote several other tightly coded library subroutines
but after six months I was given a much more important
gramming language for the company's next computer,
the Elliott 503, which was to have the same instruction
code as the existing 803 but run sixty times faster. In
spite of my education in classical languages, this was a
task for which I was even less qualified than those who
undertake it today. By great good fortune there came
into my hands a copy of the Report on the International
Algorithmic Language ALGOL 60. Of course, this lang-
uage was obviously too complicated for our customers.
How could they ever understand all those begins and
ends when even our salesmen couldn't?
Around Easter 1961, a course on ALGOL 60 was
offered in Brighton, England, with Peter Naur, Edsger
W. Dijkstra, and Peter Landin as tutors. I attended this
course with my colleague in the language project, Jill
Pym, our divisional Technical Manager, Roger Cook,
and our Sales Manager, Paul King. It was there that I
first learned about recursive procedures and saw how to
program the sorting method which I had earlier found
such difficulty in explaining. It was there that I wrote
the procedure, immodestly named QUICKSORX, on which
my career as a computer scientist is founded. Due credit
must be paid to the genius of the designers of ALGOL 60
who included recursion in their language and enabled
me to describe my invention so elegantly to the world. I
have regarded it as the highest goal of programming
language design to enable good ideas to be elegantly
expressed.
After the ALGOL course in Brighton, Roger Cook was
driving me and my colleagues back to London when he
why don't we just implement ALGOL 60?" We all instantly
agreed--in retrospect, a very lucky decision for me. But
we knew we did not have the skill or experience at that
time to implement the whole language, so I was com-
missioned to design a modest subset. In that design I
adopted certain basic principles which I believe to be as
valid today as they were then.
(1) The first principle was security: The principle that
every syntactically incorrect program should be rejected
by the compiler and that every syntactically correct
program should give a result or an error message that
was predictable and comprehensible in terms of the
source language program itself. Thus no core dumps
should ever be necessary. It was logically impossible for
any source language program to cause the computer to
run wild, either at compile time or at run time. A
consequence of this principle is that every occurrence of
every subscript of every subscripted variable was on
every occasion checked at run time against both the
upper and the lower declared bounds of the array. Many
years later we asked our customers whether they wished
us to provide an option to switch off these checks in the
interests of efficiency on production runs. Unanimously,
they urged us not to--they already knew how frequently
subscript errors occur on production runs where failure
to detect them could be disastrous. I note with fear and
horror that even in 1980, language designers and users
have not learned this lesson. In any respectable branch
of engineering, failure to observe such elementary pre-
cautions would have long been against the law.
(2) The second principle in the design of the imple-
mentation was brevity of the object code produced by the
compiler and compactness of run time working data. There
was a clear reason for this: The size of main storage on
any computer is limited and its extension involves delay
and expense. A program exceeding the limit, even by
one word, is impossible to run, especially since many of
our customers did not intend to purchase backing stores.
This principle of compactness of object code is even
more valid today, when processors are trivially cheap in
comparison with the amounts of main store they can
address, and backing stores are comparatively even more
expensive and slower by many orders of magnitude. If
as a result of care taken in implementation the available
hardware remains more powerful than may seem nec-
essary for a particular application, the applications pro-
grammer can nearly always take advantage of the extra
capacity to increase the quality of his program, its sim-
plicity, its ruggedness, and its reliability.
(3) The third principle of our design was that the entry
and exit conventions for procedures and functions should
be as compact and efficient as for tightly coded machine-
code subroutines. I reasoned that procedures are one of
the most powerful features of a high level language, in
that they both simplify the programming task and
shorten the object code. Thus there must be no impedi-
ment to their frequent use.
(4) The fourth principle was that the compiler should
use only a single pass. The compiler was structured as a
collection of mutually recursive procedures, each capable
76
Communications February 1981
of Volume 24
the ACM Number 2