Второй пример поэтапного составления программы
Теперь, когда у нас возникло представление о структуре программы как об иерархическом расслоении машин, я испытываю непреодолимое желание "повозиться" с этой моделью, т. е. составить еще одну программу. Не следует рассматривать применяемый здесь способ обозначений как тщательно продуманное общее предложение; эти обозначения я выбрал по своему вкусу, и к ним нужно относиться как к части эксперимента.
Задача состоит в следующем. Имеется строчное печатающее устройство, которое управляется двумя командами; одна команда "НСВК" (Новая строка Возврат каретки) устанавливает в качестве "текущей позиции печати" самую левую позицию следующей строки, а другая команда "ПЧСИМ(n)" печатает в текущей позиции печати символ, указываемый значением целого параметра п, и устанавливает соседнюю справа позицию в качестве новой текущей позиции печати. (В рамках нашего рассмотрения можно считать допустимыми строки бесконечной длины.) Мы будем использовать только два конкретных значения п, которые называются "пробел" и "знак". Команда "ПЧСИМ(пробел)" приводит к тому, что текущая позиция печати остается пустой, а команда "ПЧСИМ(знак)" напечатает заданный графический символ, например некоторую разновидность звездочки.
Кроме того, заданы две целые функции от целого аргумента, удовлетворяющие отношению
при 0i<1000 : 0fy(i)<100 и 0fy(i)<50
Нам требуется изготовить программу, печатающую 50 строк, которые нумеруются сверху вниз координатой у, пробегающей значения от 49 до 0; позиции в строке будут нумероваться слева направо координатой х, пробегающей значения от 0 до 99. Нужно напечатать знак в тысяче (или меньше, если будут совпадения) позиций, для которых
x=fx(i) и y=fy(i) при i от 1 до 1000
Все остальные позиции на бумаге должны оставаться пустыми. Другими словами, кривая задается в дискретном параметрическом представлении, и мы хотим использовать строчное печатающее устройство в качестве двоичного графопостроителя.
Я часто задавал эту задачу на устных экзаменах, и большинство студентов быстро соображают, что отсутствие команд ПСВК (Предыдущая строка Возврат каретки) и "предыдущая позиция" приводит к тому, что порядок обслуживания позиций печати определяется командами печати и что на этот порядок никак не влияет упорядочивание знаков, если мы нумеруем их по возрастанию значений i.
В результате студенты быстро приходят к выводу, что задача решается довольно однозначно: сначала нужно накопить тысячу i-значений, т. е. запомнить в удобной форме представление страницы, а затем напечатать страницу, руководствуясь ее представлением, находящимся в памяти. (Точнее говоря, мы предполагаем, что у машины достаточная для этого память и что вычисление значений функций fx(i) и fy(i) может оказаться столь продолжительным, что мы предпочитаем вычислять их только по одному разу для каждого i-значения.)
Теперь мы зафиксируем это проектное решение; предлагается следующий текст:
ВЫЧНАЧ begin чертить: {строить; печатать}; var отражение; instr строить(отражение), печатать(отражение) end
Этот документ рассматривается как цельная часть окончательной программы и должен интерпретироваться следующим образом. Относится к машине "ВЫЧНАЧ" (мы используем заглавные буквы для названий машин и пытаемся выразить этими названиями типы решений в программах для этих машин). Следующая строка указывает именованный алгоритм; он называется "чертить" (предполагается, что это имя всей изготовляемой программы, которая должна "чертить" кривую) и указывает желаемую последовательность выполнения двух действий: построение отражения в памяти, а затем печать на бумаге в соответствии с запомненным значением отражения. В последних двух строках задаются описания (или заголовки описаний) компонент машины, используемых в алгоритме. Первая из них указывает, что имя "отражение" будет употребляться для структуры данных, в которую будет заложено представление страницы; переменная "отражение" является единственной компонентой установленной памяти этой машины. Код операций машины содержит две команды с именами "строить" и "печатать". Прежде чем продолжить наши рассмотрения, заметим, что среди употребляемых нами сокращений есть и такие, об удачности которых пока еще трудно судить. Обе введенные в этом тексте аббревиатуры употребляются в предположении, что переменная "отражение" является единственной переменной этого типа. Если потребуется, чтобы установленная память хранила два отражения, то следует написать
Тот факт, что это действительно можно рассматривать как алгоритм для машины, станет, возможно, более наглядным, если мы рассмотрим другие алгоритмы "чертить". Например, программа
чертить: {печатать; строить}
не годится, потому что в этом случае действие "печатать" не определено;
чертить: {строить; строить; печатать}
корректна, но приводит к излишним затратам машинного времени, так как второе действие "строить" присваивает переменной "отражение" то самое значение, которое она уже имеет; программа
чертить: {строить; печатать; печатать}
имела бы определенный смысл: чертеж печатался бы дважды.
Теперь уточним нашу программистскую задачу. Если бы в нашем распоряжении имелась машина "ВЫЧНАЧ", то вся работа была бы выполнена на ней маленькой программой "чертить".
Чтобы продолжить рассуждения и с учетом реальности предполагаем теперь, что у нас нет такой машины, в точности соответствующей нашим потребностям, а поэтому наша следующая задача (подобная предыдущей!) состоит в том, чтобы изготовить такую машину.
Имеются три именованных понятия: "строить", "печатать" и "отражение", причем два первых ссылаются на последнее. Поэтому дальнейшая конкретизация последнего понятия повлияет на два первых; кроме того, очень трудно конкретизировать действие "печатать" без дальнейшего уточнения структуры "отражение". Однако действие "строить" допускает дальнейшую независимую детализацию, и именно поэтому мы будем в первую очередь заниматься дальнейшей конкретизацией понятия "строить".
Нам нужно описать, как переменной "отражение" присваивается ее значение, соответствующее требуемому расположению тысячи знаков. В целом эта операция присваивает значение переменной, которая ранее не имела определенного значения; если же исходить из того, что знаки будут добавляться по одному, то мы видим, что добавление следующего знака окажется действием над уже определенным значением "отражение".
Поэтому заманчиво рассматривать всю расстановку знаков как действие над уже определенным значением, а именно над значением, соответствующим пустой странице. Такое решение приводит к записи
ЧИСТНАЧ begin
строить: {чистить; ставить знаки}; instr чистить (отражение), ставить знаки (отражение) end
Здесь действие "чистить" присваивает отражению значение, соответствующее картине пятидесяти пустых строк, а действие "ставить знаки" перестраивает начальное значение отражения, заменяя его на значение, в которое включены тысяча (или меньше) знаков, расположенных на нашей кривой.
ЧИСТНАЧ - это тоже машина, для которой можно писать различные программы. Например, программа
строить: {чистить}
имела бы смысл, но привела бы к получению пятидесяти пустых строк;
строить {ставить знаки; чистить}
содержала бы неопределенную операцию;
строить: {чистить; чистить; ставить знаки}
содержала бы излишнюю операцию, равно как и программа
строить: {чистить; ставить знаки; ставить знаки}
В последнем случае второе действие "ставить знаки" только добавило бы в чертеж те знаки, которые там уже имелись бы, и поэтому не внесло бы изменений в значение "отражение". (Замечание об используемых обозначениях. Алгоритмическое выражение понятия "строить" через "чистить" и "ставить знаки" производится без явного упоминания имени "отражение", поскольку мы не хотим использовать в алгоритмах запись с фактическими параметрами, если комбинаторная гибкость такой записи не используется по существу в данной машине. Кроме того, хотя операция "строить" является однопараметрической, мы не вводили отдельного идентификатора для ее формального параметра. Допускаю, что это сокращение может оказаться не очень разумным.) Следующий этап проектирования наших вычислений может быть выполнен без предварительных уточнений; он состоит в описании порядка обработки тысячи знаков на кривой. Пока я предлагаю следующую запись:
IСЧИТЫВАНИЕ begin integer i; ставить знаки: (i:=0; while i<1000 do добавить знак; i плюс l}}; instr добавить знак (i, отражение) end
Этот алгоритм следует понимать применительно к машине, система команд которой предусматривает операцию "добавить знак (i,отражение)"; эта операция изменяет значение "отражение" путем добавления i-гo знака. Данный алгоритм описывает порядок, в котором обрабатываются все знаки; мы видим, что каждый знак будет обрабатываться ровно один раз.
Однако это еще не все: введена новая переменная i, алгоритм обращается к операциям, которые ссылаются на эту переменную ("i:=0", "i<1000", "i плюс 1"), и если быть последовательными до конца, то, по-видимому, нужно было перечислить эти операции в конце, поскольку они могут потребовать разъяснений на последующем этапе подобно тому, как это делалось для операции "добавить знак". Я этого не сделал, и отношусь к этим операциям примерно так же, как к заголовкам while-do. С точки зрения языковой семантики вызывает сомнение оправданность особого обращения с неявно подразумеваемым типом integer; казалось бы, трудно мотивировать, почему тип integer вводится не так, как тип "отражение", ведь оба они неявно подразумеваются в данной машине.
И все-таки я поступил именно так. Я все время разрабатываю программы для несуществующих машин и приговариваю: "Если мы теперь имеем машину, включающую предполагаемые здесь элементы, то вся работа сделана". С абстрактно-логической точки зрения это правильно, но на практике это оказывается всего лишь шуткой, так как мы отлично знаем, что невозможно предположить, чтобы имелась машина общего назначения, код операций которой был бы настолько приспособлен к нашим потребностям. Нам не следует не только забывать, но и замалчивать нашу ответственность за обеспечение этих элементов на более позднем этапе разработки. Когда теперь я обращаюсь особым образом к общепонятному типу "integer" и к операциям, определенным над переменными этого типа, то делаю это с намерением выразить, что, хотя эти возможности и нужно так или иначе обеспечить, их обеспечение лежит вне.
сферы ответственности программиста, а также что программиста устроит любая их разумная реализация.
Займемся еще одним программным элементом, который допускает дальнейшую конкретизацию вне связи с другими элементами. Нам нужно описать, как обработка i-го знака может быть выражена с помощью действий над позицией страницы
ВЫЧПОЗ begin integer x, у; добавить знак: {x:=fx(i);y:=fy(i); знак поз}; instr знак поз (х, у, отражение) end
Здесь "знак поз" изменит текущее значение переменной "отражение", поскольку к чертежу для печати добавляется знак с координатами "х" и "у." (Замечание. В этой конкретизации явно предполагается, что функции fx(i) и fy(i) могут вычисляться в любом порядке следования значений их аргументов. Если бы эти две тысячи значений функций могли считываться с вводного устройства попарно в предписанном порядке i-значений, то две последние машины можно было бы объединить в одну.) Теперь уже я не вижу возможностей дальнейших конкретизации, если не углубиться в структуру все еще несколько неясного типа "отражение". Как представляем мы себе запоминание этой величины? Нам следует установить структуру переменных типа "отражение", или, что сводится к тому же, мы должны принять решение о способе представления в памяти всех возможных значений этого типа. Выступая с лекциями перед различными аудиториями, я описывал некоторые варианты данной программы, и наверное стоит отметить, что по меньшей мере дважды часть моих слушателей начинала испытывать тревогу к тому времени, как я достигал этого места. Например, у них возникало чувство, что я не в состоянии доказать правильность построенной программы. Когда я говорил, что
чертить: {строить; печатать; печатать)
выдаст один и тот же чертеж два раза, они возражали, ссылаясь на теоретическую возможность того, что операция "печатать" изменит (посредством некоего побочного эффекта) значение "отражение" прежде, чем мы начнем выполнять вторую команду "печатать".
Разумеется, ответ на эти возражения состоит в том, что операция "печатать" должна делать именно то, что ей предписано, и не должна делать ничего другого. Но тогда возникают новые возражения: мне не удалось доказать единственность способа представления; не исключено, что "печатать" - это частичная функция, определенная не для всех возможных значений "отражение", и т. д. По-видимому, ответ на это должен состоять в следующем: эти соображения вполне законны, но следует отложить их обсуждение до более подходящего времени, а точнее, вернуться к этому после того, как мы сосредоточим внимание на вопросах представления. Очевидное преимущество нашего подхода состоит в том, что столь значительную часть программы удалось написать независимо от выбора представления для значений типа "отражение". Все, что мы сделали до сих пор, выглядит удачным использованием нашей способности к абстракции (здесь мы абстрагировались от выбора конкретного представления для структуры данных "отражение").
Но даже если мы теперь приходим к заключению, что настало время принимать решения относительно структуры данных типа "отражение", нам все еще не обязательно до конца углубляться в эту проблему. Занявшись теперь вопросом о структурной организации нашей переменной, мы можем принимать решения поэтапно, аналогично тому как мы это делали при предыдущих конкретизациях алгоритмов. Напомним, что постановка задачи началась с того, что с помощью команд "ПЧСИМ" и "НСВК" нужно организовать вычисления для получения искомого чертежа строка за строкой сверху вниз. Попытаемся формально выразить этот факт, интерпретируя отражение как массив строк. Тогда мы приходим к следующему очередному уровню:
СТРОП begin integer j; отражение: {array строка [0:49]}; печатать: {j:=49; while j>0do {печатать строку (строка [j]); j минус 1}}; чистить: {j:=49; while j>0 do чистить строку (строка [j]); j минус 1}}; знак поз: { знак в строке (строка [y])}; type строка; instr печатать строку (строка), чистить строку (строка), знак в строке (х, строка) end
В предпоследней строке текста мы ввели тип с названием "строка"; напоминаю, что тип представляет собой совокупность различимых значений, и переменная некоего типа может в любой момент 1; принимать какое-то одно значение из соответствующей совокупности. Первая строка текста означает, что тип "отражение" образуется из массива, в котором имеется 50 элементов типа "строка" с номерами от 0 до 49. Поскольку это единственный тип, образованный из строк, мы снова воздерживаемся от введения нового идентификатора (хотя может возникнуть сомнение в разумности этого решения).
Итак, операции "печатать", "чистить" и "знак поз", которые понимались как действия над величиной "отражение", транслируются в алгоритмы, выраженные с помощью операций над строкой. В записи этих алгоритмов каждый фактический параметр указывает конкретную строку; в конце описания мы приводим список команд, в котором перечисляем те действия, которые выполняются над "строкой"; при этом мы задаем тип, но не параметр.
На этом уровне появляются некоторые новые свойства. На начальных этапах (подобно тому, как мы это делали, описывая "отражение") мы проводим структурную конкретизацию типа данных примерно на такой же основе, как и алгоритмические конкретизации (вроде тех, что применялись к алгоритмам "печатать", "чистить" и "знак поз"). До этого уровня можно было рассматривать наш подход как попытку установить четкий порядок "подпрограммирования", если читатель простит этот ужасный термин! Теперь же мы отмечаем, что такая характеристика наших усилий охватывает только половину того, что мы пытаемся сделать, поскольку мы хотим применить аналогичный прием также и к структурам данных. Кроме того, каждая наша предыдущая машина описывала только одно понятие (команду или тип данных), тогда как СТРОП описывает целый комплекс понятий. Дело в том, что мы пытаемся принимать для каждого уровня отдельное проектное решение; здесь мы решаем понимать отражение отныне и впредь в терминах строк, и поэтому все операции, выполняемые над отражением в целом, должны быть сведены к операциям над составляющими его строками.
Отражение уже "отжило"; единственным необычным типом, с которым нам все еще нужно иметь дело, остается тип "строка", и именно им мы собираемся теперь заняться. Обратите особое внимание на то, что на новом уровне нам придется заниматься именно строками, и теперь уже не будет иметь значение то обстоятельство, что строки используются для составления отражений.
Для представления строки существует много различных способов. Годится и список x-координат позиций, где следует напечатать знак (этот список может быть упорядочен по возрастанию значений х), и логический массив из ста элементов, каждый из которых указывает, следует ли ставить знак в соответствующей позиции строки на чертеже; можно применить и целый массив из ста элементов, каждый из которых принимает значение "знак" или "пробел" параметра операции ПЧСИМ для соответствующей позиции печати. Последний вариант представления пригоден для более общего случая, когда на одном чертеже нужно напечатать различные кривые (с различными знаками); поэтому мы выбираем этот вариант. Это приводит к программе
ДЛИНЦИК begin integer k; строка: {integer array сим [0:99]}; печатать строку: {k:=0; while k<100 do {ПЧСИМ (сим [k]); k плюс 1}; НСВК}; чистить строку: {k:=0}; while k<100 do {сим [k]:=пробел; k плюс 1}}; знак в строке: = {сим [x]:=знак} end
Однако при выполнении этого алгоритма заполняется пробелами остаток строки справа от самого правого знака; это все равно, что стучать по клавише пробела до тех пор, пока не зазвенит звонок, когда мы печатаем на машинке и хотим перейти к новой строке. Ниже приводится вариант программы с подавлением излишних команд ПЧСИМ и даже с сохранением неопределенных значений тех переменных типа "строка", определение которых не требуется. Каждой строке ставится в соответствие счетчик f, задающий число команд ПЧСИМ для этой строки. Очистка строки теперь сводится к установке значения 0 для f
КОРЦИК begin integer k; строка: {integer f; integer array сим [0:99]}; печатать строку: {k:=0; whilek<f do {ПЧСИМ сим [k]); k плюс 1}; НСВК}; чистить строку: {f:=0}; знак в строке: {сим [x]:=знак; if fx do {k:=f; while k<x do {сим [k]:=пробел; k плюс 1}; f:=x+1}} end
Замечание, добавленное позднее.
Выше описана именно та программа, которую я демонстрировал по меньшей мере пяти различным аудиториям. Теперь, два месяца спустя, поразмыслив на досуге о правильности доказательств, я внезапно осознал, что данный алгоритм "знак в строке" компрометирует меня, так как он безобразно выглядит по сравнению со следующим вариантом:
знак в строке: {while fx do {сим [f]:=пробел; f плюс 1}; сим [x]:=знак}
Этот вариант гарантирует, что при всяком выполнении действия "сим [x]:=знак" будет выполняться отношение "x<f"; именно для обеспечения этого отношения предназначена первая строка программы. Читателю предлагается попытаться понять оба варианта программы и сравнить их логику. Сделав это, он согласится с моим мнением о слабости первоначального варианта. Второй вариант пришел мне в голову по следующей ассоциации. Условие
if В do S
используется в программах двумя различными способами. С одной стороны, имеются приложения, в которых выполнение оператора S не нарушает истинность В; с другой стороны, мы встречаем и ситуации, когда выполнение оператора S заведомо делает утверждение В ложным. В последнем случае задача условного оператора состоит в том, чтобы обеспечить после своего выполнения значение B=false. В таком случае это в сущности сокращенная запись оператор а
while В do S
который имеет свойство нарушения истинности В (при условии, что он не будет выполняться бесконечно долго). Однако для обоснования этого сокращения требуется отдельно доказать, что повторяемый оператор будет выполнен не более одного раза. (В разделе "Первый пример поэтапного составления программы" мы не стали вводить такое сокращение на уровне 2b4(4), где писали
while "значение ord слишком мало" do "увеличить ord на 1";
Здесь то же самое можно было бы сделать с помощью условия.)
