Структурное программирование

Теперь рассмотрим случай, когда рекурсивная реализация намного  изящнее циклической, легче обобщается и не хуже по эффективности²⁾

 

Рис. 3 Алгоритм Евклида

 

В данном случае путь для  получения результата не разветвляется, и нам остается лишь двигаться  по нему в правильном направлении (от цели к исходным данным) и достаточно большими шагами.

 

function Euklides (n,m: integer) integer; {

предполагаем m<=n}

begin

if n=m then resut: =n

else result: =Euklides (n mod m, m);

end;

 

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

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

Рассмотрим два крайних  случая движения по сети. Когда сеть представлена в виде структуры данных, естественно возникает метод ленивого движения по сети, когда после вычисления значений в очередной точке выбирается одна из точек, для которой все предыдущие значения уже вычислены, и вычисляются значения в данной точке. Как видно, в частности на примере золотой горы, этот метод недетерминирован и в значительной степени может быть распараллелен. Но в конкретном алгоритме нам придется выбрать конкретный способ ленивого движения, и он может быть крайне неудачен: например, он будет провоцировать длительное движение в тупик, когда у нас есть короткий путь к цели. Даже в теоретических исследованиях приходится накладывать условия на метод ленивого движения, чтобы гарантировать достижение результата (см., например, теорему о полноте семантических таблиц в книге [20] ).

Другой крайний случай движения по сети, когда сеть делится  на одинаковые слои. Например, в сети (4)

 

Рис.4 Полностью заменяемый массив

 

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

 

Рис. 5 Постепенно заменяемый массив

 

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

Еще Э. Дейкстра в книге [11] предложил в каждом блоке описывать импортированные и экспортируемые им глобальные значения. Но такая "писанина" раздражала хакеров и в итоге так и не вошла в общепризнанные системы программирования. Сейчас индустриальные технологии требуют таких описаний, но из-за отсутствия поддержки на уровне синтаксического анализа все это остается благими пожеланиями, так что, если хотите, чтобы Ваша программа была понятна хотя бы Вам, описывайте все перекрестные информационные связи!

Резюмируя вышеизложенное, можно  сделать следующие выводы.

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

Программа определяется не только сетью данных, но и конкретной дисциплиной движения по этой сети.

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

В случае, если вычисление можно  свести к вычислениям для независимых  элементов сети, чаще всего удобней рекурсия.

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

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

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

Внимание!

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

Выбор.

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

Пример 1. Пусть в некоторый момент исполнения программы Вам необходимо временно выбросить больший из двух хранимых в основной памяти обрабатываемых блоков на диск. Поскольку разница в длине менее 2¹⁶=65536) несущественна, мы можем записать выбор примерно в следующей форме.

 

if

length (A) - lengtn (B) >65536 {

Save (A); Dispose (A); A_present: =false; },

length (A) - lengtn (B) <65536 {

Save (B); Dispose (B); B_present: =false; }

fi

 

Мы воспользовались данной формой, чтобы ярче подчеркнуть условия, при которых производятся действия.

Предложенная форма записи базируется на концепции охраняемых команд, предложенной Э. Дейкстрой. Охраняемая команда исполняется лишь при условии, когда выполнена охрана. Но если данный текст читает программист, он должен понимать, что 'лишь' не всегда означает, что при выполнении условия команда будет выполнена. Оператор выбора по Дейкстре состоит из множества охраняемых команд. В конкретном синтаксисе мы используем для них форму

 

Guard Command

 

Относительное расположение охраняемых команд в операторе выбора безразлично¹⁾ . Выполняется одна из охраняемых команд, охрана которой истинна. Имеющиеся в языках конкретные формы условных предложений и предложений выбора являются подпорками для реализации охраняемых команд.

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

Когда имеется выбор, мы вынуждены  переходить от сети данных к более сложной структуре: &- -графам. Некоторые вершины могут быть помечены как -вершины, это означает, что достаточно получить один из результатов, соответствующий входящим дугам, и инициировать лишь одно из исполнений, соответствующее выходящей дуге. Для структурированности &- -графа необходимо, чтобы он был сетью, удовлетворяющей следующему условию: имеется инъекция , сопоставляющая каждой -вершине ν, из которой выходит несколько дуг, -вершину (ν), из которой выходит лишь одна дуга, такую, что любой путь, проходящий через первую вершину, проходит и через вторую. Это неудобоваримое теоретическое условие всего лишь формулирует на точном языке, что -вершины должны группироваться в структуры следующего вида, показанного на рис.14.2 (количество вариантов может быть любым).

 

Рис. 2 Сеть охраняемых команд

 

О дисциплине циклического структурного программирования. Сейчас сосредоточимся на том варианте структурного программирования, который ориентируется на циклы и массивы.

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

Внимание!

Не используйте рекурсивный  вызов процедуры внутри цикла! Рекурсия и циклы должны быть "территориально разделены"!

Данное правило пригодно в подавляющем большинстве случаев. Оно является конкретизацией для структурного программирования известного политико-социологического наблюдения:

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

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

Тем не менее иногда бывают исключения. Рассмотрим, например, схему поиска вглубь на дереве.

 

int search (ELEMENT x)

ELEMENT y; int result;

if (good (x)) {

return id (x) }

else for (int i=0; i<100; i++)

{y=get_successor (x, i);

result=search (y);

if (result>0) return result;

}

return 0;

}

Пример 1 (html, txt)

Здесь рекурсии вместе с циклом задают обход дерева возможностей, и гибельного размножения рекурсивных вызовов не происходит. Причина этого исключения в том, что цикл в данной программе - всего лишь подпорка для рекурсии. В обычном программировании нет функционалов типа mapcar языка LISP, применяющих свой первый аргумент ко всем членам второго¹⁾ .

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

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

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

Нисходящее программирование - конкретизация нисходящего проектирования для нужд программирования. Оно обладает следующими преимуществами.

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

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

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

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

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

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

Недостаточный перенос опыта  и наработок из одного проекта  в другой.

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

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

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