Рыцарь в образовании и компьютерных науках, мужик, в честь которого назвали логику, первый, кто признался в своей ошибке на миллиард долларов, разработчик qsort, празднует сегодня, 11 января, свое 82-летие. (Наверняка вместе с Кнутом.)

QuickSort

Побеседовав с Колмогоровым за флягой чая в МГУ в 1960, Хоар разработал один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(n \log n) обменов при упорядочении n элементов. Подробнее на Википедии.

Если кому влом читать, то вот объяснение танцем:

Логика Хоара

Формальная система с набором логических правил, предназначенных для доказательства корректности компьютерных программ. Была предложена в 1969 году английским учёным в области информатики и математической логики Хоаром, позже развита самим Хоаром и другими исследователями.Первоначальная идея была предложена в работе Флойда, который опубликовал похожую систему в применении к блок-схемам. (Подробнее на Википедии.)

Взаимодействующие последовательные процессы (англ. communicating sequential processes, CSP)

Это транспьютер

Формальный язык для описания моделей взаимодействия в параллельных системах. Относится к математическим теориям параллелизма, известных как исчисление процессов (или алгебра процессов), основанных на передаче сообщений по каналам. Оказал влияние на разработку языка Оккам, Limbo, Go.

Теория CSP была впервые описана в статье Чарльза Э. Хоара в 1978 году. Эта первоначальная версия была неудачной, так как не представляла неограниченный индетерминизм[en]. Впоследствии под влиянием идей, заимствованных из модели Акторов Карла Хьюитта, теория была значительно изменена. (В современных CSP Хоара от 1985 года используется неограниченный индетерминизм). C тех пор значительно развита. На практике CSP применялась в качестве инструмента формальной спецификации систем с параллелизмом (concurrency), таких как, например, транспьютера T9000 или безопасной системы электронной коммерции. Теория CSP до сих пор является предметом активных исследований в плане расширения практической применимости, в частности, увеличения размеров анализируемых систем. (Подробнее на Википедии.)

Проблема обедающих философов

Проблема была сформулирована в 1965 году Эдсгером Дейкстрой как экзаменационное упражнение для студентов. В качестве примера был взят конкурирующий доступ к ленточному накопителю. Вскоре проблема была сформулирована Ричардом Хоаром в том виде, в каком она известна сегодня

Пять безмолвных философов сидят вокруг круглого стола, перед каждым философом стоит тарелка спагетти. Вилки лежат на столе между каждой парой ближайших философов.

Каждый философ может либо есть, либо размышлять. Приём пищи не ограничен количеством оставшихся спагетти — подразумевается бесконечный запас. Тем не менее, философ может есть только тогда, когда держит две вилки — взятую справа и слева (альтернативная формулировка проблемы подразумевает миски с рисом и палочки для еды вместо тарелок со спагетти и вилок).

Каждый философ может взять ближайшую вилку (если она доступна), или положить — если он уже держит её. Взятие каждой вилки и возвращение её на стол являются раздельными действиями, которые должны выполняться одно за другим.

Суть проблемы заключается в том, чтобы разработать модель поведения (параллельный алгоритм), при котором ни один из философов не будет голодать, то есть будет вечно чередовать приём пищи и размышления. (Подробнее на Википедии.)

Ошибка на миллиард

В 2009 году на конференции QCon Хоар принес извинение:

«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 couldn't 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, a 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.»

Пруф видео тут.

Видеолекция «Could computers understand their own programs»

С днем рождения!