Лекция: О ПОНИМАНИИ ПРОГРАММ

Вычисления предназначаются для того, чтобы получить опре­деленный нужный результат. Начавшись в дискретный момент tb, они завершатся в более поздний дискретный момент и мы пред­полагаем, что их результат может быть описан путем сравнения «со­стояния в моментt0» и «состояния в моментtЕсли никакие промежуточные состояния не принимаются в рассмотрение, то счита­ется, что результат достигается некоторым простым действием.

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

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

Правильность такого разложения должна быть доказана рас­суждением с перечислением. При этом логический разрыв между программой и вычислением может быть сокращен благодаря требо­ванию, чтобы каждый линейный участок текста программы содер­жал имена или описания поддействий в том порядке, в котором они должны выполняться.

Заголовок альтернативы

if условие then оператор 1 else оператор 2

является „надстройкой“ по отношению к „оператору Г' и “оператору 2»: это две альтернативы, которые не могут быть выражены одно­временно при обычной линейной записи.)

Хоор обобщил понятие заголовка альтернативы, введя конструк­цию case-of, обеспечивающую выбор среди более чем двух воз­можностей. В виде блок-схем это выражается следующим образом:

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

Сказанного выше достаточно, чтобы рассматривать класс вы­числений, которые непосредственно разлагаются на одни и те же последовательные пронумерованные поддействия. Однако этого не­достаточно, чтобы рассматривать класс вычислений, которые непосредственно разлагаются на различное число поддействий. (Речь идет о том, что число поддействий изменяется в рамках рас­сматриваемого класса вычислений.) Именно здесь становится оче­видной полезность заголовков повторения. Сошлемся на операторы «while условие do оператор» и «repeat оператор until» условие", ко­торые могут быть представлены в виде блок-схем следующим обра­зом:

Эти блок-схемы также характеризуются наличием одного входа вверху и одного выхода внизу. Они позволяют нам выразить мысль, что действие, представляемое пунктирным блоком, оказывается при детальном рассмотрении последовательностью из «достаточного числа» поддействий определенного вида.

Итак, мы познакомились с тремя типами разложения; можно называть их соответственно «сочленением», «выбором» и «повторением». Для понимания первых двух служит рассуждение с перечислением, а для последнего нужна математическая индукция.

Программы, при написании которых управление последователь­ностью действий осуществляется только при помощи выбора и пов­торения, допускают непосредственный перевод на некий язык про­граммирования, который отличается от исходного только тем, что все управление последовательностью действий должно быть выраже­но передачами управления на метки. Однако обратное утверждение было бы неправильным. Напротив, если мы ограничимся указан­ными тремя типами разложения, то это приведет к ограничению топологии блок-схем по сравнению с различными блок-схемами, которые могут быть получены, если разрешить проведение стрелок из любого блока в любой другой блок. Отказавшись от большого разнообразия блок-схем и ограничившись данными тремя типами операторов управления, мы следуем тем самым некоей последовательностной дисциплине.

Почему я предлагаю придерживаться этой последовательностной дисциплины? Это решение может быть обосновано различны­ми способами, и я попытаюсь изложить несколько таких обосно­ваний в надежде на то, что хотя бы одно из них удовлетворит моих читателей.

В конечном счете мы стремимся изготовлять такие хорошо ор­ганизованные программы, чтобы интеллектуальное усилие (оце­ниваемое неформально), которое необходимо для их понимания, было пропорционально размеру программы (оцениваемому столь же неформально). В частности, мы должны остерегаться чрезмерных рассуждений с перечислением, что побуждает нас руководствоваться старым правилом „разделяй и властвуй"; в этом причина того, что мы предлагаем последовательно разлагать вычисления на этапы.

Разложение сочленением мы можем понимать с помощью рас­суждения с перечислением. (Это возможно при условии, что число поддействий, на которые непосредственно разлагается вычисление, достаточно мало,а результаты их применения сформулированы до­статочно точно. Мы вернемся к обсуждению этих требований позд­нее, а пока будем предполагать, что эти условия удовлетворяются.) При этом удобно высказывать суждения относительно вычислений, пользуясь текстом программы, поскольку связь между продвиже­нием вычислений и продвижением по тексту программы является тривиальной. В частности, если при детальном рассмотрении ока­зывается, что некое поддействие управляется заголовком выбора или заголовком повторения, это не затрудняет понимания непосред­ственного разложения, так как принимается во внимание только общий эффект поддействия.

30. Неоднозначность определения программы. Проблема сравнения программ.