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

Д-р наук, профессор Эдсгер Дейкстра ^[1] (Edsger W. Dijkstra, 1930−2002) — легендарный голландский и американский учёный, труды которого заложили фундамент современного программирования. Среди всех учёных прошлого Дейкстра оказал самое большое влияние на современную информатику. Он один из разработчиков концепции структурного программирования ^[2], формальной верификации ^[3], распределённых вычислений, построения компиляторов, графовых алгоритмов, дизайна алгоритмов, дизайна ПО, дизайна математических аргументов, языков программирования и операционных систем.

Некоторые статьи Дейкстры всего лишь на несколько страниц становились источником целых новых исследовательских направлений. Ряд современных концепций были впервые выявлены Дейкстрой и носят придуманные им названия. Например, параллельные вычисления ^[4].

Биография

Эдсгер Дейкстра родился 11 мая 1930 года в Роттердаме, по окончании школы восемь лет учился на факультете математики и теоретической физики Лейденского университета, десять лет отработал в Центре математики и информатики ^[5] в Амстердаме (до 1962 года).

Женился в 1957 году на коллеге Рие Дебетс. Интересно, что городские власти отказались принимать документы о браке с указанием профессии «программист», поскольку такой официально не существовало. Пришлось указать «теоретический физик».

Диссертация «Коммуникация с автоматическим компьютером» ^[6] была написана по опыту программирования компьютера Electrologica X1 ^[7], а также последующего аннотирования и обсуждения кода.

Программирование X1 впоследствии привело к разработке стандарта ALGOL 60 (об этом ниже).

Вместе с Дейкстрой над программированием X1 в Математическом центре Амстердама трудился инженер Брам Лупстра ^[9], сооснователь и технический директор компании Electrologica ^[10]. Он её основал именно для разработки и производства таких компьютеров.

В 1962−1973 гг Дейкстра занимал должность профессора математики в Техническом университете Эйндховена, потом десять лет работал в компании Burroughs ^[11] (в те годы производитель компьютеров ^[12] и конкурент IBM), а с 1984 года стал профессором компьютерных наук Техасского университета в Остине. В том году они с женой переехали в США.

В документальном фильме «Думать — это наука» ^[13] ("Denken als Discipline") для голландской телепрограммы Noorderlicht можно посмотреть, как жил и работал профессор в Техасе. Фильм вышел в апреле 2001 года.

Алгоритм короткого пути Дейкстры

Когда Дейкстра работал в Математическом центре, он придумал то, что, по его словам, стало «одним из краеугольных камней его славы» — алгоритм кратчайшего пути, также известный как алгоритм Дейкстры ^[14]. По словам Дейкстры, «это было изобретение за двадцать минут», которое он придумал, сидя на террасе кафе с чашкой кофе вместе со своей невестой Рией. Сначала он использовал алгоритм в 1956 году, чтобы продемонстрировать потенциал нового компьютера под названием ARMAC. Он понимал, что демонстрация для непрофессионалов должна содержать проблему и ответ, которые они могут понять. Решение заключалось в разработке алгоритма, который находил кратчайший маршрут между двумя городами в Нидерландах, используя упрощённую карту.

Алгоритм был официально опубликован только в 1959 году в трёхстраничной статье «Заметка по двум задачам, связанным с графами» ^[15]. После этого все теоретические разработки в области SSSP (Single-source shortest path) основывались на алгоритме Дейкстры.

Для какого-нибудь бизнесмена алгоритм может показаться скучным, если не знать, что он используется для арбитража валют на рынках ^[16], где каждое ребро графа соответствует обменному курсу каждой валютной пары:

Более оптимальное решение математической задачи означает миллиарды чистой прибыли от финансовых операций, которые в современных смарт-контрактах исполняются автоматически.

Естественно, это не единственное применение алгоритма поиска кратчайшего пути. Он также широко используется в сетевых протоколах маршрутизации, в логистике, GPS-навигации и картографических сервисах для прокладки маршрутов, робототехнике.

Разработка ALGOL 60

Ещё одним ключевым достижением во время работы Дейкстры в Математическом центре было участие в разработке языка программирования ALGOL 60 ^[17]. Хотя Дейкстра участвовал в ряде встреч, которые завершились публикацией стандарта ALGOL 60, его имя не фигурирует в списке 13-ти авторов окончательного отчёта. Он преждевременно покинул комитет, потому что не согласился с мнением большинства. Но именно во время его работы в Математическом центре они с коллегой Яапом Зонневелдом ^[18] написали первый компилятор ALGOL 60 ^[19] для X1, который, среди прочего, использовал новый метод реализации рекурсии. Небольшая книга Дейкстры «Введение в программирование на ALGOL 60» ^[20] (1962) стала стандартным справочником по этому языку программирования на ближайшие годы.

Параллельные вычисления

В 1968 году Дейкстра опубликовал знаменитую статью «Кооперация последовательных процессов» ^[21], которая заложила основу для всех последующих разработок операционных систем и дала начало параллельным вычислениям как новой концептуальной области информатики.

На самом деле статья была завершена в 1965 году: в архиве рукописей она обозначена как EWD 123. Дейкстра последовательно нумеровал все свои манускрипты как EWD_номер легендарной ручкой Mont Blanc.

В этой статье описан первый механизм синхронизации параллельных процессов — семафор с двумя операциями P и V.

В одной из прошлых статей мы познакомились с Деннисом Ритчи ^[22], который придумал циклы и рекурсию в языке С, а вот Дейкстра изобрёл параллельное программирование. Что ж, у каждой концепции есть свой автор.

В статье 1971 года ^[23] Дейкстра проиллюстрировал проблему взаимной блокировки с помощью задачи об обедающих философах. Эту задачку потом он задавал студентам на экзамене.

Формулировка:

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

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

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

Пример стал классическим для объяснения примитивов синхронизации.

Статья также привела к интенсивным поискам высокоуровневых механизмов синхронизации, что в конечном итоге привело к концепции монитора ^[24] (концепт синхронизации), впервые предложенной Пером Хансеном и Тони Хоаром.

Лекции Дейкстры были очень увлекательными благодаря его острым комментариям, ярким оборотам и любопытным цитатам ^[25], которые он записывал на доске перед началом лекции:

Дейкстра никогда не просил студентов успокоиться. Вместо этого понижал свой голос до такой степени, что его едва можно было слышно. Трюк был удивительно эффективен, вспоминают ^[26] современники.

Принцип KISS

Принцип KISS ^[27] (Keep it simple, stupid) занимает почётное место среди 56 законов и методологий ^[28], на которых основано современное программирование, а Дейкстра считается одним из основоположников философии минимализма в разработке. Он неоднократно высказывался на эту тему.

Дейкстра также говорил о влиянии инструмента, который мы пытаемся использовать, на наши привычки мышления ^[29]: «Я наблюдаю культурную традицию, которая, вероятно, имеет свои корни в эпохе Возрождения, игнорировать это влияние, рассматривать человеческий разум как высшего и автономного хозяина своих артефактов. Но если я начну анализировать привычки мышления ^[29] себя и своих соплеменников, я прихожу к совершенно другому выводу, а именно к тому, что инструменты, которые мы пытаемся использовать, и язык или нотация, которые мы используем для выражения или записи наших мыслей, являются основными факторами, определяющими, что мы можем вообще думать или выражать!»

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

Если соблюдать эти правила, то можно значительно повысить уровень доверия к программе. В идеале, мы сможем даже отказаться от тестирования, если сумеем предоставить убедительное доказательство корректности программы:

Формальный символизм

Дейкстра объясняет ^[30] важность формального символизма для математики. Эта тема напрямую связана с неудобством программирования на естественном языке.

Древнегреческая математика застопорилась, потому что оставалась вербальной, образной деятельностью, мусульманская «алгебра», после робкой попытки символизма, погибла, когда вернулась к риторическому стилю, и современный цивилизованный мир смог возникнуть — к лучшему или к худшему — только тогда, когда Западная Европа смогла освободиться от оков средневекового схоластицизма — тщетная попытка вербальной точности! — благодаря тщательно, или по крайней мере сознательно разработанному формальному символизму, за что мы обязаны таким людям, как Виет, Декарт, Лейбниц и (позже) Буль.

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

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

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

Скромный Программист

В 1972 году Эдсгер Дейкстра выступил с лекцией «Скромный программист» ^[31] ("Humble Programmer", ACM Turing Lecture), в которой рассказал об эволюции компьютерной индустрии за полвека и недооценённой роли разработчиков в ней.

Он пишет, что с самого начала изобретения автоматических компьютеров всё внимание публики было сконцентрировано именно на физических машинах. А сам программист очень скромно относился к своей работе: «Его работа черпала всю свою значимость из существования этой замечательной машины».

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

В те дремучие времена родились две точки зрения на программирование, пишет Дейкстра:

1. Действительно компетентный программист должен любить головоломки и хитрые трюки. «Но компетентный программист осознаёт ограниченный размер своего мозга ^[29], — пишет Дейкстра, — поэтому подходит к задаче программирования с полной скромностью и как чумы избегает хитроумных трюков».

2. Программирование — не более чем оптимизация вычислительного процесса. Отсюда наивное ожидание, что когда появятся более мощные машины, то все проблемы программирования будут решены.

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

Но главная причина в том, что машины стали на несколько порядков мощнее. По мере роста мощности машин росли и амбиции общества применять эти машины:

«И именно скромный программист оказался в этом взрывоопасном поле напряжения между целями и средствами. Увеличенная мощность оборудования с ещё более драматическим увеличением его надёжности сделали возможными решения, о которых программист не смел мечтать несколько лет назад. А теперь, через несколько лет, ему нужно было мечтать о них и, что ещё хуже, превращать такие мечты в реальность! Разве не удивительно, что мы оказались в кризисе программного обеспечения? Конечно, нет.

В лекции 1972 года Дейкстра высказал своё ви́дение будущего индустрии. Он считал, что в будущем разработчики смогут создавать системы невиданной сложности, затрачивая намного меньше усилий, и при этом эти системы будут практически свободны от ошибок, и в результате процесс программирования станет дешевле: «Если вы хотите более эффективных программистов, то они не должны тратить время на отладку, то есть не должны изначально делать ошибки».

К сожалению, спустя полвека приходится признать, что ПО без ошибок осталось такой же недостижимой мечтой, как и в 70-е.

Лекция про скромного программиста завершается такими словами:

Я не знаю другой технологии, которая охватывала бы соотношение объектов в иерархии и более: компьютер, благодаря своей фантастической скорости, кажется первым, кто предоставляет нам среду, где высокоиерархические артефакты возможны и необходимы. Этот вызов, а именно столкновение с задачей программирования, настолько уникален, что новый опыт может многому нас научить о самих себе. Это должно углубить наше понимание процессов проектирования и разработки, это должно дать нам лучший контроль над задачей организации наших мыслей [выделено переводчиком]. Если это не так, на мой взгляд, мы вообще не заслуживаем компьютеров!

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

Записи других лекций и выступлений можно найти в архиве рукописей Дейкстры ^[32]. Сохранилось также несколько аудио- и видеозаписей ^[33].

Рукописи Дейкстры сделаны элегантным и чётким почерком, который копировали многие его сверстники и поклонники. На самом деле, его почерк был настолько чётким и идеальным, что в конце 1980-х Лука Карделли из Исследовательского центра систем DEC разработал шрифт Dijkstra ^[34] для настольных компьютеров:

---

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

В каком-то смысле это можно сказать и сейчас, в 2026 году. Возможно, наши потомки через пару тысячелетий тоже будут смотреть на это время и говорить, что то была заря информатики, первый век IT, когда люди делали первые шажочки в проектировании интеллектуальных систем, подобных человеку. Программисты 21 века ещё чётко не понимали, как работает мозг ^[29], память, поведенческие программы, существует ли «свобода воли» и как её прописать в коде. Наверное, в будущем это станет понятно даже школьникам.

За более чем сорок лет работы в сфере вычислительной науки Дейкстра получил множество наград, включая премию Тьюринга от ACM в 1972 году.

Хотя профессора уже нет с нами, многие его идеи и высказывания как никогда актуальны. Например, мысли о глупости программирования на естественном языке ^[30] (что сейчас называют «вайбкодинг»).

© 2026 ООО «МТ ФИНАНС»