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


    

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

Эдсгер В. Дейкстра
Технологический университет, Эйндховен, Нидерланды

Am. Math. Monthly 81 (1974), 6: 608-612.
Copyright (c) 1974, Mathematical Association of America

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

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

  1. По сравнению с остальными видами интеллектуальной деятельности, математические утверждения стремятся к необыкновенной точности.
  2. Математические утверждения имеют тенденцию быть общими, т.е. они применимы к большому (часто, бесконечному) классу примеров.
  3. Математическое воплощение дисциплины доказательств допускает, что такие утверждения делаются с исключительно высоки уровнем достоверности.

Сила математического метода проистекает из комбинации всех этих трех качеств; и наоборот, когда интеллектуальная деятельность проявляет эти три качества в высокой степени, я, не преувеличивая, называю ее "деятельностью математической природы", независимо от того, знаком ли этот предмет большинству математиков. Другими словами я охотнее применяю выражение "математическая сущность" в смысле "quo modo" ["как" - лат], а не "quod" ["что" - лат].

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

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

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

Наконец, по поводу уровня достоверности его работы. Ну, он должен быть очень высоким по двум причинам. Во-первых, большая и сложная программа может быть создана только при тщательном употреблении правила "Разделяй и властвуй", и, поэтому должна состоять из многих, скажем, из N, компонентов. Если, однако, р - это вероятность того, что отдельный компонент является правильным, то вероятность Р правильности всей совокупности компонентов удовлетворяет чему-то, похожему на P <= pN. Другими словами, если р не стремится к 1, то при большом N Р будет стремиться к 0! Если мы не можем разрабатывать компоненты совершенно правильно, нечего и надеяться, что их совокупность будет работать как надо. Во-вторых, уровень достоверности должен быть очень высоким, если мы, как общество, хотим полагаться на качество алгоритма. И мы так и делаем, когда используем машины для контроля воздушных перевозок, в банках, для мониторинга пациентов в больницах или для предсказания землетрясений.

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

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

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

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

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

Утверждение, что корректность программы может и должна быть заслуживающим доверия доказательством ее правильности, было встречено с большим скептицизмом. (Раньше много людей старой закалки принимали как Закон Природы то, что каждая программа обязана содержать "баги".) Но такой скептицизм, однако, не был лишен смысла.

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

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

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

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

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

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

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

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

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

Когда - и я надеюсь, что я беспристрастен - я сопоставляю это с моим представлением о "стандартном математическом курсе обучения" (каким бы он ни был), я вынужден отметить следующие расхождения:

  1. В стандартном математическом курсе студент хорошо знает (иногда даже очень хорошо знает!) стандартный набор математических концепций, но меньше обучен изобретать собственные концепции.
  2. В стандартном математическом курсе студент хорошо знает (иногда даже очень хорошо знает!) стандартный комплектом нотаций, но он практически не умеет изобрести собственную нотацию, когда в ней возникает необходимость.
  3. В стандартном математическом курсе студент часто видит проблему настолько "маленькой", что он имеет дело с только одним семантическим уровнем. В результате многие студенты видят в математике скорее искусство организации символов на листе бумаги, чем искусство организации своих мыслей.

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


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