C.A.R. Hoare

Charles Antony Richard Hoare (Colombo, Sri Lanka, January 11, 1934), also known colloquially as Tony Hoare, is a British computer scientist.

Best known for the invention, in 1960, of Quicksort, which is the most widely used sorting algorithm in the world. He is also known for the development of Hoare's Logic, and for the formal language CSP (third most cited work in computing according to Citeseer statistics), used to specify interactions between concurrent processes that serve as the basis for the definition of the occam programming language

In 1956 he obtained a Bachelor's Degree (equivalent to a four-year degree without a master's or doctorate) in Classical Culture and Philosophy at the University of Oxford.

He was amazed at the power of mathematical logic to explain the apparent truth of mathematical theorems. He served in the British Royal Navy (1956-1958) where he studied Russian and later graduated from Moscow State University to study Probability Theory and do translations from human to machine language.

Trying to make it easier to look up words in the dictionary, he discovered the famous "Quicksort" algorithm. The function of this algorithm is to order a list of elements of the same type and it is based on the "divide and conquer" technique, so it turns a complicated problem into many simple ones, but it is also the fastest known to do this task. In fact it is, according to algorithm complexity analysis theories, the fastest possible. It is mathematically proven that you cannot make a sorting algorithm faster than Quicksort. ^{[citation needed]}

In 1960 he returned to England, where he worked as a programmer for Elliott Brothers, a small computer factory. There he led a team of people who designed the first commercial compiler for the "Algol 60" programming language.

After achieving the rank of chief engineer, he coordinated a much larger team to implement an operating system that turned out to be disastrous. Shortly thereafter he entered a hardware and software architecture company that he had to leave when it merged with his competition.

In 1968 he got an opportunity to work as a Professor of Computer Science at Queen's University in Belfast. The goal of his research was to understand why operating systems were so much more complicated than compilers, and to see if advances in programming theory could help solve computer concurrency problems.

He was always aware that it would be a very long research period and that it would be difficult for him to find industrial applications for his advances.

In 1977 he moved to Oxford University, and was committed to building a Programming Research Group, founded by Christopher Strachey.

During more than thirty years as an academic, Tony has always had important contacts with industry through consultations, research collaborations, etc.

When he reached retirement age for Oxford research, he eagerly accepted the opportunity to return to industry as a senior researcher for Microsoft in Cambridge, where he continues to work today.

Among his many recognitions, he is an honorary doctorate from several universities, such as the University of Warsaw, the University of Bath, and the Complutense University of Madrid.

Apologies and retractions

Speaking at a conference in 2009, Hoare apologized for inventing the null reference:

I call it my $1 billion mistake. It was the invention of the null reference in 1965. At that time, I was designing the first system of integral types for references in object-oriented language (ALGOL W). My goal was to ensure that all use of references was absolutely safe, with checks automatically made by the compiler. But I couldn't resist the temptation to put in a null reference simply because it was so easy to implement. This has led to countless errors, vulnerabilities and system failures, which has probably caused a billion dollars of pain and damage over the past forty years.

For many years, under his direction, his department at Oxford worked on formal specification languages such as CSP and Z. These systems did not achieve the expected adoption by the industry, and in 1995 Hoare had to reflect on the original assumptions:

Ten years ago, researchers in formal methods (and I was the most confused among them) predicted that the world of programming would adopt gratefully all the aids promised for formalization to solve the problems of reliability that arise when the programs become larger and their safety is more critical. The programs have now become very large and very critical - far beyond the scale that can be comfortably addressed by formal methods. There were many problems and failures, but these have almost always been attributable to inadequate analysis of requirements or inadequate management control. It has been proved that the world simply does not suffer significantly from the kind of problems that our research was originally intended to resolve.