Developers Club geek daily blog

1 year, 4 months ago
Sir Charles Anthony Richard Hoare or just the father of Quicksort, NULL and problem of the having dinner philosophers

The knight in education and computer sciences, the man in honor of whom called logic the first who was recognized in the error for one billion dollars, the qsort developer, celebrates today, on January 11, the 82 anniversary. (For certain together with Cnut.)

QuickSort


image
Having had a talk with Kolmogorov behind a tea flask in MSU in 1960, Hoare developed one of the fastest known universal algorithms of sorting of arrays: on average O (n \log n) of exchanges when streamlining n of elements. In more detail on Wikipedia.

If to whom vly to read, then here an explanation dance:


Hoare logic



Formal system with a set of the logical rules intended for the proof of a correctness of computer programs. It was offered in 1969 by the English scientist in the field of information science and logic theory Hoare, it is developed by Hoare and other researchers later. The initial idea was offered in work of Floyd who published similar system in application to flowcharts. (Is more detailed on Wikipedia.)

The interacting consecutive processes (English communicating sequential processes, CSP)


image
It is the transputer

Formal language for the description of models of interaction in parallel systems. Treats mathematical theories of parallelism, known as calculation of the processes (or algebra of processes) based on transmission of messages on channels. Okkam, Limbo, Go exerted impact on development of language.

The theory of CSP was for the first time described in Charles E. Hoare's article in 1978. This initial version was unsuccessful as did not represent an unlimited indeterminism [en]. Afterwards under the influence of the ideas borrowed from model of Actors of Karl Hewitt, the theory was considerably changed. (In modern CSP of Hoare of 1985 the unlimited indeterminism is used). Since that time it is considerably developed. CSP was put as the tool of the formal specification of systems with parallelism (concurrency), such as, for example, the transputer T9000 or safe system of electronic commerce into practice. The theory of CSP still is a subject of active researches in respect of expansion of practical applicability, in particular, of increase in the sizes of the analyzed systems. (Is more detailed on Wikipedia.)

Problem of the having dinner philosophers


Sir Charles Anthony Richard Hoare or just the father of Quicksort, NULL and problem of the having dinner philosophers
The problem was formulated in 1965 by Edsger Dijkstra as examination exercise for students. As an example the competing access to the tape drive was taken. Soon the problem was formulated by Richard Hoare in that type in what it is known today

Five silent philosophers sit around a round table, each philosopher is faced by a plate of spaghetti. Forks lie on a table between each couple of the closest philosophers.

Each philosopher can or is, or to reflect. Meal is not limited by amount of the remained spaghetti — the infinite stock is meant. Nevertheless, the philosopher can eat only when holds two forks — taken on the right and at the left (the alternative formulation of a problem means bowls with rice and chopsticks instead of plates from spaghetti and forks).

Each philosopher can take the next fork (if it is available), or to put — if he already holds it. Taking of each fork and its return to a table are separate actions which have to be executed one behind another.

The essence of a problem is in developing behavior model (parallel algorithm) at which any of philosophers will not starve that is will eternally alternate meal and reflections. (Is more detailed on Wikipedia.)

Error on one billion



In 2009 at the QCon conference Hoare apologized:

"I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I could not resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years. In recent years, number of program analysers like PREfix and PREfast in Microsoft have been used to check references, and give warnings if there is a risk they may be non-null. More recent programming languages like Spec# have introduced declarations for non-null references. This is the solution, which I rejected in 1965."


Proof of video here.

Video lecture "Could computers understand their own programs"




Happy birthday!

This article is a translation of the original post at habrahabr.ru/post/274865/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: sysmagazine.com@gmail.com.

We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.
Best wishes.

comments powered by Disqus