Эдсгер Дейкстра: в поисках «кратчайшего пути» к осознанному программированию
Изображение с сайта abv24.com
Один из тех людей, с именем которых связано превращение программирования из шаманства в науку, — Эдсгер Дейкстра. Он небезуспешно доказывал, что программирование — высокое искусство и интеллектуальное творчество.
Во всех своих исследованиях Дейкстра придает большое значение простоте и изяществу математических рассуждений. При написании своих работ он создал новый стиль научных и технических сообщений, который можно описать как нечто среднее между журнальными публикациями и дружеской перепиской.
Программирование — не набор пассов и заклинаний, не шаманство, не танцы с бубном, а математическая дисциплина. А всякая дисциплина, если она претендует на нечто большее, чем на внешний эффект, должна строиться на прочном фундаменте. Таким фундаментом для Дейкстры является математическая логика, а точнее — исчисление предикатов.
Сейчас это не кажется чем-то необычным, но в 50-е годы это прозвучало как откровение. Дейкстра понял и убедительно показал, как теория может и должна помочь практике.
Для особо одаренных
Эдсгер Вайб Дейкстра родился в Роттердаме (Голландия) в 1930 году. Его родители были хорошо образованными людьми: отец был химиком, а мать — математиком. В 1942 году в возрасте 12 лет Дейкстра поступил в гимназию Эрасминиум — школу для особо одаренных детей, где преподавался ряд разнообразных предметов, в том числе греческий, латынь, французский, немецкий и английский языки, биология, математика и химия.
Изображение с сайта balto-slavica.com
В 1945 году Дейкстра подумал, что он мог бы изучать право и, возможно, работать в качестве представителя Нидерландов в ООН. Однако, вследствие его успехов в изучении химии, математики и физики, он поступил в университет Лейдена, где решил заняться теоретической физикой. В 1951 году он посещал летнюю школу по программированию в Кембриджском университете.
Дилемма
За год до окончания университета Дейкстра оказался перед дилеммой: продолжить научную карьеру по основной специальности — теоретической физике или все-таки продолжать заниматься программированием:
мне надо было сделать выбор — либо прекратить программировать и стать настоящим респектабельным теоретическим физиком, либо как-то формально завершить мое обучение теоретической физике с минимальными усилиями и стать… кем же? Программистом? Но разве это респектабельная профессия? В конце концов, что такое программирование? В чем должен был состоять тот солидный объем знаний, который позволил бы считать программирование научной дисциплиной?
Однажды Дейкстра постучал в дверь кабинета своего научного руководителя ван Вейнгаардена. Терпеливо выслушав, что беспокоит Дейкстра, ван Вейнгаарден согласился, что в настоящее время есть не так уж много вещей, которые можно было бы отнести к дисциплине программирования, но затем он спокойно продолжал объяснять, что автоматические вычисления машины — не кратковременная мода, за ними будущее, что мы находимся у самых истоков и — как знать? — может быть, именно Дейкстра призван превратить программирование в почетную научную дисциплину. Это был поворотный момент всей жизни Эдсгера Дейкстра, и он как можно быстрее прошел все курсы, требующиеся для получения диплома в области теоретической физики, и начал заниматься программированием.
Дейкстра официально стал «программистом» 1 марта 1952 года и был первым голландцем, начавшим заниматься этим в своей стране. Он начал работать в качестве совместителя в Математическом центре в Амстердаме.
Туманное будущее
Надо сказать, что Дейкстра действительно рисковал выбирая столь экзотическую в те времена профессию. Программистов было мало, а компьютеры и вовсе исчислялись двумя-тремя десятками. Будущее информатики как науки было туманным — многие рассматривали (и надо признать не без оснований) информатику как ветвь прикладной математики.
Однако, ближайшие несколько лет показали — ван Вейнгаарден не ошибся, предложив своему талантливому студенту, а в дальнейшем аспиранту, выбрать программирование: с конца 50-х годов корпорация IBM начала производство компьютеров на транзисторах, что позволило существенно снизить их энергоемкость, массу и стоимость одновременно подняв объемы памяти и производительность. Моментально подтянулись другие компании и компьютеры из военных и научных лабораторий стали доступны банкам, производственным предприятиям, учебным заведениям, больницам, коммунальным службам.
Алгоритм Дейкстры
Многим программистам Дейкстра известен как создатель алгоритма «кратчайшего пути», предложенного им еще в 1952 году, который появился в результате его работы над задачей по оценке производительности компьютера ARCMAC, установленного в Математическом Центре. Этот алгоритм позволяет находить наилучший путь для перемещения между двумя точками.
Ученый также использовал этот алгоритм для решения задачи «О нахождении оптимального пути передачи электрического тока всем существенным элементам цепи, минимизируя при этом расход меди», с которой столкнулись инженеры, разрабатывавшие ARCMAC. Он назвал этот способ «алгоритмом дерева с кратчайшими ветвями».
Изображение с сайта urban-sanjoo.narod.ru
Алгоритм Дейкстры широко применяется и сегодня (например, при планировании автомобильных и авиамаршрутов, при разводке электронных плат, в протоколах маршрутизации). Относится к «жадным» алгоритмам, то есть достаточно эффективен для поиска путей на относительно небольших графах.
ALGOL-60
Порядком намаявшись в начале своей программистской карьеры с машинными кодами и с тем, что для различных моделей компьютеров один и тот же алгоритм нужно было переписывать практически с нуля, Эдсгер Дейкстра не мог не «ухватиться» за языки программирования высокого уровня.
FORTRAN, появившийся в конце 50-х годов Дейкстру не очень привлекал: в FOTRAN-е многое было принесено в жертву главной цели — во чтобы то ни стало реализовать высокоуровневый язык и избавить программиста от «проклятья» двоичных кодов. Появись FORTRAN сегодня, его шансы удержаться, думаю, были бы весьма сомнительными. Но тогда, безусловно, FORTRAN был великим шагом вперед. Однако, Дейкстре все равно FORTRAN не импонировал — ему в этом языке, по-видимому, не хватало того изящества и логичности конструкций, которые Дейкстра привык видеть в математике и логике.
Язык ALGOL-60 описывался стройной и вполне строгой нотацией (т.н. называемая «форма Бэкуса-Наура»), его разработка велась едва ли не в академической среде с присущими последней требованиями четкости, ясности и доказуемости. Критерии были строгими и язык поэтому получился изящный (не случайно такие языки программирования как PL/1, PASCAL и ADA носят явные следы влияния ALGOL-а).
Не мешкая Дейкстра приступил к реализации компилятора и успех в этом направлении подтвердил его давнюю мысль — программировать надо на «нормальных» языках, приспособленных, насколько это возможно, к психологии человека. А машинный код — ну что же, раз без него все равно никуда не деться — его можно и нужно оставить машинам.
Одной из наиболее сложных задач при трансляции языков программирования в те годы была задача компиляции арифметических выражений с учетом приоритетов операций и скобок. Дейкстра убедительно обосновал и упростил предложенный в 1957 году Ф.Брауэром и К.Замельзоном алгоритм использования для этой цели двух стеков (тогда обычно говорили «магазин» по аналогии с магазином оружия). Арифметические выражения эффективно транслировались в обратную (или «инверсную») польскую запись очень удобную для генерации объектного кода.
Пример обратной польской записи
Величайшие изобретения прошлого по версии Дейкстры
Одним из величайших изобретений, он считал, является замкнутая подпрограмма, которая воплощает одну из фундаментальных абстракций.
Вторым крупным достижением в области программного обеспечения Дейкстра называл рождение FORTRAN. Это был чрезвычайно смелый проект, который должен оцениваться как успешная методика программирования, но с очень ограниченным числом средств поддержки основной концепции. В наши дни этот язык считают устаревшим. Трагическая судьба FORTRAN — следствие его широкого признания, приковавшего мышление тысяч и тысяч программистов к прошлым ошибкам.
Третьим проектом, о котором упоминает Дейкстра, является LISP. На использованииLISP основаны многие в некотором смысле наиболее изощренные программные продукты. В шутку LISP описывался как «наиболее интеллигентный способ злоупотребления компьютером». Дейкстра считал, что подобная характеристика является большим комплиментом, поскольку она передает всю полноту освобождения: LISP помогает многим из наиболее одаренных программистов мыслить о вещах, ранее считавшихся немыслимыми.
Четвертым проектом был ALGOL-60. В то время как определение LISP до сих пор остается причудливой мешаниной из того, что язык означает, и того, как он работает, знаменитое «Сообщение об алгоритмическом языке ALGOL-60» является плодом подлинных усилий перейти на следующий уровень абстрактности и определить язык программирования способом, не зависящим от его реализации.
Пять обедающих философов
Разработчики первых операционных систем, которые и операционными системами можно назвать с большой натяжкой, работавших в пакетном режиме (когда одному заданию полностью «принадлежали» все ресурсы компьютера) почти не сталкивались с задачей, которая к середине 60-х годов прошлого века стала чрезвычайно актуальной — обеспечение доступа нескольких процессов к общим ресурсам и разделение этих ресурсов между процессами. Без этого нельзя было решить важнейшую задачу — одновременное выполнение нескольких процессов на одном компьютере. В операционных системах, использующих эти алгоритмы, никак не удавалось избежать блокирования процессами друг друга.
Разумеется, такая нестабильность и непредсказуемость поведения основной программы — операционной системы — никого не могла устроить.
Наиболее полно свои мысли по этому поводу Дейкстра изложил в статье «Взаимодействие последовательных процессов». Для решения этой проблемы Дейкстра предложил концепцию «семафора» — специальных целочисленных общих переменных и двух примитивов «P-операция» и «V-операция». Вот как сам Дейкстра описывает эти примитивы:
Эти две последнии операции всегда выполняются над семафорами и представляют единственный способ обращения к семафорам со стороны одновременно действующих процессов. Семафоры являются по существу неотрицательными целыми величинами. Если они используются только для решения задачи взаимного исключения, то область их значений составляют лишь »0» и »1».
V-операция состоит в увеличении значения аргумента (который является семафором) на 1. Такое увеличение обязано быть неделимой операцией. P-операция, напротив, будучи применной к семафору, уменьшает (также неделимым образом) значение последнего на 1. Поскольку семафор, согласно определению, число неотрицательное, то рано или поздно P-операция уменьшит его значение до 0. Процесс, инициировавший P-операцию вынужден будет ждать (т.е. фактически окажется в режиме задержки выполнения) до тех пор пока другой процесс не «сдвинет» значение этого семафора в положительную область, т.е. разблокирует семафор.
Эти концепции и их дальнейшее развитие — например, мьютексы — и сегодня применяются при проектировании и реализации операционных систем.
В эти же годы Эдсгер Дейкстра руководил созданием операционной системы THE (от «Technische Hogeschool Eindhoven») с поддержкой многозадачности. Операционная система была построена в виде иерархии из 6 уровней; при этом более низкие уровни (начиная с 0) служили базой для более высоких (вплоть до 5). На начальных уровнях были реализованы система обработки прерываний, семафоры, переключение контекстов процессов, система управления памятью, диспетчер. На средних уровнях были реализованы взаимодействие с консолью, ввод/вывод, взаимодействие с устройствами; самый верхний уровень предназначался для пользовательских программ. В дальнейшем такая модель организации операционной системы получила широкое распространение.
Для иллюстрации проблемы разделения/блокирования ресурсов и взаимодействия процессов Дейкстра предложил простую и остроумную модель; позже эта модель получила имя «задачи о пяти обедающих философах». В изложении Чарльза Хоара она звучит так:
В давние времена один богатый филантроп пожервовал свой капитал на основание некоего пансиона, чтобы дать пристанище пяти знаменитым философам. У каждого философа была своя комната, где он мог предаваться размышлениям. Была у них и общая столовая с круглым столом, вокруг которого стояли пять стульев, каждый помеченный именем того философа, которому он предназначался… Слева от каждого философа лежала золотая вилка, а в центре стояла большая миска спагетти, содержимое которой постоянно пополнялось.
Изображение с сайта dic.academic.ru
Предполагалось, что большую часть времени философ проводил в размышлениях, а почувствовав голод, шел в столовую, садился на свой стул, брал вилку слева от себя и приступал к еде. Но такова уж сложная природа спагетти, что их не донести до рта без помощи второй вилки. Поэтому философу приходилось брать вилку и справа от себя… Если вилка требовалась другому философу, ему приходилось ждать, пока она освободится.
Структурное программирование
Проникновение компьютеров во все отрасли промышленности, бизнеса, образования, а также сопутствующий этому проникновению рост объема разрабатываемого программного обеспечения вызывал обеспокоенность ведущих специалистов: программы становились все больше, все сложнее, все разнообразнее. Все это не смогло не сказаться на их качестве — оно стремительно падало.
Досадно, если ошибка была в программе начисления заработной платы, но это, в конце-концов дело поправимое. Страшно, если программная ошибка обнаруживалась в системе управления воздушным транспортом. И совсем уж катастрофической была бы ошибка в программе управления работой атомного реактора.
Дейкстра видел причины ошибок в запутанной структуре программ:
Я считаю, что программа никогда не является самоцелью; программа предназнается для того, чтобы вызвать вычисления, а цель вычислений — получить нужный результат… Я утверждаю (хотя и не могу доказать), что легкость и гибкость таких наших суждений существенно зависит от простоты взаимосвязей между программой и вычислениями… Грубо говоря, можно считать желательным, чтобы структура программы отражалась в структуре вычислений.
Он помог программной индустрии стать намного более дисциплинированной, выдвинув тезис, что оператор «go to» является вредным. Это означало, что чем больше в программе операторов go to, тем труднее разобраться в исходном коде программы.
Для обеспечения указанных легкости и гибкости Дейкстра предлагает проектировать и кодировать программы в соответствии с определенной дисциплиной, названной им структурным программированием. Известно (это математический факт известный как теорема Бема-Якопини), что любую программу можно построить с использованием трех конструкций: следования, ветвления и цикла.
Изображение с сайта itandlife.ru
Дейкстра предложил (одновременно, хотя и независимо с Никлаусом Виртом) представлять программу как иерархическую структуру блоков, каждый из которых выполняет небольшую, но завершенную задачу. Это достигается с помощью механизма процедур и функций.
Идеи структурного программирования, поначалу встреченные с недоверием, довольно скоро завоевали признание (особенно, после создания Никлаусом Виртом языка программирования PASCAL). Более того, эта методика остается актуальной и сегодня (достаточно вспомнить такие популярные языки программирования C, PASCAL или BASIC).
О пользе и вреде Goto
Этому вопросу была посвящена одна из статей на «Хабре».
Против:
1. Использование GOTO — плохой тон.
2. Самый плохой тон — возвращение с помощью метки назад.
3. GOTO — избыточный оператор. Его легко можно заменить циклами и условиями.
4. Вирт и Дейкстра говорят, что GOTO это плохо.
5. GOTO аннулирует многие возможности компилятора по оптимизации управляющих структур, из-за чего код становится медленней и объёмней.
За:
1. Группа взаимоисключающих условий.
2. Принцип вселенской причинности — если где-то есть GOTO, значит он там нужен.
3. Выход из множества циклов одновременно.
4. Конечные автоматы (пример кода).
Память
Дейкстра был активным писателем, его перу (он предпочитал авторучку клавиатуре) принадлежит множество книг и статей, самыми известными из которых являются книги «Дисциплина программирования» и «Заметки по структурному программированию», и статья «О вреде оператора GOTO» (GOTO considered harmful) — классические книги по теории структурного программирования.
Дейкстра продолжал работу в Математическом Центре до тех пор, пока в начале 70-х годов не перешел на работу исследователем в корпорацию Burroughs в США. В 1972 году АСМ наградила Дейкстра премией Тьюринга (ACM Turing Award).
В 1974 году AFIPS удостоила его памятной наградой Гарри Гуда (AFIPS Harry Goode Memorial Award). В начале 1980-х годов Дейкстра переехал в Остин, штат Техас. В 1984 году он был назначен деканом факультета компьютерных наук в Техасском университете.
Эдсгер Вайб Дейкстра является Почетным Иностранным членом Американской Академии гуманитарных, естественных и технических наук. Он также является членом Голландской королевской Академии наук, действительным членом Британского Компьютерного Общества и, наконец, доктором наук Королевского университета в Белфасте.
Изображение с сайта abv24.com
Не от мира сего
В 1957 году женился. В графе «профессия» анкеты, которую положено заполнять при регистрации брака, он написал «программист» — его заставили переписывать документы, заявив, что такой профессии не существует. В результате, как писал Дейкстра: «Хотите — верьте, хотите — нет, но в графе «профессия» моего свидетельства о браке значится забавная запись «физик-теоретик»!».
В обычной жизни Дейкстра был по-хорошему «чудаковат»: предпочитал простую ручку компьютеру, в его доме не было телевизора, он не пользовался мобильным телефоном, не смотрел кино. Он также любил музыку и был хорошим пианистом.
Когда его коллеги подготовили и издали к 60-летнему юбилею специальный сборник, Дейкстра ответил каждому из них личным благодарственным письмом, написанным от руки (а это, между прочим — 61 адресат). Ученому его уровня и положения полагался секретарь, но Дейкстра отказался от этой привилегии и все предпочитал делать сам.
В августе 2002 года Эдсгер Вибе Дейкстра скончался в своем доме в Нидерландах.
