Код
#статьи

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

Он превратил программирование в науку и откровенно насмехался над Фортраном. А ещё практиковал парное программирование задолго до этих ваших эджайлов.

Иллюстрация: macrovector / rawpixel / Freepik / Zvezdica2816 / Andreas F. Borchert / Anatoly Gorbunov / Wikimedia Commons / Дима Руденок для Skillbox Media

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

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

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

Дейкстра во время учёбы в Лейденском университете, 1948 и 1951 годы
Фото: Блог об Эдсгере Дейкстре

«В результате длинной цепочки случайностей я официально вошёл в профессию программиста в первое весеннее утро 1952 года и, насколько мне удалось выяснить, стал первым голландцем, сделавшим это у себя на родине».

Эдсгер Дейкстра,
The Humble Programmer

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

«Я должен был принять решение: либо бросить программирование и стать настоящим уважаемым физиком-теоретиком, либо формально завершить обучение по физике, приложив минимум усилий, и стать… Кем? Программистом? Но разве это уважаемая профессия?»

Эдсгер Дейкстра,
The Humble Programmer

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

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

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

«Это был поворотный момент в моей жизни, и я завершил изучение физики так быстро, как только смог. Мораль этой истории, конечно, в том, что мы должны быть очень осторожны, когда даём советы молодым людям — ведь иногда они следуют им!»

Эдсгер Дейкстра,
The Humble Programmer

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

«Тестирование программ в лучшем случае может показать наличие ошибок, но никак не их отсутствие».

Эдсгер Дейкстра

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

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

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

Нахождение кратчайшего пути от а к b
Изображение: Wikimedia Commons

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

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

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

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

Эдсгер Дейкстра

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

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

«Чем скорее мы забудем, что Fortran вообще существовал, тем лучше, потому что как средство мышления он уже не годится: он попусту растрачивает ресурс нашего мозга, слишком небезопасный, а потому за его использование приходится платить непомерную цену».

Эдсгер Дейкстра

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

Дейкстра. Год неизвестен
Фото: Блог об Эдсгере Дейкстре

«Зонневельд сидел за столом напротив, и каждая инструкция в компиляторе записывалась (ими обоими) только после того, как они обсудили и договорились, что она верна. Вечером каждый из них забирал собственную копию кода домой на случай пожара».

Сэр Тони Хоар,
британский информатик. What can we learn from Edsger W. Dijkstra?

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

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

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

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

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

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

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

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

«Происходит революция в том, как мы пишем программы и преподаём программирование… Невозможно прочитать недавнюю книгу Дейкстры „Структурное программирование“ и не изменить свою жизнь».

Дональд Кнут,
знаменитый классик информатики.
Storytelling about Lighthouse. Criticizing professor Dijkstra Considered harmless

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

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

«Прогресс возможен только в том случае, если мы приучим себя думать о программах, не рассматривая их как куски исполняемого кода».

Эдсгер Дейкстра

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

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

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

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

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

«Драгоценный дар — стиль Дейкстры: его подход к программированию как к серьёзному интеллектуальному вызову; его настойчивость и практическая демонстрация того, что программы должны быть составлены правильно, а не просто отлажены до корректного состояния; его визионерский взгляд на проблемы, лежащие в основе разработки программ… Мы стали ценить хорошие программы примерно так же, как ценим хорошую литературу. И в центре этого движения стоит Э. В. Дейкстра, который создавал настолько же красивые, насколько и прагматичные паттерны».

Из речи о заслугах Дейкстры при вручении ему премии Тьюринга

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

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

«Обучение ничего не понимающих подростков эффективному использованию формальных методов — одна из радостей жизни, потому что это приносит огромное удовлетворение».

Эдсгер Дейкстра,
On the cruelty of really teaching computing science

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

Дейкстра в 1984 году
Фото: TU/e

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

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

Эдсгер Дейкстра,
My hopes of computing science

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

«Использование COBOL калечит разум, поэтому его преподавание должно рассматриваться как уголовное преступление».

Эдсгер Дейкстра

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

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

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

«Информатика имеет к компьютерам не больше отношения, чем астрономия — к телескопам».

Дейкстра в 2002 году
Фото: Wikimedia Commons

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

«…Если через 10 лет, когда вы будете делать что-то быстрое и грязное, вы вдруг представите, что я заглядываю вам через плечо, и скажете себе: „Дейкстре бы это не понравилось“, — что ж, для меня это будет подходящей формой бессмертия».

Эдсгер Дейкстра

Больше интересного про код — в нашем телеграм-канале. Подписывайтесь!

Научитесь: Профессия Data Scientist Узнать больше
Понравилась статья?
Да

Пользуясь нашим сайтом, вы соглашаетесь с тем, что мы используем cookies 🍪

Ссылка скопирована