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