A Classical Mind: Microsoft Researcher Receives Kyoto Prize

CAMBRIDGE, England, Nov. 6, 2000 — It’s been 50 years since Sir Anthony Hoare studied Latin and Greek as a schoolboy, but he still remembers the difficulty of mastering each tongue’s complicated grammar rules. As hard as he tried, he couldn’t avoid silly flubs — ones so obvious that his teachers labeled them

MSR Cambridge researcher Tony Hoare and his wife Jill stand outside Buckingham Palace, holding the medal he received when he was knighted by Queen Elizabeth II.

The memory has stuck with Hoare, a member of the Microsoft Research (MSR) Cambridge lab, throughout his long career as a computer scientist. While it may not haunt him every day, it reminds him to look for ways to make computer languages and programming less complicated to achieve the precision, or

Over the past four decades, Hoare’s passion for precision and insights into how it may be achieved have served as beacons for the rest of the research community, leading to advances in the design of modern computer languages, increased software reliability and simplified computing with multiple computers.

Hoare, 66, will be recognized for his
“pioneering and fundamental contributions to software science”
when he receives the Kyoto Prize in Advanced Technology later this week in Japan. Awarded annually by the Inamori Foundation, the Kyoto Prize is likened to the Nobel Prize and is one of the world’s highest awards for a computer scientist. Winners are selected on the recommendation of their peers, and must have made a significant contribution to the scientific, cultural or spiritual betterment of society.

The prize comes on the heels of another honor: Britain’s Queen Elizabeth II knighted Hoare earlier this year, making him only the second computer scientist so honored.

The honors not only reflect the importance of Hoare’s work. They also indicate his standing among fellow scientists — something he is drawing upon to contribute in a new way during the latest stage of his career. Self-described as one of computer science’s
“elder statesmen,”
Hoare is helping to guide the work of other researchers — at Microsoft and elsewhere — and attempting to build bridges among disparate groups and movements within the research community.

“Only someone comfortable in different areas of research in computer science could take on such a task,”
said Professor Jayadev Misra, Regent’s chair of the University of Texas at Austin’s Computer Sciences Department.
“There may not be anyone better suited to the task than Tony Hoare.”

Catching the Wave

For someone who has achieved so much, Hoare went into computing with modest expectations. In fact, he thought he had reached a dead end when he got his first job as a computer programmer in 1960 with Elliott Brothers Ltd., a British computer-manufacturing firm. Both of his immediate superiors were only a few years older than Hoare himself.

“I figured I had missed the big wave of expansion in computers,”
he recalled recently during an interview in his office at MSR Cambridge.
“Of course, I was wrong. Computers have been on the rising edge of a technological wave continuously for 40 years.”

It’s one of the few times Hoare’s instincts have been wrong. He made his first contribution to computer science before he even became a professional programmer. After studying languages and philosophy at Oxford University, Hoare developed Quicksort, the first rapid, space-efficient algorithm for sorting sequences of numbers and words in the memory of a computer.

Still in his 20s at the time, Hoare was completing a postgraduate year at Russia’s Moscow State University. He was seeking a way to simplify machine translation of spoken languages. For efficient use of a dictionary, it was necessary to sort words of a sentence alphabetically before translating them. He came up with a simple, high-speed technique that remains at the heart of the most extensively used sorting algorithms to this day.

Longtime colleague Edsger W. Dijkstra, another of the pioneers of modern computer programming, describes Quicksort as a
“lovely algorithm…It is the thing that has become an exemplar for a wide class of designs. It alone was enough to make a man famous.”

Hoare’s Logic

But Dijkstra and other researchers agree Quicksort isn’t Hoare’s greatest achievement. That came in the late 1960s, when the first large-capacity computers kept breaking down, largely because of faults within the software.

Hoare’s solution to the so-called
“software crisis”
drew from his love of mathematics. He proposed that much like mathematical equations, programming languages should be defined and analyzed by the axioms, or accepted principles, and reasoning methods used to create correct programs.

What became known as Hoare’s Logic allowed programmers to convert programs into provable, logical formulas. At the time, the accepted method of testing a program was to review its final results. This provides little insight into the nature of a program’s faults, only showing that a problem exists, explained Misra, a contributor to
“A Classical Mind,”
a 1994 collection of essays about Hoare’s work.

“He saw the importance of proving programs correct at a time when many people didn’t realize the need for it,”
Misra said.

Dijkstra, who now calls Hoare’s proposal
“extremely courageous,”
was initially
by his colleague’s proposal.
“I rejected it as a meaningless ballet of symbols,”
he said.
“But as it worked out, a few years later I became an experienced choreographer of such ballets of symbols.”

Though still not universally applied, Hoare’s approach has become increasingly important in an era when computer programs control many vital services.

“Testing gives us some confidence, but we can never be assured the program will operate the same as in the test,”
Misra said.
“If you are going to rely on computer programs to run much of the space program, nuclear reactors and airplane traffic, we’re better off if we know a piece of software is faithful to its intent.”

Parallel Processing

Only a few years later, the challenges facing computing had evolved. The development of the microprocessor allowed multiple computers to work collaboratively and solve larger problems faster. The only concern: how to prevent these computers from tripping each other up while
“parallel processing,”
or working together.

Hoare designed Communicating Sequential Processes (CSP), a parallel programming language that allowed individual computers to communicate via messages, much as they now do over the Internet. It also eliminated the need for a shared memory among the parallel computers and inspired the development of the transputer, the first complete computer on a single silicon chip.

“He was one of the first researchers to see the importance of very disciplined communications between computers,”
Misra said.

Independent Thinker

Perhaps the most intriguing aspect of Hoare’s success in computer science is his lack of formal training. Although he holds a degree in statistics, he has taken only one course in computer programming and never earned degrees in science or mathematics. He instead preferred to view math as
“a hobby…something that one actually does to solve interesting problems, rather than as a fixed body of knowledge that one just learns to reproduce in examinations,”
Hoare said.

He considers the unifying theme of his work not the improvement of computer programs or languages, but rather the search for certainty or proof within human knowledge.

“It’s been my goal to employ the care and devotion that mathematicians give to their study, to determine if some part of that can be transferred to programming to make computer programs more reliable and so much better in general,”
he said.

Dijkstra credits Hoare’s success to his
“flexible and brilliant mind,”
as well as his good fortune to have attended British public schools — which are considered by some to be the equivalent of American private schools — and universities. These institutions allowed Hoare to pursue his many, varied interests without roping him into the orthodoxy of any one field of study.
“That made him an independent thinker,”
Dijkstra said.

“There is a huge amount of information out there and researchers who have their own agendas,”
Misra said.
“But Professor Hoare has been successful at distilling problems into deep theoretical insights and seeing the problems shared among different areas of research.”

Building Bridges

It is these skills, as well as his near-mythic reputation among his colleagues, that MSR expects will help Hoare in his latest endeavor. After more than 30 years doing research and teaching in universities, Hoare returned to private industry last year with Microsoft.

He is among 50 researchers at MSR’s Cambridge lab. Like his co-workers, Hoare is free to pursue his research interests without any requirement that his work target current Microsoft products.

One of Hoare’s primary goals is to work with MSR and other researchers to see how well the advances he and others developed decades ago have filtered into practice. In particular, he wants to help define disciplines for the creation of computer code that follow the axiomatic approach he outlined in Hoare’s Logic. This would advance the evolution of longer-lived, or
code and make this code more responsive to customer needs.

Along with attending and speaking at research conferences, Hoare spends much of his time meeting informally with other researchers to discuss their work.

“If I can encourage people who are working in these difficult areas, improve their morale or, perhaps, make sure other people see the value of what they are doing, that’s a unique contribution that I can still make,”
Hoare said.

Derek McAuley, deputy director of MSR Cambridge, agrees.
“Tony brings a keen mind and a lot of experience. The number of times we see problems that have appeared before is immense. Having his experience around means you can avoid going down rat holes that researchers went down in the past.”

Also, Hoare reports software engineering problems to the academic research community in the hope that they can help find solutions. Because of his status, the issues he raises tend to attract attention throughout the research community, which is one of the goals of Microsoft’s labs.

“We hope people view Microsoft Research as an active participant in the open research community,”
McAuley said.
“If we are going to do our share of research, we want to make sure we give good access to that information.”

Getting His Due

Despite his achievements, Hoare said that his recent awards were
“completely unexpected…out of the blue.”

He and two other recipients — one in the basic sciences, the other in arts and philosophy — will receive the Kyoto prizes Friday, November 10, as part of a 10-day ceremony that includes a meeting with the Emperor of Japan. The award also includes a cash prize of $430,000 for each recipient.

Hoare’s other recent meeting with a monarch came on Jan. 1, when Queen Elizabeth II knighted him and 20 other British citizens whose achievements have left a mark on the 20 th century or will leave a mark on the 21 st .

“I hear that many young people are good at computing,”
the queen commented during their brief introduction. Nervous, Hoare replied: “Yes, some of them, ma’am.”

Now, he kicks himself, and wonders why he didn’t think of something more profound. Something like,
“Yes, and it’s a great pleasure to continue working with them.”

Yet again, Hoare is seeking precision.

Related Posts