Заметки по структурному программированию

Более детальные проектные рассмотрения

Предыдущие разделы (в частности, "Первый пример поэтапного составления программы") вызывали критические замечания о том, что я слишком упрощенно трактую процесс проектирования программ, доходя почти до грани мошенничества. Я не считаю эту критику совсем безосновательной и, чтобы исправить дело, разберу два примера более детально. Первый пример придуман мною. Я испробовал его на нескольких устных экзаменах, а впоследствии закончил им свой лекционный курс "Введение в искусство программирования". Я поставил эту задачу перед аудиторией из пятидесяти человек, и все вместе, с моим направляющим участием, они решили ее в течение 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=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
Прежде чем отвлечься от этого примера, иллюстрирующего применение математической индукции в рассуждениях, я хочу сделать несколько дополнительных замечаний, потому что предчувствую, что к этому времени некоторые мои читатели (особенно опытные и компетентные программисты) придут в негодование; речь идет о тех читателях, для которых правильность программы (6) настолько очевидна, что их удивляет вся эта суета: "К чему напыщенное сведение проблемы к условиям (3), (4) и (5), когда всякий знает, что собой представляет первое значение из последовательности, удовлетворяющее некоему условию? Разумеется, он не может ожидать, что мы - люди, загруженные работой,- будем предоставлять такие длинные доказательства с полной математической отделкой всякий раз, когда употребим такой простой цикл, как этот." И так далее ...

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

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

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

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

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

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

О модели программы

О надежности аппаратуры

По профессии я программист и обсуждаю в этой работе программы; истинной темой этого раздела является, в сущности, надежность программ. Тем не менее в заголовке я упоминаю "аппаратуру", так как считаю программы специфической формой аппаратов и желаю хоть раз выразить глубокую уверенность в том, что многие мои соображения, относящиеся к программному обеспечению, справедливы с соответствующими поправками и применительно к проектированию машинной аппаратуры.
Современные вычислительные машины - это изумительные комплексы оборудования, но еще более изумляет неопределенность критериев оценки правильности результатов работы машины. Все основывается на предположении, что аппаратура функционирует правильно.
Ограничимся временно рассмотрением машинной аппаратуры; удивительно, насколько легко убедить человека в том, что она сконструирована безошибочно. Несколько лет назад в университете, где я работаю, появилась новая машина. В сопроводительной документации утверждалось, что среди многого прочего имеется схема умножения 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/2 if dd<= r do r:=r - dd

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

уполовинить dd;

О противоречии между правильностью доказательств и правильностью реализации

В предыдущем разделе подразумевалась "точная арифметика"; мой опыт показывает, что обоснованность таких доказательств часто ставится под сомнение людьми, которые ссылаются на то, что на практике в нашем распоряжении никогда не бывает абсолютно точной арифметики: обычно имеется верхняя граница для допустимых целых значений; действительные числа представляются только с конечной точностью и т. д. Так в чем же ценность таких доказательств? Мне кажется, что ответ на этот вопрос состоит в следующем. Если человек доказывает правильность программы применительно к идеализированному совершенному миру, то ему не следует удивляться, если что-то идет не так, когда эта идеальная программа выполняется на "несовершенной" машине. Это очевидно. Поэтому если мы хотим доказать правильность программы для более реального мира, то прежде всего необходимо четко осознать, что все используемые в программе операции (и, в частности, все арифметические операции) не обязательно выполняются точно; при этом мы должны сформулировать подобные аксиомам свойства, которым эти операции должны удовлетворять для того, чтобы программа выполнялась правильно, т. е. те свойства, на которых основывается доказательство правильности. (Для примера из предыдущего раздела требуется всего лишь точная целая арифметика в интервале [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)

В первой конструкции следование на первом уровне управляется заголовком выбора, а во второй конструкции - заголовком повторения. Я могу доказать эквивалентность результатов вычислений, однако я не могу считать эти программы эквивалентными при какой-либо другой полезной интерпретации понятия эквивалентности. Я вынужден был прийти к заключению, что "трудно сравнивать" программы (1) и (2). Сначала такой вывод весьма удручал меня. Однако со временем я смирился с тем, что такая несравнимость является реальным фактом; в этом одна из основных причин того, что выбор между (1) и (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)

Программа (4) отличается от программы (3) тем, что повторения заканчиваются, как только обнаружено отличие в какой-то паре. При одних и тех же входных данных число повторений в этих двух программах может отличаться; поэтому эти программы сравнимы в нашем понимании только тогда, когда две последние строки каждой программы считаются описывающими единое действие, не подразделяемое на поддействия. Но какая же между ними связь с точки зрения результатов после завершения повторений? Чтобы выяснить это, докажем правильность данных программ. Для массивов X и Y мы можем определить (N+l) функций РАВНЫj при 0jN следующим образом:

при j=0 PABHЫj=true

при j>0 РАВНЫj=РАВНЫj-1(X[j]=Y[j])

(5)

В терминах этих функций требуется доказать окончательный результат: равны=РАВНЫN

Обе программы сохраняют отношение

равны := РАВНЫj

(6)

при возрастании значений j,, начиная от j=0. Было бы заманчиво рассматривать программы (3) и (4) как различные конкретизации одной и той же (абстрактной) программы (7):

j:=0; равны : = РАВНЫ0; while "возможно, все еще: равны РАВНЫN" do begin j:=j+1; равны: =РАВНЫj end

(7)

в которой фраза "возможно, все еще: равны РАВНЫN", заменяет некоторое открытое элементарное условие типа "до сих пор". В процессе выполнения этой программы будет поддерживаться отношение равны=РАВНЫj

Программы (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СЧИТЫВАНИЕ" и "ВЫЧПОЗ" в терминах строк, хотя их можно было бы еще объяснять непосредственно .через отражение, т. е. независимо от выбираемого представления отражения. Другими словами, в первоначальном, варианте мы искуснее использовали свою способность к абстракции, чем в помеченном варианте. Чем больше число зерен, которые не зависят от конкретного представления, тем больше приспособляемость программы и тем легче ее понимать, поскольку эти зерна доступны пониманию на более высоком уровне абстракции. По-видимому, практика показывает, что требования приспособляемости и ясности имеют общую основу и, более того, сочетаются самым естественным образом. Это весьма радует (хотя и не удивляет). Это также проясняет (по крайней мере для меня) предмет нашего рассмотрения. К чему бы мы ни пришли, это не будет универсальным методом решения проблем автоматическим путем или с участием человека. Однако если человек сумеет найти решение, то мы можем помочь ему правильно оценить различные аспекты "изящества" этого решения. А уже это послужит ему ориентиром.

Об абстракции

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

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

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

Организация групп и последовательностей

Первый пример поэтапного составления программы

"таблица p"	1a
"заполнить таблицу p первой тысячей простых чисел"	1b
"напечатать таблицу p"	1c