Тони Хор – компютърен гений и създател на най-разрушителната уязвимост в историята почина на 92 години

На 5 март, на 92 годишна възраст почина Чарлз Антъни Ричард Хор – един от хората, които в буквалния смисъл помогнаха за създаването на съвременното програмиране в сегашния му вид. Дори тези, които никога не са чували пълното име на Хор, най-вероятно са се сблъсквали с идеите му директно: чрез алгоритми за сортиране, чрез начини за проверка на кода за коректност, чрез модели за паралелна работа на програми и дори чрез старата, болезнено позната грешка null.

Най-често Хор се споменава като създател на Quicksort.

Той създава алгоритъма през 1959 година. Според спомените на съвременниците му, тласъкът е бил спор с шефа му. Историята изглежда почти банална, но резултатът се оказа изключително дълголетен. Десетилетия по-късно Quicksort все още остава един от най-бързите и удобни начини за сортиране в множество практически задачи.

Идеята на Quicksort на пръв поглед е проста. Програмата избира един елемент като референтен, след което разпределя всички останали стойности в две групи: по-малки от референтни и по-големи от нея. След това същата операция се повтаря за всяка група поотделно, докато масивът не се подреди. Значението на идеята е, че Хор предложи много удачно съчетание на скорост, простота и практичност. Алгоритъмът не само изглеждаше добре на теория, но и работеше отлично на реални машини. Именно затова Quicksort беше използван при реализацията на командата sort в Unix, а след това беше включен в библиотеките на различни езици за програмиране. За студенти и преподаватели той отдавна се превърна в класически пример за това как рекурсията и добрите инженерни изчисления дават решение, което не остарява заедно с хардуера.

Приносът на Хор не се ограничава само с този алгоритъм за сортиране. В края на 60-те години той разработва това, което по-късно започва да се нарича логика на Хор.

Същността на тази работа е изключително приложна. Когато програмист пише код, винаги възниква въпросът: как да се докаже, че програмата наистина прави точно това, което е замислено, а не просто изглежда правилна при няколко теста? Логиката на Хор предложи строг метод за това. Тя позволява да се формулират условия преди и след изпълнението на фрагмент от програмата, а след това да се провери дали желаният резултат се запазва. В опростен вид подходът изглежда така: ако на входа едно твърдение е вярно, то след изпълнението на командата другото трябва да стане вярно. За света на програмирането този начин на разсъждение се оказа изключително важен. С негова помощ може не само да се търсят бъгове, но и предварително да се доказва коректността на особено критични системи, където грешката струва твърде скъпо.

По-късно Хоар се заема с още една трудна област – конкурентните изчисления. Става дума за програми, в които няколко процеса работят едновременно, обменят данни и си влияят взаимно. На практика именно тук започват най-неприятните и трудноуловими сривове: забивания, надпревари на данни, взаимни блокировки, поведение, което е невъзможно да се възпроизведе стабилно. За да опише такива неща не на ниво предположения, а в ясни правила, Хоар предложил модела Communicating Sequential Processes, или CSP.

Същността на CSP е, че е удобно да разглеждаме паралелната система като набор от отделни процеси, които се изпълняват независимо, но взаимодействат чрез обмен на съобщения. Такъв подход помага да не смесваме всичко в един хаотичен поток от състояния, а да разделим поведението на програмата на разбираеми части: кой какво прави, в кой момент чака данни, кога изпраща резултат и къде може да възникне зацикляне. За теорията на програмирането моделът стана много важен, а за практиката той повлия на това как са организирани механизмите за паралелна работа в различни езици, включително Erlang, Go и Clojure. С други думи, Хоар помогна да се формулира език, на който програмистите и до днес обсъждат едновременното изпълнение на задачи без объркване.

Хор беше ценен не само заради техническата дълбочина на идеите си, но и заради рядката яснота на изказа си. През 1973 година, говорейки за ALGOL 60, той отбеляза, че езикът е изпреварил времето си до такава степен, че се е оказал по-добър не само от предшествениците си, но и от почти всички свои последователи. Зад тази фраза не стоеше желание да блесне с остроумие, а погледът на човек, който виждаше развитието на езиците за програмиране отвътре и добре разбираше колко бързо успешните идеи потъват под слой от усложнения, компромиси и неуспешни надстройки.

През 1980 година Хор получава наградата „Тюринг“ – най-престижната награда в областта на информатиката. Още по-широко разпространение получи неговата лекция „The Emperor’s Old Clothes“ (Старите дрехи на императора). Именно оттам произлезе една от най-известните мисли за проектирането на програми: системата може да бъде направена толкова проста, че недостатъците ще бъдат веднага забележими, или толкова сложна, че никой вече няма да види явните недостатъци. Разработчиците цитират тази фраза не защото звучи ефектно, а защото в нея има твърде много истина. Сложността в софтуера често не решава проблемите, а просто по-добре скрива слабите места.

В биографията на Хор има и разработка, за която по-късно той говори със съжаление. Заедно с Никлаус Вирт той участва в създаването на ALGOL W, един от вариантите за развитие на ALGOL 60. Комитетът, занимаващ се с бъдещето на езика в крайна сметка заложи на ALGOL 68. Това решение фактически прекъсна линията, която можеше да се развие по друг начин. При това идеите на ALGOL W не изчезнаха безследно: по-късно те повлияха на Pascal.

Именно в тази работа Хоар добави механизъм, който по-късно ще нарече „грешката за милиард“.

Става дума за нулевия указател или нулевата препратка. От практическа гледна точка идеята изглеждаше много удобна: програмата можеше да съхранява специална стойност, която означаваше липса на обект или данни. Реализирането на такъв механизъм беше лесно и в началото решението изглеждаше разумно. Проблемът се прояви по-късно. Веднага щом кодът пропусне да провери дали зад такава препратка има реален обект, програмата се срива или започва да се държи непредсказуемо. От такива ситуации възникнаха огромно количество сривове, уязвимости и аварии по целия свят. Хор по-късно директно призна, че е добавил null твърде лесно, без да оцени колко проблеми ще донесе такава на пръв поглед удобна конструкция.

През 2024 година, юлското издание на FACS, бюлетин за формалните аспекти на компютърните науки беше посветено на 90-годишнината на Хоар. След смъртта му се появиха нови текстове в негова памет, включително публикации на Музея по история на компютрите и лични спомени на колеги. От тези отзиви ясно личи как го помнят. Хор се помни не просто като автор на Quicksort или лауреат на наградата „Тюринг“. Колегите пишат за човек, който умееше да измисля фундаментални неща, честно признаваше собствените си грешки и оставяше след себе си идеи, които и до днес работят в ежедневния код.

Смъртта на Хор затваря не просто една голяма лична история, а цяла глава в развитието на информатиката. Quicksort научи програмите бързо да въвеждат ред в данните. Логиката на Хор даде на разработчиците начин строго да проверяват коректността на кода. CSP помогна да се обясни как трябва да комуникират паралелните процеси. Дори историята с null остана важен урок за това как едно удобно решение може да вреди на цялата индустрия в продължение на десетилетия. Такъв набор от постижения се среща рядко дори сред най-големите имена в компютърните науки.