КаталогИндекс раздела


    

Мои надежды в компьютерной науке

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

My Hopes on Computing Sience
Proc. 4th Int. Conf. On Software Engineering, Sept. 17-19, 1979, Munich, Germany
(EWD 709)

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

"О, нет. Только помни формулы и знай, что ты идешь неправильным путем, если тебе требуется больше пяти строк."

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

Четверть века спустя, формулы по-прежнему пугают меня. Когда я впервые увидел доказательство Хоара для корректности процедуры "FIND", я ужаснулся и объявил, что такой балет символов не является моей "чашкой чая".

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

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

Я могу объяснить эти отношения любви-ненависти только одним способом. Почему я должен продолжать содрогаться над знаками формул, если я вместо этого могу лучше понять их смысл? Я теперь думаю так, я знаю по печальному опыту, что слишком многие математики и ученые-компьютерщики имели несчастье, состоящее в том, что у них не было мудрого совета моей мамы в восприимчивом шестнадцатилетнем возрасте. Слишком часто пятистрочное ограничение игнорируется, и вместо использования компактной формальной записи, сохраняющей текст кратким, авторы используют его - даже в ограниченном пространстве! - для внесения сложности, значительно превышающей ту, с которой я могу чувствовать себя комфортно. Отсюда - мое содрогание. (Я не знаю, какого вы мнения о знаменитом Отчете по алгоритмическому языку ALGOL 60. Я очень восторгаюсь им и думаю, что его слава - весьма заслуженная. Но в ретроспективе я думаю, что синтаксис ALGOL 60, хотя и строго определенный, более вычурный, чем хотелось бы, и, определенно, введение такого большого числа излишеств стало возможным именно из-за компактности BNF.)

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

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

*         *
*

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

Моей первой задачей в Математическом Центре в Амстердаме было написание точной функциональной спецификации для компьютера, который был в разработке. Я сделал это наилучшим образом, которым мог, и сделал это, скорее всего, хорошо - с точки зрения точности. Но было кое-что, что меня шокировало: в течение нескольких дней после его появления мой замечательный отчет стал широко известен как "ужасная проза".

В это время я только чувствовал, что мы должны научиться лучше писать о нашем предмете. Я думаю, что это было не так до 1960 года, когда Петер Наур познакомил нас с известной цитатой из Виттгенатена:

"Мы можем говорить вообще, можем говорить ясно, а о том, о чем мы не можем сказать, мы должны хранить молчание."

которая сразу прояснила мне, что мы, следовательно должны научиться лучше думать о нашем предмете.

Тем временем я получил другой лингвистический шок: я стал членом ACM, незадолго до того, как начали выходить его "Communications". До этого я почти не имел доступа к иностранной литературе. То, что я прочитал, было написано стилем, настолько отличающимся от того, к которому я привык в относительной изоляции, что я был совершенно поражен. Весьма антропоморфная терминология была для меня в новинку и плохо совмещалась с моими культурными корнями; как, например, анимизм, скрывающий термин "bag"; мы никогда не называли баг жуком, мы всегда называли его ошибкой.

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

Еще одно замечание по поводу языка, которое кажется мне важным. Поскольку английский язык стал эсперанто для компьютерной науки, коллеги, для которых английский был родным языком, часто чувствовали себя несколько виноватыми в чем-то, что они рассматривали как незаслуженное преимущество перед большинством иностранцев. Их чувство вины было неуместным, поскольку преимущество было у нас. Была очень полезной необходимость делать вашу работу на языке, который оставался для вас иностранным, поскольку это заставляло вас выражаться более сознательно. (Я думаю, что самой превосходной прозой, написанной в нашей области, должен считаться упоминавшийся Отчет по ALGOL 60: его редактор имел то преимущество быть - кроме того, что он выдающийся человек - датчанином. Я всегда чувствовал, что стабильность и заслуженная слава ALGOL 60 во многом происходит непосредственно от непоколебимой точности английского языка Петера Наура.)

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

Почему нас привлекает область автоматизированных вычислений? Почему мы продолжаем ею восхищаться? Что на самом деле является ядром компьютерной науки?

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

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

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

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

Я чрезвычайно сожалею о том, что использовал термин "понятность" в комбинации "легкий для понимания", которая вводит путаницу тем, что не призывает тщательно определять различия между подходящим (convenient) и общепринятым (conventional), а эти различия являются, боюсь, жизненно важными: я ожидаю от ученых-компьютерщиков наиболее подходящего стиля мышления и понимания, а не общепринятого. (Это не слишком неожиданно, как-никак, мышление - это только привычка и должны ли мы ожидать от наших старых привычек, что они будут адекватными, встретившись впервые в нашей культуре с миром радикально новый рассуждений?)

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

  1. отделение от конкретных вещей и эффективное использование абстракции;
  2. разработка и использование нотаций, предназначенных для нужного нам манипулирования;
  3. отмена анализа частных случаев, в частности, комбинаторного взрыва их.

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

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

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

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

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

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

Масштаб проблем обучения громадный. Если вы согласны с этим - а я думаю, вы должны согласиться, - мое благословение с вами. Оно - и многое еще! - вам понадобиться, потому что вы столкнетесь с огромными препятствиями на своем пути. Вы должны будете победить, по крайней мере, двух драконов. Люди, путающие "любовь к совершенству" и "требование совершенства" будут обвинять вас в последнем, а затем осуждать вас за первое. Более того, вопреки всем свидетельствам обратного, возможность обучения эффективному мышлению будет категорически отрицаться, и ваш методологический вклад - необходимый более, чем что угодно другое - будет объявлен "только для гениев": помните, когда будете сражаться с этим вторым драконом, что чаше всего слово "гений" используется не как комплимент, а только как оправдание для лености ума.

*         *
*

Для благополучного будущего компьютерной науки - как и любой другой науки - существенно, чтобы ее достижения были хорошо опубликованы, чтобы следующее поколение могло начать оттуда, где остановилось предыдущее. Выше я выразил некоторое мое неудовлетворение по поводу современных публикаций в нашей области. Это очень серьезная проблема и это более чем чисто образовательная проблема. Как мы публикуем сложную часть программного обеспечения? (Мы можем воспроизвести код, но он пригоден только для механического выполнения. Я понимаю "опубликовать" в научном смысле: наш текст должен полностью все объяснять для внимательного читателя.) Конечно же, многие статьи по алгоритмам могут уже сейчас писаться значительно лучше, но никто не знает, как это сделать! И эта общая неспособность делает эту техническую проблему неотложной и неразрешимой. Одна из моих страстных надежд - в том, что мы решим ее.

Как должна выглядеть публикация, посвященная сложной части программного обеспечения? Мы еще не знаем этого, но две вещи кажутся определенными. Во-первых, текст будет "математическим" в том смысле, который вкладывал в это понятие Морис Клайн:

"Более, чем чем-либо другим, математика является методом."

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

В отношениях между математикой и компьютерной наукой последнее было до сих пор скрыто, и мне кажется, что пришло время вернуть наши долги. Помимо расширения рамок применяемости математических приемов (как показано выше), мы можем также изменить их традиционные приложения. Когда наконец исчисление предикатов станет обязательным инструментом в повседневных рассуждениях математиков всех сортов, когда замена асимметричного включения на симметричную дизъюнкцию будет лишено названия "сокращение до абсурда" из-за своего специального статуса и эквивалентность не будет выражаться нескладным "тогда и только тогда", когда математики обогатятся огромным разнообразием индуктивных аргументов, во всех этих случаях такая эволюция может быть прослежена как благотворное влияние компьютерной науки.

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

Как хорошо мы, например, можем разделять вопросы корректности и вопросы эффективности? Оба вопроса являются настолько "главными", что я не верю в то, что тут может быть значительный прогресс, если только мы не научимся разделять их полностью.

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

Эта трудность не должна недооцениваться: это все равно, что попросить среднего математика объяснить евклидову геометрию, не рисуя картинок. Морис Клайн отмечает:

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

Аналогия почти совершенная: картинки являются для геометрии тем, что истории вычислений ("трассировки") являются для компьютерной науки, "и нам не запрещается рассуждать без них". Но привычки к операционному мышлению прочно укоренились во многих широко распространенных традициях от теории автоматов, через LISP до FORTRAN'а и BASIC'а, и многие люди, включая ученых-компьютерщиков, обучались при помощи трассировок "как опоры и обнаруживают для себя невозможность ходить без этой подпорки". В случае унипрограммирования трассировка, являющаяся линейной последовательностью состояний и событий, является осуществимой и "полезной", как картинка в двух- и трехмерной геометрии. Но в случае мультипрограммирования трассировки неосуществимы и "подпорка не годится".

Для евклидовой геометрии аналитические методы Декарта, представили альтернативу для подпорки, а в аналитической геометрии обобщение от трех на большее число измерений технически происходит очень плавно. В программировании основанные на постулатах методы Флойда и Хоара обеспечили альтернативу для подпорки; в унипрограммировании они делали это очень успешно, но их обобщение на мультипрограммирование является - насколько я знаю, и на тот момент, когда это пишется - менее гладким, хотя после успешного начала Гриса и Уики я не имею ни малейших сомнений в том, что в долговременном плане оно будет весьма успешным. Необходимость очень аккуратно очерчивать "точечные действия" является новым аспектом игры; открытие Лоу дало конструкторам большую свободу во встраивании в пространство и время действий, вовлеченных в реализацию единичных точечных действий. (Одним из способов, которыми мы можем оценить очевидно большую трудность разработки мультипрограмм, является то, что конструктор заинтересован в гораздо большей свободе: при каких обстоятельствах, например, ему разрешается реализовать в точечное действие распределенной системе - при наличии другого трафика! - действием в узле A, за которым следует "медленное" сообщение из A в B и, наконец, после принятия сообщения, некоторое действие в B?)

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

*         *
*

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

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

Другим является чувствительность к рынку, бесспорная уверенность в том, что промышленные продукты, только потому, что они являются таковыми, становятся, благодаря своему существованию, предметом, достойным научного внимания, независимо от того, какой могильник ошибок в них встроен. В шестидесятые годы сражение, в котором нужно было защитить компьютерную науку от вырождения в "как нам жить с IBM 360" было выиграно, и "курсы" - обычно "углубленные"! - по MVS (или что у там вас есть) теперь ограничены не очень представительной субкультурой коммерческого обучения. Но теперь мы слышим, что появление микропроцессоров должно произвести революцию в компьютерной науке! Я не верю, в это, за исключением того, что погоня за сиюминутным запутает уже сделанное. Возможно, понадобится такое же сражение.

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

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

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

За расцвет абстрактных типов данных я несу некоторую со-ответственность, придумав и пустив в обиход термин "представительная абстракция" в 1972 году, и если он превратился в ошибку, то часть вины лежит на мне. Одна возможность того, что он может быть ошибкой, происходит из того факта, что он является некоторым приукрашиванием состояния; после пяти лет интенсивных исследований и разработок, стек является единственным из разработанных абстрактных типов данных. Это сильно отличается от того, что случилось, когда было введено то, что его вдохновило, - законченные подпрограммы! Для этих печальных до сих пор результатов исследований, посвященных абстрактным типам данных, я могу на моей нынешней стадии понимания предложить два приблизительных объяснения. Одно состоит просто в том, что абстрактные типы данных значительно более сложны, так что их значительно труднее специфицировать, чем подпрограммы, что на порядок труднее придумать полезный тип. (Если это именно тот случай, я должен только подождать.) Другое состоит в том, что после того, как все сказано и рассказано, тип интерфейса, обеспечиваемого абстрактным типом данных, не подходит для его назначения: когда мы тщательно анализируем действительно сложные алгоритмы, мы вполне можем обнаружить, что доказательство корректности не допускает деления на части, тогда как одна или две части могут быть спокойно идентифицированы при помощи абстрактного типа данных. Другими словами, надежда на то, что абстрактные типы данных будут нам очень помогать, вполне может базироваться на недооценке логической сложности сложных алгоритмов и, следовательно, чрезмерно упрощенного подхода к процессу проектирования программ.

Преобразования программ - каждое из которых воплощается в теореме! - рассматривались как кандидаты, которые могут внести необходимую совокупность знаний. Надежды состоят в том, что преобразования из небольшой библиотеки обеспечат путь от наивной, неэффективной, но очевидно корректной программы к сложному и эффективному решению. Теперь я вижу, как через преобразование программ может быть достигнут выигрыш в эффективности за счет устранения необходимости повторных вычислений одних и тех же промежуточных результатов, даже в ситуации, когда эта возможность - заметьте, что промежуточные результаты никогда не являются частью исходного оператора программы! - на первый взгляд неожиданна. И еще моя надежда сдержана по такой причине: когда, в противоположность корректности естественного алгоритма, с которого мы начинаем, корректность эффективного алгоритма критично зависит от (возможно, углубленной) математической теоремы, цепочка преобразований будет составлять подтверждение последней, а, насколько я знаю, механическая верификация доказательств является очень громоздкой и, наверное, такой и останется. Я боюсь, что большие надежды на преобразование программ могут базироваться только на том, что кажется мне недооценкой логического баланса, который требуется для оправдания действительно эффективных алгоритмов. Определенно верно, что каждое преобразование программы воплощает теорему, но та ли эта теорема, которая может внести значительный вклад в совокупность знаний и понимание, которые дадут нам зрелость? Я сомневаюсь, поскольку многие из них являются слишком тривиальными и слишком привязанными к нотации программ.

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

В моих скитаниях по земному шару я узнал, что только несколько человек склонны помочь мне начать и поддерживать беседу по очень узкому вопросу: "Профессор, Дейкстра, какими исследованиями вы сейчас занимаетесь?" Я научился бояться этого вопроса, поскольку он заставляет меня онеметь или, в лучшем случае, заикаться. Как-то я решил, что я лучше придумаю заготовленный ответ на него, и одно время использовал и короткий, и правдивый ответ: "Программирование". Обычный ответ, который я получал, был очень показательным: "О, понимаю, языки программирования", и когда я отвечал: "Нет, программирование," - мой доброжелательный собеседник нечасто замечал, что его поправили.

В ACM есть специальная группа по интересам по языкам программирования, но нет по программированию как таковому; ее новейшее периодическое издание посвящено языкам программирования и системам, но не программированию как таковому. Сообщество компьютерной науки почти болезненно зафиксировалось на программной нотации, оно подразделилось на столько субкультур, сколько мы имеем более или менее принятых языков программирования, субкультур, из которых ни одна не делает различия между истинными проблемами и проблемами, порожденными языком программирования, который она приняла (иногда почти как религию). Для этой болезненной фиксации я могу предложить одно объяснение: мы полностью осознаем, что в нашей работе, возможно, более, чем где-либо еще, подходящие нотационные соглашения являются критичными, но также: мы более, чем кто-либо страдаем от общего непонимания их важной роли.

Проблема, конечно, более общая: каждый опытный математик знает, что достижения критически зависят от наличия подходящей нотации. Кто-то может отсюда простодушно предположить, что разработка подходящей нотации должна быть центральной темой математической методологии. Удивительно, что традиционный математический мир плохо принимает во внимание эту тему. Нескладные нотационные соглашения прижились во многих математических публикациях, оставляя место для одного только заключения: математиков даже не обучают, как выбрать подходящую нотацию из имеющихся, не говоря уже о разработке новой при необходимости.

Это удивительное молчание математиков о том, что является сердцем их ремесла, наводит на мысль о том, что сказать о нем что-то осмысленное - трудная задача. (Иначе они бы сделали это.) И я могу объяснить это только тем фактом, что традиционный математик всегда прибегать к естественному языку, при помощи которого он может склеить свои формулы вместе.

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

 

Nuenen, апрель 1979


КаталогИндекс раздела