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

     int fib(int n)

     {int fib1,fib2;

     fib1=1; fib2=1;

     if (n>2){

     for (int i=2;i<n;i++){

     int j; j=fib1+fib2; fib1=fib2; fib2=j;

     }

     };

     return(fib2);

     }

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

     int fib(int n)

     { if (n<3) return(1);

     else return(fib(n-1)+fib(n-2));

     }

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

       

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

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

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

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

     begin

     if n=m then resut:=n

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

     end;

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

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

     

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

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

1. Сеть данных сама по себе в программу не переходит, в программу переходят лишь некоторые свойства сети в качестве призраков и некоторые куски сети в качестве реальных значений.
2. Программа определяется не только сетью данных, но и конкретной дисциплиной движения по этой сети.
3. В случае, если очередные слои сети, появляющиеся при движении согласно заданной дисциплине, примерно одинаковы и состоят из многих взаимосвязанных значений, у нас возникает циклическая программа.
4. В случае, если вычисление можно свести к вычислениям для независимых элементов сети, чаще всего удобней рекурсия.
5. Самый общий способ движения по сети − ленивое движение, когда мы имеем право вычислить следующий объект сети, если вычислены все его предшественники.
6. Структурное программирование нейтрально по отношению к тому, каким именно способом будет исполняться полученная программа: последовательно, детерминированно, недетерминированно, совместно, параллельно либо даже на распределенной системе, − поскольку сеть лишь частично предписывает порядок действий.
7. Конкретный выбор порядка действий в последовательной детерминированной программе является подпоркой, о которой постоянно забывают. Поэтому он чаще всего вредит при перестройке программы.

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

Выбор

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

     Пример: Пусть в некоторый момент исполнения программы. Вам необходимо временно выбросить больший из двух хранимых в основной памяти обрабатываемых блоков на диск. Поскольку разница в длине менее (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.

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

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

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

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

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

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

     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;

     }

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