1

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

Избранные статьи

Перевод выполнил Alf ([email protected]).

Первоисточник: http://shelek.com/

Публикуется на OberonCore.ru

с любезного разрешения переводчика.

2

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

Избранные статьи

Программирование как вид человеческой деятельности

Навстречу корректным программам

Смиренный программист

Два взгляда на программирование

Почему программное обеспечение такое дорогое?

О природе информатики

Научная фантастика и научная реальность в информатике

Почему американская информатика кажется неизлечимой

Конец Информатики?

Ответы на вопросы студентов отделения программного обеспечения

3 О переводах или От редактора перевода.

Уважаемые читатели!

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

Почему именно Дейкстра Как-то само собой так сложилось, что в России Дейкстру обходили и продолжали обходить вниманием.

Впервые я познакомился с его трудами много лет назад, благодаря моему университетскому научному руководителю Владиславу Вениаминовичу Кривицкому, которому я столь многим обязан в своем профессиональном становлении. Он доставал какими-то неведомыми мне путями (учитывая, что слова «персональный» и «компьютер»

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

Названия некоторых из этих статей я помню до сих пор: «Смиренный программист», «Как быть, если правда колет глаза», «Почему программное обеспечение такое дорогое»… Отечественное книгоиздание почему-то не баловало нас книгами Дейкстры. Из огромного множества его работ переведены и изданы в тогдашнем СССР были буквально считанные единицы, да и те достать было весьма трудно. Издавали Кнута, Вирта, Ульмана, Цикритзиса… Дейкстру упорно игнорировали.

Наступили другие времена, но положение существенно не изменилось. Посмотрим на полки в отделе компьютерной литературы книжного магазина: «HTML для чайников», «Освой С++ за 5 минут»… Концептуальных книг не прибавилось.

Окончательное решение взяться за самостоятельный перевод возникло, когда мне попалась статья "Ремесленник или ученый?". После ее прочтения захотелось собрать у себя побольше столь же мудрых статей, чтобы было что почитать между изучением весьма полезных, но столь же и скучных справочных мануалов по.NET или MFC.

Я был просто поражен тем, что поиск в Сети почти не принес результатов. Нашлись «Как быть, если правда колет глаза» и «Притча», добросовестно передираемые друг у друга неутомимыми создателями «хоумпагов» и используемые для заполнения скудного раздела «Юмор» (видимо, они решили, что Дейкстра – писатель-юморист сродни Марку Твену или Джерому). Нашлась та самая статья в «Компьютерре». Подключились другие форумчане, нашли еще с пяток крошечных статей. И все! За прошедшие годы утеряно даже то немногое, что передавалось друг другу на 1200-футовых бобинах магнитной ленты… Единственный выход – браться за дело самим. Что после некоторой раскачки и было сделано.

К счастью, оказалось, что университет штата Техас бережно хранит наследие своего почетного профессора. Бумаги, которые остались после смерти Дейкстры в 2002 г., были отсканированы и опубликованы на сайте университета. Осталось только выбрать наиболее интересные из них, перевести и опубликовать на сайте Грома.

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

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

О стиле перевода Разумеется, по возможности я старался придерживаться дословного перевода, не отступая от авторского текста. Тем не менее не всегда это удавалось.

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

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

Кому и зачем это нужно сегодня Многие, наверное, зададут этот вопрос. И неудивительно. Ведь уже не одно десятилетие действует закон Мура, согласно которому количество транзисторов на кристалле удваивается каждые полтора-два года, а следом за ним – и производительность процессоров на их основе. Вычислительная мощность, сконцентрированная сегодня в системном блоке персонального компьютера на рабочем столе секретарши, многократно перекрывает мощность крупного вычислительного центра 70-х годов XX века. Давно забыты перфокарты и магнитные барабаны. Программирование тоже прошло огромный путь от автокодов до сложнейших и в то же время весьма облегчающих жизнь программиста систем вроде Visual Studio.NET.

Казалось бы, чему может научить нас человек, большинство работ которого написаны 20-30 лет назад и более? Ведь изменилось все: оборудование, языки программирования, операционные системы… Оказывается, как и в любой науке, в информатике есть истины, которые, будучи открыты, сохраняются неограниченно долго. И Дейкстра был один из немногих, кто подошел к новой дисциплине – программированию – не как ремесленник и даже не как инженер, а как настоящий ученый, виртуозно владеющий математическим аппаратом (сказалась подготовка физика-теоретика) и системным подходом.

Чему же учил нас Эдсгер Дейкстра? Прежде всего, он настаивал на том, что программист-профессионал обязан владеть математическим инструментарием. Особенно это относится к математической логике, поскольку помимо умения писать программы, нужно также при необходимости уметь и доказать их правильность. Разумеется, и сам он был в этом образцом, его математической эрудиции можно только позавидовать.

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

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

Программирование как вид человеческой деятельности Введение В качестве введения мне хотелось бы начать разговор с истории и цитат. История эта – о физике Людвиге Больцмане, который хотел достичь своих результатов путем громоздких вычислений. Кто-то однажды пожаловался на то, что его методы ужасны, на что Больцман заявил, что «об элегантности должны заботиться портные и сапожники», дав тем самым понять, что его самого это никоим образом не беспокоит.

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

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

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

«Когда компьютер выдает результаты, почему мы должны им доверять, если только мы им действительно доверяем?», а затем: «Какие меры мы можем предпринять, чтобы повысить степень нашей уверенности в том, что выданные результаты – это то, что нам нужно на самом деле?».

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

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

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

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

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

Несмотря на все свои недостатки, математические рассуждения представляют замечательную модель того, как можно охватить чрезвычайно сложные структуры посредством мозга, возможности которого ограничены. Кажется, стоит разобраться, до какой степени эти проверенные методы могут быть перенесены в искусство использования компьютеров. В разработке языков программирования можно позволить себе руководствоваться в первую очередь тем, «что машина может делать». Впрочем, учитывая, что язык программирования – это мост между пользователем и машиной и фактически может рассматриваться как его инструмент, кажется столь же важным рассматривать, «что Человек может придумать». Именно в этом русле мы продолжим наше исследование.

О структуре убедительных программ Техника управления сложностью известна с древних времен: “Divide et impera” (разделяй и властвуй). Аналогия между построением доказательства и построением программы, пожалуй, просто поразительна. В обоих случаях даны отправные точки (аксиомы и существующая теория против примитивов и доступных библиотечных программ), в обоих случаях задана цель (доказанная теорема против желаемых результатов), в обоих случаях сложность преодолевается делением на части (леммы против подпрограмм и процедур).

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

1. Он разрабатывает полные спецификации отдельных частей.

2. Он убеждается, что проблема в целом решается при наличии в его распоряжении частей программы, удовлетворяющих этим спецификациям.

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

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

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

Предположение о том, что программист сделал подходящее разбиение, находит подтверждение в том, что становится возможным выполнить первые два этапа:

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

Возможно, здесь уместно заметить, что если я правильно понял нынешнее отношение к проблеме определения языка, при несколько более формальном подходе состоятельность техники разбиения подвергается сомнению. Те, кто выдвигает возражения, аргументируют свою точку зрения следующим образом. Когда вы используете механизм, подобный описанному двухэтапному, во-первых, должны быть созданы спецификации, а во-вторых, описано, как все это работает. При этом вы вынуждены в лучшем случае сказать дважды одно и то же, но вероятнее всего, вы придете к противоречию. С точки зрения статистики, как ни грустно мне об этом говорить, последнее замечание достаточно серьезно. Единственный ясный путь к определению языка, возражают они, это просто определение механизмов, потому что все, что они будут делать, следует из этого. Мой вопрос: «А как оно следует?» мудро оставляют без ответа, и я боюсь, что это тонкое, но порой значительное различие между понятиями «определено»

и «известно» сделают их работу интеллектуальным упражнением, которое ведет в тупик.

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

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

Сравнение некоторых альтернатив Развернутое сравнение кода машины Фон-неймановского типа – хорошо известное отсутствием ясности – и различных типов алгоритмических языков было бы не лишним.

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

Это наблюдение приводит нас к рассмотрению статуса переменной информации.

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

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

Обычное средство от этого – совместное введение операторов присвоения и goto.

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

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

Идея состоит в следующем: то, то нам известно как «передача управления», т.е.

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

Я поставил несколько программных экспериментов и сравнил текст на ALGOL с текстом, полученным мной на модифицированной версии ALGOL 60, в котором оператор goto был упразднен, а оператор for – будучи слишком помпезным и сложным – заменен более простой конструкцией повтора. Последние версии было потруднее создавать: мы так хорошо знакомы с командой перехода, что требовались некоторые усилия, чтобы забыть его! Во всех попытках, впрочем, программы без goto оказались короче и понятнее.

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

Понятие цикла, столь фундаментальное в программировании, имеет еще один аспект.

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

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

Последнее рассмотрение указывает выход из этого затруднения: помимо переменных, в распоряжении программиста должны быть «локальные константы», т.е.

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

Вышеупомянутое – это призыв осознать, что концепция «локальной константы» имеет право на существование. Если меня правильно информировали, это уже было заложено в CPL, язык программирования, разработанный совместными усилиями в математической лаборатории Кембриджского университета в Англии.

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

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

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

Prof. Dr. E.W.Dijkstra Department of Mathematics Technological University P.O.Box

EINDHOVEN

The Netherlands Навстречу корректным программам Цель данного документа – отметить, какие вспомогательные средства для нашего интеллекта мы имеем в своем распоряжении для разработки и понимания алгоритмов, продемонстрировать некоторые приемы программирования, которые мы можем попытаться применить к своим задачам без ущерба для понимания, и подчеркнуть потребность в том, чтобы наши программы (т.е. окончательные и промежуточные версии) как можно точнее отражали наше понимание задачи и алгоритма ее решения.

Среди вспомогательных средств для интеллекта я особо хотел бы упомянуть три:

1. Перечисление.

2. Математическая индукция.

3. Абстракция.

Я рассматриваю как применение Перечисления умственные усилия, необходимые для понимания либо последовательной программы, выполняющей фиксированную временную последовательность действий, либо условного оператора, либо оператора выбора (так называемая «конструкция case»). Я считаю, что одно из основных свойств человеческого разума – плохая способность к перечислению. В частности, это означает:

1a) что текст, описывающий фрагмент последовательной программы, должен выполнять небольшое количество действий (то есть соответствующие вычисления могут быть сгруппированы и восприняты как небольшое количество действий, последовательных во времени);

1b) что количество альтернативных ветвей в операторе выбора должно быть невелико.

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

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

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

Лайтманс показал, что эта циклическая задача эквивалентна следующей линейной задаче. Задан линейный массив на 36 позиций; нужно составить программу, находящую все способы (если они есть), которыми эти позиции могут быть заполнены нулями и единицами (по одной цифре в каждой позиции) таким образом, что 32 пятерки, составленные из смежных позиций, представляют 32 различных шаблона пяти двоичных цифр. Мы можем ограничиться последовательностями, начинающимися с пяти нулей, при этом 32 начальные цифры решения линейной задачи представляют решение циклической, и наоборот. [Доказательство Лайтманса выглядит следующим образом. Каждое решение линейной задачи начинается с 000001…, потому что последовательность 00000 может встретиться только единожды; кроме того, последовательность 10000 также может встретиться только единожды. Поскольку за этими последовательностями могут идти только 00000 или 00001 (уже имеющиеся в первых двух пятерках), то последовательность 10000 не может встретиться в середине линейной последовательности и поэтому может появиться только в конце. В результате каждое решение линейной задачи заканчивается четырьмя нулями, и таким образом кольцо замыкается!]. Мы должны решить линейную задачу, наложив дополнительное условие, что решения (если их несколько) должны выдаваться в алфавитном порядке.

Самое грубое описание программы – это единственная инструкция.

Версия 0:

«выполни всю работу».

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

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

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

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

Определим «длину последовательности» как количество пятерок, которое она содержит (то есть длина = число цифр – 4). Будем называть последовательность «приемлемой», если никакие две различные пятерки в ней не представляют одинаковых цепочек цифр. С такими определениями решения – это подмножество множества приемлемых последовательностей, а именно те, у которых длина = 32.

Мы не знаем, существуют ли решения вообще, но зато знаем, что множество приемлемых последовательностей не пусто (например, «00000»); у нас нет готового критерия для распознавания «последнего решения », когда мы его достигнем в нашем наборе приемлемых последовательностей; впрочем, мы можем пометить «виртуальное последнее решение» (а именно «00001»): когда оно достигнуто, мы знаем, что все приемлемые последовательности с пятью ведущими нулями просмотрены и что больше решений найдено не будет. Подытожим, что мы знаем о множестве приемлемых последовательностей:

1. Оно непустое и конечное.

2. Мы знаем первый член («00000»).

3. Мы знаем виртуальный последний член («00001») 4. Мы можем преобразовать приемлемую последовательность в следующую приемлемую последовательность 5. Решения – это все приемлемые последовательности (кроме виртуальной), удовлетворяющие условию «длина последовательности равна 32».

Переход от рассмотрения только набора решений к рассмотрению набора приемлемых последовательностей явился следующим шагом в нашем анализе, который является первым улучшением: программой, в которой инструкции оперируют объектом (все еще достаточно абстрактным), называемым «последовательностью».

Версия 1:

Установить последовательность на первую приемлемую;

repeat if длина последовательности = 32 do принять последовательность как решение;

преобразовать последовательность в следующую приемлемую until последовательность – это (первый или) виртуальный последний член Для пояснения этой программы уместно было бы сделать пару замечаний.

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

Замечание 2. Оператор «принять последовательность как решение» может изрядно озадачить читателя. Он вполне может оказаться пустым. Он включен в тест затем, чтобы подчеркнуть, что за «следующей точкой с запятой» последовательность рассматривается как представляющая решение. (Можно представить его себе как вытаскивание первых цифр).

Критерий «приемлемости» имеет важное свойство:

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

Преобразовать последовательность в следующую приемлемую:

преобразовать приемлемую-последовательность в следующую потенциальноприемлемую-последовательность ;

while потенциально-приемлемая-последовательность не является приемлемой do преобразовать потенциально-приемлемую-последовательность в следующую потенциально-приемлемую-последовательность ;

принять последовательность как приемлемую Когда мы рассматриваем «преобразовать последовательность в следующую приемлемую» как доступный примитив, значение «последовательности» всегда приемлемо; только лишь при рассмотрении его внутреннего строения – в данном случае возле точки с запятой в предыдущем фрагменте – текущее значение «последовательности» - это потенциально-приемлемая-последовательность.

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

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

преобразовать приемлемую-последовательность в следующую потенциальноприемлемую-последовательность:

while последовательность заканчивается единицей do удалить последнюю цифру из последовательности;

заменить последний нуль единицей В приведенных выше пошаговых усовершенствованиях программы мы сосредоточили внимание на действиях программы с последовательностью. Теперь пора более явно представить решения, как в действительности должен быть представлен абстрактный объект под названием «последовательность». Введем integer k и положим k = длина последовательности. Затем введем integer array d[-3:33] для представления цифр, при этом d[-3] d[-2] ……. d[k] представляют последовательность. (1) Замечание 1: с d[-3] по d[0] должны быть равны нулю.

Замечание 2: Максимальная длина приемлемой-последовательности = 32; так как алгоритм оперирует с потенциально-приемлемыми-последовательностями и потенциально-приемлемая-последовательность – это приемлемаяпоследовательность, дополненная одной цифрой, то максимальная длина последовательности – 33.

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