Человек-алгоритм: жизнь и въедливые наблюдения Эдсгера Дейкстры

Те, кто вкатывается в айти, часто интересуются: «Нужна ли математика программисту?» Им обычно отвечают, что да, но не везде, не всегда и вообще можно без неё. А вот Эдсгер Дейкстра считал, что любую программистскую задачу нужно математически описать, доказать правильность выбранного алгоритма и только потом решать.

Первый голландский программист

Эдсгер Вибе Дейкстра родился в Роттердаме в 1930 году. Отец его был химиком, мать — математиком, а сам он мечтал о карьере юриста. Однако после школы по совету родителей Эдсгер поступил на отделение математики и теоретической физики Лейденского университета. Поворотным пунктом стало знакомство с Адрианом ван Вейнгаарденом, директором отдела вычислений Математического центра Амстердама. Именно там Эдсгер начал программировать.

В какой-то момент совмещать физику и программирование стало сложно — пришлось выбирать что-то одно. Теоретическая физика была признанной и солидной дисциплиной, а вот вкатываться в айти в то время ещё никто не спешил.

Во время женитьбы в 1957 году Дейкстру попросили назвать свою профессию. Когда он ответил: «Программист», сотрудники муниципалитета сказали, что такой профессии в Нидерландах нет — пришлось назваться физиком.

Надо понимать, что в те годы во всём мире было всего два-три десятка компьютеров, а задача программиста чаще всего сводилась к тому, чтобы рассчитать траекторию снаряда или решить математическую проблему — ни смузи, ни печенек, ни саббатикала.

Эдсгер посоветовался с Вейнгаарденом, и тот направил юного Дейкстру на путь истинный.

Первые компьютеры Математического центра собирались на электронных лампах. Они занимали много места, буквально пожирали энергию и регулярно ломались. Работа заключалась в том, что коллеги Эдсгера сначала описывали взаимодействие «железа» и софта. Затем они собирали компьютер, а Дейкстра писал софт для пока ещё не существующей машины.

Из этой работы Дейкстра вынес два урока, которые повлияли на его дальнейшие взгляды. Во-первых, важно писать ясную документацию, а во-вторых, если тщательно продумать программу, потом придётся тратить на отладку меньше времени.

Алгоритм имени себя

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

Алгоритм работает пошагово. Сначала задаётся исходная точка, затем алгоритм по очереди ищет самый короткий из путей от этой точки до других. На каждом шаге он «посещает» одну точку и помечает её как пройденную. Когда все точки пройдены, алгоритм завершает свою работу.

Алгоритм Дейкстры широко используется для решения следующих задач:

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

Забыть Fortran, любить Algol и уберечь код от пожара

Дейкстра известен своими едкими афоризмами. В то время высокоуровневых языков программирования было немного, и одним из них был Fortran. Дейкстра называл его «инфантильным расстройством».

А вот Algol 60 благодаря своей стройности, ясности и изяществу пришёлся Дейкстре по душе. Вместе с программистом Яапом Зонневельдом он написал компилятор и разработал алгоритмы, которые были необходимы для реализации полной версии языка. Также Дейкстра способствовал включению рекурсии в определение Algol 60 и первым ввёл понятие «стека» для трансляции рекурсивных программ. А ещё в процессе работы над компилятором Дейкстра изобрёл и впервые применил на практике технику парного программирования.

Сам Дейкстра, вспоминая эту практику, пишет о том, что они имели дело с двумя типами ошибок: ошибками написания и ошибками мышления. С помощью парного программирования они боролись с первым типом. Сравнивая свои перфокарты, они обычно находили более двадцати расхождений и исправляли их. А вот с ошибками мышления было сложнее: приходилось убеждать друг друга, почему предложенный код будет работать.

Сам Дейкстра считал, что информатика как дисциплина зародилась как раз после публикации отчёта по Algol 60.

Операционная система THE

В 1962 году Дейкстру назначили профессором математики в Технологическом университете Эйндховена. Там он создал операционную систему THE (названа в честь университета Technische Hogeschool te Eindhoven), которая повлияла на дизайн всех операционных систем. В процессе работы над ТНЕ Дейкстра ввёл ряд принципов проектирования, которые прочно вошли в лексикон профессиональных программистов: уровни абстракции, программирование по слоям, семафор и взаимодействующие последовательные процессы.

Проблема была в том, что разные процессы в ОС блокировали друг друга, а когда удавалось этого избежать, система всё равно намертво зависала. Дейкстра назвал это явление взаимоблокировкой (deadlock). Для решения проблемы он предложил концепцию «семафора» — примитива синхронизации работы процессов и потоков, в основе которого лежит счётчик, который умеет производить две атомарные операции: увеличение и уменьшение.

Могут ли подводные лодки плавать?

За свою жизнь Дейкстра написал — один и в соавторстве — девять книг, двенадцать глав, сорок статей, тридцать четыре материала для конференций и двадцать две другие публикации. И это не считая серии заметок, называемых EWD. Дейкстра всегда считал долгом учёного поддерживать оживлённую переписку со своими научными коллегами — более сорока лет он рассылал нескольким десяткам адресатов копии своих последовательно пронумерованных технических заметок (EWD1, EWD22 и так далее), отчётов о поездках, проницательных наблюдений и едких комментариев.

Благодаря повсеместному распространению ксерокса и широкому интересу к трудам Дейкстры неофициальный тираж многих EWD в конечном итоге достиг тысячи экземпляров. Многие идеи, которые он излагал в заметках, вроде взаимоблокировки, сборки мусора на лету и самостабилизирующихся систем, положили начало новым областям информатики.

Примечательно, что будучи программистом и имея дело с компьютерами, Дейкстра всё писал от руки на бумаге. Даже когда коллеги уговорили его купить Macintosh, он использовал его только для электронной почты и веб-сёрфинга. Он не работал с текстовыми процессорами. Как и в случае с программами, он считал, что лучше сначала тщательно продумать текст, а потом написать его начисто — без переписывания или редактирования.

Однажды зимой Дейкстра поскользнулся, упал и сломал правое запястье. Вместо того чтобы отдохнуть пару недель, он научился писать левой рукой. А когда правая рука восстановилась, он продолжал периодически писать левой, чтобы сохранить навык.

Компьютеры становились всё популярнее, и их начинали применять всё в большем количестве областей — естественно, возрастала и потребность в софте, программ писалось всё больше, они становились сложнее и объёмнее, а качество неизбежно падало. Думая над тем, как решить эту проблему, Дейкстра написал свои «Заметки по структурному программированию», в которых сформулировал принципы проектирования программ. Сегодня они считаются стандартом, но на тот момент это была настоящая революция:

• большие системы должны строиться на основе множества более мелких компонентов (модульность);
• более мелкие компоненты могут быть также собраны из других компонентов;
• проектирование должно начинаться с перечисления отдельных проблем и рассмотрения каждой группы проблем независимо от других;
• математическая логика является и должна быть основой для проектирования программного обеспечения.

Результатом дальнейших размышлений Дейкстры о структурном программировании стала книга «Дисциплина программирования», опубликованная в 1976 году. Она возвела программирование на новую высоту. Проблема была в том, что программы в те годы нередко писали путём проб и ошибок. Дейкстра противопоставил этому формальный математический подход, показав, что программы могут быть красивыми, изящными и при этом надёжными. Именно так он превращал программирование в научную дисциплину.

Дейкстра выступал за то, чтобы доказывать правильность программы с помощью математических методов, и призывал программистов мыслить алгоритмически. Собственно, книга представляет элегантные решения пары десятков задач разной степени сложности.

За свои идеи и наработки в 1972 году Дейкстра получил премию Тьюринга — самую престижную награду в области информатики. Хотя известную работу знаменитого математика, премию имени которого он получил, Дейкстра в своём едком стиле прокомментировал так: «Вопрос о том, могут ли машины мыслить, примерно так же актуален, как вопрос о том, могут ли подводные лодки плавать».

Одна из радостей жизни

В 1984 году Дейкстра начал работу на факультете информатики Техасского университета в Остине, где раскрылся с ещё одной стороны — как талантливый, увлечённый и оригинальный преподаватель.

В начале семестра он фотографировал каждого студента, чтобы запомнить все имена. Он никогда не следовал учебникам и формальным программам, не использовал проекторы — всё писал на доске. Дейкстра задавал сложные домашние задания и тщательно изучал решения своих студентов, оставляя комментарии, которые нередко превышали по размеру сами решения. Каждый студент сдавал экзамен по несколько часов. А в конце Дейкстра угощал его пивом и дарил копию той самой фотографии со своим автографом.

Дейкстра серьёзно относился к образованию и считал, что одним из результатов любого исследования должны становиться обучающие материалы.

Говорят, Дейкстра неохотно брал на старшие курсы университета студентов со знанием Фортрана «по той причине, что вместе с этими знаниями могли привиться дурные привычки программирования».

Дейкстре бы это не понравилось

Благодаря изучению теоретической физики и математики Дейкстра хорошо знал, что такое настоящая наука, понимал, что должны быть концепции, терминология и логика — это и помогло ему превратить программирование в настоящую науку.

А закончить статью мы бы хотели ещё одной фирменной цитатой от Эдсгера:

Человек, оказавший фундаментальное влияние на развитие программирования, вёл довольно скромную, почти спартанскую жизнь. У него не было ни телевизора, ни видеоплеера, ни мобильного телефона, он не ходил в кино. На досуге он играл на пианино и посещал концерты классической музыки — его любимым композитором был Моцарт. Дейкстра умер в 2002 году от рака.