1. Введение.
В качестве вступления я хотел бы начать этот разговор с истории и цитаты.
История о физике Людвике Больцмане, который был готов достичь своих целей с помощью длительных вычислений. Однажды кто-то пожаловался на безобразие этих методов, в свою защиту Больцман заявил, что «элегантность — это забота портных и сапожников», подразумевая, что он отказывался от неё.
В отличие от этого я хотел бы процитировать другого известного учёного девятнадцатого века — Джорджа Буля. В середине своей книги «Исследование законов мышления» в главе «Об условиях совершенного метода» он пишет: «Я говорю здесь не только о том совершенстве, которое заключается в силе, но и о том, что также основано на представлении о целостности и гармонии. Вероятно, что тщательный анализ этого вопроса приведёт нас к выводу, что совершенный метод должен быть не только эффективным по отношению к предметам, для которых он предназначен, но должен во всех своих частях и процессах проявлять определённое единство и гармонию ». Вряд ли кто-то не заметит различия в этих подходах.
Наше бессознательная ассоциация элегантности с роскошью может быть одним из источников неявного предположения, что элегантность обходится дорого. Одна из моих главных целей — показать, что элегантность является выгодной. Это даст нам более ясное понимание истинной природы качества программ и того, как они выражаются посредством языка программирования. Из этого понимания мы попытаемся извлечь некоторые подсказки относительно того, какие функции языка программирования наиболее желательны. Наконец, мы надеемся убедить вас, что разные цели противоречат друг другу меньше, чем это кажется на первый взгляд.
2. О качестве результатов.
Даже в предположении о безупречно работающих машинах мы должны задавать себе вопросы: «Когда автоматический компьютер даёт результаты, почему мы им доверяем, если мы вообще это делаем?» и «Какие меры мы можем предпринять, чтобы повысить нашу уверенность в том, что полученные результаты действительно являются намеченными результатами?»
Насколько актуален первый вопрос, можно проиллюстрировать простым, несколько упрощенным примером. Предположим, что математик, интересующийся теорией чисел, имеет в своем распоряжении машину с программой для факторизации чисел. Этот процесс может закончиться одним из двух способов: либо он даёт факторизацию заданного числа, либо отвечает, что данное число простое. Предположим теперь, что наш математик хочет проверить, скажем, двадцатизначное десятичное число, в то время как у него есть веские основания полагать, что это простое число. Если машина подтвердит это ожидание, он будет счастлив; если он обнаружит факторизацию, математик может быть разочарован, потому что его интуиция снова одурачила его, но, если сомневается, он может взять настольную машину и умножить полученные множители, чтобы проверить, воспроизводит ли результат оригинальное число. Однако ситуация резко меняется, если он ожидает, что данное число не является простым: если машина теперь производит множители, он находит свои ожидания подтвержденными и, кроме того, он может проверить результат путем умножения. Однако, если машина возвращается с ответом, что данное число, вопреки его ожиданиям и самым тёплым желаниям, увы, простое число, с какой стати он должен верить этому?
Наш пример показывает, что даже в полностью дискретных задачах вычисление результата не является чётко определённой работой, чётко определённой в том смысле, что можно сказать «Я сделал это», не обращая внимания на убедительную силу результата, то есть его "качества".
Ситуация программиста очень похожа на ситуацию чистого математика, который разрабатывает теорию и доказывает результаты. Долгое время чистые математики думали (и некоторые из них все еще думают), что теорема может быть полностью доказана, что вопрос о том, является ли предполагаемое доказательство теоремы достаточным или нет, допускает абсолютный ответ «да» или «нет» . Но это иллюзия, поскольку, как только кто-то думает, что он что-то доказал, он все равно обязан доказать, что первое доказательство было безупречным и так далее, до бесконечности! Никогда нельзя гарантировать, что доказательство правильное, лучше всего сказать: «Я не обнаружил никаких ошибок». Иногда мы льстим себе идеей предоставления неопровержимых доказательств, но на самом деле мы лишь делаем правильность наших выводов правдоподобной. Настолько правдоподобной, что аналогия может послужить отличным источником вдохновения.
Несмотря на все свои недостатки, математические рассуждения представляют собой выдающуюся модель того, как понять чрезвычайно сложные структуры человеческим мозгом, который от природы имеет ограниченные возможности. И, кажется, стоит исследовать, в какой степени эти проверенные методы могут быть перенесены в искусство использования компьютера. При разработке языков программирования можно руководствоваться в первую очередь размышлением над тем, «что может сделать машина». Однако, учитывая, что язык программирования является мостом между пользователем и машиной (что он может фактически рассматриваться как инструмент), кажется столь же важным учитывать «то, что может думать человек». Именно в этом ключе мы продолжим наши исследования.
3. О структуре убедительных программ.
Техника овладения сложностью известна с древних времен: «Divide et impera» («Разделяй и властвуй»). Аналогия между построением доказательства и построением программы снова поразительна. В обоих случаях указываются доступные исходные точки (аксиомы и существующая теория в сравнении с примитивами и доступными библиотечными программами), в обоих случаях ставится цель (доказываемая теорема в сравнении с желаемой производительностью), в обоих случаях сложность решается делением на части (леммы против подпрограмм и процедур).
Я предполагаю, что гений программиста соответствовал сложности его проблемы, и предполагаю, что он достиг подходящего разбиения задачи на части. Затем он поступает обычным образом на следующих этапах:
а) он делает полные спецификации отдельных частей
б) он удовлетворён тем, что в целом проблема решена, если он имел в своем распоряжении части программы, соответствующие различным спецификациям
в) он конструирует отдельные части, удовлетворяющие спецификациям, но не зависящие друг от друга и от дальнейшего контекста, в котором они будут использоваться.
Очевидно, что создание такой отдельной детали может снова оказаться задачей такой сложности, что внутри этой части работы требуется дополнительное разбиение на части.
Некоторые люди могут подумать, что техника разбиения просто наметила довольно косвенный и извилистый способ достижения своих целей. Мои собственные чувства, возможно, лучше всего описываются словами, что я прекрасно осознаю, что нет никакой Королевской дороги к математике, иными словами, у меня очень маленькая голова, и я должен с этим жить. Поэтому я рассматриваю технику разбиения как один из довольно базовых образцов человеческого понимания и считаю, что стоит попытаться создать обстоятельства, в которых она может быть наиболее плодотворно применена.
Предположение о том, что программист создал подходящее разбиение на части, находит своё отражение в возможности выполнить первые два этапа: спецификацию частей и проверку того, что они вместе выполняют работу. Здесь элегантность, точность, ясность и глубокое понимание проблемы являются обязательными. Но вся техника разбиения основана на чём-то менее откровенном, на том, что я хотел бы назвать «принципом невмешательства». На этапе 2 предполагается, что правильная работа целого может быть установлена только с учетом внешней спецификации для частей, а не с учетом особенностей их внутренней конструкции. На третьем этапе снова возникает принцип невмешательства: здесь предполагается, что отдельные части могут быть задуманы и созданы независимо друг от друга.
Возможно, это тот момент, когда нужно упомянуть, что при условии, что я правильно истолковываю признаки современного отношения к проблемам определения языка, в некоторых более формальных подходах обоснованность техники анализа подвергается сомнению. Их сторонники утверждают следующее: всякий раз, когда вы даете механизму такое двухэтапное определение, сначала, во-первых, должны быть созданы спецификации, а во-вторых, описано, как всё это работает; вы, в лучшем случае, дважды говорили одно и то же, но, по всей вероятности, вы противоречили себе. И, к сожалению, с точки зрения статистики, это последнее замечание является сильной стороной. Они утверждают, что единственный чистый путь к определению языка — это просто определение механизмов, потому что из этого будет следовать то, что они тогда будут делать. Мой вопрос "Как это следует?" мудро оставлен без ответа, и я боюсь, что их пренебрежение тонким, но иногда грандиозным различием между понятиями «определенный» и «известный» сделает их усилия интеллектуальным упражнением, ведущим в другой тупик.
После этой экскурсии мы возвращаемся к самому программированию. Все, кто знаком с ALGOL 60, согласятся с тем, что его концепция процедуры в достаточной степени удовлетворяет нашим требованиям невмешательства как по своим статическим свойствам (например, по свободе выбора локальных идентификаторов), так и по его динамическим свойствам (например, возможность вызывать процедуру, прямо или косвенно, изнутри себя).
Ещё один яркий пример повышения ясности за счет невмешательства, гарантированного структурой, представлен всеми языками программирования, в которых допускаются алгебраические выражения. Вычисление таких выражений с помощью последовательной машины, имеющей арифметическую единицу ограниченной сложности, подразумевает использование временного хранилища для промежуточных результатов. Их анонимность в исходном языке гарантирует невозможность непреднамеренного уничтожения одного из них перед его использованием, как это было бы возможно, если бы вычислительный процесс был описан в машинном коде типа фон Неймана.
4. Сравнение некоторых альтернатив.
Широкое сравнение между машинным кодом типа фон Неймана (хорошо известным своей неясностью) и различными типами алгоритмических языков может быть не лишним.
Во всех случаях выполнение программы состоит из повторяющегося противостояния двух информационных потоков, один (скажем, «программа») постоянен во времени, а другой (скажем, «данные») меняется. В течение многих лет считалось одним из существенных достоинств кода типа фон Неймана, что программа может изменять свои собственные инструкции. Тем временем мы обнаружили, что именно эта возможность в значительной степени ответственна за отсутствие ясности в программах машинного кода. Одновременно с этим была поставлена под сомнение его незаменимость: все известные мне алгебраические компиляторы создают объектную программу, которая остаётся постоянной на протяжении всей фазы выполнения.
Это наблюдение подводит нас к рассмотрению статуса переменной информации. Давайте сначала ограничимся изучением языков программирования без операторов присваивания и без операторов goto . При условии, что спектр допустимых значений функций достаточно широк и концепция условного выражения входит в число доступных примитивов, можно записать вывод каждой программы в качестве значения большой (рекурсивной) функции. Для последовательного компьютера это можно перевести в постоянную объектную программу, в которой во время выполнения используется стек для отслеживания текущей иерархии вызовов и значений фактических параметров, предоставляемых при этих вызовах.
Несмотря на его элегантность, можно сделать серьезные возражения против такого языка программирования. Здесь информацию в стеке можно рассматривать как объекты с вложенным временем жизни и с постоянным значением в течение всего времени их жизни. Нигде (кроме неявного увеличения счетчика инструкций, которое отражает ход времени) значение уже существующего именованного объекта заменяется другим значением. В результате единственный способ сохранить вновь сформированный результат — поместить его на верх стека; у нас нет никакого способа выразить, что более раннее значение становится теперь устаревшим, и время жизни последнего будет продлено, хотя и лишено смысла. Подводя итог: это элегантно, но неадекватно. Второе возражение, которое, вероятно, является прямым следствием первого, состоит в том, что такие программы становятся после определённой, быстро достигаемой степени вложенности, ужасно трудно читать.
Обычным средством защиты является комбинированное введение оператора goto и оператора присваивания. Оператор goto позволяет нам с помощью обратного перехода повторить фрагмент программы, в то время как оператор присваивания может создать необходимую разницу в статусе между последовательными повторениями.
Но у меня есть причины спросить, не является ли оператор goto средством похуже, чем дефект, который он стремился исправить. Например, два менеджера департамента программирования из разных стран и разных профессий (один в основном научный, а другой в основном коммерческий) сообщили мне, независимо друг от друга и по собственной инициативе, о том, что качество их программистов обратно пропорционально плотности появлений goto в их программах. Это был стимул, чтобы попытаться покончить с оператором goto.
Идея состоит в том, что то, что мы знаем как «передача контроля», то есть замена значения счетчика инструкций, является операцией, обычно подразумеваемой как часть более мощных обозначений. Я упомяну переход к следующему утверждению, вызову процедуры и возврату, условным конструкциям и оператору for. И вопрос в том, не сбивается ли с толку программист, получая отдельный контроль над этим.
Я провел различные эксперименты по программированию и сравнил текст ALGOL с текстом, который я получил в модифицированных версиях ALGOL 60, в которых оператор goto был отменён, а оператор for (помпезный и чрезмерно сложный) был заменён предложением примитивного повторения. Последние версии было сложнее сделать: мы настолько хорошо знакомы с порядком прыжков, что требуется некоторое усилие, чтобы его забыть! Однако во всех случаях, когда пытались, программа без операторов goto оказалась короче и понятнее.
Исток увеличения ясности вполне понятен. Как хорошо известно, не существует алгоритма для определения, заканчивается ли данная программа или нет. Другими словами: каждый программист, который хочет создать безупречную программу, должен по крайней мере убедить себя осмотром, что его программа действительно завершится. В программе, в которой было сделано неограниченное использование оператора goto , этот анализ может быть очень сложным из-за большого разнообразия способов, которыми программа может не остановиться. После отмены оператора goto программа может перестать останавливаться только в двух случаях: либо с помощью бесконечной рекурсии (через механизм процедур), либо с помощью оператора повторения. Это значительно упрощает проверку.
Понятие повторения, столь фундаментальное в программировании, имеет ещё одно последствие. Нет ничего необычного в том, что внутри последовательности операторов, подлежащих повторению, есть одно или несколько подвыражений, которые не меняют своего значения во время повторения. Если такую последовательность повторять много раз, было бы прискорбной тратой времени, если бы машине приходилось пересчитывать одни и те же значения снова и снова. Одним из выходов из этого является делегировать оптимизатору обнаружение таких константных подвыражений, чтобы он мог выполнять вычисления их значений вне цикла. Без оптимизирующего транслятора очевидное решение состоит в том, чтобы предложить программисту писать код несколько более явно, и он может сделать это, введя столько дополнительных переменных, сколько постоянных подвыражений в повторении, и присвоив им значения перед вводом повторения. Я хотел бы подчеркнуть, что оба способа написания программы в равной степени вводят в заблуждение. В первом случае транслятор сталкивается с ненужной загадкой для обнаружения постоянства, во втором случае мы ввели переменную, единственной функцией которой является обозначение константы. Последнее наблюдение показывает выход из сложности: помимо переменных программист будет обслуживаться «локальными константами», то есть идентифицируемыми величинами с конечным временем жизни, в течение которых они будут иметь постоянное значение, это было определено в момент введения количества. Такие величины не новы: формальные параметры процедур уже отображают это свойство. Вышесказанное является призывом признать, что понятие «локальная константа» имеет свое право на существование. Если я хорошо осведомлён, это уже было признано в CPL — языке программирования, разработанном совместными усилиями вокруг Математической лаборатории Кембриджского университета в Англии.
5. Двойной выигрыш в ясности.
Я подробно обсуждал, что убедительная сила результатов в значительной степени зависит от ясности программы, от степени, в которой она отражает структуру процесса, который должен быть выполнен. Для тех, кто чувствует себя в основном обеспокоенным эффективностью, измеряемой в более грубых единицах хранения и машинного времени, я хотел бы отметить, что повышение эффективности всегда сводится к эксплуатации структуры. И для них я хотел бы подчеркнуть, что все упомянутые структурные свойства могут быть использованы для повышения эффективности реализации. Я кратко рассмотрю их.
Отношение времени жизни, удовлетворяемое локальным количеством процедур, позволяет нам размещать их в стеке, что позволяет очень эффективно использовать доступное хранилище; анонимность промежуточных результатов позволяет нам динамически минимизировать ссылки на хранилища с помощью автоматически управляемого набора накопительных аккумуляторов; постоянство выполняемого текста программы очень помогает в машинах с различными уровнями хранения и значительно снижает сложность расширенного управления; предложение повторения облегчает динамическое обнаружение бесконечных циклов и, наконец, локальная константа является успешным кандидатом для хранилища с медленной записью и быстрым чтением, когда оно доступно.
Позвольте мне сделать вывод. Когда я познакомился с понятием алгоритмических языков, я никогда не оспаривал преобладающее тогда мнение, что проблемы проектирования и реализации языка были в основном вопросом компромиссов. Каждое новое удобство для пользователя должно было оплачиваться трудоёмкостью его реализации: либо в форме повышенной трудности во время трансляции, либо во время выполнения, либо во время обоих. Что ж, мы, безусловно, не живём на небесах, и я не собираюсь отрицать возможность конфликта между удобством и эффективностью, но сейчас я протестую, когда этот конфликт представляется как полное обобщение ситуации. Я считаю, что стоит исследовать, в какой степени потребности Человека и Машины идут рука об руку, и посмотреть, какие методы мы можем разработать для пользы всех нас. Я верю, что это исследование принесёт плоды, и если этот разговор заставил некоторых из вас разделить эту горячую надежду, он достиг своей цели.
Проф. Д-р Эдсгер В. Дейкстра
Кафедра математически
Технологический университет
POBox 513
EINDHOVEN
Нидерланды
