Более детальные проектные рассмотрения
Предыдущие разделы (в частности, "Первый пример поэтапного составления программы") вызывали критические замечания о том, что я слишком упрощенно трактую процесс проектирования программ, доходя почти до грани мошенничества. Я не считаю эту критику совсем безосновательной и, чтобы исправить дело, разберу два примера более детально. Первый пример придуман мною. Я испробовал его на нескольких устных экзаменах, а впоследствии закончил им свой лекционный курс "Введение в искусство программирования". Я поставил эту задачу перед аудиторией из пятидесяти человек, и все вместе, с моим направляющим участием, они решили ее в течение 90 минут.
Мы рассматриваем множество символов, состоящее из букв, пробела (пр) и точки (тчк). Слова образуются из одной или нескольких, но не более чем из двадцати букв. Входной текст состоит из одного или нескольких слов; соседние слова разделяются одним или несколькими пробелами; за последним словом может следовать любое число пробелов (в частности, нуль), и весь входной текст заканчивается точкой. С помощью символьной функции ЧОС (Чтение очередного символа) следует прочесть входной текст от первой буквы первого слова и до завершающей точки включительно.
Для выдачи выходного текста нужно использовать элементарную функцию ПОС(х) (т, е. Печать очередного символа) с символьным значением параметра. Если бы задача программы состояла в том, чтобы копировать текст, то годилась бы следующая программа (в предположении, что мы умеем работать с переменными, принимающими символьные значения):
char x; repeat х:=ЧОС; ПОС(x) until x= тчк
Однако в этом примере текст нужно подвергнуть следующему преобразованию:
в выходном тексте соседние слова должны разделяться одним пробелом; в выходном тексте сразу же за последним словом должна стоять одиночная точка; если присвоить словам номера 0, 1,2, 3, ... в порядке слева направо (т. е. в том порядке, в каком они считываются при повторяемом вычислении функции ЧОС), то слова с четными номерами должны копироваться, тогда как буквы из слов с нечетными номерами должны печататься в обратном порядке.
Например, входной текст
"эта---программа-никуда-не-годится--",
нужно преобразовать в вид
"эта-аммаргорп-никуда-ен-годится."
(Здесь "-" используется для представления пробела). Я самым искренним образом советую читателям прежде, чем читать дальше, попытаться составить эту программу самостоятельно и записать свои соображения в таком виде, чтобы можно было сравнить их с тем, что я предложу далее. (У опытного программиста это должно занять гораздо меньше времени, чем 90 минут.) Поскольку неизвестна длина непустого входного текста, представляется естественной следующая структура программы:
увертюра; repeat нечто until готово; финал
Однако сразу встает вопрос: "С чем же мы имеем дело, когда однократно выполняем "нечто"?" Возникают четыре предположения. Это может оказаться
одним символом входного текста; одним символом выходного текста; словом (из обоих текстов); двумя соседними словами (из обоих текстов).
Первые два предположения сразу же были отвергнуты без особых объяснений, хотя (а может быть, потому что) объяснить это нетрудно. (Первый вариант не подходит из-за того, что за счет очередного символа входного текста можно выработать самое различное количество выходной информации; аналогичное возражение справедливо и для второго предположения. Помимо всего прочего, программа с циклом в цикле оказывается в общем случае более наглядной, а это наводит на мысль искать более крупные части.) Аудитория отвергла четвертое предположение на том основании, что завершающая точка могла бы с такой же вероятностью оказаться после нечетного числа слов, как и после четного. Чтобы выявить выбор третьего варианта, мы написали на доске:
увертюра; repeat обработать очередное слово until чтение точки; финал
Все были удовлетворены, поскольку эта программа четко выражает тот факт, что мы имеем дело с выходными словами точно в том порядке, в каком читаются соответствующие входные слова; однако в ней не отражено, что половина слов должна печататься в перевернутом виде.
Это было указано слушателям, после чего они быстро ввели соответствующую специальную переменную. Сначала поступило предложение подсчитывать число обработанных слов и выполнять обработку в зависимости от четности или нечетности содержимого этого счетчика, но кислое выражение моего лица оказалось достаточным для догадки, что в этой ситуации лучше воспользоваться логической переменной. Решили, что "увертюра" должна включать
вперед:=true
а в операции "обработать очередное слово" нужно вслед за печатью, порядок которой зависит от текущего значения "вперед", выполнить
вперед:=non вперед
Меня очень обрадовало, что они ввели переменную "вперед" до того, как стали вникать в подробности отделения слов, которыми они занялись потом. У них ушло больше времени на то, чтобы осознать, что дальнейшая конкретизация действия "обработать очередное слово" требует точного описания тех символов входного текста, которые предполагается читать, и тех символов выходного текста, которые предполагается печатать при выполнении повторяемого оператора. В действительности мне пришлось обратить их внимание на это обстоятельство, после чего я спросил их, в каком из двух текстов организация групп представляется более естественной. Они предпочли выходной текст и выбрали следующую организацию групп (указывая разделение вертикальной чертой):
|эта-|аммаргорп-|никуда-|ен-|годится.|
т, е. разбиение на слова, сопровождаемые соответствующим разделителем. Затем я попросил организовать соответствующие группы из входных символов. Сосредоточив внимание на разделителях, они предложили следующее разделение входных символов (справа налево!):
|эта---п|рограмма--н|икуда-н|е--г|одится--.|
так как один из них заметил, что нашей программе достаточно "знать", что за выходным словом нужно ставить пробел, "увидев" первую букву следующего входного слова. Я хранил молчание, предоставив им разобраться в выбранной ими организации групп символов, пока один из них не обнаружил, что особая организация группы символов для первого входного слова является неизящной и что группы следует организовать так:
э|та---п|рограмма--н|икуда-н|е--г|одится--.|
т.е. что первый символ первого слова должен быть прочтен в увертюре. Была введена еще одна переменная, и у нас получилась следующая программа:
boolean вперед; char x; вперед:=true; х:=ЧОС; repeat обработать очередное слово; вперед:=non вперед until х=тчк
Здесь вторая строка представляет увертюру. В то же время мы решили, что финал может быть пустым. Этот этап был достигнут после первых 45 минут, и затем последовал небольшой перерыв. Лично я сознавал, что проблема уже решена и что остальное - дело техники. Однако моя аудитория оказалась недостаточно опытной, и на завершение программы ушли все последующие 45 минут. Слушатели единодушно решили ввести массив
char array с [1:20]
для запоминания букв из слова. (Никто не заметил, что считывание букв и выдача их в обратном порядке на печать могли выполняться рекурсивной программой.) В сущности, нужно производить четыре действия: читать буквы из слова, печатать буквы из слова, читать информацию, необходимую для выбора печатаемого разделителя, и печатать этот разделитель. Я не перечислял эти четыре действия и не спрашивал у слушателей, как бы они решили вопрос о том, как эти действия будут группироваться или объединяться. Аудитория решила, что следует сначала все прочитать, а затем все напечатать. (Вряд ли такое решение можно считать разумным.)
Пытаясь конкретизировать процессы чтения и печати, они столкнулись с неожиданным препятствием. По крайней мере меня удивило, как медленно до них доходило, что требуется еще определить взаимосвязь между чтением и печатью для передачи обрабатываемых слов независимо от того, что эта взаимосвязь тривиальна. Прошло довольно много времени, прежде чем все осознали, что значение с[i] следует приравнять t-й букве из слова, читаемого слева направо. Чуть ли не половина слушателей недоумевала, из-за чего мы суетимся, но потребовалось много времени и на то, чтобы установить, что требуется также некоторая форма представления длины слова.
Никто не предложил использовать для этого запоминание разделителя; они ввели специальную целую переменную "l" для подсчета числа букв в слове. Было решено, что первое слово "эта" следует представлять следующим образом:
с[1]="э", с[2]="т", с[3]="а" и l=3.
Они продолжали испытывать затруднения по поводу вхождения в цикл чтения, и только когда я повторил: "итак, мы решили, что "l" предназначается для представления числа букв слова, запомненных в массиве", они приняли решение начать процесс чтения так:
l:=0; repeat l:=l+1; c[l]:=x; x:=ЧОС until x=прx=тчк
(в первом наброске было пропущено "x=тчк", но это быстро исправили). После того как эта запись появилась на доске, они завершили процесс чтения без особых затруднений:
while x=пр do x:=ЧОС
Когда мы переключили внимание на процесс печати, дело пошло быстрее. Разумеется, процесс чтения прояснил задачу взаимосвязи, и предложения посыпались со всех сторон. До этого я не знакомил слушателей с проблемой, кодировать ли заголовок альтернативы между двумя повторениями или же заголовок повторения применительно к оператору альтернативы (см. стр. 33). Я ждал пока эта проблема естественно возникнет, здесь она встретилась, и я продемонстрировал ее аудитории. Неожиданно для меня один из студентов предложил совместить оба цикла с помощью дополнительных переменных. Мы ввели три целых переменных "k, доб, разд", и печать букв приобрела вид
if вперед then begin k:=0; доб:=+1; разд:=l end
else begin k:=l+1; доб:=-1; разд:=1 end; repeat k:=k+доб; ПОС(с[k]) until k=разд
а далее следовало
if x=тчк then ПОС(тчк) else ПОС(пр)
Итак, мы пришли к следующей программе:
boolean вперед; char x; char array с[1:20]; integer l, k, доб, разд; вперед:=true; x:=ЧОС; repeat l:=0; repeat l:=l+1; c[l]:=x; x:=ЧОС until x=np х=тчк; while x=пр do х:=ЧОС; if вперед then begin k:=0; доб:=+1; разд:=l end
else begin k:=l+1; доб:=-1; разд:=l end
repeat k:=k+доб; ПОС(с[k]) until k=разд; if x=тчк then ПОС(тчк) else ПОС(пр); вперед:=non вперед until x=тчк
Я включил этот раздел вовсе не потому, что в нем рассматривается интересная задача. Напротив, хочется отметить, что эта задача выглядит слишком тривиальной для того, чтобы служить хорошим тестовым материалом для методического анализа проблемы составления программ. Этот раздел включен, потому что правдиво отражает то, что произошло в классной комнате. Следует рассматривать его как частичный ответ на часто задаваемый мне вопрос, до какой степени я способен научить стилю программирования. (Я никогда не пользовался в своей педагогической практике "Заметками по структурному программированию", предназначенными в основном для себя и своих коллег. Описанный в этом разделе учебный эксперимент был поставлен в конце курса "Введение в искусство программирования", для которого я подготовил отдельный конспект лекций с упражнениями и всем подобающим. Когда я пишу эти строки, моим студентам еще предстоит сдавать экзамен, и поэтому для меня остается открытым вопрос, насколько я преуспел в своих лекциях студентам. Курс им нравится, я слыхал, что они называют мои программы "логическими поэмами", так что у меня есть основания для оптимизма.)
К читателю
Эти заметки относятся к жанру "писем к себе": одни и те же соображения очень часто вертелись у меня в голове, и чтобы отвлечься от них, я был просто вынужден записать их. Перечитывая написанное, я не всегда испытывал полное удовлетворение.
Прежде всего я чувствовал, что страдаю излишним многословием. Тем не менее я, не пытаюсь ужать текст (теперь), во-первых, потому, что это вызвало бы дополнительную задержку и я снова увлекся бы этими размышлениями, а во-вторых, потому что прежний опыт заставляет меня бояться, что я окажусь непонятым: часто программист склонен рассматривать свои (иногда довольно специфические) трудности как суть программирования, и в результате существует большое разнообразие мнений о том, что же такое программирование на самом деле.
Надеюсь, что, несмотря на недостатки моей работы, вам понравятся хотя бы некоторые ее части. Если эти заметки послужат источником вдохновения или позволят вам по-новому оценить профессию программиста, то мои основные цели будут достигнуты.
Прежде чем опубликовать "Заметки по структурному программированию" в книге, я распространял их частным образом. Проявленный читателями интерес, за который я выражаю здесь признательность, послужил одним из основных стимулов, чтобы присоединить к этим заметкам некоторый дополнительный материал и сделать их доступными широкой публике. В частности, я хотел бы поблагодарить Б. Флойда, Р. Лондона им. Вуджера за одобрительные замечания, а П. Наура за критические суждения. В заключение хочу выразить признательность миссис Э. Л. Дейкстра-Такер за любезную помощь в моем противоборстве с английским.
О количественной ограниченности наших возможностей
Я обращаюсь здесь к основной проблеме этой публикации. Речь идет о построении больших программ, запись которых может оказаться, скажем, такого же размера, как весь текст этого раздела. При этом я счел необходимым включить примеры для иллюстрации различных методов. По чисто практическим причинам приходится демонстрировать малые программы, во много раз меньшие, чем те программы "натуральной величины", которые я имею в виду. Основная проблема и состоит в том, что именно это различие в масштабах является одним из основных источников наших трудностей при программировании!
Было бы прекрасно, если бы мне удалось проиллюстрировать различные методы на примерах малых программ, а затем закончить фразой: "...и столкнувшись с программой, в тысячу раз большей, вы построите ее точно таким же способом". Однако этот распространенный прием обучения был бы в данном случае обречен на неудачу; один из основных тезисов моей работы в том и состоит, что любые два объекта, которые отличаются в чем-то по меньшей мере в сто или более раз, становятся совершенно несопоставимыми.
История показывает, что в эту истину очень трудно поверить. По-видимому, мы слишком привыкли пренебрегать различиями в размерах, трактовать их как "некоторые несущественные количественные различия". Мы говорим себе, что если можем что-то сделать один раз, то можем сделать это и дважды, и по индукции приходим к убеждению, что можем сделать это столько раз, сколько потребуется; как раз это-то и не верно! Умножение на тысячу уже выходит далеко за пределы нашего воображения.
Чтобы убедить в этом читателей, я приведу два примера. Годовалый младенец будет ползти на четвереньках со скоростью, скажем, миля в час. Однако скорость тысяча миль в час достигается только с помощью сверхзвукового реактивного двигателя. Если рассматривать как способные к передвижению объекты младенца, и реактивный самолет, то они оказываются несопоставимыми, поскольку все, на что способен один, недоступно другому, и наоборот.
Другой пример: человек может закрыть глаза и вообразить, будто он стоит на открытом месте - в степи или на берегу моря и будто издали приближается галопом большая необузданная лошадь; он может "увидеть", как она приблизилась на всем скаку и промчалась мимо. Проделать то же самое умозрительно с вереницей из тысячи таких больших животных оказывается невозможным: ваше сердце замерло бы от ужаса, если бы вам это удалось!
Острота проблемы усугубляется тем, что вопросы размеров не только послужили мне материалом для этой публикации, но относятся к существу предмета: распространенная привычка недооценивать специфические трудности при больших размерах программ представляется мне одной из основных причин недостатков теперешнего программного обеспечения. Подводя итог сказанному, я вижу только один выход: рассмотреть проблемы размеров как можно более тщательно. Отсюда и название этого раздела.
Начнем с "размера" вычислений, т. е. с количества информации и числа выполняемых операций. Существенно, что этот размер велик, так как если бы он оказался малым, то легче было бы обойтись без машины и произвести вычисления вручную. Право вычислительной машины на существование, ее полезность именно в том и состоит, что она способна выполнять большие вычисления, которые непосильны нам, людям. Мы хотим, чтобы машина делала то, чего мы сами никогда не смогли бы сделать, и параметры современной вычислительной техники таковы, что самые заурядные машинные вычисления выходят далеко за пределы нашего "безоружного" воображения.
Тем не менее мы должны организовать счет таким способом, чтобы, маневрируя нашими ограниченными возможностями, обеспечить нужные результаты вычислений. Организация счета включает в себя составление программы; здесь мы сталкиваемся с новой проблемой размера, а именно с проблемой длины текста программы, и с этим также следует полностью разобраться. Нам следует осознать тот факт, что наша способность читать или писать текст в очень большой степени зависит от размера этого текста.
В телефонной книге моей страны информация об абонентах группируется по городам или деревням, а в пределах каждой такой группы список абонентов упорядочивается по фамилиям в алфавитном порядке. Сам я живу в маленьком селении, и если знаю телефонный номер, то мне достаточно просмотреть несколько колонок, чтобы выяснить, кому он принадлежит, но в большом городе то же самое оказалось бы сложной задачей обработки данных!
По аналогии мне хотелось бы привлечь внимание читателя к тому факту, что "ясность" можно определить количественными характеристиками; этот факт, как это ни странно, не учитывается многими математиками. Теорема, утверждающая некое следствие из заполняющего десять страниц набора условий, вряд ли окажется практически полезной, если при каждом применении теоремы требуется проверять все эти условия. В евклидовой геометрии теорема Пифагора справедлива для любых трех точек А, В и С, таких, что через А и С можно провести прямую, перпендикулярную прямой, соединяющей В и С. Многие ли математики отдают себе отчет в том, что эта теорема сохраняет силу в тех случаях, когда некоторые или все точки А, В, С совпадают. Тем не менее, этим в значительной мере объясняется удобство применения теоремы Пифагора. Подвожу итог: человек соображает медленно, а емкость его памяти очень мала, и ему следует получше научиться жить в таких условиях, учитывать ограниченность своих возможностей и относиться к ней с полным уважением, а не пытаться игнорировать ее, так как такие тщеславные попытки будут обречены на неудачу.
О математической индукции
Я особо выделил математическую индукцию потому, что это единственный способ рассуждения, который в конечном итоге позволяет нам совладать с циклами (типа тех, что описываются с помощью заголовков повторения) и с рекурсивными процедурами. Хочу привести один пример.
Рассмотрим последовательность значений d0, d1, d2,d3, ...
заданную так:
для i=0 di=D (2a)
для i>0 di = f(di-1) (2b)
где D - некое заданное значение и f - заданная (вычислимая) функция. Требуется присвоить переменной d значение первого элемента dk из последовательности, которое удовлетворяет заданному (вычислимому) условию "утв". Известно, что такое значение существует для конечного k. Более формально можно сказать, что требуется установить отношение
d=dk (3)
где k задается выражениями
утв(dk) (4)
и
non утв (di) (5)
для всех i, удовлетворяющих 0 i < k
Рассмотрим теперь следующий фрагмент программы:
| d:=D
while non утв (d) do d:=f(d) |
(6) |
Здесь первая строка представляет начальную установку, а вторая представляет цикл, управляемый (надеюсь, не требующим пояснений) заголовком повторения while ... do. (С помощью условия if ... do, использованного в предыдущем примере, семантика заголовка повторения может быть описана формально: текст
while B do S
семантически эквивалентен тексту
if B do
begin S; while B do S end
и означает, что non В - необходимое и достаточное условие прекращения повторений.)
Мы будем называть в конструкции while B do S оператор S "повторяемым оператором" и докажем, что в программе (6) после n-го выполнения повторяемого оператора справедливо (при n0)
d=dn (7а)
и
non утв (di) для всех значений i, удовлетворяющих 0i<n (7b)
Методом перечисления убеждаемся в том, что это утверждение справедливо при n=0; мы хотим доказать (также методом перечисления), что если оно справедливо при n=N (N0), то оно справедливо и при n=N+1.
После N-го выполнения повторяемого оператора отношения (7a) и (7b) выполняются при n=N. Для того чтобы произошло (N+1)-е выполнение, необходима и достаточна истинность условия
non утв (d)
которое в силу (7а) для n=N (т. е. при d=dN) означает
non утв (dN)
Поэтому условие (7b) справедливо для n=N+1. Кроме того, из равенства d=dN и из (2b) следует, что
f(d)=dN+1
так что непосредственным результатом (N+1)-го выполнения повторяемого оператора будет установление отношения
d:=f(d)
т. е. отношения (7а) для N=N+1, и таким образом индуктивный переход (7) обоснован.
Теперь покажем, что повторения прекращаются после k-гo выполнения повторяемого оператора. При n>k не может быть n-го выполнения, так как в силу (7b) это означало бы
non утв (dk)
а это противоречило бы условию (4).
Если повторения прекращаются после n-ro выполнения повторяемого оператора, то необходимое и достаточное условие прекращения повторений, т.е.
non(non утв (d))
в силу (7а) принимает вид
утв (dn) (8)
Этим исключается прекращение повторений при n<k, так как оно противоречило бы условию (5). Итак, повторения прекратятся при n=k, и поэтому (3) следует из (7а), (4) следует из (8) и (5) - из (7b). Наше доказательство завершено.
Прежде чем отвлечься от этого примера, иллюстрирующего применение математической индукции в рассуждениях, я хочу сделать несколько дополнительных замечаний, потому что предчувствую, что к этому времени некоторые мои читатели (особенно опытные и компетентные программисты) придут в негодование; речь идет о тех читателях, для которых правильность программы (6) настолько очевидна, что их удивляет вся эта суета: "К чему напыщенное сведение проблемы к условиям (3), (4) и (5), когда всякий знает, что собой представляет первое значение из последовательности, удовлетворяющее некоему условию? Разумеется, он не может ожидать, что мы - люди, загруженные работой,- будем предоставлять такие длинные доказательства с полной математической отделкой всякий раз, когда употребим такой простой цикл, как этот." И так далее ...
Признаюсь чистосердечно: пышность и пространность приведенного выше доказательства раздражают и меня. Однако в настоящее время у меня нет лучшего выхода, если я действительно стремлюсь обосновать правильность этой программы. Впрочем, иногда это вызывает у меня такую же злость, какую я испытывал много лет назад, изучая мудреные доказательства первых простых теорем планиметрии, в которых утверждались факты, не менее очевидные, чeм сами аксиомы Евклида.
Конечно, я не осмеливаюсь утверждать (по крайней мере теперь!), что программист должен предоставлять такое доказательство всякий раз, когда пишет в своей программе простой цикл. Тогда бы он вообще никогда не смог написать программу любого размера! ЭТО было бы столь же нереально, как явное и полное сведение любого доказательства в планиметрии к аксиомам Евклида. (См. раздел "О количественной ограниченности наших возможностей".)
Хочу сделать три вывода из сказанного. Во-первых, когда программист рассматривает конструкцию типа (6) как заведомо правильную, он имеет на это право потому, что знаком с такой конструкцией. Я предпочитаю рассматривать его поведение как неосознанную ссылку на теорему, которую он знает, хотя не исключено, что он никогда не удосуживался сформулировать ее. Когда-то он убедился в ее правильности, хотя, возможно, он уже забыл свой способ доказательства и хотя этот способ (возможно) и непригоден для публикации. Тем не менее мы могли бы сформулировать свое мнение о программе (6) в виде, скажем, "теоремы линейного поиска", а зная такое название, гораздо легче (и более естественно) апеллировать к нему интуитивно.
Во-вторых, насколько мне известно, не существует набора теорем типа рассмотренной выше, полезность которых была бы общепризнанной. Однако не следует удивляться этому, так как отсутствие такого набора теорем является непосредственным следствием того факта, что не сформулировано четко понятие основного объекта, т.е. программы. Тип объекта, с которым имеет дело программист, т.е.
программы, значительно менее формализован, чем тип объекта в планиметрии. Между тем развитая интуиция программиста выражается, по-видимому, в том, что он ограничивается по мере возможности хорошо знакомыми структурами программ и проявляет особую осторожность и тщательность при построении необычных (для себя) программных конструкций. Однако для формализации программирования могли бы оказаться полезными поиски теорем, соответствующих таким необычным программам.
В-третьих, протяженность доказательства, которое потребовалось нам в предыдущем примере, представляет собой предостережение, которое не может быть оставлено без внимания. Конечно, не исключено, что более искусный математик провел бы доказательство короче и изящнее, чем это удалось мне. Лично же я склонен сделать вывод, что само программирование труднее, чем принято считать. Будем смиренно воспринимать громоздкость доказательства как убедительный совет ограничиваться по возможности простыми структурами и проявлять максимальную интеллектуальную умеренность, остерегаясь "хитроумных конструкций" как чумы.
О модели программы
Чтобы иметь программу, мы должны сначала составить ее. Когда она у нас появится, мы должны будем ее выполнять (если ее изготовление имело хоть какой-то смысл). В этом разделе мы будем уделять мало внимания действиям по составлению и выполнению программы, а попытаемся рассматривать программу как статический объект. Мы хотим рассматривать ее как объект со сложной структурной организацией, и основной вопрос состоит в следующем: какие типы структур мы предусматриваем и почему. Надеемся, что в конце концов добьемся такой структуры программ, которая окажется идеальной и для процесса составления, и для последующего ее выполнения. Разумеется, я всегда помню об этих процессах, но здесь мне не хочется их обсуждать; в частности, я не хочу затрагивать методологические вопросы (продвигаться ли "снаружи внутрь" или наоборот) и вообще не собираюсь заниматься здесь проблемами реализации программ.
Коль скоро нас интересует программа сама по себе, то основным предметом обсуждения становится, по-видимому, наше желание, чтобы программа была записана именно так, как мы ее понимаем и как хотели бы объяснять ее другим людям. Однако без дальнейших уточнений все это выглядит пустыми отеческими поучениями; поэтому я попытаюсь внести больше ясности.
Рассмотрим очень простое вычисление, в котором можно выделить три различных действия, выполняемых последовательно, например ввод данных, обработка (т. е. собственно вычисление) и вывод результатов. Одним из способов представления такой программы является длинная цепочка операторов:
begin
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . end
Вводя для наглядности метки, получаем такую форму записи:
begin начало ввода: . . . . . . . . . . . начало обработки: . . . . . . . . . . . начало вывода: . . . . . . . . . . . end
При такой записи мы, читая текст, знаем, что нас ждет впереди.
Еще лучше писать так:
begin ввод: begin . . . . . . . . . . . . . . end; обработка: begin . . . . . . . . . . . . . . end; вывод: begin . . . . . . . . . . . . . . end; end
Здесь метки рассматриваются не столько как указатели точек в тексте программы, сколько как названия областей (ограниченных парами скобок begin-end), которые следуют за этими метками, или же как названия трех действий, на которые разложено вычисление. Однако если мы принимаем такую точку зрения, то три "метки" все равно остаются комментариями, т. е. пояснительным фоном для пользы любознательных читателей, тогда как мне хотелось бы рассматривать их как неотъемлемую часть программы. Для меня желательно, чтобы текст моей программы как-то отражал тот факт, что вычисление было разложено на последовательные три действия, независимо от того, как будут выглядеть эти действия при детальном рассмотрении. Это можно сделать, выписав где-то "текстуальную" последовательность из трех (абстрактных) операторов
ввод; обработка; вывод
в предположении, что последовательность выполнения этих трех действий будет на самом деле управляться данной текстуальной последовательностью. Причем дальнейшая конкретизация этих трех действий будет задана "где-то еще", возможно, по отдельности, и уж во всяком случае без соблюдения относительного порядка.
Итак, если бы замкнутые подпрограммы не были изобретены более чем двадцать лет тому назад, то сейчас было бы самое время ввести их! Другими словами, мы возвращаемся к привычным понятиям, и настолько привычным, что многие читатели даже испытывают разочарование. Лично я его не испытываю, так как нет ничего зазорного в том, чтобы придерживаться проверенного метода все время, пока он удовлетворяет нас. Однако нам следует ясно осознать те преимущества, которые мы хотим из него извлечь; в случае необходимости мы должны доработать его, и, наконец, нам надлежит четко установить правила его использования. Поэтому я позволю себе дать обзор понятия подпрограммы с тем большим основанием, что мое мнение об этом понятии изменилось в течение последнего года.
Впервые я познакомился с понятием замкнутой подпрограммы в связи с системой EDSAC [Wilkes М. V.
, Wheeler D. J., Gill S., The Preparation of Programsfor an Electronic Digital Computer; with Special Reference to the EDSAC and the use of a Library of Subroutins, Addison-Wesley Press, 1951.], где понятие подпрограммы служило основой библиотеки стандартных программ. В те времена конструирование машинной аппаратуры было рискованным делом, и многие стандартные программы служили для расплаты и без того малой памятью и временем счета за несовершенство электронных схем; если в машинном коде не предусматривалась операция деления, то обзаводились подпрограммами деления. Однако, как ни странно, я не припоминаю, чтобы какие-то подпрограммы получили признание как средство "перестройки" имеющейся машины в более удобную. Мне не помнится также, чтобы в те времена пользователи проектировали и строили подпрограммы, отражая в них анализ своих задач. Преимущественно дело сводилось к стандартным программам, по отношению к которым пользователь выступал только в роли потребителя. В конечном счете я видел в них главным образом средство сокращения длины программы. Вся же программа в целом по-прежнему воспринималась как действие в рамках единой однородной памяти в пространстве состояний команд; весь счет оставался единым последовательным процессом, выполняемым одним процессором.
В последующие годы я прочел много курсов программирования, истово проповедуя это учение, и часто объяснял, как при обращении передается адрес возврата и как затем выполнение подпрограммы начинается с установки "связи", т. е. команды возврата в конце подпрограммы. Теперь я склонен считать, что основная программа имеет свой собственный счетчик команд, который сразу же продолжает продвигаться после завершения выполнения подпрограммы, и уж, конечно, не стану рассматривать "застывшее значение" этого счетчика как параметр, передаваемый подпрограмме. (Прежняя концепция все еще довлеет над структурой многих машин. Мы встречались с машинами, в которых при обращении к подпрограмме связь запоминается по "адресу нуль" в подпрограмме, тогда как первая выполняемая команда подпрограммы подразумевается по "адресу один"; при такой организации затруднена реализация реентерабельности и рекурсивных подпрограмм.
Даже в текущем десятилетии встречаются машины, которые при прерывании запоминают "состояние" прерванной программы в ячейках, соответствующих прерывающей, а не прерываемой программе!)
Десятью годами позже, когда появился АЛГОЛ-60, декорации переменились, и мы перестали говорить о замкнутых подпрограммах: отныне мы называли их "процедурами". Они по-прежнему воспринимались программистами как очень удобное средство сокращения текста программы; однако программисты все чаще и чаще начинали использовать их в целях структурной организации с таким расчетом, чтобы приспособление программы к ожидаемым изменениям постановки задачи могло свестись к замене одного или нескольких тел процедур или же к изменению некоторых фактических параметров в каком-то обращении к процедуре. Но основным новшеством явилось понятие локальных переменных.
Это понятие получило отражение в двух важных аспектах. Первым было понятие "области действия", т. е. идея о том, что не все переменные одинаково доступны на протяжении всей программы: локальные переменные процедуры не доступны вне тела этой процедуры, так как вне процедуры они не имеют никакого смысла. Только самой процедуры касается, какие локальные переменные нужны ей для выполнения стоящей перед ней задачи; основной программе нет до этого дела, и понятие "области действия" рационально отражает тот факт, что основную программу можно (и нужно!) представлять себе вне связи с этими локальными переменными. Мы можем не вполне одобрять принятые в языке АЛГОЛ-60 конкретные правила образования областей действия, но нам следует признать, что это был весьма значительный шаг в правильном направлении.
Второй аспект новизны определялся тем фактом, что процедуры могут использоваться рекурсивно, а точнее говоря, тем, что процедуре разрешается обращаться к самой себе прямо или косвенно. В прошлом многие горячо оспаривали оправданность этой возможности. Насколько я могу судить, теперь пыл этих страстей уже утих. Возражения против рекурсивных процедур всегда сводились к ссылкам на потерю эффективности: нереентерабельная программа могла бы выполняться гораздо более эффективно.
Однако с появлением мультипрограммирования возник дополнительный стимул для гибкой организации памяти. И если даже еще существуют вычислительные машины, в которых нереентерабельная программа может выполняться гораздо эффективнее, а за применение рекурсивных подпрограмм приходится расплачиваться слишком дорогой ценой, то я беру на себя смелость утверждать, что теперь следует называть такую машину старомодной. Если мы пользуемся рекурсивной процедурой, то должны четко осознавать разницу между ее статическим текстом и динамическим выполнением. Одно дело - текст процедуры и совсем другое - множество обрабатываемых ею в данное время локальных переменных.
Все это хорошо, но теперь настало время поговорить о недостатках (не знаю уж, назовете ли вы их лингвистическими или логическими). Локальные переменные "создаются" при входе в процедуру и "ликвидируются" при выходе из нее. Именно это автоматическое регулирование времени существования переменных, относящихся к выполнению процедуры, позволяет нам реализовывать (рекурсивные) процедуры с помощью стека (т. е. организации памяти по принципу "последним пришел - первым ушел"). То обстоятельство, что относящиеся к выполнению процедуры локальные переменные существуют только во время этого выполнения, делает невозможной "закулисную" передачу информации от одного выполнения процедуры к другому.
Чтобы обойти эту трудность, ввели понятие "own" (собственная переменная), но это не решило проблему: в случае рекурсии становится весьма сомнительной реальная польза от собственных переменных, а кроме того, нет возможности написать набор процедур с общими собственными переменными. (Мы можем прибегнуть к моделированию, описав такие переменные во внешнем блоке, объемлющем описания данных процедур, но тогда эти переменные станут слишком доступными в силу определения области действия, а, следовательно, их уже нельзя считать "закулисными"). Отсюда следует вывод - совсем не новый и разделяемый многими - о том, что понятие "own" в том виде, как оно введено в АЛГОЛе-60, следует признать неудачным и что мы должны искать новые способы регулирования и описания времени существования, доступности и идентичности локальных переменных.
Я недоволен понятием процедуры еще и потому, что оно по-прежнему представляется в первую очередь средством сокращения текста программы (впрочем, в случае рекурсии длина текста может оказаться неизвестной).
Семантика обращения к процедуре описывается с помощью известного "правила копирования": обращение к процедуре должно пониматься как сокращенное обозначение, поскольку семантика гласит, что следует заменить это обращение копией текста тела процедуры (с надлежащим согласованием идентификаторов и с подстановкой параметров), после чего модифицированный текст будет выполняться той же машиной, которая выполняет основную программу. Внешне это выглядит так, что единый текст программы должен выполняться единственной последовательной машиной. И именно эта картина единственной машины перестает удовлетворять меня.
Я хочу считать, что основная программа выполняется своей собственной, предназначенной только для нее машиной, снабженной подходящим набором команд применительно к соответствующим переменным и управляемой с помощью собственного счетчика команд. Короче говоря, должно иметься все необходимое для того, чтобы наша основная программа могла решить задачу, если в нашем распоряжении находится такая машина. Такая точка зрения позволяет опираться на тот факт, что правильность основной программы может обсуждаться и доказываться независимо от наличия этой (возможно, все же умозрительной) машины. Нам только необходимо иметь описание этой машины, достаточное для того, чтобы правильно понимать выполнение рассматриваемой основной программы.
Лично для меня понятие умозрительной машины - это порождение моего абстрактного мышления, и в этом смысле я не вижу принципиального отличия от обычного способа понимания программы, написанной на так называемом языке высокого уровня., когда мы не знаем, как выполняются различные виды операций (наподобие умножения и вычитания), и не знаем таких несущественных деталей, как система счисления, применяемая в аппаратуре, обеспечивающей в конечном итоге выполнение программы.
Разумеется, на самом деле такой идеальной машины не существует, и поэтому наша следующая задача - структурно аналогичная исходной задаче - состоит в том, чтобы запрограммировать моделирование машины "верхнего уровня".
Программируя такое моделирование, мы должны так организовать структуры данных, чтобы предусмотреть все разнообразие состояний машины верхнего уровня; более того, нам нужен набор алгоритмов, каждый из которых обеспечивает выполнение некой инструкции из системы команд машины верхнего уровня. И наконец, в машине "нижнего уровня" могут иметься некоторые частные переменные, введенные только для ее надобностей и не имеющие никаких аналогов в рамках машины верхнего уровня. Однако весь этот комплекс программ пишется для машины, которая, по всей видимости, не будет физически существовать, и поэтому следующим этапом будет моделирование ее с помощью программ для машины еще более низкого уровня и так далее до тех пор, пока мы наконец не получим программу, которую можно выполнить с помощью имеющегося у нас машинного оборудования.
Если мы преуспели в построении своей программы по такому плану, то мы тем самым расположили эту программу на нескольких слоях. Каждый программный слой должен пониматься совершенно независимо от других в предположении, что имеется машина, соответствующая выполнению этого слоя. В то же время функция каждого слоя состоит в моделировании машины, которая соответствовала бы ближайшему более высокому уровню. Почему выбрана именно эта модель? Каких преимуществ мы рассчитываем добиться с ее помощью? Я попытаюсь перечислить эти преимущества.
(1) Как отмечалось в разделе "Первый пример поэтапного составления программы", наш программистский опыт убедительно свидетельствует о том, что организация различных слоев, соответствующих разным уровням абстракции, очень помогает составлению программы.
(2) Есть основания надеяться, что многие модификации программ могут быть теперь представлены заменой одной (умозрительной) машины другой подходящей машиной.
(3) Можно надеяться, что эта модель позволит нам лучше справляться с проблемами, которые возникают, когда нужно модифицировать программу во время ее работы. Если машина на некотором уровне остановлена между двумя своими командами, то все машины нижних уровней полностью отключены и могут быть заменены, тогда как для каждой машины верхнего уровня следует считать, что произошло прерывание во время выполнения команды, а их состояние нужно рассматривать как переходное.
В последовательностной машине допускается интерпретация состояния только в промежутках между выполнением команд, и описанная нами иерархия машин, у каждой из которых имеется свой собственный счетчик команд (подсчитывающий именно ее команды), оказывается более удобной, если мы хотим применительно к каждому конкретному моменту решать, какие интерпретации справедливы. Для обычного языка программирования, где прогресс вычислений измеряется однородной мерой, скажем с точностью до одного оператора, мы испытываем некоторую беспомощность, когда сталкиваемся с вопросом, какие интерпретации справедливы в те или иные моменты.
(4) Можно надеяться, что эта модель поможет нам даже справиться (частично или полностью) с проблемами, возникающими после обнаружения некоторой функциональной некорректности. (Недавно я участвовал в проектировании и разработке одной системы мультипрограммирования, и чуть ли не больше всего нам досаждала наша полная неспособность оценить (механически) границы области бедствия, когда какая-то ячейка памяти выдавала сигнал ошибки по четности. Единственная защитная реакция, которую мы смогли реализовать, состояла в немедленном прекращении работы машины, и вряд ли таким решением можно гордиться.) (5) Эта картина иерархического расслоения машин выявляет одну из опасностей чрезмерного применения принципа "разделяй и властвуй", когда различные компоненты программируются настолько независимо друг от друга, что возникает дублирование работы (или что-нибудь похуже). Говоря, что слой содержит набор программ для некоторой умозрительной машины, мы подчеркиваем этим подразумеваемое наличие общего фонда примитивных подпрограмм для этого набора. Разделение работы - хорошая вещь, но нужно это делать так, чтобы суметь потом связать концы с концами.
О надежности аппаратуры
По профессии я программист и обсуждаю в этой работе программы; истинной темой этого раздела является, в сущности, надежность программ. Тем не менее в заголовке я упоминаю "аппаратуру", так как считаю программы специфической формой аппаратов и желаю хоть раз выразить глубокую уверенность в том, что многие мои соображения, относящиеся к программному обеспечению, справедливы с соответствующими поправками и применительно к проектированию машинной аппаратуры.
Современные вычислительные машины - это изумительные комплексы оборудования, но еще более изумляет неопределенность критериев оценки правильности результатов работы машины. Все основывается на предположении, что аппаратура функционирует правильно.
Ограничимся временно рассмотрением машинной аппаратуры; удивительно, насколько легко убедить человека в том, что она сконструирована безошибочно. Несколько лет назад в университете, где я работаю, появилась новая машина. В сопроводительной документации утверждалось, что среди многого прочего имеется схема умножения 27-разрядных чисел с фиксированной запятой. Казалось бы, законный вопрос: "Правилен ли этот умножитель, работает ли он в соответствии со своим описанием?"
Вот наивный ответ: "Ну что же, число различных перемножений, которые должны выполняться правильно этим умножителем, конечно и равно 254; поэтому давайте проверим их все". Однако, каким бы разумным ни казался этот ответ, он непригоден, так как, хотя одно перемножение занимает всего несколько десятков микросекунд, общее время, требуемое для этого конечного числа перемножений, составило бы более чем 10 000 лет! Отсюда следует вывод, что исчерпывающее тестирование даже одиночной компоненты типа умножителя оказывается совершенно нереальным. (Тестирование всей машины по тому же принципу требовало бы доказательства правильной работы всех возможных программ!)
Подсчитанный нами десятитысячелетний срок означает, что за время своего существования умножитель должен будет выполнить только ничтожную часть огромного числа всех возможных перемножений, на которые он способен: практически ничего он сделать не успеет.
Как ни странно, мы все же требуем, чтобы он был способен правильно выполнить любое перемножение, если поступит соответствующий приказ. Это фантастическое качество требуется потому, что мы не знаем заранее, какие именно ничтожно малые по своему количеству умножения потребуется выполнить. В наших рассуждениях о программах мы говорим о "произведении", абстрагируясь от конкретных значений сомножителей: мы не знаем их и не хотим их знать; не наше дело их знать, наше дело их не знать! Мы вполне законно хотим мыслить в терминах общего понятия "произведения" без учета специфики конкретных вычислений, но платой за это является именно требование, чтобы правильно выполнялось любое умножение из огромного множества. Вот так обстоит дело с желанием иметь правильный умножитель.
Но как установить правильность убедительным способом? Поскольку умножитель рассматривается как черный ящик, единственное, что мы можем сделать, это "проверить на примерах", т, е. предложить умножителю обозримое количество пар сомножителей и проверить результаты. Но с точки зрения десяти тысяч лет очевидно, что мы можем проверить только ничтожную часть возможных перемножений. Целые классы в некотором смысле "критических" перемножений могут остаться непроверенными, и в отношении столь желаемой надежности наш контроль остается в высшей степени неудовлетворительным. Поэтому такой способ не годится.
Непосредственный вывод состоит в следующем: убедительная демонстрация правильности невозможна, пока аппаратура рассматривается как черный ящик; единственная наша надежда в том, чтобы не считать аппаратуру черным ящиком. Я назову это "принятием во внимание структуры аппаратуры".
Аппараты, которыми мы собираемся заниматься впредь, - это программы. (С программной аппаратурой во многих отношениях легче иметь дело, чем с электронными схемами, которые в сущности являются аналоговыми устройствами и подвержены износу.) И для программ совершенно безнадежно пытаться устанавливать правильность тестированием, исключающим малейшие сомнения, если не принимается во внимание структура этих программ.
Другими словами, мы отмечаем, что степень возможной уверенности в правильности программы определяется не только внешним описанием программы и режима ее работы, но существенно зависит от ее внутренней структуры.
Возвращаясь к основному предмету наших рассмотрении, т. е. к по-настоящему большим программам, мы заключаем из предыдущего, что их величина сама по себе требует высокого уровня уверенности в отдельных компонентах программы. Если вероятность правильности отдельной компоненты равна р, то вероятность правильности всей программы, состоящей из N таких компонент, равна примерно P = pN
Если число N будет очень велико, то значение р должно быть очень и очень близко к 1, если мы хотим, чтобы значение Р существенно отличалось от нуля!
Если теперь принять предпосылку, что задача программиста не только в том, чтобы изготовить правильную программу, но и в том, чтобы убедительно продемонстрировать ее правильность, то приведенные выше соображения существенно влияют на деятельность программиста: его продукция должна иметь удобную структуру.
Последующая часть этой монографии посвящена в основном исследованию того, какая структура программы может оказаться наиболее удобной для применения. В дальнейшем читателю станет ясно, что правильность программ не является единственным предметом моих рассмотрении; я буду заниматься также проблемой приспособляемости, или управляемости программ. Я выделяю проблему управляемости программ преднамеренно и постараюсь обосновать этот выбор.
Хотя в прошлом возрастание мощности универсального оборудования смягчало остроту проблемы эффективности программ, именно это возрастание породило и новые трудности. Если человек получает в свое распоряжение мощную машину, то он пытается ее использовать, и объем задач, за которые он берется, определяется масштабом оборудования: никто не станет программировать алгоритм, выполнение которого заняло бы двадцать лет. В связи с тем что за последние десять или пятнадцать лет производительность вычислительных машин увеличилась в тысячи раз, пользователи стали гораздо более бесцеремонными при выборе проблем, которые они считают "технически разрешимыми".
Пользователи хотят, чтобы размеры, сложность и изощренность программ увеличивались исключительно быстрыми темпами, и в последние годы стало очевидным, что в целом наши программистские возможности не поспевают за этими неумеренными аппетитами.
Мощность доступного оборудования будет продолжать расти: можно ожидать, что инженеры разработают еще более быстрые машины, и даже независимо от таких разработок мы станем свидетелями того, как класс машин, которые теперь считаются исключительно быстрыми, будет получать все более и более широкое распространение. Соответственно будут расти и задачи, которые мы захотим решать на этих машинах; именно на этой экстраполяции основывается мое представление о сущности программирования. Я прихожу к выводу, что возникает настоятельная необходимость перестать подходить к программированию с точки зрения минимизации коэффициента отношения стоимости к результату. Следует осознать, что уже теперь программирование в гораздо большей степени стало интеллектуальным состязанием: искусство программировать - это умение организовать сложную систему и управлять ее бесчисленными элементами, пресекая всеми силами присущую им тенденцию к изначальному хаосу. Мое нежелание считать эффективность первоочередной заботой программиста не означает, что я вообще пренебрегаю эффективностью. Напротив, я признаю, что соображения эффективности могут послужить убедительным основанием для изменения логически правильной программы. Однако я твердо уверен, что мы можем разрешить себе оптимизацию (какова бы она ни была) только при условии, что это не повлечет за собой потерю управляемости. Я закончу этот раздел замечанием о значении вычислительных машин. Эти машины представляют собой самые "удобные и мощные орудия", и, по мнению многих, они преобразовали всю нашу цивилизацию. Я рискнул бы высказать мнение, что пока .мы относимся к ним как к орудиям, мы можем существенно недооценивать их значение. Возможно, что в качестве орудий они проводят лишь малую борозду на ниве нашей цивилизации, тогда как гораздо большее влияние на всю нашу культуру оказывает их способность выступать в качестве партнера в интеллектуальном состязании. Следствие из первой части этого раздела: Тестирование программ может служить для доказательства наличия ошибок, но никогда не докажет их отсутствия!
О наших интеллектуальных средствах
В предыдущем разделе мы высказали утверждение, что программист должен придать своей программе "удобную структуру"; структура программы упоминалась в связи с проблемой убедительной демонстрации правильности программы.
Но как же мы убеждаем? И как мы убеждаемся? Как мы достигаем понимания? Общему обсуждению именно таких вопросов посвящен этот раздел. Я приношу самые искренние извинения профессиональным психологам, поскольку мои рассуждения будут совершенно дилетантскими. Однако я надеюсь (и верю), что они помогут нам обрести критерий для оценки полезности предлагаемой структурной организации.
Среди интеллектуальных средств, которые применяются для понимания программы (или для доказательства ее правильности), я хотел бы четко выделить следующие три:
(1) перечисление;
(2) математическая индукция;
(3) абстракция.
О перечислении
Я считаю, что мы прибегаем к перечислению, когда пытаемся проверить правильность вычислений, которые сводятся к обозримому множеству последовательно выполняемых операторов, включая условные операторы выбора одного из двух или более вариантов. Приведу простой пример "рассуждения с перечислением".
Требуется доказать, что последовательное выполнение следующих двух операторов:
dd:=dd/2; if dd r do r:=r-dd
применительно к переменным r и dd сохраняет отношения
0 r < dd(1)
инвариантными. Достаточно "проследить" этот кусочек программы, предположив, что первоначально условие (1) выполняется. После выполнения первого оператора, уменьшающего вдвое значение dd, но не изменяющего r, будут выполняться отношения
0 r < 2*dd (2)
Теперь выделим два взаимно исключающих случая.
ddr. В сочетании с (2) это приводит к отношениям
dd r < 2*dd (3)
В этом случае будет выполнен оператор, следующий за do. В результате r уменьшится на dd, и из (3) следует, что в конечном итоге
0 r < dd
т. е. отношение (1) будет выполняться.
Отрицание ddr (т. е. dd>r).
В этом случае следующий за do оператор будет пропущен, и поэтому окончательным будет неизмененное значение r. В этом случае сочетание отношений dd>r и (2), справедливого после выполнения первого оператора, приводит сразу к
0 r < dd
так что и во втором случае будет выполняться условие (1).
Итак, мы завершили доказательство инвариантности отношения (1); одновременно мы завершили пример рассуждения с перечислением, включающий условия.
О понимании программ
За свою жизнь я видел много учебников по программированию, весьма напоминающих обычные учебники по вождению автомашин, в которых человека учат, как ухаживать за машиной, вместо того чтобы научить его, как использовать машину, чтобы попасть в нужное ему место.
Я считаю, что программа никогда не является самоцелью; программа предназначается для того, чтобы вызвать вычисления, а цель вычислений - получить нужный результат. Несмотря на то что программа является конечным продуктом деятельности программиста, возможные вычисления по этой программе - "осуществление" которых предоставляется машине! - вот истинное содержание его труда. Например, всякий раз, когда программист утверждает, что его программа правильна, он на самом деле высказывает суждение о тех вычислениях, которые она может вызвать.
Сложность ситуации усугубляется тем обстоятельством, что последний этап всего процесса, т. е. переход от (статической) программы к (динамическим) вычислениям в сущности предоставлен машине. Поэтому в каком-то смысле изготовление программы представляет больше трудностей, чем разработка математической теории: и программа, и теория - это структурные, вневременные объекты; но если математическая теория имеет непосредственный смысл, то программа приобретает смысл только во время ее выполнения.
В оставшейся части этого раздела мы ограничимся рассмотрением программ, написанных для последовательностной машины, и обсудим некоторые следствия того, что нам необходимо использовать наше понимание программы, чтобы высказывать суждения о производимых ею вычислениях. Я утверждаю (хотя и не могу доказать), что легкость и гибкость таких наших суждений существенно зависит от простоты взаимосвязей между программой и вычислениями, а особенно от способа последовательного управления вычислениями. Грубо говоря, можно считать желательным, чтобы структура программы отражалась в структуре вычислений. Однако возникает вопрос: "Что можем мы сделать, чтобы сократить логический разрыв между статическим текстом программы (развернутым в "поле текста") и соответствующими вычислениями (развернутыми во времени)?"
Вычисления предназначаются для того, чтобы получить определенный нужный результат.
Начавшись в дискретный момент t0 они завершатся в более поздний дискретный момент t1, и мы предполагаем, что их результат может быть описан путем сравнения "состояния в момент t0 " и "состояния в момент t1". Если никакие промежуточные состояния не принимаются в рассмотрение, то считается, что результат достигается некоторым простым действием.
Если же мы включаем в рассмотрение ряд промежуточных состояний, то это означает, что мы разлагаем действие на временные этапы. Оно представляется как последовательное вычисление, т.е. временная последовательность некоторых поддействий, и мы должны убедиться в том, что общий эффект этой последовательности поддействий на самом деле тождествен желаемому результату всего вычисления. В простейшем случае производится разбор, или разложение, на конечное число поддействий, которые могут быть перенумерованы, можно представить в виде блок-схемы следующим образом: Правильность такого разложения должна быть доказана рассуждением с перечислением. При этом логический разрыв между программой и вычислением может быть сокращен благодаря требованию, чтобы каждый линейный участок текста программы содержал имена или описания поддействий в том порядке, в котором они должны выполняться. В нашем прежнем примере (с инвариантностью соотношения 0<=r<dd)
dd:=dd/2 if dd<= r do r:=r - dd
такое условие удовлетворяется. Это вычисление непосредственно разлагается в последовательность двух действий; в тексте программы распознаем такую структуру:
уполовинить dd; уменьшить r по модулю dd.
Рассматриваем все начальные состояния, удовлетворяющие соотношению 0<=r<dd, и убеждаемся, что данное разложение на два поддействия применимо при рассмотрении всех соответствующих вычислений. Пока все хорошо.
Однако программа пишется в предположении, что "уменьшить r по модулю dd" не является простым действием в отличие от "уменьшить r на dd". При рассмотрении всех возможных выполнений действия "уменьшить r по модулю dd" естественно различать некоторые случаи, когда имеет место действие "уменьшить r на dd", тогда как в остальных случаях значение r не изменяется.
Записав
if dd<= r do уменьшить r на dd
мы выразили, что на данном уровне детализации действие "уменьшить r по модулю dd" может принять одну из двух взаимно исключающих форм, и одновременно задали критерий того, как производится выбор между этими двумя формами. Если рассматривать "if dd<= r do" как условие, применяемое к "уменьшить r на dd", то естественно, что условие помещается в начало условного оператора. (В этом смысле заголовок альтернативы
if условие then оператор 1 else оператор 2
является "надстройкой" по отношению к "оператору 1" и "оператору 2": это две альтернативы, которые не могут быть выражены одновременно при обычной линейной записи.) Хоор обобщил понятие заголовка альтернативы, введя конструкцию case-of ("вариант из"), обеспечивающую выбор среди более чем двух возможностей. В виде блок-схем это выражается следующим образом:
Общее свойство всех этих блок-схем состоит в том, что у каждой из них один вход вверху и один выход внизу. Пунктирные блоки обозначают, что каждая блок-схема может в свою очередь интерпретироваться (независимо от содержимого пунктирного контура) как единое действие при последовательных вычислениях. Если говорить чуть более точно, мы имеем дело с большим числом возможных вычислений, непосредственно разлагаемых в одну и ту же временную последовательность поддействий, и только при более детальном рассмотрении, а именно при заглядывании внутрь пунктирного блока, выясняется, что над разнообразием возможных вычислений такое поддействие может принимать одну из перечисленных различных форм.
Сказанного выше достаточно, чтобы рассматривать класс вычислений, которые непосредственно разлагаются на одни и те же последовательные пронумерованные поддействия. Однако этого недостаточно, чтобы рассматривать класс вычислений, которые непосредственно разлагаются на различное число поддействий. (Речь идет о том, что число поддействий изменяется в рамках рассматриваемого класса вычислений.) Именно здесь становится очевидной полезность заголовков повторения.
Сошлемся на операторы "while условие do оператор" и "repeat оператор until условие", которые могут быть представлены в виде блок-схем следующим образом:
Эти блок- схемы также характеризуются наличием одного входа вверху и одного выхода внизу. Они позволяют нам выразить мысль, что действие, представляемое пунктирным блоком, оказывается при детальном рассмотрении последовательностью из "достаточного .числа" поддействий определенного вида.
Итак, мы познакомились с тремя типами разложения; можно называть их соответственно "сочленением", "выбором" и "повторением". Для понимания первых двух служит рассуждение с перечислением, а для последнего нужна математическая индукция.
Программы, при написании которых управление последовательностью действий осуществляется только при помощи выбора и повторения, допускают непосредственный перевод на некий язык программирования, который отличается от исходного только тем, что все управление последовательностью действий должно быть выражено передачами управления на метки. Однако обратное утверждение было бы неправильным. Напротив, если мы ограничимся указанными тремя типами разложения, то это приведет к ограничению топологии блок-схем по сравнению с различными блок-схемами, которые могут быть получены, если разрешить проведение стрелок из любого блока в любой другой блок. Отказавшись от большого разнообразия блок-схем и ограничившись данными тремя типами операторов управления, мы следуем тем самым некоей последовательностной дисциплине.
Почему я предлагаю придерживаться этой последовательностной дисциплины? Это решение может быть обосновано различными способами, и я попытаюсь изложить несколько таких обоснований в надежде на то, что хотя бы одно из них удовлетворит моих читателей.
В конечном счете мы стремимся изготовлять такие хорошо организованные программы, чтобы интеллектуальное усилие (оцениваемое неформально), которое необходимо для их понимания, было пропорционально размеру программы (оцениваемому столь же неформально).
В частности, мы должны остерегаться чрезмерных рассуждений с перечислением, что побуждает нас руководствоваться ярым правилом "разделяй и властвуй"; в этом причина того, что мы предлагаем последовательно разлагать вычисления на этапы.
Разложение сочленением мы можем понимать с помощью рассуждения с перечислением. (Это возможно при условии, что число поддействий, на которые непосредственно разлагается вычисление, достаточно мало, а результаты их применения сформулированы достаточно точно. Мы вернемся к обсуждению этих требований позднее, а пока будем предполагать, что эти условия удовлетворяются.) При этом удобно высказывать суждения относительно вычислений, пользуясь текстом программы, поскольку связь между продвижением вычислений и продвижением по тексту программы является тривиальной. В частности, если при детальном рассмотрении оказывается, что некое поддействие управляется заголовком выбора или заголовком повторения, это не затрудняет понимания непосредственного разложения, так как принимается во внимание только общий эффект поддействия. Следствие: если при детальном рассмотрении поддействия выясняется, что оно управляется заголовком выбора, то выбор конкретного пути несуществен на первом уровне разложения (важно только, чтобы выбирался правильный путь). Аналогично если при детальном рассмотрении поддействия выясняется, что оно управляется заголовком повторения, то число выполнений повторяемого оператора также не является существенным (важно только, чтобы число повторений было правильным). Точно так же мы можем непосредственно понимать заголовки выбора, пользуясь рассуждением с перечислением, и понимать заголовки повторения с помощью математической индукции. Я считаю большим удобством, что для всех трех типов разложения мы знаем подходящие способы рассуждения. Можно указать еще одно преимущество предлагаемой последовательностной дисциплины. В процессе понимания программ мы устанавливаем соотношения. В нашем примере рассуждения с перечислением мы устанавливаем, что фрагмент программы
dd:=dd/2; if ddr do r:=r-dd
сохраняет отношения 0<=r<dd
инвариантными. Однако, если даже мы можем гарантировать, что эти отношения справедливы перед выполнением данной части программы, из этого нельзя сделать вывод, что они справедливы всегда: вовсе необязательно, чтобы они имели место в промежутке между выполнением двух операторов, заключенных в кавычки. Другими словами, справедливость таких отношений зависит oт продвижения вычислений, и это представляется типичным для последовательного процесса.
Аналогично мы приписываем смысловые значения переменным: переменная может быть счетчиком числа выполнений событий заданного типа, например, числа строк, напечатанных на текущей странице. Переход к новой странице сразу же сопровождается засылкой нуля в счетчик, а печать очередной строки непосредственно сопровождается прибавлением единицы к счетчику. Опять-таки непосредственно перед обновлением или увеличением счетчика интерпретация "числа строк, напечатанных на текущей странице", не является определенной. Присвоение переменной такого смыслового значения может быть выполнено только в зависимости от хода вычислений. Это наводит нас на следующий вопрос: "Как мы характеризуем ход вычислений?"
Коротко можно сказать, что мы ищем координатную систему, с помощью которой можно идентифицировать дискретные точки продвижения вычислений, и хотим, чтобы эта координатная система не зависела от переменных, которые обрабатываются под управлением программы. Если нам нужно, чтобы значения таких переменных описывали продвижение вычислений, то получается замкнутый логический круг, потому что мы хотим интерпретировать смысл этих переменных именно в связи с продвижением вычислений.
(Еще более веской причиной для того, чтобы не полагаться на значения этих переменных, является существование программы, содержащей бесконечный цикл, проходящий конечное число различных состояний. Невозможность выхода из цикла следует из того факта, что в различных точках продвижения вычислений имеет место одинаковое состояние.
Но тогда очевидно, что это состояние непригодно для того, чтобы различать между собой данные две различные точки продвижения вычислений!)
Мы можем сформулировать нашу проблему другим способом. Дана работающая программа и предполагается, что до завершения счета она остановлена в одной из дискретных точек продвижения вычислений. Каким способом мы можем идентифицировать точку прерывания, если, например, хотим повторить вычисления именно до этой самой точки? Кроме того, если останов был вызван какой-то динамической ошибкой, то как мы можем идентифицировать соответствующую точку продвижения вычислений, не прибегая к полному копированию памяти?
Для простоты предположим, что текст нашей программы находится в специальном (линейном) поле текста и что существует способ идентификации точек в программе, соответствующих дискретным точкам продвижений вычислений. Будем называть этот способ идентификации "текстуальным индексированием". (Если дискретные сточки продвижения вычислений располагаются между последовательными выполнениями операторов, то текстуальное индексирование идентифицирует, например, точки с запятыми.) Текстуальный индекс представляет собой нечто вроде обобщенного счетчика команд, его значение указывает место в тексте.
Если мы ограничиваемся при разложении только сочленением и выбором, то для идентификации продвижения вычислений достаточно одного текстуального индекса. Если же допускаются заголовки повторения, то текстуальные индексы уже не обеспечивают описание продвижения вычислений. Однако при каждом входе в заголовок повторения система могла бы заводить так называемый "динамический индекс", неукоснительно отсчитывающий очередной номер соответствующего текущего повторения; по окончании повторений система должна устранить соответствующий динамический индекс. Поскольку заголовки повторений могут оказаться последовательно вложенными один в другой, то удобно пользоваться стеком (т.е. памятью, организованной по принципу "последним пришел - первым ушел").
Первоначально стек пуст. При входе в заголовок повторения новый динамический индекс (с начальным значением нуль или единица) добавляется в вершину стека. Всякий раз, когда принимается решение, что повторения еще не закончились, верхний элемент этого стека увеличивается на 1. Если же принимается решение, что повторения завершились, производится удаление верхнего элемента из стека. (Такая организация весьма наглядно отражает то обстоятельство, что после завершения повторений перестают быть существенными число выполнений повторяемого оператора и даже сам факт повторения.)
Когда язык программирования допускает процедуры, уже не удается обойтись одним текстуальным индексом. Если текстуальный индекс указывает место внутри тела процедуры, то динамическое продвижение вычислений определяется только тогда, когда мы также описываем тот вызов процедуры, к которому мы обращаемся: однако это можно сделать, только задав специальный текстуальный индекс, указывающий место вызова. При включении процедур необходимо использовать обобщение текстуального индекса, представляющее собой стек текстуальных индексов, увеличивающийся на один элемент при вызове процедуры и уменьшающийся на один элемент при возврате из процедуры. Весьма существенно, что значения этих индексов не контролируются программистом. Они определены (либо из распечатки его программы, либо из динамики текущего вычисления) независимо от тогo, нравится это ему или нет. Они могут служить независимыми координатами для описания продвижения вычислений, образуя "независимую от переменных" систему отсчета, в рамках которой можно приписывать переменным смысловые значения. Разумеется, даже при произвольном использовании передач управления существует независимая от программиста координатная система, с помощью которой можно однозначно описывать продвижение последовательных вычислений; это своего рода условные часы, которые отсчитывают число "дискретных точек продвижения вычислений", пройденных от начала выполнения программы.Эта система однозначна, но она совершенно бесполезна, так как текстуальный индекс уже не является составной частью такой координатной системы. Из сказанного можно сделать следующий вывод. Если мы считаем своей обязанностью контролировать вычисления (интеллектуально!), обращаясь к тексту управляющей вычислениями программы, то нам следует смиренно довольствоваться наиболее систематизированными способами организации следования, гарантирующими самое непосредственное отражение "продвижения вычислений" в "продвижении по тексту".
О противоречии между правильностью доказательств и правильностью реализации
В предыдущем разделе подразумевалась "точная арифметика"; мой опыт показывает, что обоснованность таких доказательств часто ставится под сомнение людьми, которые ссылаются на то, что на практике в нашем распоряжении никогда не бывает абсолютно точной арифметики: обычно имеется верхняя граница для допустимых целых значений; действительные числа представляются только с конечной точностью и т. д. Так в чем же ценность таких доказательств?
Мне кажется, что ответ на этот вопрос состоит в следующем. Если человек доказывает правильность программы применительно к идеализированному совершенному миру, то ему не следует удивляться, если что-то идет не так, когда эта идеальная программа выполняется на "несовершенной" машине. Это очевидно. Поэтому если мы хотим доказать правильность программы для более реального мира, то прежде всего необходимо четко осознать, что все используемые в программе операции (и, в частности, все арифметические операции) не обязательно выполняются точно; при этом мы должны сформулировать подобные аксиомам свойства, которым эти операции должны удовлетворять для того, чтобы программа выполнялась правильно, т. е. те свойства, на которых основывается доказательство правильности. (Для примера из предыдущего раздела требуется всего лишь точная целая арифметика в интервале [0,2a].)
При написании программы, работающей с действительными числами с приближенным выполнением операций, человек должен быть уверен, что выполняются некоторые предположения, такие, как b>0 означает, что
a*b=b*a
-(a*b)=(-a)*b
0*x=0
1*x=x и т. д.
Очень часто справедливость таких отношений оказывается существенной для логики программы. Чтобы обеспечить вычислимость, программисту следует быть как можно менее требовательным, но хорошая реализация должна удовлетворять как можно большему числу разумных требований.
Здесь уместно покаяться в одной моей ошибке. При реализации языка АЛГОЛ-60 мы решили, что отношение х=у будет принимать значение true не только в случае точного равенства, но также и тогда, когда значения х и у отличаются только в самом младшем разряде машинного представления, поскольку в противном случае было бы слишком маловероятно, что когда-нибудь удастся вычислить значение true.
Мы думали тогда о сходимости итераций, которые могли бы колебаться при ограниченной точности вычислений. Поскольку мы были очень щедры (с лучшими намерениями!) в трактовке действительных чисел как равных, часто выбранная нами операция сравнения оказывалась настолько слабой, что ее вообще вряд ли можно было использовать. Ситуация сводилась к тому, что программист, установив истинность отношений а=b и b=с, не имел права сделать вывод, что а=с. Мы быстро отказались от такого решения. На основании накопленного мною опыта такого рода я могу утверждать, что программист может использовать предоставленное ему средство программирования только с учетом определенных свойств этого средства; и наоборот, программист должен уметь сформулировать, какие именно свойства ему требуются. (Обычно программисты так не поступают, поскольку отсутствуют традиции отбора свойств, не требующих обоснования, и поэтому потребовалось бы утомительное перечисление слишком многих подробностей. Обильное распространение вычислительных машин с отвратительной аппаратной реализацией плавающей запятой, а также превратное представление, будто вычислительные машины предназначены непосредственно для специалистов по численному анализу, - все это нанесло большой ущерб программированию как профессии.)
О расплате машинной памятью за ускорение вычислений
В нынешних последовательных вычислительных машинах (я пишу эти строки весной 1969 г.) можно выделить два основных компонента: активный (процессор) и пассивный (память). Активный компонент должен быть быстрым, а пассивный должен быть большим. Далее мы будем рассуждать в предположении, что это разделение функций сохранится еще довольно долго, так что имеет смысл изучать вытекающие из него следствия.
С точки зрения программиста, машинная память и время счета это два различных ресурса, и я считаю, что именно программист (а не система) должен нести ответственность за их распределение, т. е. за разделение между ними необходимой нагрузки. Данный раздел посвящен разбору следствий этой обязанности программиста. Мы не собираемся рассматривать конкретные методы оценки нагрузок, т. е. давать количественные критерии, которыми программист руководствовался бы при своем выборе. Вместо этого мы изучим логическую связь между различными вариантами, которые волен выбирать сам программист.
Замечание. Не исключено, что этот выбор частично может быть возложен на систему. Однако во всех сколько-нибудь нетривиальных случаях проектирование распределения и установление эквивалентности требуют, по-видимому, математической изобретательности программиста. Все попытки автоматизировать этот род интеллектуальной деятельности выходят за рамки этой работы.
В простейшем случае мы имеем дело с вычислением, при котором регулярно требуется значение "ФУН(арг)", где "ФУН" - заданная вычислимая функция, определенная для текущих значений одной или нескольких хранимых в памяти переменных под общим названием "арг". При варианте программы A запоминается только значение арг, а значение ФУН(арг) вычисляется всякий раз, когда оно понадобится. При варианте B вводится дополнительная переменная, скажем фун, назначение которой состоит в том, чтобы хранить значение "ФУН(арг)", соответствующее текущему значению арг.
Если вариант A содержит
арг:= ... (т. е. присваивание значения арг)
то вариант B будет содержать
арг:= ...; фун : = ФУН(арг)
Этим обеспечивается сохранение отношения
фун = ФУН (ар г)
В результате выполнения этого отношения всякий раз, когда вариант A требует вычисления ФУН(арг), вариант B обратится к текущему значению переменной фун. Вариант B может быть предпочтен варианту A по двум причинам. Если значение ФУН(арг) требуется чаще, чем происходит перевычисление арг, то вариант B потребовал бы меньше времени счета. В случае необходимости этот прием может быть развит путем введения еще одной (на этот раз логической) функции "фун текущ", указывающей, выполняется ли отношение "фун = ФУН(арг)". В таком случае присваивание нового значения арг связывается с выполнением
фун текущ:=false
Всякий раз, когда требуется значение ФУН(арг), мы проверяем значение этой логической переменной и получаем ответ, следует ли перевычислять заново ФУН(арг). Если да, то вычисляемое значение присвоится переменной фун, а переменная "фун текущ" в соответствии со своим смыслом получит новое значение true. Назовем этот последний вариант программы именем C. Очевидно, что все три программы эквивалентны с точки зрения получаемых окончательных результатов и отличаются только в тех местах, где вариант A перевычисляет арг или использует значение ФУН(арг). Разумеется, ниоткуда не следует, что вариант B или C должен быть получен из варианта A автоматически. Однако весьма часто ситуация оказывается не столь простой, и теперь мы переходим к рассмотрению второй причины для введения такой переменной "фун". Часто бывает очень неудобно вычислять ФУН(арг) "из ничего" для произвольных значений арг, тогда как гораздо легче посчитать, как изменяется значение ФУН(арг) при данном изменении значения арг. В таких случаях корректировка значения "фун" ближе отражает существо функциональной зависимости, чем это подразумевается действием
арг:= ......; фун:=ФУН(арг)
Часто такая возможность бывает близко связана не только с существом функциональной зависимости, но также и с "историей переменной арг" в процессе счета! Мы наблюдали впечатляющий пример в программе табулирования простых чисел (см.
При тщательном изучений выяснилось, что существовала вторая комбинаторная головоломка, причем можно было установить взаимно однозначное соответствие между решениями этих двух задач. Если бы я решал вторую комбинаторную задачу, то нашел бы, что "фун" и "арг" поменялись ролями! В рамках традиционного программирования, которое не способствует выявлению таких функциональных зависимостей, обе, головоломки могли бы, вероятно, быть решены с помощью одинаковых программ, тогда как я изготовил две программы с различной структурной организацией. И я полагаю, что поступил правильно, так как единая программа для обеих головоломок требовала бы различных доказательств ее правильности в зависимости от того, какую головоломку предполагается решать, а это оборачивается некоторой несправедливостью, если мы хотим также, чтобы наше понимание вычислений отражалось в структуре наших программ.
раздел "Первый пример поэтапного составления программы") в связи с введением переменной ord, которая функционально зависит от j, а точнее говоря, представляет минимальное значение, удовлетворяющее условию
p[ord]2>j
причем корректировка ord оказалась весьма удобной операцией благодаря тому, что значения j монотонно возрастали со временем. Мне бы хотелось, чтобы в процессе понимания программ легко распознавались такие дополнительные переменные, хранящие избыточную информацию, даже если при этом функциональная зависимость несколько неопределенна, как в случае таблицы "крат" из того же примера. Я склонен рассматривать такие программы как некие оптимизированные конкретизации более абстрактной программы, даже если достигаемая введением дополнительных переменных оптимизация играет существенную роль в обеспечении эффективности программы. С точки зрения эффективности такая дополнительная переменная может оказаться настолько важной, что утратой чувства реальности обернулась бы попытка рассуждать на таком уровне, где мы абстрагируемся от наличия этой переменной. Способ обращения с такой дополнительной переменной часто оказывается существом алгоритма, и именно здесь мы часто пожинаем плоды своей математической изобретательности. Дело в том, что, хотя возможность хотя бы одной такой оптимизирующей конкретизации является существенной для изготовления практичной программы, часто при более внимательном изучении выясняется, что даже на самом низком уровне имеется выбор между различными оптимизирующими конкретизациями.
Замечание. Я вспоминаю одну программу, где дополнительная информация была настолько избыточной, что можно было бы не только вывести значение "фун" из "арг", но и наоборот. Зависимость между "фун" и "арг" неожиданно оказалась симметричной, и я был всерьез озадачен: с какой это стати я обращаюсь с ними столь несимметрично. Программа, о которой идет речь, порождала все решения комбинаторной головоломки.
О семействах программ
В предыдущем разделе мы рассмотрели конструирование программы для заданной задачи; при этом мы подходили к окончательной программе как к изолированному объекту, структурно обособленному и оцениваемому по индивидуальным критериям. Структура программы определялась последовательными разложениями; назначение этой структуры состояло в том, чтобы получить программу, правильность которой могла бы быть доказана без особых интеллектуальных усилий.
В этом разделе я постараюсь объяснить, почему предпочитаю рассматривать программу не как изолированный объект, а как представителя семейства "сопоставимых" программ. Если обратиться к традиционной терминологии, то сопоставимыми программами можно считать либо различные программы решения одной задачи, либо сходные программы для сходных задач.
Так почему же программист не может сосредоточить свое внимание на той программе, которую ему нужно составить, и почему ему следует принимать также во внимание целое семейство программ? Прежде всего вряд ли можно утверждать, что вы знаете, что делаете, если вы не в состоянии представить свое действие как обдуманный выбор из некоего множества действий, которые вы также могли бы предпринять. Однако если мы хотим осознать должным образом трудности построения больших сложных программ, то рассмотрение семейств становится оправданным и с чисто практической точки зрения. (А нам необходимо осознать эти специфические трудности: практика показала, что если некто способен отлично справляться с работой определенного масштаба, то из этого вовсе не следует, что он не напутает, если займется гораздо более трудным делом).
Разумеется, одно из обязательных свойств больших программ состоит в том, что они должны допускать последующее внесение изменений. Это объясняется тем, что часто даже логически правильные программы оказываются неподходящими для вычисления (например, не удовлетворяют одному или нескольким количественным критериям). Вторая причина может состоять в том, что, хотя программа логически правильна и даже вполне удовлетворяет исходным требованиям, она оказывается правильным решением не совсем правильно поставленной задачи; при этом приходится уточнять постановку задачи и соответственно модифицировать программу.
Таким образом, мы должны уметь модифицировать существующую программу (за такого рода деятельностью утвердилось несколько странное название: "сопровождение программы").
Итак, дело сводится к манипулированию текстом программы. Напомним кстати, что именно такая потребность послужила аргументом в пользу перфокарт и против перфолент при выборе средств ввода текстов программ. Впрочем, фактическая модификация текста программы может производиться многими различными способами. Я считаю, что если обращаться с текстом программы как с обычной линейной последовательностью символов, то по мере роста размеров текстов задача выявления и описания нужных изменений может стать просто непосильной для человека.
Если программа должна существовать в двух различных вариантах, то мне не хотелось бы рассматривать текст одной программы как модификацию текста другой. Гораздо предпочтительнее, чтобы обе отличающиеся программы могли рассматриваться в каком-то смысле как разные потомки одного прародителя, причем под прародителем понимается более или менее абстрактная программа, включающая то, что есть общего у обоих вариантов. Можно надеяться на то, что этого общего прародителя удастся легко распознать в предшествующей документации. Мы хотим, чтобы
(1) доказательство правильности этих двух вариантов проводилось по возможности единообразно; (2) у этих двух вариантов была по возможности одинаковая кодировка; (3) область действия модификации легко поддавалась локализации; это условие не выполняется, если переход от одной программы к другой требует сложных изменений, затрагивающих весь текст.
Итак, в этом наша конечная цель. Побудительной причиной служит потенциальное сходство между задачами модификации программы и составления программы: сформировав программу на некотором промежуточном этапе конкретизации, мы тем самым в сущности описываем в удобной форме "общего прародителя" для всех программ, которые могут быть получены дальнейшими конкретизациями. Имеется аналогия между "выбором решения" и "откладыванием решения": в обоих случаях мы имеем дело с тем, что остается, когда мы абстрагируемся от такого решения.
Накопленный нами опыт программирования подсказывает и вторую побудительную причину.
В процессе поэтапного составления программы, продвигаясь вглубь существа проблемы и проходя последовательно усложняющиеся конкретизации, мы на ранних этапах не только откладываем решение о том, как будут реализованы определенные замыслы, но также и не торопимся связывать себя четкой формулировкой этих замыслов. В последующих конкретизациях дальнейшие детали фактической постановки задачи прояснят ситуацию. (Далее в примерах мы продемонстрируем это еще нагляднее, чем для задачи табулирования простых чисел.) Поэтому наши первые уровни конкретизации в равной степени пригодны для целого класса постановок задач.
Другими словами, поэтапный подход подразумевает, что даже в случае хорошо поставленной задачи некоторые аспекты формулировки этой задачи игнорируются на первых порах. Это означает, что программист не рассматривает поставленное перед ним задание как изолированную работу, а имеет тенденцию относиться к этому заданию как к представителю целого семейства; другими словами, он предпочитает обобщить исходную постановку задачи в удобной для себя форме. Последовательно добавляя дополнительные подробности, он в конце концов привязывает свой алгоритм к решению исходной задачи.
Все это хорошо известно; каждый опытный программист всегда поступает именно так. Однако я концентрирую на этом внимание по целому ряду причин. Если заданная постановка задачи усложнена, т. е. ее нельзя воспринять мгновенно, то программисту необходимо анализировать эту постановку задачи именно таким способом (см. разд. "О количественной ограниченности наших возможностей"). Кроме того, даже если задача полностью определена, то все равно разумно предупредить возможность как можно большего количества последующих изменений в постановке задачи, которые удается заранее предусмотреть и учесть. Отмечая это, мы вовсе не призываем писать настолько "общие" программы, чтобы происходила недопустимая потеря эффективности, которая вполне возможна при непродуманных обобщениях постановки задачи (такие обобщения часто возникают под нажимом коммерсантов).
Однако мой опыт позволяет утверждать, что даже в рамках традиционного программирования оказывается весьма полезным умение искать подходящие обобщения осознанных надобностей, потому что эти рассмотрения могут внести ясность в то, как следует организовать структуру окончательной программы. А такие рассмотрения сводятся к ... осознанию (более или менее явному) целого семейства программ!
В одном из предшествовавших разделов ("О надежности аппаратуры") необходимость продуманной структурной организации программы представлялась как следствие требования о доказуемости .правильности программы. В этом разделе мы установили и другую причину: структура программы должна быть организована так, чтобы допускать внесение добавлений или изменений. Составленная нами программа не только должна отражать (в своей структуре) наше понимание этого факта; нужно еще, чтобы ее структура наглядно показывала, какого типа добавления могут вноситься без затруднений. К счастью, эти два требования естественно сочетаются.
О сравнении программ
Повседневная практика программирования показывает, что если задана проблема, которую нужно решить заданным алгоритмом, то программа для заданной машины определяется далеко не однозначно. При проектировании вычислительного процесса программист должен производить выбор из различных альтернатив. Даже имея правильную программу, он часто будет испытывать побуждение изменить ее; мотивом к этому может служить, например, ощущение, что другая программа оказалась бы более выигрышной с точки зрения требований, связанных с реализацией вычислений при помощи имеющихся ресурсов оборудования.
В связи с этим возникает проблема эквивалентности программ: даются две программы и ставится вопрос, вызывают ли они вычисления, приводящие к одинаковым результатам. После надлежащей формализации (как способа задания программ, так и машины, которая выполняет вычисления, вызываемые этими программами, а также "результатов" вычислений) можно, по-видимому, свести нашу проблему к корректно сформулированной задаче абстрактной математики. Однако я не собираюсь рассматривать эту проблему в такой общей форме. Напротив, вместо того чтобы начинать с двух произвольных заданных программ (например независимо придуманных двумя различными авторами), я интересуюсь различными программами, которые могут считаться изобретениями одного и того же разума; при этом возникает вопрос: как нам задумать (и структурно организовать) такие две различные программы, с тем чтобы облегчить работу по их сравнению.
Я проделал много экспериментов, и могу следующим образом подытожить накопленный мною опыт. Две программы, которые вызывают вычисления, приводящие к одинаковым результатам, эквивалентны именно в этом смысле и заведомо ни в каком другом. :и мы хотим сравнивать программы с целью сравнения соответствующих им вычислений, то основной вывод состоит в следующем. Это невозможно (или бесполезно, непривлекательно, или ужасно трудно, или подберите любой другой отрицательный эпитет), если по-разному организовано следование по двум программам, которые мы пытаемся сравнить.
Точнее говоря, сравнивать две программы и вычисления, которые могли бы быть ими вызваны, имеет смысл лишь тогда, когда удается разложить сопоставляемые вычисления на временную последовательность действий, которые допускают взаимное отображение, причем соответствующие тексты программ могут быть точно так же разложены на инструкции, каждая из которых соответствует одному из таких действий. Это очень сильное органичение. Сейчас я приведу первый пример.
Исключая побочный эффект логической проверки и предполагая значение "B2" постоянным (т. е. не изменяемым при выполнении "S1", так и "S2"), мы можем установить эквивалентность следующих двух программ:
|
if B2 then begin while B1 do S1 end else begin while B1 do S2 end |
(1) |
|
while Bl do begin if B2 then S1 else S2 end | (2) |
Приведу теперь второй, несколько более сложный пример несравнимости.
Заданы два массива X[1:N] и Y [1:N] и имеется логическая переменная "равны"; требуется составить программу, которая присваивает логической переменной "равны" значение высказывания "данные два массива поэлементно равны".
Пустые массивы (при N=0) считаются равными.
Введя переменную j и присваивая переменной "равны" значение высказывания "среди первых j пар не обнаружено отличий", мы можем написать следующие две программы:
|
j:=0; равны: = true; while jN do begin j:=j+1; равны:=равны(X[j] = Y[j]) end | (3) |
|
j:=0; равны = true; while jN равны do begin j:=j+1; равны:=(X[j] = Y[j]) end | (4) |
| при j=0 PABHЫj=true при j>0 РАВНЫj=РАВНЫj-1(X[j]=Y[j]) |
(5) |
Обе программы сохраняют отношение
| равны := РАВНЫj | (6) |
|
j:=0; равны : = РАВНЫ0; while "возможно, все еще: равны РАВНЫN" do begin j:=j+1; равны: =РАВНЫj end | (7) |
Программы (3) и (4) отличаются тем, что они с помощью разных критериев обеспечивают для переменной "равны" конечное значение РАВНЫN.
В программе (3) выбран очень простой критерии, а именно j=N
Когда начинается очередное выполнение повторяемого оператора, отношение равны=РАВНЫj
все еще выполняется. Поэтому после выполнения присваивания j:=j+1 выполняется отношение равны =РАВНЫj-1
и поэтому оператор присваивания равны:=равны (X[j] - Y[j])
представляет собой непосредственную запись рекуррентного соотношения (5). Чтобы прийти к программе (4), мы должны предварительно провести некоторый анализ применительно к рекуррентному соотношению (5). Из этого соотношения можно вывести (опять таки с помощью математической индукции), что если PABHЫj=false, то PABHЫN=false и поэтому если PABHЫj=false, то РАВНЫj=РАВНЫN. Если возникает такая ситуация, то можно гарантировать и равенство "равны=РАВНЫN,", и это приводит к программе (4). Набор поддействий, с которыми должен справиться повторяемый оператор в программе (4), ограничивается начальным состоянием "paвны=true", и поэтому в программе (4) присваивание "равны: = РАВНЫj" может быть упрощено до вида равны:=(Х[j] =Y[j])
Теперь ясно, почему введение программы (7) как абстракции программ (3) и (4) только запутало ситуацию. С помощью фразы "возможно, все еще: равныРАВНЫN" мы устанавливали истинность или ложность логического выражения, не сформулировав само это выражение, и это оказалось очень сложным. Мы пытались интерпретировать (7) как программу, в которой следование на верхнем уровне было частично не определено и изменялось в зависимости от конкретизации. В итоге мы пытались рассматривать последние строки программы (7) как модель для последних строк как программы (3), так и программы (4), но это оказалось бесперспективным, поскольку вызываемые этими строками вычисления не могут быть разложены с соблюдением взаимно однозначного соответствия. На этом мы заканчиваем обсуждение программ, которые мы считаем несравнимыми. Примеры сравнимых программ будут встречаться в следующих разделах.Заключительное замечание: мы сформулировали принцип, что "сопоставляемые вычисления могут быть разложены в последовательность действий, между которыми удается установить взаимно однозначное соответствие". Мы вовсе не требовали, чтобы такие сопоставляемые действия приводили к одинаковым результатам! Мы можем сравнивать не только разные варианты программ для выполнения одной и той же работы, но и различные программы для выполнения сходных работ.
О том, чего мы достигли
Размышляя о рассматриваемой нами структуре программ, я метафорически представлял себе программу как бусы из отдельных жемчужных зерен.
Мы описывали программу с помощью уровней, и каждый уровень содержал "конкретизации" понятий, которые предполагались имеющимися на более высоких уровнях. Эти конкретизации были либо динамическими (алгоритмы), либо статическими (структуры данных), и их должна была понимать соответствующая машина. Я использую термин "зерно" для такой машины вместе с относящимися к ней конкретизациями.
Наша предыдущая программа представляет собой бусы из шести зерен либо в порядке
ВЫЧНАЧ ЧИСТНАЧ IСЧИТЫВАНИЕ ВЫЧПОЗ СТРОП ДЛИНЦИК
либо в порядке
ВЫЧНАЧ ЧИСТНАЧ IСЧИТЫВАНИЕ ВЫЧПОЗ СТРОП КОРЦИК
ДЛИНЦИК и КОРЦИК - это два разных зерна; они сводят одинаковые понятия ("верхнего уровня") к одним и тем же понятиям ("нижнего уровня"); отличаются только способы конкретизации: это разные варианты программ решения одной и той же задачи на одной и той же машине.
Изменение программы будет рассматриваться как замена одного или более зерен в первоначальных бусах на одно или несколько других зерен. Каждое зерно - это отдельный элемент, и из них составляются программы. Теперь мы считаем составление программы (как представителя класса взаимосвязанных программ) процессом из двух этапов: изготовление зерен (в большем количестве, чем строго необходимо), а затем выборочное нанизывание их в соответствующих бусах.
Для такого двухэтапного подхода имеется много причин. Проектируя программу, мы должны рассмотреть очень много различных программ, а когда наша программа будет готова, нам потребуется изменять ее (заменяя на один из эквивалентных вариантов). Коль скоро мы воспринимаем программы как линейные строки основных символов языка программирования, а к изменению программы относимся как к обработке текста такого уровня, то каждое изменение программы следует понимать в масштабе всей совокупности программ (правильных или ошибочных!), которые могут быть написаны на этом языке программирования.
Неудивительно, что при этом изменение программы оказывается весьма рискованным! Основной символ - это слишком маленький и лишенный смысловой нагрузки объект для того, чтобы описывать с его помощью такие процессы. Естественным элементом для описания таких модификаций представляется зерно, воплощающее в себе независимое проектное решение или, быть может, изолированный аспект исходной постановки задачи.
Еще одно подтверждение той же мысли. С появлением языка АЛГОЛ-60 выяснилось, что синтаксис является весьма эффективным средством для выражения структуры текста программы. (Синтаксис окружили таким ореолом, что многие специалисты стали отождествлять системное программирование с синтаксическим анализом.) Однако при этом несколько упускали из виду, что при выражении структуры через синтаксис эта структура задается очень неявно, т. е. должна выводиться путем применения алгоритма грамматического разбора к линейной последовательности основных символов. Это огорчительно, если учесть, что весьма часто модификация программы оставляет без изменений большие части структуры, так что после утомительного нового грамматического разбора модифицированного текста повторно выявляется та же самая структура. У меня сложилось твердое мнение, что пригодность методов контекстно-свободного анализа для представления структуры сильно преувеличивалась. (Мои ближайшие сотрудники показали мне следующую ошибку в одной программе на языке АЛГОЛ-60. Программа выдавала ошибочные результаты, хотя трансляция производилась с соответствующим полным контролем, который требовал в добавление к тексту программы заключительный символ progend после последнего end. Этот добавочный символ в неподходящем месте программы служил сигналом об ошибке; благодаря этому, можно было установить правильность соответствия скобок begin-end. Оказалось, что
где-то в программе была пропущена кавычка, закрывающая строку; где-то в последующем тексте программы была пропущена кавычка, открывающая строку; структура begin-end полученной программы была синтаксически правильна; идентификаторы, описанные между двумя пропусками, использовались только в этом участке программы, так что даже контекстно-зависимый контроль не мог сигнализировать об ошибке.
К тому времени у меня уже были сомнения в пригодности контекстно-свободных методов для выражения макроскопической структуры, и поэтому я пришел в восторг, когда мне показали эту ошибку).
Чем больше я размышляю о зернах, тем больше убеждаюсь в том, что нечто вроде зерен - это единственный выход из положения, если мы сознаем, что должны принимать во внимание (для большой программы) порядка тысячи возможных вариантов. Нельзя ожидать, что программист будет изготовлять каждый вариант из этой тысячи с самого начала, независимо один от другого. Я вижу единственный способ обеспечения такого потенциального разнообразия в применении комбинаторных методов, т. е. в том, чтобы изготовить больше зерен (скажем, 250), чем нужно для одних бус (скажем, 200) и выборочно нанизывать их в бусы. Другого подходящего способа я не вижу. Можно было бы достигнуть большого разнообразия, применяя комбинаторные перестановки, но для нас это не годится, потому что окончательные бусы должны быть надлежащим образом подогнаны, и если заданы зерна, то вполне определен порядок нанизывания их на нить для получения подогнанных бус. К тому же, если это и не так, то допустимые изменения порядка оказываются отнюдь не по существу.
К тому же с помощью зерен проясняется смысл "неполной" программы, состоящей из верхней части бус: ее можно рассматривать как полную программу для выполнения на соответствующей машине (возможная реализация которой задается нижней частью бус). В сущности, правильность верхней части бус может быть доказана безотносительно к выбору нижней части. Между двумя последовательными зернами мы можем сделать "зазор" в виде руководства по машине, реализуемой частью бус снизу от зазора и используемой в программе, которая представлена частью бус сверху от зазора. Это руководство служит средством сопряжения между, двумя частями бус. Такая форма сопряжения кажется нам более удобной, чем интерпретация представления данных как средства сопряжения операций; в частности, она лучше обеспечивает комбинаторную гибкость, которая требуется, когда программа должна обладать приспособляемостью.
Сделаем еще замечание относительно областей действия понятий вдоль бус.
Например, понятие "отражение" вводится в нашем верхнем зерне "ВЫЧНАЧ" и исчерпывающе объясняется в предпоследнем снизу зерне "СТРОП". Если мы теперь придем к заключению, что программа в рассматриваемом виде требует слишком много машинной памяти и поэтому мы не можем позволить себе введение переменной "отражение", то нам предстоит пересмотр основной программы и мы должны будем заменить верхние пять зерен на другие, потому что ими исчерпывается область действия понятия "отражение". Нижнее зерно (либо "ДЛИНЦИК", либо "КОРЦИК") может быть сохранено без изменений. (Мы упоминаем об этом, чтобы проиллюстрировать тот факт, что замена зерна никоим образом не предопределяет замену нижнего зерна.)
В связи с вопросом об областях действия понятий вдоль бус мне хотелось бы привлечь внимание читателей к одному наблюдению, которое произвело на меня сильное впечатление, когда я впервые сделал его. (В ретроспективе оно представляется совершенно очевидным, и именно поэтому имеет смысл изложить его.) Для каждого зерна мы принимаем "независимое проектное решение", и поэтому порядок зерен вдоль бус подразумевает порядок проектных решений. Можем ли мы изменить этот порядок? Да, можем, хотя тогда у нас будут другие зерна. Экспериментируя, я следовал известному совету: если у вас есть два элемента (в нашем случае "строить" и "печатать"), первым делом выявите их взаимосвязь (в нашем случае "отражение"), и тогда оба элемента можно будет конкретизировать независимо один от другого. Я так и сделал и пришел к следующему виду бус:
ВЫЧНАЧ СТРОП' ЧИСТНАЧ' IСЧИТЫВАНИЕ' ВЫЧПОЗ' КОРЦИК
(Четыре промежуточных зерна помечены для указания того, что ими заменены другие зерна, хотя в них воплощены те же самые решения, что и в соответствующих исходных зернах.) Получившаяся программа более запутанная. Почему?
Вдоль бус мы можем указывать для каждого понятия его область действия. Разумеется, они перекрещиваются, и мы можем рассматривать их как отдельные нити, которые сплетаются в цельное толкование как некий вид "логического каната".
Запутанному варианту соответствует логический канат, свитый из большего числа местами более длинных нитей; такой логический канат "толще", а вся конструкция более тесно взаимосвязана. Это наблюдение произвело на меня сильное впечатление потому, что оно очень наглядно показало (по крайней мере мне), что изящество, ясность и тому подобное в значительной степени определяются количественными аспектами. (Этим владел Моцарт: многие его произведения, от которых замирает дыхание, обманчиво просты; кажется, будто они созданы практически из ничего!)
Можно сформулировать это наблюдение в более научных терминах. Помеченный вариант запутан, потому что отражение сводится к строкам на слишком ранней стадии, а это вынуждает нас описывать "ВЫЧНАЧ", "IСЧИТЫВАНИЕ" и "ВЫЧПОЗ" в терминах строк, хотя их можно было бы еще объяснять непосредственно .через отражение, т. е. независимо от выбираемого представления отражения. Другими словами, в первоначальном, варианте мы искуснее использовали свою способность к абстракции, чем в помеченном варианте. Чем больше число зерен, которые не зависят от конкретного представления, тем больше приспособляемость программы и тем легче ее понимать, поскольку эти зерна доступны пониманию на более высоком уровне абстракции. По-видимому, практика показывает, что требования приспособляемости и ясности имеют общую основу и, более того, сочетаются самым естественным образом. Это весьма радует (хотя и не удивляет). Это также проясняет (по крайней мере для меня) предмет нашего рассмотрения. К чему бы мы ни пришли, это не будет универсальным методом решения проблем автоматическим путем или с участием человека. Однако если человек сумеет найти решение, то мы можем помочь ему правильно оценить различные аспекты "изящества" этого решения. А уже это послужит ему ориентиром.
Об абстракции
На этом этапе мне трудно четко охарактеризовать абстракцию отчасти потому, что она проникает во все аспекты программирования. Рассмотрим некий алгоритм и все возможные вычисления, которые могут быть порождены этим алгоритмом.
Если исходить из вычислений, то алгоритм - это то, что остается, если абстрагироваться от конкретных значений обрабатываемых данных. Понятие "переменной" представляет собой абстракцию соответствующего текущего значения. Я слышал (к большому сожалению, не могу вспомнить, от кого) мнение, что, как только человек осознал, как в программировании используются переменные, он понял сущность программирования. Мы можем найти подтверждение этому мнению, если вспомним использование математической индукции применительно к повторениям цикла: с одной стороны, именно благодаря абстракции понятия вводятся таким образом, что удается сформулировать индуктивный переход; с другой стороны, именно организация повторений требует введения понятия "переменной". (При отсутствии повторений мы могли бы ограничиться "величинами", значения которых должны определяться не более чем по одному разу и никогда не переопределяются в отличие от значений переменных.)
Абстракция присутствует также в процессе присваивания операциям имен и использования этих операций с точки зрения того, "что она делает", с полным безразличием к тому, "как она работает". (Аналогично следует считать, что руководство по программированию описывает абстрактную машину: конкретная аппаратура, предоставляемая изготовителем, - это не что иное как механическая - и обычно несовершенная! - модель этой абстрактной машины.) Имеется явная аналогия между использованием в программе именованной операции независимо от того, "как она работает", и использованием теоремы независимо от того, как она доказывалась. Даже если ее доказательство исключительно запутанное, теорема может оказаться очень удобной для практического использования.
Здесь я снова сошлюсь на количественную ограниченность наших возможностей.
Рассуждение с перечислением не вызывает нареканий, пока оно проходит, но поскольку мы мыслим довольно медленно, такое рассуждение пройдет не слишком далеко. Рассуждение с перечислением оказывается подходящим интеллектуальным средством только при строгом соблюдении умеренности его применения. Следует рассматривать абстракцию как основной интеллектуальный прием, позволяющий ослабить количественные ограничения, которые накладываются на рассуждение с перечислением.
(В этом месте М. Вуджер из Национальной физической лаборатории, Теддингтон, Англия, сделал замечание, которое я с благодарностью привожу. "Имеется аналогия между неанализируемыми терминами, в которых формулируется аксиома или теорема, и неанализируемыми операндами, к которым предполагается применять именованную операцию".)
Организация групп и последовательностей
Пока мы рассматриваем подход к программированию, при котором четко распознается иерархия уровней абстракции. Материал данного раздела применим также к программированию на языках программирования в том виде, как они понимаются в настоящее время, т. е. на уровне неизменяемой семантики. (И есть основания полагать, что выводы этого раздела применимы за рамками ограниченной области программирования, поскольку они касаются решения проблем в общем случае.)
Я проиллюстрирую мою основную мысль на двух примерах, которые я тоже использовал на устных экзаменах. Первым примером я обязан Н. Вирту.
Задача состоит в том, чтобы построить программу, генерирующую непустые последовательности из цифр О, 1 и 2 без непустых поэлементно совпадающих соседних подпоследовательностей; эти последовательности требуется генерировать в лексикографическом порядке до тех пор, пока не будет получена последовательность длины 100 (т. е. из ста цифр). Программист может использовать известный факт, что удовлетворяющая этим условиям последовательность длины 100 действительно существует. Список последовательностей, которые должны генерироваться, начинается так:
0 01 010 0102 01020 010201 0102010 0102012 .......
Мы занимаемся поиском "хороших" последовательностей и предполагаем, что имеется элементарная операция проверки, является ли испытуемая последовательность хорошей. Если она хорошая, то эта последовательность печатается и расширяется присоединением нуля, что дает новую испытуемую последовательность. Если же последовательность не является хорошей, мы выполняем над ней операцию "увеличить" для получения следующей испытуемой последовательности; при этом имеющиеся в конце цифры 2 удаляются, а последняя оставшаяся цифра увеличивается на 1. (Операции "расширить нулем" и "увеличить" обеспечивают лексикографический порядок генерации испытуемых последовательностей; поэтому выбираемые из них решения будут печататься также в лексикографическом порядке.)
Алгоритм начнется с исследования приведенных ниже испытуемых последовательностей; те последовательности, которые помечены звездочками, будут отвергнуты как "нехорошие",
0 *00 01 010 *0100 *0101 0102 01020 *010200 010201 0102010 *01020100 *01020101 *01020102 *0102011 0102012 .......
Я заметил, что большинство моих студентов были склонны писать программу со следующей структурой:
установить в исходную последовательность одиночный нуль, repeat if хорошая then
begin печатать испытуемую последовательность; расширить испытуемую последовательность нулем end else
увеличить испытуемую последовательность until длина=101
Хотя эта программа дает правильный результат, она может (и мне бы хотелось сказать - должна) вызывать возражения. Первое возражение относится к критерию останова. Когда будет напечатано решение длины 100, мы (зная алгоритм) можем сообразить, что после этого начальная испытуемая последовательность будет иметь длину 101, а это и есть критерий останова. Однако такой способ обоснования критерия останова является слишком обходным и неестественным. (То, насколько он неестественный, ярко продемонстрировали студенты, которые не замечали, что генерируется лишняя испытуемая последовательность, и описывали испытуемую последовательность как массив из 100 элементов, а не из 101). Второе возражение состоит в том, что операция "увеличить испытуемую последовательность" никогда не увеличивает длину этой последовательности; поэтому, после того как отвергается испытуемая последовательность, выполняется ненужная проверка длины. (Я использовал этот пример на студенческих экзаменах, не выделив перед этим в своих лекциях общие принципы решения проблем, и поэтому не испытывал особой досады. В каком-то смысле я даже был доволен впечатлением от этих экзаменов, потому что оно оказалось для меня побудительным мотивом к тому, чтобы разобраться как можно глубже в принципах решения проблем, сформулировать и преподавать их.) Приведенные выше возражения не применимы к следующей программе, в которой пустая последовательность трактуется как действительное решение, которое не должно печататься. На том же уровне детализации эта программа имеет следующую структуру:
установить испытуемую последовательность пустой; repeat расширить испытуемую последовательность нулем; while не хорошая do увеличить испытуемую последовательность; печатать испытуемую последовательность until длина=100
Здесь длина - это длина печатаемого решения (если оно есть); это избавляет нас от неестественного обоснования прежнего критерия останова. Кроме того, не будет генерироваться впустую избыточная последняя испытуемая последовательность (которая даже не проверялась) и не будет более появляться лишняя проверка длины; поскольку теперь у нас два цикла; один внутри другого. Последнее соображение, вероятно, окажется наиболее убедительным для тех, кто считает эффективность главным критерием. Лично я, придавая существенное значение понимаемости, отдаю предпочтение второй программе, потому что могу интерпретировать ее как конкретизацию следующей программной структуры:
установить последовательность пустой; repeat преобразовать последовательность в следующее решение; печатать последовательность until длина=100
Эта (более абстрактная) программа имеет дело только с теми последовательностями, которые являются решениями: на этом уровне описания можно игнорировать то обстоятельство, что переход от одного решения к следующему осуществляется через некую последовательность испытуемых решений, которые оказываются неподходящими. Вторым примером я обязан Дж. Вейзенбауму. Нужно составить программу, которая для заданного положительного целого п определяет наименьшее число s, которое может быть разложено в сумму вида аn+bn по крайней мере двумя нетривиально различными способами.
(Для n=1 s=2=01-21=11+11 n=2 s=25=02=52=32+42
n=4 s=635318657=594-1584=1334+1344)
Когда я впервые использовал этот пример на устном экзамене, студент потратил двадцать минут на то, чтобы как-то разобраться в задаче, а затем набросал алгоритм поиска, который, если бы его слегка подправить, действительно позволял бы найти число, допускающее различные разложения в суммы вида аn+bn. Однако студент не мог доказать, что вырабатываемое его алгоритмом значение s было бы минимальным значением. (Фактически он до последнего момента просто игнорировал эту часть постановки задачи.) Затем он перестроился и написал программу следующего вида:
integer s, k; s:=l; repeat s:=s+1; k:="число способов разложения s на сумму вида an+bn" until k>1
получив при этом безнадежно неэффективный алгоритм. Его ошибка состояла в том, что он решил на слишком раннем этапе последовательно исследовать натуральные числа, подавляющее большинство которых вовсе не допускают нужного разложения. Если же принять во внимание, что мы ищем значение минимального разложимого числа, удовлетворяющего некоему дополнительному требованию, то мы приходим к алгоритму, первый набросок которого может иметь такой вид:
integer k, s, t; t:=1 (и другие начальные установки); repeat s:="минимальное разложимое значение, превышающее t" k:="число способов разложения этого минимального значения" t:=s until k>1
Можно накапливать в памяти множество триплетов (пар чисел с соответствующими s-значениями), в которых каждый раз будут представлены одна или несколько пар с минимальным s-значением, превышающим t, и перестраивать это множество всякий раз, когда увеличивается значение t. При этом получается программа, которая более эффективно обеспечивает продвижение t от одного разложимого значения к следующему разложимому значению. Итак, речь идет о программировании (а может быть, о решении проблем в общем случае?) методом разумной отсрочки решений и оформлений!
Первый пример поэтапного составления программы
В разделе "О понимании программ" я делал упор на необходимость такой систематизации следования, при которой структура вычислений могла бы отражаться в структуре программы; в этом плане мы можем говорить о единой структурной организации программы и вычислений. В данной секции я попытаюсь придать несколько больше содержания все еще довольно туманному понятию .структурной организации. Мы попытаемся употребить нашу способность к абстракции для того, чтобы сократить область применения рассуждений с перечислением, и будем последовательно применять способы разложения, рассмотренные в разделе "О понимании программ".
Вместо того чтобы предоставить читателям (как уже готовую конструкцию) то, что я склонен называть хорошо организованными .программами, мне хотелось бы описать чрезвычайно подробно процесс составления такой программы. Я поступаю так потому, что программы не существуют изначально; напротив, их нужно создавать, и меня особенно интересуют именно те программы, которые, .как мне кажется, достаточно хорошо соответствуют нашим возможностям построения и понимания.
Пусть перед нами стоит задача научить машину печатать таблицу первой тысячи простых чисел, причем число 2 считается первым простым числом.
Замечание 1. Этот пример был выбран потому, что он, с одной стороны, достаточно сложен для того, чтобы служить моделью некоторых общих проблем, с которыми мы сталкиваемся в программировании, а с другой стороны, его математическая основа настолько проста и всем знакома, что не будет отвлекать нашего внимания.
Замечание 2. Я не утверждаю, что моя окончательная программа будет "наилучшей возможной" с точки зрения любого критерия, .который вздумает выбрать кто-либо из читателей. По крайней мере два читателя предыдущего варианта этой работы, встретив вычисление остатков посредством операции деления, бурно прореагировали: "Но ведь всякий знает, что самый эффективный способ порождения простых чисел состоит в использовании решета Эратосфена"; после этого они оказались не в состоянии читать что-либо далее.
Сущность нашего подхода будет состоять в том, чтобы составлять программу мелкими шагами, принимая на каждом этапе как можно меньше решений.
По мере детализации анализа проблемы будет происходить дальнейшее усовершенствование программы.
Если нужно получить алгоритм, то желательно, чтобы вычисления состояли из действий, соответствующих удобному для понимания набору инструкций. Простейшей формой нашей программы является описание 0:
begin "напечатать первую тысячу простых чисел" end
и если "напечатать первую тысячу простых чисел" отсылает нас к инструкции из принятого набора, то описание 0 решает нашу задачу. Чтобы продолжить рассуждения, предполагаем, что такая инструкция не входит в принятый набор. Поэтому нам следует придумать вычисление, состоящее из "более простых" действий и приводящее к получению желаемых результатов. Прежде всего предлагается отделить получение простых чисел от их печати, и мы вводим описание 1":
begin variable "таблица р"; "заполнить таблицу р первой тысячью простых чисел"; "напечатать таблицу р" end
показывающее, что наше вычисление состоит из последовательности двух действий и выполняется над фиксированной областью памяти, содержащей одну переменную под названием "таблица р". Первое действие присваивает значение этой переменной, а второе действие управляется полученным к тому времени значением этой переменной.
Опять-таки, если "заполнить таблицу р первой тысячью простыx чисел" и "напечатать таблицу р" встречаются в принятом наборе инструкций (а "таблица р" относится к классу допустимых ресурсов), то наша задача решена. И снова, чтобы продолжить рассуждения, мы предполагаем, что это не так. Это означает, что в следующей конкретизации мы должны выразить результаты этих двух действий с помощью двух дальнейших подвычислений. Кроме того, мы должны решить, как представлять информацию, которая должна содержаться в промежуточном значении все еще довольно неопределенного объекта "таблица р".
Прежде чем следовать далее, я хотел бы подчеркнуть, как мало мы приняли решений, когда написали описание 1, и в сколь незначительной степени была принята во внимание исходная постановка нашей задачи.
На каком- то этапе придется решать эту проблему, и возникают вопросы: "когда?" и "как?"
В принципе намечаются два подхода. Первый подход состоит в том, чтобы попытаться отсрочить решение о разложении "таблицы р" на (более нейтральные и менее проблемно-ориентированные) компоненты. Если мы откладываем решение вопроса о разложении "таблицы р", то нам остается теперь конкретизировать то или иное действие или оба действия. Мы можем сделать это, подбирая подходящий набор операций над все еще таинственным объектом "таблица р", затем мы объединяем эти операции и, руководствуясь их требованиями, разрабатываем наиболее удобную структуру "таблицы р".
С другой стороны, можно пытаться принимать решения относительно структуры "таблицы р". Если решено, как будет представляться таблица первой тысячи простых чисел, то дальнейшая конкретизация каждого из двух действий может выполняться независимо от другого действия.
Оба подхода одинаково сложны; степень удобства алгоритма для выполнения, скажем, первого подвычисления будет сильно зависеть от легкости и изящества возможной реализации предполагаемых операций над "таблицей р", и если одна или несколько операций оказываются слишком неудобными, то вся постройка разбивается вдребезги. С другой стороны, если мы поспешно примем необдуманное решение относительно структуры "таблицы р", то вполне; возможно, что тогда окажется затруднительной реализация подвычислений. Невозможно обойти эту проблему: в изящной программе, структура "таблицы р" и относящиеся к ней вычисления должны быть хорошо согласованы. Я полагаю, что поведение умелого программиста сводится в первую очередь к попыткам найти самое лёгкое решение, т. е. такое решение, которое требовало бы минимальных затрат усилий (методом проб и ошибок, последовательной подгонки и т.д.) при максимально обоснованной надежде на то, что не придется сожалеть об этом решении.
Чтобы не затягивать чрезмерно рассмотрение этой проблемы, предположим, что у программиста хватает мужества решить, что отныне нужно в первую очередь заняться установлением структуры "таблицы р".
Коль скоро принята такая точка зрения, немедленно возникает следующая альтернатива.
С одной стороны, мы можем попытаться использовать тот факт, что "таблица первой тысячи простых чисел" является не просто таблицей из тысячи чисел, какой была бы, скажем, таблица месячных заработков тысячи работников фабрики, но что все эти числа различны между собой.
Воспользовавшись этим, мы можем представить нашу информацию с помощью линейного логического массива, последовательные элементы которого соответствуют последовательным числам натурального ряда и указывают, является ли соответствующее число ряда простым. Теория чисел дает нам оценку порядка тысячного простого числа, а тем самым и граничную достаточной длины массива. Организовав нашу информацию таким способом, мы подготовили бы аппарат для того, чтобы с легкостью отвечать на вопрос: "Является ли значение п (меньшее чем максимум) простым?" С другой стороны, можно предпочесть массив типа integer, в котором будут перечислены последовательные простые числа. (При этом будет использована та же оценка, полученная методами теории чисел, коль скоро максимальное значение элемента массива должно быть задано заранее). Во втором случае мы создаем аппарат, удобный для ответа на вопрос: "Какое значение принимает k-е простое число при k1000?"
Мы советовали бы программисту предпочесть второе представление. Оно более удобно для операции печати, когда следует печатать именно простые числа, а не числа натурального ряда с указанием того, простые они или нет. Оно обеспечивает преимущества и на этапе вычислений, даже если учесть, что для поиска простых множителей заданного числа может оказаться полезной проверка, является ли простым то или иное число.
Следующим этапом конкретизации нашей программы будет формулировка соглашения относительно представления все еще таинственного объекта "таблица p" и переопределение наших двух операций в соответствии с этим соглашением.
Соглашение состоит в том, что информация, которая должна содержаться в "таблице p", будет представляться значениями элементов массива "integer array p[1:1000]"; при 1k1000 значение p[k] будет равно k-му простому числу, причем простые числа упорядочиваются в порядке возрастания их значений. (Если возникнет вопрос о максимальном значении этих целых чисел, то мы будем предполагать, что согласно теории чисел оно достаточно велико.)
Если мы захотим теперь описать эту конкретизацию, то столкнемся с новой трудностью.
Наше описание 1 имело форму единой программы благодаря тому, что представляло собой конкретизацию единого действия "напечатать первую тысячу простых чисел", сформулированного в описании 0. (Если говорить более строго, описание 1 могло бы иметь форму тела процедуры.) Однако дело обстоит не так на нашем следующем уровне, когда требуется конкретизировать (в каком-то смысле одновременно) три именования, а именно "таблицу p" и два действия, и мы должны ввести некоторую идентифицирующую терминологию для указания того, что конкретизируется.
Чтобы продолжить обсуждение, сделаем весьма спорное утверждение. Скажем так: описание 0 - это правильный текст программы, выраженный с помощью одного именованного действия "напечатать первую тысячу простых чисел"; пусть оно идентифицируется кодом 0a. Описание 1 называется "1", потому что представляет собой следующую конкретизацию описания 0; оно содержит конкретизацию действия 0a (единственного термина, которым выражается описание 0), а само выражается с помощью трех именованных понятий, которым мы присваиваем следующие коды:
| "таблица p" | 1a |
| "заполнить таблицу p первой тысячей простых чисел" | 1b |
| "напечатать таблицу p" | 1c |
Описание 2:
1a="integer array p[1:1000]" 1b="для k от 1 до 1000 приравнивать p[k] k-му простому числу" 1c="p[k] для k от 1 до 1000"
Описание 2 выражается с помощью трех именованных понятий, которым мы присваиваем (очевидным образом) коды 2a, 2b и 2c. (В кодовом обозначении описание 2 выглядит очень банально: оно только констатирует, что для 1a, 1b и 1c мы выбрали конкретизации 2a, 2b и 2c соответственно.)
Замечание. При представлении информации, которая должна содержаться в "таблице p", мы предпочли не использовать ни тот факт, что каждое печатаемое значение встречается только один раз, ни то, что они встречаются в порядке возрастания величин. Другими словами, это означает, что действие, которое должно выполняться под именем 2c, рассматривается как частный случай печати любого набора из тысячи целых чисел (это могла бы быть таблица месячных заработков тысячи пронумерованных работников!). Точный результат действия печати в этом примере однозначно определяется как первая тысяча простых чисел; однако мы представляем его себе как частый случай более широкого класса возможностей. При дальнейшей конкретизации действия 2c мы занимаемся всем этим классом, а частный случай в рамках этого класса описывается значениями элементов массива p. Когда люди говорят об "описании взаимосвязей", у меня часто возникает впечатление, что они отвлекаются от подразумеваемого обобщения понятия класса "возможных" действий.
Если 2b и 2c встречаются в принятом наборе инструкций (а следовательно, 2a является потенциально доступным ресурсом), то вся наша проблема решается. Чтобы продолжить рассуждения, мы опять предполагаем, что это не так. При этом мы сталкиваемся с задачей представления подвычислений для 2b и 2c. Однако теперь, поскольку уже введен уровень 2, соответствующие конкретизации для 2b и 2c могут быть построены независимо.
Конкретизация для 2b: "для k от 1 до 1000 приравнивать p[k] k-му простому числу".
Мы ищем описание 2b1, т. е. первую конкретизацию для 2b. Дополнительная нумерация после 2b (вместо того, чтобы называть наше следующее описание "3 с чем-то") вводится для того, чтобы отметить взаимную независимость конкретизации для 2b и 2с соответственно.
В описании 2b1мы должны дать алгоритм присвоения значений элементам массива p.
Это означает, что мы должны, например, описать, в каком порядке будут производиться эти присваивания. В нашей первой конкретизации мы хотим описать именно это и ничего более. Очевидный, но нелепый вариант описания начинается следующим образом ("номер варианта" заключается в скобки):
2b1(1): begin р [1]:=2; р[2]:=3; р[3]:=5; р[4]:=7; р[5]:=11; ... end
При этом предполагается, что познания программиста включают в себя таблицу первой тысячи простых чисел. Мы не станем заниматься этим вариантом хотя бы потому, что он ставит под сомнение, нужна ли вообще программисту вычислительная машина. Если задано первое простое число (=2), а тысячное предполагается неизвестным программисту, то самым естественным порядком заполнения массива р представляется порядок возрастания значений индексов. Выражая эту мысль, мы приходим (например) к записи
2b1(2): begin integer k, j; k:=0; j:= 1; while k<1000 do begin "увеличить j до значения следующего простого числа"; k:=k+1; p[k]:=j end
end
Если идентифицировать переменную k как номер очередного найденного простого числа и убедиться в том, что наше первое простое число (=2) действительно представляет собой наименьшее простое число, большее чем 1 (оно равно начальному значению j), то правильность описания 2b1(2) легко доказывается математической индукцией (в предположении, что существует достаточное количество простых чисел). Описание 2b1(2) оказывается законченной программой, если в предусмотренный набор входит операция "увеличить j до значения следующего простого числа" - назовем ее 2b1(2)а, - однако мы предположим, что это не так. В таком случае нам нужно выразить в следующей конкретизации способ увеличения j (и опять-таки ничего более). Мы приходим к описанию уровня 2b2(2)
2b1(2)а= begin boolean jпростое; repeat j:=j+1; "присвоить'переменной jпростое значение предиката: j является простым числом" until jпростое end
Замечание. Здесь мы используем форму repeat- until ("повторить - пока не"), чтобы указать, что значение j всегда должно увеличиваться по крайней мере один раз.
И в этом случае правильность описания вряд ли может быть поставлена под сомнение.
Впрочем, если предположить, что программист знает, что, за исключением числа 2, все последующие простые числа являются нечетными, то можно ожидать, что его не удовлетворит приведенный выше вариант, поскольку это описание оказывается совершенно неэффективным. Расплатой за "отсутствие дара предвидения" является пересмотр варианта 2b1(2).
Простое число 2 будет обрабатываться отдельно, после чего будут циклически перебираться в поиске простых чисел только нечетные значения. Вместо записи 2b1(2) мы получаем описание
2b1(3): begin integer k, j; р[1]:=2; k:= 1; j:= 1; while k<do begin "увеличить нечетное j до значения следующего простого числа" k:=k+1; p[k]:=j end
end
причем аналогичная конкретизация заключенной в кавычки операции - назовем ее 2b1(3) а - приводит к описанию уровня 2b2(3):
2b1(3)а= begin boolean jпростое; repeat j:=j+2; "присвоить при нечетном j переменной jпростое значение предиката: j является простым числом"; until jпростое end
Мы метались между двумя уровнями описания всего лишь для того, чтобы привести к удобному для нас виду взаимосвязь между внешней структурой и тем примитивным действием, которое должно соответствовать этой структуре. Ясно, что это метание, этот способ проб и ошибок не вызывает положительных эмоций, но, не обладая даром предвидения, я не нахожу другого выхода, когда приходится принимать последовательные решения; наши попытки могут рассматриваться как сравнительно дешевые исследовательские эксперименты в поиске наиболее удобного способа организации такой взаимосвязи.
Замечание. И 2b1(2), и 2b1(3) могут быть в общих чертах описаны так:
begin "присвоить таблице p и j начальные значения"; while "таблица p не заполнена" do
begin "увеличить j до значения следующего простого числа, которое должно быть добавлено"; "добавить j к таблице p" end
end
но мы не станем этим пользоваться, так как эти два варианта отличаются организацией следования (см.
разд. "О сравнении программ"), и мы считаем их несравнимыми. Выбрав описание 2b1(3), мы принимаем решение, что наш пробный вариант 2b1(2) - как и 2b1(1) - уже не является применимым и потому отбрасывается.
Замена варианта 2b1(2) на 2b1(3) оправдывается повышением эффективности на уровнях более детальной конкретизации. Это повышение эффективности достигается на уровне 2b2, поскольку теперь значение j может увеличиваться каждый раз на 2. Оно проявится также в связи с недоопределенным еще примитивным действием на уровне 2b2(3), где алгоритм "присвоить при нечетном j переменной jпростое значение предиката: j является простым числом" должен только служить для анализа нечетных значений. И снова в описании 2b2(3) мы конкретизируем 2b1(3) в виде алгоритма, который полностью решает нашу проблему, если в принятый набор входит инструкция: "присвоить при нечетном j переменной jпростое значение предиката: j является простым числом", назовем ее "2b2(3)a". Мы опять предполагаем, что это не так, другими словами, мы должны произвести явно вычислительную проверку, имеется ли у заданного нечетного значения j какой-нибудь множитель. Только на этом этапе алгебра по-настоящему попадает в поле нашего зрения. Здесь мы используем свое знание того, что нужно только проверять простые множители; более того, мы будем пользоваться тем фактом, что все подлежащие проверке простые числа уже могут быть найдены в заполненной части массива p. Мы используем следующие факты:
(1) Если значение j нечетное, то наименьшим возможным множителем, подлежащим проверке, является p[2], т.е. минимальное простое число, большее чем 2. (2) Наибольшим простым числом, подлежащим проверке, является p[ord-1], где p[ord] - минимальное простое число, квадрат которого превосходит j.
(Здесь я пользуюсь также и тем фактом что минимальное простое число, квадрат которого превосходит j, уже может быть найдено в таблице p. Смиренно процитирую замечание Кнута по поводу прежней версии этой программы, где я использовал данный факт без обоснования: "Здесь вы упустили существенное обстоятельство! В вашей программе применяется тонкий результат теории чисел, согласно которому всегда
доказательства правильности программы
Рассмотрим следующий фрагмент программы:
integer r, dd; r:=a; dd:=d; while dd r do dd:=2*dd; while dd d do begin dd:=dd/2; if dd r do r:=r-dd; end
в предположении, что целые константы а и d удовлетворяют отношениям
a 0 и d 0
Чтобы применить теорему линейного поиска (см. раздел "О наших интеллектуальных средствах", подраздел "О математической индукции"), рассмотрим последовательность значений, заданную формулами
для i=0 ddi=d
для i>0 ddi=2*ddi-1
Отсюда с помощью обычных математических приемов можно вывести, что
ddn=d*2n (1)
Кроме того, поскольку d>0, можно сделать вывод, что для любого конечного значения r отношение
ddk >r
будет выполняться при некотором конечном значении k; первый цикл завершается при
dd=d*2k
Решая уравнение
ddi=2*di-1
относительно di-1, получаем
di-1=di/2
и теперь теорема линейного поиска позволяет нам утверждать, что второй цикл тоже завершится. (На самом деле второй цикл выполнится в точности столько же раз, сколько и первый.)
По окончании первого цикла
dd=ddk
и поэтому выполняется соотношение
0 r < dd (2)
Как было показано ранее (раздел "О наших интеллектуальных средствах", подраздел "О перечислении"), это соотношение сохраняется при выполнении повторяемого оператора второго заголовка. После завершения повторений (в соответствии с заголовком while ddd do) мы получим
dd=d
Отсюда и из соотношения (2) следует, что
0 r < d (3)
Далее мы доказываем, что после начала работы программы всегда выполняется отношение
dd 0 mod (d) (4)
Это следует, например, из того, что возможные значения dd имеют вид (см. (1))
d*2i при 0 i k
Наша следующая задача состоит в том, чтобы показать, что после присваивания r начального значения всегда выполняется отношение
a r mod (d) (5)
(1) Оно выполняется после начальных присваиваний. (2) Повторяемый оператор первого заголовка (dd:=2*dd) сохраняет отношение (5), и поэтому весь первый цикл сохраняет отношение (5). (3) Повторяемый оператор из второго цикла состоит из двух операторов. Первый (dd:=dd/2) сохраняет инвариантность (5); второй также сохраняет отношение (5), так как он либо не изменяет значение r, либо уменьшает r на текущее значение dd, а эта операция в силу (4) также сохраняет справедливость отношения (5). Таким образом, весь повторяемый оператор второго цикла сохраняет инвариантность (5), а поэтому и весь второй цикл сохраняет отношение (5).
Объединяя отношения (3) и (5), получаем, что окончательное значение r удовлетворяет условиям 0 r < d и a r mod (d)
т.е. r - это наименьший неотрицательный остаток от деления а на d. Замечание 1. Программа
integer r, dd, q; r:=a; dd:=d; q:=0; while dd r do dd:=2*dd; while dd d do
begin dd:=dd/2; q:=2*q; if dd r do begin r:=r-dd; q:=q+1 end
end
присваивает переменной q значение соответствующего частного. Доказательство может основываться на проверке инвариантности отношения a=q*dd+r
(Я обязан этим примером моему коллеге Н. Г. де Бруэйну.)
Замечание 2. В подразделе "О математической индукции" доказали теорему линейного поиска. В предыдущем доказательстве мы использовали другую теорему о повторениях (которая, разумеется может быть доказана только математической индукцией, но доказательство настолько простое, что мы оставляем его читателю в качестве упражнения). Эта теорема состоит в том, что если перед началом повторений выполняется некоторое соотношение Р, истинность которого не нарушается однократным выполнением повторяемого оператора, то соотношение Р будет выполняться и после завершения повторений. Это очень полезная теорема, и она часто позволяет нам избежать явного применения математической индукции. (Можно сформулировать эту теорему несколько более кратко: для цикла while В do S
нужно показать, что оператор S таков, что истинность P B
перед выполнением S означает истинность Р
после выполнения этого оператора.)
Замечание 3. Предлагаю читателю в качестве упражнения ( за которое следует благодарить Дж. Кинга, Питтсбург, США) доказать, что при целых А, В, х, у и z и при условии, что A > 0 и B > 0
после выполнения фрагмента программы
х:=А; у:=В; z:=1; while y 0 do
begin if нечет (у) do
begin y:=y -1; z:=z*x end; y:=y/2; x:=x*x; end
будет получено окончательное значение z = АB. Доказательство сводится к тому, чтобы показать, что (несмотря на оператор у:=у/2) все переменные сохраняют целые значения. Наш метод позволяет показать инвариантность отношений x > 0 и y 0 и АB = z*хy
Проблема восьми ферзей
Этот последний раздел заимствован из конспекта моих лекций "Введение в искусство программирования". Я обязан этим примером Н.Вирту (как и многими другими хорошими примерами). Этот раздел добавлен по двум причинам.
Во-первых, это еще одна попытка отдать должное процессу творчества. (Я приступаю к изложению этого примера, когда студенты еще не знакомы с понятием обратного прослеживания, и разъясняю это понятие в процессе разбора примера.)
Вторая и более важная причина состоит в том, что здесь мы имеем дело с рекурсией как приемом программирования. В предыдущих разделах (в частности, см. "О модели программы") я обсуждал понятие подпрограммы. Там оно явилось воплощением "операционной абстракции". Во взаимосвязи между основной программой и подпрограммой мы можем совершенно четко выделить два различных семантических уровня. На уровне основной программы подпрограмма представляет элементарное действие; на этом уровне представляет интерес только "что это нам дает" и совершенно несущественно "как это делается". На уровне тела подпрограммы мы сосредоточиваем внимание на том, как она работает, но можем - и должны - абстрагироваться от способа ее использования. Такое явное разделение двух семантических уровней "что это дает" и "как это делается" не устраивает разработчика рекурсивной процедуры. Поэтому для проектирования рекурсивных подпрограмм требуются иные интеллектуальные приемы, что оправдывает включение данного раздела в эту работу. Рекурсивную процедуру следует и воспринимать, и осмысливать на одном семантическом уровне; в этом смысле она скорее напоминает средство управления последовательностью счета наподобие заголовков повторения.
Требуется составить программу, генерирующую все конфигурации восьми ферзей на шахматной доске из 8x8 полей с таким условием, чтобы ни один ферзь не мог взять никакого другого ферзя. Другими словами, в искомых конфигурациях никакие два ферзя не могут находиться на одной горизонтали, на одной вертикали или на одной диагонали.
У нас нет оператора, генерирующего все эти конфигурации; именно в получении такого оператора состоит наша задача.
Для таких задач имеется весьма общий подход (ср. "Организация групп и последовательностей"), который состоит в следующем. Назовем искомое множество конфигураций множеством А. Займемся поиском множества В конфигураций со следующими свойствами:
множество А является подмножеством множества В; если задан элемент из множества B, то не представляет особого труда установить, принадлежит ли он множеству А; мы можем получить оператор, генерирующий все элементы множества В.
С помощью генератора (3) элементов множества В можно генерировать по очереди все элементы из В; к ним будет применяться логический критерий (2), который устанавливает, должны ли эти элементы пропускаться или передаваться в генерируемое таким образом множество А. В силу условия (1) этот алгоритм породит все элементы множества А. Сделаем три замечания:
Все наши рассуждения становятся оправданными, когда множество В не идентично множеству А, а поскольку оно должно содержать А в качестве подмножества, оно должно быть больше, чем множество А. Однако для повышения эффективности разумно выбрать множество В "как можно меньшим": чем больше в нем окажется элементов, тем чаще придется отбрасывать его элементы в соответствии с логическим критерием (2). Нам следует искать такой логический критерий, который легко применяется; по крайней мере, не должно вызывать трудностей установление факта, что некий элемент из В не принадлежит множеству А. Это также диктуется соображениями эффективности, так как можно ожидать, что множество В окажется на порядок больше множества А, т.е. потребуется отбросить большинство элементов из В. Предполагается, что легче генерировать элементы множества В, чем непосредственно генерировать элементы множества А. Если тем не менее генерация элементов множества В все же представляет трудности, то мы можем снова провести наше рассуждение, повторно применить тот же прием и искать еще большее множество С конфигураций, содержащее В в качестве подмножества и т. д. (Внимательный читатель заметит, что мы именно так поступим при разборе данного примера.)
Выше мы наметили общий подход, применимый для многих весьма различных задач. Когда мы сталкиваемся с конкретной задачей, т. е. с конкретным искомым множеством А, то, конечно, проблема сводится к выбору подходящего множества В. Оптимист мог бы подумать, что это не представляет труда, так как возможен следующий прием. Мы перечисляем все взаимно независимые условия, которым должны удовлетворять наши элементы множества А, и затем отбрасываем одно из этих условий. Иногда это удается, однако в общем случае такой прием оказывается слишком наивным: его недостаточность становится очевидной, если вслепую применить его к проблеме восьми ферзей. Мы можем охарактеризовать наши решения двумя условиями:
на доске имеются восемь ферзей; никакие два ферзя не могут взять один другого.
Отбрасывание любого из этих условий дает следующие варианты множества В:
В1: все конфигурации из N ферзей на доске, где никакие два ферзя не могут взять один другого; В2: все конфигурации из восьми ферзей на доске.
Но оба эти множества столь несообразно велики, что им соответствуют совершенно бесполезные алгоритмы. Поэтому нам следует проявить больше изобретательности. Возникает вопрос: "Каким образом?"
Так вот, на этом этапе рассуждений, находясь в некотором затруднении, мы заботимся не столько об эффективности нашей окончательной программы, сколько об эффективности нашего процесса мышления! Поэтому если мы хотим организовать список свойств решений в надежде найти путеводную нить, то при таком обходном пути поиска нам не следует затрачивать слишком много умственной энергии; другими словами, для начала мы должны ограничиться самыми очевидными свойствами.
Эту головоломку я предложил одному преподавателю математики из нашего университета, чтобы проучить его за высказанное мнение, будто программирование - легкое дело. Он нарушил сформулированное выше правило и занялся поиском интересных нетривиальных свойств. Он высказал предположение, что если разделить доску на четыре квадрата по 4x4 поля, то каждый квадрат должен содержать двух ферзей, а затем приступил к доказательству этого предположения, не убедившись предварительно, может ли это принести ему реальную пользу.
Он все еще не решил эту задачу, и, насколько мне известно, ему не удалось и опровергнуть свое предположение.
Итак, продолжим наше рассмотрение и перечислим те очевидные свойства, которые сразу приходят в голову.
(a) Никакая горизонталь не может содержать более одного ферзя, нужно разместить восемь ферзей, и доска содержит восемь горизонталей. Отсюда мы делаем вывод, что каждая горизонталь будет содержать ровно одного ферзя.
(b) Аналогично делаем вывод, что каждая вертикаль будет содержать ровно одного ферзя.
(c) Имеются 15 "восходящих" диагоналей, каждая из которых содержит не более одного ферзя, т. е. восемь восходящих диагоналей содержат ровно по одному ферзю, а семь восходящих диагоналей являются пустыми.
(d) Аналогично приходим к выводу, что восемь нисходящих диагоналей содержат ровно по одному ферзю и семь являются пустыми.
(е) Если задана какая-то непустая конфигурация ферзей, в которой никакие два ферзя не могут взять один другого, то удаление любого одного из этих ферзей приведет к появлению конфигурации, сохраняющей это свойство.
Последнее свойство является очень важным. (Честно говоря, здесь я не вижу способа компенсировать недостаток изобретательности.) В нашей прежней терминологии это свойство сообщает нам нечто о любой непустой конфигурации из множества В1. Если мы начинаем с какого-то решения (которое является конфигурацией восьми ферзей из множества В1) и удаляем одного ферзя, то мы получаем конфигурацию семи ферзей из множества В1; удаление еще одного ферзя приведет снова к конфигурации из множества В1, и мы можем продолжать этот процесс, пока шахматная доска не опустеет. Можно было бы заснять этот процесс на кинопленку, и, прокручивая ее в обратном направлении, мы бы увидели, как пустая доска постепенно заполняется добавлением одиночных ферзей и как последовательное прохождение различных конфигураций из множества В1 приводит нас к данному решению. (Я не берусь судить, поможет ли читателям этот трюк с обратным прокручиванием киноленты, и упоминаю о нем только потому, что лично мне такие приемы помогают.) При получении такой киноленты любое решение можно сводить к пустой доске многими способами, и имеется в точности столько же способов построения каждого решения при обратном прокручивании пленки.
Можем ли мы извлечь пользу из этой свободы выбора. Мы отвергли множество В1 из-за того, что оно слишком велико, но, быть может, удастся найти в нем подходящее подмножество, в котором каждая непустая конфигурация окажется одноферзевым расширением только одной конфигурации из этого подмножества. Это "свойство расширения" подразумевает, что мы собираемся рассматривать конфигурации, в которых на доске менее чем по восемь ферзей, и что мы хотели бы формировать новые конфигурации, добавляя по одному ферзю к имеющимся конфигурациям. (По-видимому, такая операция будет сравнительно простой).
Итак, наше внимание переключается непосредственно на генерацию элементов (все еще таинственного) множества В. Например, в каком порядке их генерировать? И снова возникает вопрос, которому до сих пор мы не уделили ни малейшего внимания: в каком порядке мы собираемся генерировать решения, т. е. элементы множества A? Можно ли сделать на этот счет какое-то разумное предположение в надежде, что оно поможет нам распутать клубок решений. (Мой опыт подсказывает, что такой вопрос об упорядочивании обычно очень проясняет ситуацию. Дело не только в том, что нам нужно изготовить последовательную программу, которая по определению будет порождать решения в некотором порядке, так что необходимо на каком-то этапе установить этот порядок. Установленный порядок обычно дает нам ключ к доказательству того, что программа будет порождать все решения, причем каждое решение только по одному разу.)
Прежде всего нам нужно найти ответ на вопрос, как мы будем характеризовать имеющиеся у нас решения. Чтобы охарактеризовать решение, мы должны задать позиции восьми ферзей. Сами по себе ферзи не являются упорядоченными, но для горизонталей и вертикалей существует определенный порядок, и мы можем предположить, что они нумеруются от 0 до 7. Согласно свойству (а), каждая горизонталь содержит ровно одного ферзя, и поэтому мы можем упорядочить ферзей в соответствии с номерами занимаемых ими горизонталей. Тогда каждая конфигурация из восьми ферзей может быть задана значением массива integer array x[0:7], где x[i] - номер вертикали, занимаемой ферзем из i-й горизонтали.
В таком случае каждое решение представляет собой "восьмизначное слово" (х[0]... х[7]), и я полагаю, что разумнее всего генерировать эти слова в алфавитном порядке.
Замечание.
Тем самым открывается путь для алгоритмов, в которых горизонтали и вертикали рассматриваются по-разному, тогда как исходная постановка задачи была симметричной относительно горизонталей и вертикалей. Предыдущие рассуждения наводят нас именно на рассмотрение асимметричных алгоритмов.
Вернемся к алфавитному порядку; теперь мы вышли на знакомую колею. Если элементы множества А должны генерироваться в алфавитном порядке, причем их нужно генерировать, выбирая из большего множества В, то стандартный метод состоит в том, чтобы генерировать элементы множества В также в алфавитном порядке и порождать элементы нашего подмножества в том порядке, в каком они встречаются в множестве В.
Сначала мы должны генерировать все решения с х[0]=0 (если такие существуют), затем решения с х[0]=1 (если найдутся) и т. д.; из решений с фиксированным значением х[0]=0 нужно сначала генерировать те, у которых х[1]=0 (если такие существуют), затем те, у которых х[1]=1 (если существуют) и т. д. Другими словами, ферзь из горизонтали 0 помещается в вертикаль 0, т. е. в нижний левый угол доски, и остается там до тех пор, пока не завершится генерация всех элементов множества А (и В) с ферзем 0 в этой позиции, и только после этого ферзь 0 передвигается на один квадрат вправо, в следующую вертикаль. При каждом положении ферзя 0 ферзь 1 будет перемещаться слева направо в горизонтали 1, перескакивая через поля, которые находятся под ударом ферзя 0; при каждом комбинированном положении первых двух ферзей ферзь 2 перемещается по горизонтали 2 слева направо, пропуская все поля, которые находятся под ударом предыдущих ферзей, и т. д.
Но таким образом мы уже нашли множество В! Оно является подмножеством множества В1 и состоит из всех конфигураций, в которых по одному ферзю в каждой из первых N горизонталей, причем никакие два ферзя не могут взять один другого.
Критерием того, что элемент из В принадлежит также множеству А, является равенство N=8.
Теперь, когда мы выбрали множество В, перед нами стоит задача генерации элементов этого множества в алфавитном порядке.
Можно было бы попытаться использовать для этого оператор "ГЕНЕРИРОВАТЬ ОЧЕРЕДНОЙ ЭЛЕМЕНТ ИЗ В" в программе вида
НАЧАТЬ С ПУСТОЙ КОНФИГУРАЦИИ; repeat ГЕНЕРИРОВАТЬ ОЧЕРЕДНОЙ ЭЛЕМЕНТ ИЗ В; if N=8 then ПЕЧАТАТЬ КОНФИГУРАЦИЮ until В ИСЧЕРПАНО
(Здесь мы воспользовались тем фактом, что пустая конфигурация принадлежит B, но не принадлежит A и не является единственным элементом множества В. Мы не сделали никаких предположений относительно существования решений.) Однако программа такой структуры не очень удобна по двум причинам. Во-первых, мы не располагаем готовым критерием распознавания последнего элемента из В, и, по всей видимости, следует обобщить оператор "ГЕНЕРИРОВАТЬ ОЧЕРЕДНОЙ ЭЛЕМЕНТ ИЗ В" таким образом, чтобы он порождал указание "В ИСЧЕРПАНО", когда он применяется к последнему "истинному" элементу множества В. Во-вторых, не вполне ясно, как реализовать оператор "ГЕНЕРИРОВАТЬ ОЧЕРЕДНОЙ ЭЛЕМЕНТ ИЗ В": число ферзей на доске может оставаться неизменным, может уменьшаться и может увеличиваться. Итак, здесь мы сталкиваемся с трудностями. Что можно сделать, чтобы избежать их? До тех пор пока мы считаем последовательность конфигураций из множества В единой и однородной и не подразделяем ее на ряд подпоследовательностей, соответствующая структура программы будет оставаться единым циклом, как в предыдущем варианте. Если мы ищем иную структуру программы, то именно поэтому должны задать себе вопрос: "Как организовать разложение последовательности конфигураций из множества В на ряд подпоследовательностей?" С учетом того, что последовательность конфигураций из множества В должна генерироваться в алфавитном порядке, и по аналогии с основным подразделением в словаре (а именно по первой букве) первичная организация групп является очевидной: по позиции ферзя 0. Если на время забыть о необходимости печатать те конфигурации из В, которые принадлежат также и множеству А, то генерирование всех элементов множества В представляется следующим образом:
НАЧАТЬ С ПУСТОЙ КОНФИГУРАЦИИ; h:=0; repeat УСТАНОВИТЬ ФЕРЗЯ В ПОЛЕ [0,h]; ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ С ФИКСИРОВАННЫМ ПОЛОЖЕНИЕМ ФЕРЗЯ 0; УБРАТЬ ФЕРЗЯ С ПОЛЯ [0,h]; h1:=h+1 until h=8
Но теперь снова возникает вопрос: как группировать все конфигурации с фиксированным положением ферзя 0? У нас уже готов ответ: в порядке возрастания номеров вертикалей, содержащих ферзя 1, т. е.
h1:=0; repeat if ПОЛЕ [1, h1] СВОБОДНО do
begin УСТАНОВИТЬ ФЕРЗЯ В ПОЛЕ [1, h1]; ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ С ФИКСИРОВАННЫМ ПОЛОЖЕНИЕМ ПЕРВЫХ ДВУХ ФЕРЗЕЙ; УБРАТЬ ФЕРЗЯ С ПОЛЯ [1, h] end; h1:=h1 + 1 until h1 =8
Для оператора "ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ с ФИКСИРОВАННЫМ ПОЛОЖЕНИЕМ ПЕРВЫХ ДВУХ ФЕРЗЕЙ" можно написать аналогичный фрагмент программы, и т. д. Вкладывая эти фрагменты один в другой, мы получили бы правильную программу с восьмикратным вложением циклов, причем эти циклы оказались бы весьма и весьма однообразными. Такой способ имеет два недостатка:
он требует непомерной писанины; он обеспечивает программу решения нашей проблемы для шахматной доски из 8x8 полей, но для решения той же головоломки, например при доске из 10x10 полей, потребовалась бы новая, еще более длинная программа.
Нам нужен способ выполнения всех циклов под управлением одного и того же текста программы. Можем ли мы сделать тексты циклов идентичными? И можем ли мы воспользоваться их идентичностью? Начнем с замечания, что самый внешний и самый внутренний циклы являются исключениями. Самый внешний цикл исключителен в том смысле, что он не содержит проверки, свободно ли поле [0, h], поскольку мы знаем, что оно свободно. Но хотя мы знаем, что оно свободно, не будет вреда от включения условия
if ПОЛЕ [0, h] СВОБОДНО do
в результате чего самый внешний цикл приобретает такой же вид, как шесть следующих циклов.
Самый внутренний цикл исключителен в том смысле, что коль скоро восемь ферзей размещены на доске, то нет смысла генерировать все конфигурации с фиксированным положением этих ферзей, так как доска уже заполнена.
Вместо этого нужно печатать конфигурацию, поскольку найден элемент множества В, принадлежащий одновременно и множеству А. Мы можем совместить самый внутренний цикл с остальными семью циклами, заменив строку "ГЕНЕРИРОВАТЬ" на строку
if ДОСКА ЗАПОЛНЕНА then ПЕЧАТАТЬ КОНФИГУРАЦИЮ else ГЕНЕРИРОВАТЬ ВСЕ КОНФИГУРАЦИИ, РАСШИРЯЮЩИЕ ИМЕЮЩУЮСЯ
Для этого мы вводим глобальную переменную "n", служащую счетчиком ферзей, имеющихся на доске. Проверка "ДОСКА ЗАПОЛНЕНА" приобретает вид "n=8", операции над полями могут содержать ип" в качестве первого индекса. Теперь единственное различие между восемью циклами состоит в том, что у каждого из них "свое отдельное h". На этом этапе мы получаем утвердительный ответ на вопрос, можно ли воспользоваться идентичностью циклов. Прохождение через восемь вложенных циклов может вызываться с помощью рекурсивной процедуры "генерировать", описывающей однократное выполнение цикла. С ее помощью вся программа сводится к виду
НАЧАТЬ С ПУСТОЙ КОНФИГУРАЦИИ; п: =0; генерировать
где "генерировать" описывается рекурсивно следующим образом:
procedure генерировать; begin integer h; h:=0; repeat if ПОЛЕ [n, h] СВОБОДНО do begin УСТАНОВИТЬ ФЕРЗЯ В ПОЛЕ [n, h]; n:=n+1; if n=8 then ПЕЧАТАТЬ КОНФИГУРАЦИЮ else генерировать; n:=n-1; УБРАТЬ ФЕРЗЯ С ПОЛЯ (n, h] end
h:=h+1 until h=8 end
Каждое выполнение процедуры "генерировать" вводит свою отдельную локальную переменную h, заменяя тем самым переменные h, h1, ..., h8, которые потребовались бы нам при написании восьми вложенных циклов. Хотя наша программа и корректна для этого уровня детализации, она все же не завершена, так как ее конкретность не доведена до стандартной степени детализации, требуемой нашим языком программирования. В следующей конкретизации нам следует согласовать способ представления конфигураций на доске. Мы уже более или менее решили, что будем использовать массив
integer array x [0:7]
в котором по очереди задаются номера вертикалей, занимаемых ферзями, а также решили, что скаляр
integer n
следует использовать для представления числа ферзей на доске. Точнее говоря,
п=число ферзей на доске
x[i] при 0<in=номер вертикали, занимаемой ферзем из i-й горизонтали.
Сочетание массива х и скаляра n является достаточным для фиксации любой конфигурации из множества В, причем это будут только конфигурации с шахматной доски. Следовательно, у нас нет логической необходимости в дополнительных переменных. Тем не менее, мы введем еще кое-какие переменные, поскольку с практической точки зрения они могут сослужить нам хорошую службу.
Проблема состоит в том, что приходится часто проверять, попадает ли под удар некое поле из очередной свободной горизонтали, а если основываться только на имеющихся данных, то такая проверка оказывается довольно дорогостоящей и требует значительных затрат времени. Именно здесь нам пригодится стандартный прием, описанный в разделе "О расплате машинной памятью за ускорение вычислений" (см. стр. 52). Роль запоминаемого аргумента играет конфигурация ферзей на доске, но ее значение заменяется отнюдь не как придется, ведь мы только добавляем или удаляем одного ферзя. И нам нужны дополнительные таблицы (содержащие функцию от текущей конфигурации), которые облегчат проверку, является ли некое поле свободным; свойством этих таблиц должна быть легкость обновления при добавлении или удалении одного ферзя в имеющейся конфигурации.
Как это сделать? Например, можно представить себе логический массив из-8х8 элементов, указывающих для каждого поля, является ли оно свободным. Если мы заводим такой массив для всей доски, то добавление ферзя может повлиять на 28 полей. Однако удаление ферзя оказывается при этом трудоемким процессом, так как ниоткуда не следует, что поля, которые не находятся более под ударом этого ферзя, становятся вообще свободными: они могут находиться под ударом одного или нескольких ферзей, остающихся в конфигурации.
Против этого есть средство (опять-таки стандартное), состоящее в том, чтобы ставить в соответствие каждому полю не логическую переменную, а целочисленный счетчик, накапливающий число ферзей, бьющих это поле. Тогда добавление ферзя приводит к увеличению на "1" значений двадцати восьми или менее счетчиков, а удаление этого ферзя уменьшает на "1" значения тех же счетчиков; поле является свободным тогда, когда соответствующий счетчик равен нулю. Можно действовать таким способом, но возникает вопрос, не переусердствуем ли мы при этом: внесение двадцати восьми поправок представляется поистине слишком тяжелой расплатой за установку или удаление одного ферзя.
Всякий раз, когда мы интересуемся, свободно ли некое поле, этому полю соответствует горизонталь (которая свободна по определению, так что нам не нужно об этом заботиться), соответствует одна из восьми вертикалей (которая вся должна быть пустой), соответствует одна из пятнадцати восходящих диагоналей (которая вся должна быть пустой) и одна из пятнадцати нисходящих диагоналей (которая вся должна быть пустой). Это наводит на мысль, что нам нужно следить за
свободными вертикалями; свободными восходящими диагоналями; свободными нисходящими диагоналями.
Поскольку каждая вертикаль или диагональ попадает под удар только один раз, для них не нужны свои счетчики, а достаточно иметь соответствующие логические переменные. Вертикали идентифицируются своими номерами, и для них мы вводим массив
boolean array верт [0:7]
где "верт[i]" означает, что i-я вертикаль вся свободна. А как идентифицировать диагонали? Вдоль каждой восходящей диагонали разность между номером горизонтали и номером вертикали является постоянной; а их сумма остается постоянной вдоль каждой нисходящей диагонали. Следовательно, соответствующие разность и сумма оказываются простейшими индексами, позволяющими различать диагонали, и поэтому, чтобы следить за свободными диагоналями, мы вводим массивы
boolean array вос[-7:+7], нис[0:14]
Проверка, является ли свободным поле [п, h], приобретает вид верт[h]вос[п-h]нис[n+h]
а установка или удаление ферзя сводятся к перечислению трех логических элементов, по одному в каждом массиве.
begin integer n, k; integer array x[0:7]; boolean array верт[0:7], вос[-7:+7], нис[0:14]; procedure генерировать; begin integer h; h:=0; repeat if ПОЛЕ [n,h] СВОБОДНО: (верт[h]вос[n-h]нис[n+h]) do begin УСТАНОВИТЬ ФЕРЗЯ В ПОЛЕ [n,h]: x[n]:=h; верт[h]:=false; вос[n-h]:=false; нис[n+h]:=false; n:=n+l if ДОСКА ЗАПОЛНЕНА: (n=8) then begin ПЕЧАТАТЬ КОНФИГУРАЦИЮ: k:=0; repeat печатать (x[k]); k:=k+1 until k=8; новая строка end
else генерировать; n:=n-1; УБРАТЬ ФЕРЗЯ С ПОЛЯ [n,h]: нис[n+h]:=true; вос[n-h]:=true; верт[h]:=true end; h:=h+l until h=8 end; НАЧАТЬ С ПУСТОЙ КОНФИГУРАЦИИ: n:=0; k:=0; repeat верт[k]:=true; k:=k+l until k=8; k:=0; repeat вoc[k-7]:=true; нис[k]:=true; k:=k+l until k=15; генерировать end
В окончательной программе вводится переменная "k"для общих вычислительных надобностей, операторы и выражения снабжаются метками (в прописных буквах). Заметим, что мы совмещаем два уровня описания: то, что было операторами и функциями на более высоком уровне, теперь появляется в виде пояснительных меток. Этой окончательной программой мы завершаем последний раздел. Мы пытались продемонстрировать пример рассуждения, где можно обнаружить прием обратного прослеживания, а также пример рассуждения, в котором можно узнать описывающую его рекурсивную процедуру. Самый существенный вывод из этого раздела состоит, по-видимому, в том, что весь соответствующий анализ и синтез можно выполнять до принятия решения о том, как (и насколько избыточно) конфигурация будет представляться в машинной памяти. Разумеется, такие предварительные рассмотрения принесут хорошие плоды лишь в том случае, когда в конце концов удастся найти подходящее представление конфигураций.Тем не менее, я считаю принципиальным мысленное отделение уровня абстракции, на котором можно позволить себе не заботиться об этом. В заключение хочу поблагодарить терпеливых читателей, дочитавших до этого места.
Второй пример поэтапного составления программы
Теперь, когда у нас возникло представление о структуре программы как об иерархическом расслоении машин, я испытываю непреодолимое желание "повозиться" с этой моделью, т. е. составить еще одну программу. Не следует рассматривать применяемый здесь способ обозначений как тщательно продуманное общее предложение; эти обозначения я выбрал по своему вкусу, и к ним нужно относиться как к части эксперимента.
Задача состоит в следующем. Имеется строчное печатающее устройство, которое управляется двумя командами; одна команда "НСВК" (Новая строка Возврат каретки) устанавливает в качестве "текущей позиции печати" самую левую позицию следующей строки, а другая команда "ПЧСИМ(n)" печатает в текущей позиции печати символ, указываемый значением целого параметра п, и устанавливает соседнюю справа позицию в качестве новой текущей позиции печати. (В рамках нашего рассмотрения можно считать допустимыми строки бесконечной длины.) Мы будем использовать только два конкретных значения п, которые называются "пробел" и "знак". Команда "ПЧСИМ(пробел)" приводит к тому, что текущая позиция печати остается пустой, а команда "ПЧСИМ(знак)" напечатает заданный графический символ, например некоторую разновидность звездочки.
Кроме того, заданы две целые функции от целого аргумента, удовлетворяющие отношению
при 0i<1000 : 0fy(i)<100 и 0fy(i)<50
Нам требуется изготовить программу, печатающую 50 строк, которые нумеруются сверху вниз координатой у, пробегающей значения от 49 до 0; позиции в строке будут нумероваться слева направо координатой х, пробегающей значения от 0 до 99. Нужно напечатать знак в тысяче (или меньше, если будут совпадения) позиций, для которых
x=fx(i) и y=fy(i) при i от 1 до 1000
Все остальные позиции на бумаге должны оставаться пустыми. Другими словами, кривая задается в дискретном параметрическом представлении, и мы хотим использовать строчное печатающее устройство в качестве двоичного графопостроителя.
Я часто задавал эту задачу на устных экзаменах, и большинство студентов быстро соображают, что отсутствие команд ПСВК (Предыдущая строка Возврат каретки) и "предыдущая позиция" приводит к тому, что порядок обслуживания позиций печати определяется командами печати и что на этот порядок никак не влияет упорядочивание знаков, если мы нумеруем их по возрастанию значений i.
В результате студенты быстро приходят к выводу, что задача решается довольно однозначно: сначала нужно накопить тысячу i-значений, т. е. запомнить в удобной форме представление страницы, а затем напечатать страницу, руководствуясь ее представлением, находящимся в памяти. (Точнее говоря, мы предполагаем, что у машины достаточная для этого память и что вычисление значений функций fx(i) и fy(i) может оказаться столь продолжительным, что мы предпочитаем вычислять их только по одному разу для каждого i-значения.)
Теперь мы зафиксируем это проектное решение; предлагается следующий текст:
ВЫЧНАЧ begin чертить: {строить; печатать}; var отражение; instr строить(отражение), печатать(отражение) end
Этот документ рассматривается как цельная часть окончательной программы и должен интерпретироваться следующим образом. Относится к машине "ВЫЧНАЧ" (мы используем заглавные буквы для названий машин и пытаемся выразить этими названиями типы решений в программах для этих машин). Следующая строка указывает именованный алгоритм; он называется "чертить" (предполагается, что это имя всей изготовляемой программы, которая должна "чертить" кривую) и указывает желаемую последовательность выполнения двух действий: построение отражения в памяти, а затем печать на бумаге в соответствии с запомненным значением отражения. В последних двух строках задаются описания (или заголовки описаний) компонент машины, используемых в алгоритме. Первая из них указывает, что имя "отражение" будет употребляться для структуры данных, в которую будет заложено представление страницы; переменная "отражение" является единственной компонентой установленной памяти этой машины. Код операций машины содержит две команды с именами "строить" и "печатать". Прежде чем продолжить наши рассмотрения, заметим, что среди употребляемых нами сокращений есть и такие, об удачности которых пока еще трудно судить. Обе введенные в этом тексте аббревиатуры употребляются в предположении, что переменная "отражение" является единственной переменной этого типа. Если потребуется, чтобы установленная память хранила два отражения, то следует написать
Тот факт, что это действительно можно рассматривать как алгоритм для машины, станет, возможно, более наглядным, если мы рассмотрим другие алгоритмы "чертить". Например, программа
чертить: {печатать; строить}
не годится, потому что в этом случае действие "печатать" не определено;
чертить: {строить; строить; печатать}
корректна, но приводит к излишним затратам машинного времени, так как второе действие "строить" присваивает переменной "отражение" то самое значение, которое она уже имеет; программа
чертить: {строить; печатать; печатать}
имела бы определенный смысл: чертеж печатался бы дважды.
Теперь уточним нашу программистскую задачу. Если бы в нашем распоряжении имелась машина "ВЫЧНАЧ", то вся работа была бы выполнена на ней маленькой программой "чертить".
Чтобы продолжить рассуждения и с учетом реальности предполагаем теперь, что у нас нет такой машины, в точности соответствующей нашим потребностям, а поэтому наша следующая задача (подобная предыдущей!) состоит в том, чтобы изготовить такую машину.
Имеются три именованных понятия: "строить", "печатать" и "отражение", причем два первых ссылаются на последнее. Поэтому дальнейшая конкретизация последнего понятия повлияет на два первых; кроме того, очень трудно конкретизировать действие "печатать" без дальнейшего уточнения структуры "отражение". Однако действие "строить" допускает дальнейшую независимую детализацию, и именно поэтому мы будем в первую очередь заниматься дальнейшей конкретизацией понятия "строить".
Нам нужно описать, как переменной "отражение" присваивается ее значение, соответствующее требуемому расположению тысячи знаков. В целом эта операция присваивает значение переменной, которая ранее не имела определенного значения; если же исходить из того, что знаки будут добавляться по одному, то мы видим, что добавление следующего знака окажется действием над уже определенным значением "отражение".
Поэтому заманчиво рассматривать всю расстановку знаков как действие над уже определенным значением, а именно над значением, соответствующим пустой странице. Такое решение приводит к записи
ЧИСТНАЧ begin
строить: {чистить; ставить знаки}; instr чистить (отражение), ставить знаки (отражение) end
Здесь действие "чистить" присваивает отражению значение, соответствующее картине пятидесяти пустых строк, а действие "ставить знаки" перестраивает начальное значение отражения, заменяя его на значение, в которое включены тысяча (или меньше) знаков, расположенных на нашей кривой.
ЧИСТНАЧ - это тоже машина, для которой можно писать различные программы. Например, программа
строить: {чистить}
имела бы смысл, но привела бы к получению пятидесяти пустых строк;
строить {ставить знаки; чистить}
содержала бы неопределенную операцию;
строить: {чистить; чистить; ставить знаки}
содержала бы излишнюю операцию, равно как и программа
строить: {чистить; ставить знаки; ставить знаки}
В последнем случае второе действие "ставить знаки" только добавило бы в чертеж те знаки, которые там уже имелись бы, и поэтому не внесло бы изменений в значение "отражение". (Замечание об используемых обозначениях. Алгоритмическое выражение понятия "строить" через "чистить" и "ставить знаки" производится без явного упоминания имени "отражение", поскольку мы не хотим использовать в алгоритмах запись с фактическими параметрами, если комбинаторная гибкость такой записи не используется по существу в данной машине. Кроме того, хотя операция "строить" является однопараметрической, мы не вводили отдельного идентификатора для ее формального параметра. Допускаю, что это сокращение может оказаться не очень разумным.) Следующий этап проектирования наших вычислений может быть выполнен без предварительных уточнений; он состоит в описании порядка обработки тысячи знаков на кривой. Пока я предлагаю следующую запись:
IСЧИТЫВАНИЕ begin integer i; ставить знаки: (i:=0; while i<1000 do добавить знак; i плюс l}}; instr добавить знак (i, отражение) end
Этот алгоритм следует понимать применительно к машине, система команд которой предусматривает операцию "добавить знак (i,отражение)"; эта операция изменяет значение "отражение" путем добавления i-гo знака. Данный алгоритм описывает порядок, в котором обрабатываются все знаки; мы видим, что каждый знак будет обрабатываться ровно один раз.
Однако это еще не все: введена новая переменная i, алгоритм обращается к операциям, которые ссылаются на эту переменную ("i:=0", "i<1000", "i плюс 1"), и если быть последовательными до конца, то, по-видимому, нужно было перечислить эти операции в конце, поскольку они могут потребовать разъяснений на последующем этапе подобно тому, как это делалось для операции "добавить знак". Я этого не сделал, и отношусь к этим операциям примерно так же, как к заголовкам while-do. С точки зрения языковой семантики вызывает сомнение оправданность особого обращения с неявно подразумеваемым типом integer; казалось бы, трудно мотивировать, почему тип integer вводится не так, как тип "отражение", ведь оба они неявно подразумеваются в данной машине.
И все-таки я поступил именно так. Я все время разрабатываю программы для несуществующих машин и приговариваю: "Если мы теперь имеем машину, включающую предполагаемые здесь элементы, то вся работа сделана". С абстрактно-логической точки зрения это правильно, но на практике это оказывается всего лишь шуткой, так как мы отлично знаем, что невозможно предположить, чтобы имелась машина общего назначения, код операций которой был бы настолько приспособлен к нашим потребностям. Нам не следует не только забывать, но и замалчивать нашу ответственность за обеспечение этих элементов на более позднем этапе разработки. Когда теперь я обращаюсь особым образом к общепонятному типу "integer" и к операциям, определенным над переменными этого типа, то делаю это с намерением выразить, что, хотя эти возможности и нужно так или иначе обеспечить, их обеспечение лежит вне.
сферы ответственности программиста, а также что программиста устроит любая их разумная реализация.
Займемся еще одним программным элементом, который допускает дальнейшую конкретизацию вне связи с другими элементами. Нам нужно описать, как обработка i-го знака может быть выражена с помощью действий над позицией страницы
ВЫЧПОЗ begin integer x, у; добавить знак: {x:=fx(i);y:=fy(i); знак поз}; instr знак поз (х, у, отражение) end
Здесь "знак поз" изменит текущее значение переменной "отражение", поскольку к чертежу для печати добавляется знак с координатами "х" и "у." (Замечание. В этой конкретизации явно предполагается, что функции fx(i) и fy(i) могут вычисляться в любом порядке следования значений их аргументов. Если бы эти две тысячи значений функций могли считываться с вводного устройства попарно в предписанном порядке i-значений, то две последние машины можно было бы объединить в одну.) Теперь уже я не вижу возможностей дальнейших конкретизации, если не углубиться в структуру все еще несколько неясного типа "отражение". Как представляем мы себе запоминание этой величины? Нам следует установить структуру переменных типа "отражение", или, что сводится к тому же, мы должны принять решение о способе представления в памяти всех возможных значений этого типа. Выступая с лекциями перед различными аудиториями, я описывал некоторые варианты данной программы, и наверное стоит отметить, что по меньшей мере дважды часть моих слушателей начинала испытывать тревогу к тому времени, как я достигал этого места. Например, у них возникало чувство, что я не в состоянии доказать правильность построенной программы. Когда я говорил, что
чертить: {строить; печатать; печатать)
выдаст один и тот же чертеж два раза, они возражали, ссылаясь на теоретическую возможность того, что операция "печатать" изменит (посредством некоего побочного эффекта) значение "отражение" прежде, чем мы начнем выполнять вторую команду "печатать".
Разумеется, ответ на эти возражения состоит в том, что операция "печатать" должна делать именно то, что ей предписано, и не должна делать ничего другого. Но тогда возникают новые возражения: мне не удалось доказать единственность способа представления; не исключено, что "печатать" - это частичная функция, определенная не для всех возможных значений "отражение", и т. д. По-видимому, ответ на это должен состоять в следующем: эти соображения вполне законны, но следует отложить их обсуждение до более подходящего времени, а точнее, вернуться к этому после того, как мы сосредоточим внимание на вопросах представления. Очевидное преимущество нашего подхода состоит в том, что столь значительную часть программы удалось написать независимо от выбора представления для значений типа "отражение". Все, что мы сделали до сих пор, выглядит удачным использованием нашей способности к абстракции (здесь мы абстрагировались от выбора конкретного представления для структуры данных "отражение").
Но даже если мы теперь приходим к заключению, что настало время принимать решения относительно структуры данных типа "отражение", нам все еще не обязательно до конца углубляться в эту проблему. Занявшись теперь вопросом о структурной организации нашей переменной, мы можем принимать решения поэтапно, аналогично тому как мы это делали при предыдущих конкретизациях алгоритмов. Напомним, что постановка задачи началась с того, что с помощью команд "ПЧСИМ" и "НСВК" нужно организовать вычисления для получения искомого чертежа строка за строкой сверху вниз. Попытаемся формально выразить этот факт, интерпретируя отражение как массив строк. Тогда мы приходим к следующему очередному уровню:
СТРОП begin integer j; отражение: {array строка [0:49]}; печатать: {j:=49; while j>0do {печатать строку (строка [j]); j минус 1}}; чистить: {j:=49; while j>0 do чистить строку (строка [j]); j минус 1}}; знак поз: { знак в строке (строка [y])}; type строка; instr печатать строку (строка), чистить строку (строка), знак в строке (х, строка) end
В предпоследней строке текста мы ввели тип с названием "строка"; напоминаю, что тип представляет собой совокупность различимых значений, и переменная некоего типа может в любой момент 1; принимать какое-то одно значение из соответствующей совокупности. Первая строка текста означает, что тип "отражение" образуется из массива, в котором имеется 50 элементов типа "строка" с номерами от 0 до 49. Поскольку это единственный тип, образованный из строк, мы снова воздерживаемся от введения нового идентификатора (хотя может возникнуть сомнение в разумности этого решения).
Итак, операции "печатать", "чистить" и "знак поз", которые понимались как действия над величиной "отражение", транслируются в алгоритмы, выраженные с помощью операций над строкой. В записи этих алгоритмов каждый фактический параметр указывает конкретную строку; в конце описания мы приводим список команд, в котором перечисляем те действия, которые выполняются над "строкой"; при этом мы задаем тип, но не параметр.
На этом уровне появляются некоторые новые свойства. На начальных этапах (подобно тому, как мы это делали, описывая "отражение") мы проводим структурную конкретизацию типа данных примерно на такой же основе, как и алгоритмические конкретизации (вроде тех, что применялись к алгоритмам "печатать", "чистить" и "знак поз"). До этого уровня можно было рассматривать наш подход как попытку установить четкий порядок "подпрограммирования", если читатель простит этот ужасный термин! Теперь же мы отмечаем, что такая характеристика наших усилий охватывает только половину того, что мы пытаемся сделать, поскольку мы хотим применить аналогичный прием также и к структурам данных. Кроме того, каждая наша предыдущая машина описывала только одно понятие (команду или тип данных), тогда как СТРОП описывает целый комплекс понятий. Дело в том, что мы пытаемся принимать для каждого уровня отдельное проектное решение; здесь мы решаем понимать отражение отныне и впредь в терминах строк, и поэтому все операции, выполняемые над отражением в целом, должны быть сведены к операциям над составляющими его строками.
Отражение уже "отжило"; единственным необычным типом, с которым нам все еще нужно иметь дело, остается тип "строка", и именно им мы собираемся теперь заняться. Обратите особое внимание на то, что на новом уровне нам придется заниматься именно строками, и теперь уже не будет иметь значение то обстоятельство, что строки используются для составления отражений.
Для представления строки существует много различных способов. Годится и список x-координат позиций, где следует напечатать знак (этот список может быть упорядочен по возрастанию значений х), и логический массив из ста элементов, каждый из которых указывает, следует ли ставить знак в соответствующей позиции строки на чертеже; можно применить и целый массив из ста элементов, каждый из которых принимает значение "знак" или "пробел" параметра операции ПЧСИМ для соответствующей позиции печати. Последний вариант представления пригоден для более общего случая, когда на одном чертеже нужно напечатать различные кривые (с различными знаками); поэтому мы выбираем этот вариант. Это приводит к программе
ДЛИНЦИК begin integer k; строка: {integer array сим [0:99]}; печатать строку: {k:=0; while k<100 do {ПЧСИМ (сим [k]); k плюс 1}; НСВК}; чистить строку: {k:=0}; while k<100 do {сим [k]:=пробел; k плюс 1}}; знак в строке: = {сим [x]:=знак} end
Однако при выполнении этого алгоритма заполняется пробелами остаток строки справа от самого правого знака; это все равно, что стучать по клавише пробела до тех пор, пока не зазвенит звонок, когда мы печатаем на машинке и хотим перейти к новой строке. Ниже приводится вариант программы с подавлением излишних команд ПЧСИМ и даже с сохранением неопределенных значений тех переменных типа "строка", определение которых не требуется. Каждой строке ставится в соответствие счетчик f, задающий число команд ПЧСИМ для этой строки. Очистка строки теперь сводится к установке значения 0 для f
КОРЦИК begin integer k; строка: {integer f; integer array сим [0:99]}; печатать строку: {k:=0; whilek<f do {ПЧСИМ сим [k]); k плюс 1}; НСВК}; чистить строку: {f:=0}; знак в строке: {сим [x]:=знак; if fx do {k:=f; while k<x do {сим [k]:=пробел; k плюс 1}; f:=x+1}} end
Замечание, добавленное позднее.
Выше описана именно та программа, которую я демонстрировал по меньшей мере пяти различным аудиториям. Теперь, два месяца спустя, поразмыслив на досуге о правильности доказательств, я внезапно осознал, что данный алгоритм "знак в строке" компрометирует меня, так как он безобразно выглядит по сравнению со следующим вариантом:
знак в строке: {while fx do {сим [f]:=пробел; f плюс 1}; сим [x]:=знак}
Этот вариант гарантирует, что при всяком выполнении действия "сим [x]:=знак" будет выполняться отношение "x<f"; именно для обеспечения этого отношения предназначена первая строка программы. Читателю предлагается попытаться понять оба варианта программы и сравнить их логику. Сделав это, он согласится с моим мнением о слабости первоначального варианта. Второй вариант пришел мне в голову по следующей ассоциации. Условие
if В do S
используется в программах двумя различными способами. С одной стороны, имеются приложения, в которых выполнение оператора S не нарушает истинность В; с другой стороны, мы встречаем и ситуации, когда выполнение оператора S заведомо делает утверждение В ложным. В последнем случае задача условного оператора состоит в том, чтобы обеспечить после своего выполнения значение B=false. В таком случае это в сущности сокращенная запись оператор а
while В do S
который имеет свойство нарушения истинности В (при условии, что он не будет выполняться бесконечно долго). Однако для обоснования этого сокращения требуется отдельно доказать, что повторяемый оператор будет выполнен не более одного раза. (В разделе "Первый пример поэтапного составления программы" мы не стали вводить такое сокращение на уровне 2b4(4), где писали
while "значение ord слишком мало" do "увеличить ord на 1";
Здесь то же самое можно было бы сделать с помощью условия.)
