О понимании программ
За свою жизнь я видел много учебников по программированию, весьма напоминающих обычные учебники по вождению автомашин, в которых человека учат, как ухаживать за машиной, вместо того чтобы научить его, как использовать машину, чтобы попасть в нужное ему место.
Я считаю, что программа никогда не является самоцелью; программа предназначается для того, чтобы вызвать вычисления, а цель вычислений - получить нужный результат. Несмотря на то что программа является конечным продуктом деятельности программиста, возможные вычисления по этой программе - "осуществление" которых предоставляется машине! - вот истинное содержание его труда. Например, всякий раз, когда программист утверждает, что его программа правильна, он на самом деле высказывает суждение о тех вычислениях, которые она может вызвать.
Сложность ситуации усугубляется тем обстоятельством, что последний этап всего процесса, т. е. переход от (статической) программы к (динамическим) вычислениям в сущности предоставлен машине. Поэтому в каком-то смысле изготовление программы представляет больше трудностей, чем разработка математической теории: и программа, и теория - это структурные, вневременные объекты; но если математическая теория имеет непосредственный смысл, то программа приобретает смысл только во время ее выполнения.
В оставшейся части этого раздела мы ограничимся рассмотрением программ, написанных для последовательностной машины, и обсудим некоторые следствия того, что нам необходимо использовать наше понимание программы, чтобы высказывать суждения о производимых ею вычислениях. Я утверждаю (хотя и не могу доказать), что легкость и гибкость таких наших суждений существенно зависит от простоты взаимосвязей между программой и вычислениями, а особенно от способа последовательного управления вычислениями. Грубо говоря, можно считать желательным, чтобы структура программы отражалась в структуре вычислений. Однако возникает вопрос: "Что можем мы сделать, чтобы сократить логический разрыв между статическим текстом программы (развернутым в "поле текста") и соответствующими вычислениями (развернутыми во времени)?"
Вычисления предназначаются для того, чтобы получить определенный нужный результат.
Начавшись в дискретный момент t0 они завершатся в более поздний дискретный момент t1, и мы предполагаем, что их результат может быть описан путем сравнения "состояния в момент t0 " и "состояния в момент t1". Если никакие промежуточные состояния не принимаются в рассмотрение, то считается, что результат достигается некоторым простым действием.
Если же мы включаем в рассмотрение ряд промежуточных состояний, то это означает, что мы разлагаем действие на временные этапы. Оно представляется как последовательное вычисление, т.е. временная последовательность некоторых поддействий, и мы должны убедиться в том, что общий эффект этой последовательности поддействий на самом деле тождествен желаемому результату всего вычисления. В простейшем случае производится разбор, или разложение, на конечное число поддействий, которые могут быть перенумерованы, можно представить в виде блок-схемы следующим образом: Правильность такого разложения должна быть доказана рассуждением с перечислением. При этом логический разрыв между программой и вычислением может быть сокращен благодаря требованию, чтобы каждый линейный участок текста программы содержал имена или описания поддействий в том порядке, в котором они должны выполняться. В нашем прежнем примере (с инвариантностью соотношения 0<=r<dd)
dd:=dd/2 if dd<= r do r:=r - dd
такое условие удовлетворяется. Это вычисление непосредственно разлагается в последовательность двух действий; в тексте программы распознаем такую структуру:
- уполовинить dd;
- уменьшить r по модулю dd.
Рассматриваем все начальные состояния, удовлетворяющие соотношению 0<=r<dd, и убеждаемся, что данное разложение на два поддействия применимо при рассмотрении всех соответствующих вычислений. Пока все хорошо.
Однако программа пишется в предположении, что "уменьшить r по модулю dd" не является простым действием в отличие от "уменьшить r на dd". При рассмотрении всех возможных выполнений действия "уменьшить r по модулю dd" естественно различать некоторые случаи, когда имеет место действие "уменьшить r на dd", тогда как в остальных случаях значение r не изменяется.
Записав
if dd<= r do уменьшить r на dd
мы выразили, что на данном уровне детализации действие "уменьшить r по модулю dd" может принять одну из двух взаимно исключающих форм, и одновременно задали критерий того, как производится выбор между этими двумя формами. Если рассматривать "if dd<= r do" как условие, применяемое к "уменьшить r на dd", то естественно, что условие помещается в начало условного оператора. (В этом смысле заголовок альтернативы
if условие then оператор 1 else оператор 2
является "надстройкой" по отношению к "оператору 1" и "оператору 2": это две альтернативы, которые не могут быть выражены одновременно при обычной линейной записи.) Хоор обобщил понятие заголовка альтернативы, введя конструкцию case-of ("вариант из"), обеспечивающую выбор среди более чем двух возможностей. В виде блок-схем это выражается следующим образом:
Общее свойство всех этих блок-схем состоит в том, что у каждой из них один вход вверху и один выход внизу. Пунктирные блоки обозначают, что каждая блок-схема может в свою очередь интерпретироваться (независимо от содержимого пунктирного контура) как единое действие при последовательных вычислениях. Если говорить чуть более точно, мы имеем дело с большим числом возможных вычислений, непосредственно разлагаемых в одну и ту же временную последовательность поддействий, и только при более детальном рассмотрении, а именно при заглядывании внутрь пунктирного блока, выясняется, что над разнообразием возможных вычислений такое поддействие может принимать одну из перечисленных различных форм.
Сказанного выше достаточно, чтобы рассматривать класс вычислений, которые непосредственно разлагаются на одни и те же последовательные пронумерованные поддействия. Однако этого недостаточно, чтобы рассматривать класс вычислений, которые непосредственно разлагаются на различное число поддействий. (Речь идет о том, что число поддействий изменяется в рамках рассматриваемого класса вычислений.) Именно здесь становится очевидной полезность заголовков повторения.
Сошлемся на операторы "while условие do оператор" и "repeat оператор until условие", которые могут быть представлены в виде блок-схем следующим образом:
Эти блок- схемы также характеризуются наличием одного входа вверху и одного выхода внизу. Они позволяют нам выразить мысль, что действие, представляемое пунктирным блоком, оказывается при детальном рассмотрении последовательностью из "достаточного .числа" поддействий определенного вида.
Итак, мы познакомились с тремя типами разложения; можно называть их соответственно "сочленением", "выбором" и "повторением". Для понимания первых двух служит рассуждение с перечислением, а для последнего нужна математическая индукция.
Программы, при написании которых управление последовательностью действий осуществляется только при помощи выбора и повторения, допускают непосредственный перевод на некий язык программирования, который отличается от исходного только тем, что все управление последовательностью действий должно быть выражено передачами управления на метки. Однако обратное утверждение было бы неправильным. Напротив, если мы ограничимся указанными тремя типами разложения, то это приведет к ограничению топологии блок-схем по сравнению с различными блок-схемами, которые могут быть получены, если разрешить проведение стрелок из любого блока в любой другой блок. Отказавшись от большого разнообразия блок-схем и ограничившись данными тремя типами операторов управления, мы следуем тем самым некоей последовательностной дисциплине.
Почему я предлагаю придерживаться этой последовательностной дисциплины? Это решение может быть обосновано различными способами, и я попытаюсь изложить несколько таких обоснований в надежде на то, что хотя бы одно из них удовлетворит моих читателей.
В конечном счете мы стремимся изготовлять такие хорошо организованные программы, чтобы интеллектуальное усилие (оцениваемое неформально), которое необходимо для их понимания, было пропорционально размеру программы (оцениваемому столь же неформально).
В частности, мы должны остерегаться чрезмерных рассуждений с перечислением, что побуждает нас руководствоваться ярым правилом "разделяй и властвуй"; в этом причина того, что мы предлагаем последовательно разлагать вычисления на этапы.
Разложение сочленением мы можем понимать с помощью рассуждения с перечислением. (Это возможно при условии, что число поддействий, на которые непосредственно разлагается вычисление, достаточно мало, а результаты их применения сформулированы достаточно точно. Мы вернемся к обсуждению этих требований позднее, а пока будем предполагать, что эти условия удовлетворяются.) При этом удобно высказывать суждения относительно вычислений, пользуясь текстом программы, поскольку связь между продвижением вычислений и продвижением по тексту программы является тривиальной. В частности, если при детальном рассмотрении оказывается, что некое поддействие управляется заголовком выбора или заголовком повторения, это не затрудняет понимания непосредственного разложения, так как принимается во внимание только общий эффект поддействия. Следствие: если при детальном рассмотрении поддействия выясняется, что оно управляется заголовком выбора, то выбор конкретного пути несуществен на первом уровне разложения (важно только, чтобы выбирался правильный путь). Аналогично если при детальном рассмотрении поддействия выясняется, что оно управляется заголовком повторения, то число выполнений повторяемого оператора также не является существенным (важно только, чтобы число повторений было правильным). Точно так же мы можем непосредственно понимать заголовки выбора, пользуясь рассуждением с перечислением, и понимать заголовки повторения с помощью математической индукции. Я считаю большим удобством, что для всех трех типов разложения мы знаем подходящие способы рассуждения. Можно указать еще одно преимущество предлагаемой последовательностной дисциплины. В процессе понимания программ мы устанавливаем соотношения. В нашем примере рассуждения с перечислением мы устанавливаем, что фрагмент программы
dd:=dd/2; if ddr do r:=r-dd
сохраняет отношения 0<=r<dd
инвариантными. Однако, если даже мы можем гарантировать, что эти отношения справедливы перед выполнением данной части программы, из этого нельзя сделать вывод, что они справедливы всегда: вовсе необязательно, чтобы они имели место в промежутке между выполнением двух операторов, заключенных в кавычки. Другими словами, справедливость таких отношений зависит oт продвижения вычислений, и это представляется типичным для последовательного процесса.
Аналогично мы приписываем смысловые значения переменным: переменная может быть счетчиком числа выполнений событий заданного типа, например, числа строк, напечатанных на текущей странице. Переход к новой странице сразу же сопровождается засылкой нуля в счетчик, а печать очередной строки непосредственно сопровождается прибавлением единицы к счетчику. Опять-таки непосредственно перед обновлением или увеличением счетчика интерпретация "числа строк, напечатанных на текущей странице", не является определенной. Присвоение переменной такого смыслового значения может быть выполнено только в зависимости от хода вычислений. Это наводит нас на следующий вопрос: "Как мы характеризуем ход вычислений?"
Коротко можно сказать, что мы ищем координатную систему, с помощью которой можно идентифицировать дискретные точки продвижения вычислений, и хотим, чтобы эта координатная система не зависела от переменных, которые обрабатываются под управлением программы. Если нам нужно, чтобы значения таких переменных описывали продвижение вычислений, то получается замкнутый логический круг, потому что мы хотим интерпретировать смысл этих переменных именно в связи с продвижением вычислений.
(Еще более веской причиной для того, чтобы не полагаться на значения этих переменных, является существование программы, содержащей бесконечный цикл, проходящий конечное число различных состояний. Невозможность выхода из цикла следует из того факта, что в различных точках продвижения вычислений имеет место одинаковое состояние.
Но тогда очевидно, что это состояние непригодно для того, чтобы различать между собой данные две различные точки продвижения вычислений!)
Мы можем сформулировать нашу проблему другим способом. Дана работающая программа и предполагается, что до завершения счета она остановлена в одной из дискретных точек продвижения вычислений. Каким способом мы можем идентифицировать точку прерывания, если, например, хотим повторить вычисления именно до этой самой точки? Кроме того, если останов был вызван какой-то динамической ошибкой, то как мы можем идентифицировать соответствующую точку продвижения вычислений, не прибегая к полному копированию памяти?
Для простоты предположим, что текст нашей программы находится в специальном (линейном) поле текста и что существует способ идентификации точек в программе, соответствующих дискретным точкам продвижений вычислений. Будем называть этот способ идентификации "текстуальным индексированием". (Если дискретные сточки продвижения вычислений располагаются между последовательными выполнениями операторов, то текстуальное индексирование идентифицирует, например, точки с запятыми.) Текстуальный индекс представляет собой нечто вроде обобщенного счетчика команд, его значение указывает место в тексте.
Если мы ограничиваемся при разложении только сочленением и выбором, то для идентификации продвижения вычислений достаточно одного текстуального индекса. Если же допускаются заголовки повторения, то текстуальные индексы уже не обеспечивают описание продвижения вычислений. Однако при каждом входе в заголовок повторения система могла бы заводить так называемый "динамический индекс", неукоснительно отсчитывающий очередной номер соответствующего текущего повторения; по окончании повторений система должна устранить соответствующий динамический индекс. Поскольку заголовки повторений могут оказаться последовательно вложенными один в другой, то удобно пользоваться стеком (т.е. памятью, организованной по принципу "последним пришел - первым ушел").
Первоначально стек пуст. При входе в заголовок повторения новый динамический индекс (с начальным значением нуль или единица) добавляется в вершину стека. Всякий раз, когда принимается решение, что повторения еще не закончились, верхний элемент этого стека увеличивается на 1. Если же принимается решение, что повторения завершились, производится удаление верхнего элемента из стека. (Такая организация весьма наглядно отражает то обстоятельство, что после завершения повторений перестают быть существенными число выполнений повторяемого оператора и даже сам факт повторения.)
Когда язык программирования допускает процедуры, уже не удается обойтись одним текстуальным индексом. Если текстуальный индекс указывает место внутри тела процедуры, то динамическое продвижение вычислений определяется только тогда, когда мы также описываем тот вызов процедуры, к которому мы обращаемся: однако это можно сделать, только задав специальный текстуальный индекс, указывающий место вызова. При включении процедур необходимо использовать обобщение текстуального индекса, представляющее собой стек текстуальных индексов, увеличивающийся на один элемент при вызове процедуры и уменьшающийся на один элемент при возврате из процедуры. Весьма существенно, что значения этих индексов не контролируются программистом. Они определены (либо из распечатки его программы, либо из динамики текущего вычисления) независимо от тогo, нравится это ему или нет. Они могут служить независимыми координатами для описания продвижения вычислений, образуя "независимую от переменных" систему отсчета, в рамках которой можно приписывать переменным смысловые значения. Разумеется, даже при произвольном использовании передач управления существует независимая от программиста координатная система, с помощью которой можно однозначно описывать продвижение последовательных вычислений; это своего рода условные часы, которые отсчитывают число "дискретных точек продвижения вычислений", пройденных от начала выполнения программы.Эта система однозначна, но она совершенно бесполезна, так как текстуальный индекс уже не является составной частью такой координатной системы. Из сказанного можно сделать следующий вывод. Если мы считаем своей обязанностью контролировать вычисления (интеллектуально!), обращаясь к тексту управляющей вычислениями программы, то нам следует смиренно довольствоваться наиболее систематизированными способами организации следования, гарантирующими самое непосредственное отражение "продвижения вычислений" в "продвижении по тексту".
