Эдсгер Дейкстра: в поисках «кратчайшего пути» к осознанному программированию

Эдсгер Дейкстра: в поисках «кратчайшего пути» к осознанному программированию

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

Длительное время работал в фирме Burroughs Corporation. В 1970-е годы вместе с Чарльзом Хоаром и Никлаусом Виртом разработал основные положения ставшей классикой методологией разработки программ — структурного программирования.

В последние годы жизни преподавал в США, в Техасском университете. Умер 6 августа 2002 года.

Научные достижения

Известность Дейкстре принесли его работы в области применения математической логики при разработке компьютерных программ. Он активно участвовал в разработке языка программирования Алгол и написал первый компилятор Aлгол-60. Будучи одним из авторов концепции структурного программирования, он проповедовал отказ от использования инструкции GOTO. Также ему принадлежит идея применения «семафоров» для синхронизации процессов в многозадачных системах и алгоритм нахождения кратчайшего пути на ориентированном графе с неотрицательными весами рёбер, известный как Алгоритм Дейкстры. В 1972 году Дейкстра стал лауреатом премии Тьюринга.

Литературные труды

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

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

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

Влияние

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

• Студентов, ранее изучавших Бейсик, практически невозможно обучить хорошему программированию. Как потенциальные программисты они подверглись необратимой умственной деградации
• Вопрос «умеет ли компьютер думать» имеет не больше смысла, чем вопрос «умеет ли подводная лодка плавать».
• Проекты, предлагающие программирование на естественном языке, гибельны по своей сути.
• Когда советское правительство приняло решение о переходе советской промышленности к копированию зарубежных образцов вычислительной техники, Дейкстра назвал это решение величайшей победой Запада в Холодной войне, а выбранную для клонирования модель IBM/360 (прообраз советской ЕС ЭВМ) — величайшей диверсией Запада против СССР.

ЭДСГЕР ДЕЙКСТРА “Смиренный” программист

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

Один из тех людей, с именем которых связано превращение программирования из шаманства в науку, — Эдсгер Дейкстра. Профессиональный словарь программиста полон слов, введенных или предложенных Э. В. Дейкстрой, — “дисплей”, “мертвая хватка”, “семафор”, “программирование с минимумом операторов go to”, “структурное программирование”. Однако его влияние на программирование является более всепроникающим. Ценнейший вклад Дейкстры — его стиль: подход к программированию как к высокому искусству и интеллектуальному творчеству, настойчивые требования и практическая демонстрация того, что программы должны быть с самого начала правильно составлены, а не просто отлаживаться до тех пор, пока не станут правильными; ясное понимание того, какие проблемы лежат в основе программирования. Во всех своих исследованиях Дейкстра придает большое значение простоте и изяществу математических рассуждений. При написании своих работ он создал новый стиль научных и технических сообщений, который можно описать как нечто среднее между журнальными публикациями и дружеской перепиской.

Эдсгер Вайб Дейкстра родился в Роттердаме (Голландия) в 1930 году. Его родители принадлежали к интеллигенции и были хорошо образованными людьми: отец был химиком, а мать — математиком. В 1942 году в возрасте 12 лет Дейкстра поступил в гимназию Эрасминиум — школу для особо одаренных детей, где преподавался ряд разнообразных предметов, в том числе греческий, латынь, французский, немецкий и английский языки, биология, математика и химия.

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

Вследствие длинной череды совпадений Дейкстра официально стал программистом первым весенним утром 1952 года и был первым голландцем, начавшим заниматься этим в своей стране. Он стал работать в качестве совместителя в Математическом центре в Амстердаме. После того как он прозанимался программированием где-то около трех лет, у него состоялась важная беседа с ван Вейнгаарденом, который был тогда его руководителем в Математическом центре. Дело в том, что Дейкстра параллельно изучал теоретическую физику в Лейденском университете, но совмещать эти два занятия становилось все труднее, и ему надо было сделать выбор — либо прекратить программировать и стать настоящим физиком, либо стать… кем же? Программистом? Но разве это респектабельная профессия? Однажды Дейкстра постучал в дверь кабинета ван Вейнгаардена и, когда, несколько часов спустя, покидал его кабинет, он чувствовал себя абсолютно другим человеком. Терпеливо выслушав, что беспокоит Дейкстра, ван Вейнгаардена согласился, что в настоящее время есть не так уж много вещей, которые можно было бы отнести к дисциплине программирования, но затем он спокойно продолжал объяснять, что автоматические вычисления машины — не кратковременная мода, за ними будущее, что мы находимся у самых истоков и — как знать? — может быть, именно Дейкстра призван превратить программирование в почетную научную дисциплину. Это был поворотный момент всей жизни Эдсгера Дейкстра, и он как можно быстрее прошел все курсы, требующиеся для получения диплома в области теоретической физики, и начал заниматься программированием.

Однако одной из проблем, с которой он столкнулся, было то, что к тому времени программирование еще не было официально признано профессией. (Когда он подавал документы для регистрации брака в 1957 году, ему пришлось написать в качестве своей профессии “физик-теоретик”.) Все первые автоматические электронные компьютеры были уникальными, построенными в единственном экземпляре машинами, очень громоздкими и действительно фантастическими. Поэтому несчастных программистов едва замечали. По мере того как мощность машин возросла более чем в тысячу раз, честолюбивые замыслы общества, связанные с применением этих машин, росли в той же пропорции, и именно несчастный программист обнаружил, что его работа оказалась в поле зрения между целями и средствами. Тогда, в середине 60-х годов, случилось нечто ужасное: появились компьютеры так называемого третьего поколения. Когда о таких ЭВМ было объявлено и стали известны их функциональные спецификации, многим из программистов стало не по себе; по крайней мере, такое чувство возникло у Эдсгера Дейкстра. Было естественно ожидать, что такие вычислительные машины хлынут потоком на компьютерный рынок, и следовало ожидать, что их организация будет более разумной. Но проект содержал такие серьезные ошибки, что Дейкстра почувствовал, что одним ударом прогресс в информатике был заторможен по меньшей мере лет на десять. Это была самая черная неделя во всей его профессиональной карьере. Вот, что говорил он по этому поводу: “Быть может, печальнее всего то, что после всех этих лет разочаровывающего опыта многие все еще честно верят в то, что в силу некоторого закона природы машины должны быть именно такими”.

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

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

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

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

Четвертым проектом был ALGOL-60. В то время как определение LISP до сих пор остается причудливой мешаниной из того, что язык означает, и того, как он работает, знаменитое “Сообщение об алгоритмическом языке ALGOL-60” является плодом подлинных усилий перейти на следующий уровень абстрактности и определить язык программирования способом, не зависящим от его реализации.

Это все было в прошлом. Однажды Дейкстра набросал один из вариантов будущего развития программного обеспечения. “Картина такова, что еще до завершения семидесятых мы сможем изобрести и реализовать системы такого рода, которые сейчас находятся на пределе наших возможностей программировать, и затратить на них лишь несколько процентов тех усилий, которых они требуют ныне, и, кроме того, эти системы будут практически свободными от ошибок. Такая решительная перемена за такой короткий период времени была бы революцией. Но на сколько вероятно, что эта революция произойдет? По-видимому, надо, чтобы выполнились три основных условия. Весь мир должен признать необходимость перемены; во- вторых, экономическая необходимость этой перемены должна быть достаточно сильной; и, в-третьих, эта перемена должна быть технически выполнимой”. Поворотной точкой была Конференция по технике программного обеспечения в Гармише в октябре 1968 года. Эта конференция стала сенсационной, когда на ней впервые был открыто признан кризис программного обеспечения. Поэтому первое условие Дейкстра считал выполненным.

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

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

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

Третий довод основан на конструктивном подходе к проблеме правильности программы. Единственный эффективный способ значительно повысить доверие к программе — это дать убедительное доказательство правильности. Программист должен доказывать правильность программы одновременно с ее написанием.

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

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

И последним доводом в пользу технической реализуемости революции он привел широкую применимость хорошо разложимых на компоненты решений.

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

Проф. М. Гуда и проф. Э. Дейкстра в Техническом университете Эйндховена

Многим программистам Дейкстра известен как создатель алгоритма “кратчайшего пути”, предложенного им еще в 1952 году, который появился в результате его работы над задачей по оценке производительности компьютера ARCMAC, установленного в Математическом Центре. Этот алгоритм позволяет находить наилучший путь для перемещения между двумя точками. Ученый также использовал этот алгоритм для решения задачи “О нахождении оптимального пути передачи электрического тока всем существенным элементам цепи, минимизируя при этом расход меди”, с которой столкнулись инженеры, разрабатывавшие ARCMAC. Он назвал этот способ “алгоритмом дерева с кратчайшими ветвями”. В начале 60-х годов Дейкстра применил идею взаимного исключения к технологии связи между компьютером и его клавиатурой. Он использовал символы Р и V для представления двух операций, производимых в задаче взаимного исключения. Эта идея стала частью практически всех современных процессоров и модулей памяти, начиная с 1964 года, когда IBM впервые использовала ее в своей архитектуре IBM/360. Он помог программной индустрии стать намного более дисциплинированной, выдвинув тезис, что оператор “go to является вредным”. Это означало, что чем больше в программе операторов go to, тем труднее разобраться в исходном коде программы. Эдсгер Дейкстра стоял у истоков структурного программирования. В 1972 году он вместе с Оле Далом и Тони Хоаром опубликовал основополагающую монографию “Структурное программирование”.

Дейкстра продолжал работу в Математическом Центре до тех пор, пока в начале 70-х годов не перешел на работу исследователем в корпорацию Burroughs в США. В 1972 году ACM наградила Дейкстра премией Тьюринга (ACM Turing Award). В 1974 году AFIPS удостоила его памятной наградой Гарри Гуда (AFIPS Налу Goode Memorial Award). В начале 1980-х годов Дейкстра переехал в Остин, штат Техас. В 1984 году он был назначен деканом факультета компьютерных наук в Техасском университете.

Эдсгер Вайб Дейкстра является Почетным Иностранным членом Американской Академии гуманитарных, естественных и технических наук. Он также является членом Голландской королевской Академии наук, действительным членом Британского Компьютерного Общества и, наконец, доктором наук Королевского университета в Белфасте.

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

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

Алгоритм Дейкстры нахождения кратчайшего пути

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

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

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.

Инициализация

Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Первый шаг

Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.

Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из 1-й во 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7.

Аналогично находим длины пути для всех других соседей (вершины 3 и 6).

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.

Второй шаг

Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Вершина 1 уже посещена. Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9