Shall we play a game?
0,0
рейтинг
11 января в 14:37

Разработка → Сэр Чарльз Энтони Ричард Хоар или просто батя Quicksort, NULL и проблемы обедающих философов



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

QuickSort


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

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


Логика Хоара



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

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


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

Формальный язык для описания моделей взаимодействия в параллельных системах. Относится к математическим теориям параллелизма, известных как исчисление процессов (или алгебра процессов), основанных на передаче сообщений по каналам. Оказал влияние на разработку языка Оккам, 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»




С днем рождения!
Алексей @hackerquest
карма
17,0
рейтинг 0,0
Shall we play a game?
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (7)

  • +1
    Мне кажется, что в те далекие годы избежать изобретения null reference было невозможно, уж слишком простая и эффективая штука. А вот то, что вовремя не нашлось своего Дейкстры, который бы растоптал эту концепцию, уже обидно.
    • 0
      А можно подробнее в чем минус null reference и что предлагается взамен? Допустим есть целое число, например возраст в анкете и если пользователь не ввел — почему не можем оставить там null? Не выкидывать же остальные значения формы если пользователь захочет ее позже заполнить.
  • –1
    Не понимаю формулировку «изобретение null reference».
    Переменная, называемая ссылкой — это, в аппаратном виде, область памяти, хранящая число.
    Странно, что сэр Хоар приписывает себе изобретение записи в память значения 0.
    Я, пожалуй, припишу себе изобретение записи в память значения -1…
    Торопитесь, товарищи, изобретатели, количество чисел ограничено битностью!!!
    • 0
      en.wikipedia.org/wiki/Tony_Hoare#Apologies_and_retractions — там есть контекст
      • 0
        Да, контекст ясен. Если строго, то утверждение «It was the invention of the null reference in 1965» не верно, вне зависимости от контекста. Чтобы что-либо назвать изобретением, это должно обладать признаком технической новизны.
        По вопросу использования null reference в Алгол-е, как мне кажется, подобным образом драматизировать не стоит. Стоит побороться не с null reference, а с его неквалифицированным использованием и плохим тестированием продукта. Иначе по логике нужно отменять ножи, токарные станки, и много других инструментов.
        Возможный вариант решения — условно блокировать потенциально опасные инструменты, как это сделано в некоторых других языках.

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