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

Общая характеристика структурного программирования

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

Мы рассматриваем структурное программирование как равноправный член сообщества альтернативных ему друзей-соперников¹⁾ .

Начнем с того, что обратимся к истории.

В теории схем программ было замечено, что некоторые случаи блок-схем легче поддаются анализу. Поэтому естественно было выделить такой класс блок-схем, что и сделали итальянские ученые С. Бем и К. Джакопини в 1966 г. Они доказали, что любую блок-схему можно привести к структурированному виду, использовав несколько дополнительных булевых переменных. Э. Дейкстра подчеркнул, что программы в таком виде, как правило, являются легче понимаемыми и модифицируемыми, так как каждый блок имеет один вход и один выход.

В качестве методики структурного программирования Э. Дейкстра предложил пользоваться лишь конструкциями цикла и условного оператора, изгоняя go to как концептуально противоречащее этому стилю²⁾ .

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

Средства структурного программирования в первую очередь включаются во все языки программирования традиционного типа и во многие нетрадиционные языки. Они занимают основное место в учебных курсах программирования и в теоретических работах (например, ,[4] ,[9]).

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

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

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

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

Для структурного стиля программирования требуется следующее. Задача разбивается на подзадачи, и таким образом выстраивается дерево вложенности подзадач. Информационное пространство структурируется в точном соответствии с деревом вложенности: для каждой подзадачи оно состоит из ее локальных объектов, определяемых вместе с подзадачей и для нее, и так называемых глобальных объектов, определяемых как информационное пространство непосредственно объемлющей подзадачи. Таким образом, информационное пространство всей задачи (подзадачи самого верхнего уровня) расширяется по мере перехода к подзадачам за счет их локальных объектов. Для различных дочерних подзадач одной подзадачи оно имеет общую часть — информационное пространство родительской подзадачи⁴⁾ .

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

К структурным операторам добавляются либо циклы, либо рекурсии.

Внимание!

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

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

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

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

Первым обратил внимание на необходимость введения призраков для логического и концептуального анализа программ Г.С. Цейтин в 1971 г. В Америке это «независимо» открыли заново в 1979 г., хотя упомянутая статья Цейтина была опубликована на английском языке в общедоступном издании. Даже название сущностям было дано то же самое… Этому важнейшему и традиционно игнорируемому понятию посвящена отдельная лекция в курсе «Основания программирования» .

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

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

Для структурного программирования весьма важно требование:

Все структуры подчиняются структуре информационного пространства.

Это общее требование конкретизируется в следующие.

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

Подзадачи могут обмениваться данными только посредством обращения к объектам из общей части их информационных пространств (в современных языках чаще всего к глобальным).

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

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

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

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

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

Сети данных.

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

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

Рассмотрим пример. Известному стандартному приему программирования в языках без кратных присваиваний — обмену двух значений через промежуточное.

z: = second;

second: = first;

first: = z;

соответствует следующая сеть данных:

Рис. 1 Обмен значений

Здесь first, second, z можно считать комментариями, а сами данные опущены, поскольку их конкретные значения не важны.

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

first, second: =second, first;

Даже если бы они были, представьте себе, как неудобно станет читать длинное кратное присваивание и понимать, какое же выражение какой переменной присваивается!

В случае программы вычисления факториала¹⁾ сеть потенциально бесконечна вниз, поскольку аргументом может быть любое число, но по структуре еще проще:

Рис. 2

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

function fact (n: integer): integer;

var j, res: integer;

begin

res: =1;

for j: =1 to n do res: =res*j;

result: =res;

end;

int fact (int n)

{if (n==0) return (1);

else return (n*fact (n-1)); }

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

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

int fib (int n)

{int fib1, fib2;

fib1=1; fib2=1;

if (n>2) {

for (int i=2; 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.

Рис. 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;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Внимание!

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

Выбор.

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

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

if

length (A) — lengtn (B) >65 536 {

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

length (A) — lengtn (B) <65 536 {

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, применяющих свой первый аргумент ко всем членам второго¹⁾ .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реальный проект³⁾ — это смесь нисходящего и восходящего подходов:

сначала сверху вниз для выяснения крупных строительных блоков;

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

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

Как в нисходящем, так и в восходящем подходе важно обеспечить согласование потоков управления и потоков данных. Основным инструментом здесь может быть взгляд на программу со стороны сетей данных. Поскольку цикл появляется как реализация послойного движения по сети, а массив — как представление слоя сети, то видно, что на самом деле основной информационной структурой цикла является слой сети. Например, в цикле, реализующем числа Фибоначчи, — это структура из fib1 и fib2. Структура, представляющая очередной слой сети, называется реальным параметром (в отличие от формального параметра, диктуемого языком программирования и часто являющегося подпоркой) цикла. Реальный параметр мы будем называть просто параметром.

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

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

Методика циклического и рекурсивного структурного программирования с использованием инвариантов и недетерминированности (но без явного упоминания сетей данных) прекрасно изложена в учебных пособиях Алагича, Арбиба и Гриса,. Настольной книгой программиста должна служить также книга Кормена и др. (учебник MIT), в которой можно найти множество хороших примеров того, как находить правильные программные решения и со вкусом использовать подпорки.

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

И, наконец, необходимо заметить следующее.

Внимание!

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

Переходы и выдаваемые значения. В общее употребление структурное программирование вошло после популяризировавшей его работы Э. Дейкстры, в которой, к сожалению, не было даже намека на его ограничения. Ограничения структурного программирования вытекают как из самой его сути, так и из теоремы Бема-Джакопини. Применение структурных переходов, которые ввел в практику и теорию Д. Кнут (откопавший оригинальную работу Бема-Джакопини и четко выделивший ограничения дейкстровского структурного подхода¹⁾), избавляет от многих недостатков, присущих методике Дейкстры. Структурные переходы — переходы лишь вперед и на более высокий уровень структурной иерархии управления, ни в каком случае не выводящие нас за пределы данного модуля.

/* Примеры структурных goto. */

…

do {y = f (x, y) };

if (y>0) break;

x=g (x, y);

}while (x>0);

…

{…

{

if (All_Done) goto Success;

}

…

Success: Hurra; }

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

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

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

Есть одно ограничение структурных переходов, известное с 80-х гг. ХХ века (cм.), по крайней мере один раз достоверно повредившее создателям отечественной серии машин Эльбрус, в которых на аппаратном уровне поддерживалось структурное и функциональное программирование. Структурные переходы (в том числе и завершители) некорректны, когда они выводят нас из функции-параметра вызова другой функции. Ирония в том, что абсолютно четкая и полная реализация завершителей еще до осознания необходимости данного средства и тем более задолго до осознания пределов его применимости была проделана именно там, где они в общем случае некорректны (в языке LISP). В нем, как мы видели, процедуры являются полноправными значениями, могут быть параметрами и результатами других процедур. Самый очевидный случай некорректности (правда, вылавливаемый системой обнаружения динамических ошибок Common Lisp), когда мы внутри созданной процедуры завершаем блок, существовавший в момент создания процедуры, но переставший существовать в тот момент, когда ее вызвали. Наверняка многие наталкивались на непонятное поведение программ с завершителями, но в соответствии с общераспространенным «позитивным» мышлением не обращали внимания на данный феномен.

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

if x=0 then sin (y) else tan (y)

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

Эту концепцию попытались перенести на язык традиционного типа в языке Алгол 68. На первый взгляд получилось очень красиво. Например, оператор

if x>0 then a1 else a2 fi [if y>0 then j else i fi]: =

if z>0 then sin (u) else tan (u) fi

намного компактней и красивей последовательности условных операторов, которую придется написать в Pascal или C++. Но концепция вырабатываемого значения оказалась в концептуальном противоречии и с оператором присваивания, и с совместными вычислениями. Например, согласно семантике Алгола 68, следующая запись

(x: =3, у: =x+y, z: =x+y)

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

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

Методология функционального моделирования SADT

Методология SADT разработана Дугласом Россом. На ее основе разработана, в частности, известная методология IDEF0 (Icam DEFinition), которая является основной частью программы ICAM (Интеграция компьютерных и промышленных технологий), проводимой по инициативе ВВС США.

Методология SADT представляет собой совокупность методов, правил и процедур, предназначенных для построения функциональной модели объекта какой-либо предметной области. Функциональная модель SADT отображает функциональную структуру объекта, т. е. производимые им действия и связи между этими действиями. Основные элементы этой методологии основываются на следующих концепциях:

графическое представление блочного моделирования. Графика блоков и дуг SADT-диаграммы отображает функцию в виде блока, а интерфейсы входа/выхода представляются дугами, соответственно входящими в блок и выходящими из него. Взаимодействие блоков друг с другом описываются посредством интерфейсных дуг, выражающих «ограничения», которые в свою очередь определяют, когда и каким образом функции выполняются и управляются;

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

ограничение количества блоков на каждом уровне декомпозиции (правило 3−6 блоков);

связность диаграмм (номера блоков);

уникальность меток и наименований (отсутствие повторяющихся имен);

синтаксические правила для графики (блоков и дуг);

разделение входов и управлений (правило определения роли данных).

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

Методология SADT может использоваться для моделирования широкого круга систем и определения требований и функций, а затем для разработки системы, которая удовлетворяет этим требованиям и реализует эти функции. Для уже существующих систем SADT может быть использована для анализа функций, выполняемых системой, а также для указания механизмов, посредством которых они осуществляются Состав функциональной модели Результатом применения методологии SADT является модель, которая состоит из диаграмм, фрагментов текстов и глоссария, имеющих ссылки друг на друга. Диаграммы — главные компоненты модели, все функции ИС и интерфейсы на них представлены как блоки и дуги. Место соединения дуги с блоком определяет тип интерфейса. Управляющая информация входит в блок сверху, в то время как информация, которая подвергается обработке, показана с левой стороны блока, а результаты выхода показаны с правой стороны. Механизм (человек или автоматизированная система), который осуществляет операцию, представляется дугой, входящей в блок снизу (см. рисунок).

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

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

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

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

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

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

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

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

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

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

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

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

Для того, чтобы указать положение любой диаграммы или блока в иерархии, используются номера диаграмм. Например, А21 является диаграммой, которая детализирует блок 1 на диаграмме А2. Аналогично, А2 детализирует блок 2 на диаграмме А0, которая является самой верхней диаграммой модели. На следующем рисунке показано типичное дерево диаграмм.

Типы связей между функциями. Одним из важных моментов при проектировании ИС с помощью методологии SADT является точная согласованность типов связей между функциями. Различают по крайней мере семь типов связывания:

Ниже каждый тип связи кратко определен и проиллюстрирован с помощью типичного примера из SADT.

(0) Тип случайной связности: наименее желательный.

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

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

(2) Тип временной связности. Связанные по времени элементы возникают вследствие того, что они представляют функции, связанные во времени, когда данные используются одновременно или функции включаются параллельно, а не последовательно.

(3) Тип процедурной связности. Процедурно-связанные элементы появляются сгруппированными вместе вследствие того, что они выполняются в течение одной и той же части цикла или процесса. Пример процедурно-связанной диаграммы приведен на cледующем рисунке.

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

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

(6) Тип функциональной связности. Диаграмма отражает полную функциональную связность, при наличии полной зависимости одной функции от другой. Диаграмма, которая является чисто функциональной, не содержит чужеродных элементов, относящихся к последовательному или более слабому типу связности. Одним из способов определения функционально-связанных диаграмм является рассмотрение двух блоков, связанных через управляющие дуги, как показано на рисунке «Функциональная связность» .

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

C = g (B) = g (f (A))

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

Моделирование потоков данных (процессов)

Внешние сущности

Системы и подсистемы

Процессы

Накопители данных

Потоки данных

Построение иерархии диаграмм потоков данных

В основе данной методологии (методологии Gane/Sarson) лежит построение модели анализируемой ИС — проектируемой или реально существующей. В соответствии с методологией модель системы определяется как иерархия диаграмм потоков данных (ДПД или DFD), описывающих асинхронный процесс преобразования информации от ее ввода в систему до выдачи пользователю. Диаграммы верхних уровней иерархии (контекстные диаграммы) определяют основные процессы или подсистемы ИС с внешними входами и выходами. Они детализируются при помощи диаграмм нижнего уровня. Такая декомпозиция продолжается, создавая многоуровневую иерархию диаграмм, до тех пор, пока не будет достигнут такой уровень декомпозиции, на котором процесс становятся элементарными и детализировать их далее невозможно.

Источники информации (внешние сущности) порождают информационные потоки (потоки данных), переносящие информацию к подсистемам или процессам. Те в свою очередь преобразуют информацию и порождают новые потоки, которые переносят информацию к другим процессам или подсистемам, накопителям данных или внешним сущностям — потребителям информации. Таким образом, основными компонентами диаграмм потоков данных являются:

внешние сущности;

системы/подсистемы;

процессы;

накопители данных;

потоки данных.

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