13Методы структурного программирования 14Краткое описание подхода
Структу́рное программи́рование — методология разработки программного обеспечения, в основе которой лежит представление программы в виде иерархической структуры блоков. Предложена в 70-х годах XX века Э. Дейкстрой, разработана и дополнена Н. Виртом.
В соответствии с данной методологией
Любая программа представляет собой структуру, построенную из трёх типов базовых конструкций:
последовательное исполнение — однократное выполнение операций в том порядке, в котором они записаны в тексте программы;
ветвление — однократное выполнение одной из двух или более операций, в зависимости от выполнения некоторого заданного условия;
цикл — многократное исполнение одной и той же операции до тех пор, пока выполняется некоторое заданное условие (условие продолжения цикла).
В программе базовые конструкции могут быть вложены друг в друга произвольным образом, но никаких других средств управления последовательностью выполнения операций не предусматривается.
Повторяющиеся фрагменты программы (либо не повторяющиеся, но представляющие собой логически целостные вычислительные блоки) могут оформляться в виде т. н. подпрограмм (процедур или функций). В этом случае в тексте основной программы, вместо помещённого в подпрограмму фрагмента, вставляется инструкция вызова подпрограммы. При выполнении такой инструкции выполняется вызванная подпрограмма, после чего исполнение программы продолжается с инструкции, следующей за командой вызова подпрограммы.
Разработка программы ведётся пошагово, методом «сверху вниз».
Сначала пишется текст основной программы, в котором, вместо каждого связного логического фрагмента текста, вставляется вызов подпрограммы, которая будет выполнять этот фрагмент. Вместо настоящих, работающих подпрограмм, в программу вставляются «заглушки», которые ничего не делают. Полученная программа проверяется и отлаживается. После того, как программист убедится, что подпрограммы вызываются в правильной последовательности (то есть общая структура программы верна), подпрограммы-заглушки последовательно заменяются на реально работающие, причём разработка каждой подпрограммы ведётся тем же методом, что и основной программы. Разработка заканчивается тогда, когда не останется ни одной «затычки», которая не была бы удалена. Такая последовательность гарантирует, что на каждом этапе разработки программист одновременно имеет дело с обозримым и понятным ему множеством фрагментов, и может быть уверен, что общая структура всех более высоких уровней программы верна. При сопровождении и внесении изменений в программу выясняется, в какие именно процедуры нужно внести изменения, и они вносятся, не затрагивая части программы, непосредственно не связанные с ними. Это позволяет гарантировать, что при внесении изменений и исправлении ошибок не выйдет из строя какая-то часть программы, находящаяся в данный момент вне зоны внимания программиста.
15Основная структура данных – сеть данных
Рассмотрим основную структуру данных, которая появляется при структурном программировании. Учет этой структуры позволяет преобразовать благие пожелания о согласованности информационных потоков и хода передач управления в достаточно строгую методику.
Сеть данных может быть формально описана как ациклический ориентированный граф, в котором все ко-пути (т.е. пути, взятые наоборот) конечны и вершинам которого сопоставлены значения.
Рассмотрим пример. Известному стандартному приему программирования в языках без кратных присваиваний - обмену двух значений через промежуточное.
z: = second;
second: = first;
first: = z;
соответствует следующая сеть данных:
-Обмен значений
Здесь first, second, z можно считать комментариями, а сами данные опущены, поскольку их конкретные значения не важны.
На этом примере видно, что порой для лучшего структурирования сети целесообразно вводить дополнительные вершины, соответствующие сохраняющимся значениям. Ребро, ведущее из одной такой вершины в другую, обозначается при помощи стрелочки, похожей на равенство. Видно так же, как материя воздействует на идею, заставляя вводить дополнительные операторы и дополнительные значения. В данном случае переменная z и включающие ее операторы являются подпорками, и, если их исключить, сеть данных становится проще. Но в общераспространенных языках программирования нет кратных присваиваний типа
first,second: =second,first;
Даже если бы они были, представьте себе, как неудобно станет читать длинное кратное присваивание и понимать, какое же выражение какой переменной присваивается!
В случае программы вычисления факториала1) сеть потенциально бесконечна вниз, поскольку аргументом может быть любое число, но по структуре еще проще:
– вычисление факториала
Перекрестных зависимостей между параметрами нет, следовательно, возможны две известные реализации факториала: циклическая и рекурсивная. Покажем их на разных языках, ибо все равно, на каком традиционном языке их писать.
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)); }
16Потоковая обработка
Схема построения циклической программы называется потоковой обработкой. Значения на следующей итерации цикла зависят от значений на предыдущей.
Для чисел Фибоначчи (та же схема (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 достаточно велико, каждое из предыдущих значений функции Фибоначчи будет вычисляться много раз, причем без всякого толку: результат всегда будет один и тот же! Зато все подпорки убраны...
17Алгоритм золотой горы
В следующем примере неэффективность рекурсии по сравнению с хорошо организованным циклом еще более очевидная. Пусть надо найти путь, на котором можно собрать максимальное количество золота, через сеть значений, подобную показанной на рис 4.
-Золотая гора
При циклической организации вычислений нам придется посчитать значение в каждой точке горы всего один раз (найти добычу на оптимальном пути в эту точку). Здесь используется то свойство оптимальных путей, которое делает возможным так называемые методы волны или динамического программирования: каждый начальный отрезок локально оптимального пути локально оптимален. Это свойство является призраком, стоящим за эффективной циклической реализацией алгоритма, а многочисленные пути, соответственно, призрачными значениями, которые не нужно вычислять. В рекурсивной реализации мы не учитываем данного призрака, и он беспощадно мстит за вопиющее незнание теории.
18Алгоритм Евклида
Теперь рассмотрим случай, когда рекурсивная реализация намного изящнее циклической, легче обобщается и не хуже по эффективности2)
-Алгоритм Евклида
В данном случае путь для получения результата не разветвляется, и нам остается лишь двигаться по нему в правильном направлении (от цели к исходным данным) и достаточно большими шагами.
function Euklides (n,m: integer) integer; {
предполагаем m<=n}
begin
if n=m then resut: =n
else result: =Euklides (n mod m, m);
end;
Если пытаться вычислить наибольший общий делитель методом движения от данных к цели, то нам придется построить громадный массив значений НОД, лишь ничтожная часть значений в котором будет нужна для построения результата. Затраты на вычисление каждого отдельного элемента в данном случае малы, а при обратном направлении движения повторный счет не возникает.
Алгоритм Евклида в простейшем случае моделирует ту ситуацию, которая появляется в задачах обработки рекурсивных структур, например списков. То, что в отдельных случаях возникает повторный счет, - небольшое зло, когда эти случаи редки и нерегулярны. Повторный счет возникает и в циклических программах, поскольку найти в большом массиве совпадающие элементы порою труднее, чем заново посчитать нужные нам значения. Именно поэтому рекурсия оказалась столь эффективным методом работы со списками и позволила построить адекватный первопорядковый фундамент для современного функционального программирования.
Рассмотрим два крайних случая движения по сети. Когда сеть представлена в виде структуры данных, естественно возникает метод ленивого движения по сети, когда после вычисления значений в очередной точке выбирается одна из точек, для которой все предыдущие значения уже вычислены, и вычисляются значения в данной точке. Как видно, в частности на примере золотой горы, этот метод недетерминирован и в значительной степени может быть распараллелен. Но в конкретном алгоритме нам придется выбрать конкретный способ ленивого движения, и он может быть крайне неудачен: например, он будет провоцировать длительное движение в тупик, когда у нас есть короткий путь к цели. Даже в теоретических исследованиях приходится накладывать условия на метод ленивого движения, чтобы гарантировать достижение результата Другой крайний случай движения по сети, когда сеть делится на одинаковые слои. Например, в сети (4).
-Полностью заменяемый массив
Можно представить слой статическим массивом и вроде бы полностью забыть о самой сети. Забытый призрак мстит за себя, в частности, при необходимости распараллеливания вычислений, и предыдущий случай отнюдь не эквивалентен следующему.
-Постепенно заменяемый массив
Конечно же большая сеть данных становится необозримой. Справиться с нею можно, лишь разбив сеть на подсети. Таким образом, блоки программы соответствуют относительно автономным подсетям.
Еще Э. Дейкстра в книге [11] предложил в каждом блоке описывать импортированные и экспортируемые им глобальные значения. Но такая "писанина" раздражала хакеров и в итоге так и не вошла в общепризнанные системы программирования. Сейчас индустриальные технологии требуют таких описаний, но из-за отсутствия поддержки на уровне синтаксического анализа все это остается благими пожеланиями, так что, если хотите, чтобы Ваша программа была понятна хотя бы Вам, описывайте все перекрестные информационные связи!
Резюмируя вышеизложенное, можно сделать следующие выводы.
Сеть данных сама по себе в программу не переходит, в программу переходят лишь некоторые свойства сети в качестве призраков и некоторые куски сети в качестве реальных значений.
Программа определяется не только сетью данных, но и конкретной дисциплиной движения по этой сети.
В случае, если очередные слои сети, появляющиеся при движении согласно заданной дисциплине, примерно одинаковы и состоят из многих взаимосвязанных значений, у нас возникает циклическая программа.
В случае, если вычисление можно свести к вычислениям для независимых элементов сети, чаще всего удобней рекурсия.
Самый общий способ движения по сети - ленивое движение, когда мы имеем право вычислить следующий объект сети, если вычислены все его предшественники.
Структурное программирование нейтрально по отношению к тому, каким именно способом будет исполняться полученная программа: последовательно, детерминировано, недетерминировано, совместно, параллельно либо даже на распределенной системе, - поскольку сеть лишь частично предписывает порядок действий.
19Метод нисходящего программирования
Нисходящее программирование - конкретизация нисходящего проектирования для нужд программирования. Оно обладает следующими преимуществами.
Нисходящее программирование породило хорошо согласованное с ним нисходящее построение структур данных, а нисходящее построение структур данных является простейшим частным случаем глубокой идеальной концепции - абстракции данных. Согласно парадоксу изобретателя, даже простейшие частные случаи высокоуровневых концепций при удачном применении улучшают все характеристики умственных конструкций (в частности, программ).
При таком проектировании на каждом уровне можно ограничиваться одной моделью вычислений, в частности операционной, на которую ориентировано структурное программирование.
Возможно раннее программирование, когда прототип программы, работающий хотя бы в условиях грубой эмуляции будущих решений низкого уровня, позволяет продемонстрировать, как будет работать полная программа, и улучшить ее пользовательские характеристики.
Ни один конкретный способ анализа либо синтеза не является универсальным. Нисходящее программирование, конечно же, тоже таковым не является. Причины тому, в частности, следующие2) .
Невозможность при нисходящем структурном программировании увидеть тождественность процедур, работающих на разных ветвях декомпозиции, а тем более унифицировать несколько формально различных процедур на разных ветвях в одну общую.
Недостаточный учет особенностей, которые могут возникнуть после конкретной реализации запланированных блоков программы, что довольно часто вызывает необходимость полной перепланировки системы после реализации ее блоков, а вслед за такой перепланировкой реализованные для других спецификаций блоки часто оказываются отнюдь не лучшими из возможных.
Недостаточный перенос опыта и наработок из одного проекта в другой.
В нынешних методиках нисходящего проектирования ко всему перечисленному добавляется еще и навязывание последовательного стиля мышления, что мешает воспользоваться преимуществами нетрадиционных машин.
Это указывает на необходимость средств, позволяющих поднимать уровень понятий. Поэтому в разработке структурных программ применяется также подход, получивший название восходящего программирования.
К примеру, когда строят библиотеку, занимаются обобщением задачи. Части, выделяемые в виде библиотечных средств, выбираются таким образом, чтобы они были применимы в различных контекстах.
20Методология SADT
Методология SADT разработана Дугласом Россом. На ее основе разработана, в частности, известная методология IDEF0 (Icam DEFinition), которая является основной частью программы ICAM (Интеграция компьютерных и промышленных технологий), проводимой по инициативе ВВС США.
Методология SADT представляет собой совокупность методов, правил и процедур, предназначенных для построения функциональной модели объекта какой-либо предметной области. Функциональная модель SADT отображает функциональную структуру объекта, т.е. производимые им действия и связи между этими действиями. Основные элементы этой методологии основываются на следующих концепциях:
графическое представление блочного моделирования. Графика блоков и дуг SADT-диаграммы отображает функцию в виде блока, а интерфейсы входа/выхода представляются дугами, соответственно входящими в блок и выходящими из него. Взаимодействие блоков друг с другом описываются посредством интерфейсных дуг, выражающих "ограничения", которые в свою очередь определяют, когда и каким образом функции выполняются и управляются;
строгость и точность. Выполнение правил SADT требует достаточной строгости и точности, не накладывая в то же время чрезмерных ограничений на действия аналитика. Правила SADT включают:
ограничение количества блоков на каждом уровне декомпозиции (правило 3-6 блоков);
связность диаграмм (номера блоков);
уникальность меток и наименований (отсутствие повторяющихся имен);
синтаксические правила для графики (блоков и дуг);
разделение входов и управлений (правило определения роли данных).
отделение организации от функции, т.е. исключение влияния организационной структуры на функциональную модель.
Методология SADT может использоваться для моделирования широкого круга систем и определения требований и функций, а затем для разработки системы, которая удовлетворяет этим требованиям и реализует эти функции. Для уже существующих систем SADT может быть использована для анализа функций, выполняемых системой, а также для указания механизмов, посредством которых они осуществляются Состав функциональной модели Результатом применения методологии SADT является модель, которая состоит из диаграмм, фрагментов текстов и глоссария, имеющих ссылки друг на друга. Диаграммы - главные компоненты модели, все функции ИС и интерфейсы на них представлены как блоки и дуги. Место соединения дуги с блоком определяет тип интерфейса. Управляющая информация входит в блок сверху, в то время как информация, которая подвергается обработке, показана с левой стороны блока, а результаты выхода показаны с правой стороны. Механизм (человек или автоматизированная система), который осуществляет операцию, представляется дугой, входящей в блок снизу (см. рисунок).
Одной из наиболее важных особенностей методологии SADT является постепенное введение все больших уровней детализации по мере создания диаграмм, отображающих модель.
- Концепт методологии SADT
На рисунке, где приведены четыре диаграммы и их взаимосвязи, показана структура SADT-модели. Каждый компонент модели может быть декомпозирован на другой диаграмме. Каждая диаграмма иллюстрирует "внутреннее строение" блока на родительской диаграмме.
Иерархия диаграмм. Построение SADT-модели начинается с представления всей системы в виде простейшей компоненты - одного блока и дуг, изображающих интерфейсы с функциями вне системы. Поскольку единственный блок представляет всю систему как единое целое, имя, указанное в блоке, является общим. Это верно и для интерфейсных дуг - они также представляют полный набор внешних интерфейсов системы в целом.
Затем блок, который представляет систему в качестве единого модуля, детализируется на другой диаграмме с помощью нескольких блоков, соединенных интерфейсными дугами. Эти блоки представляют основные подфункции исходной функции. Данная декомпозиция выявляет полный набор подфункций, каждая из которых представлена как блок, границы которого определены интерфейсными дугами. Каждая из этих подфункций может быть декомпозирована подобным образом для более детального представления.
Во всех случаях каждая подфункция может содержать только те элементы, которые входят в исходную функцию. Кроме того, модель не может опустить какие-либо элементы, т.е., как уже отмечалось, родительский блок и его интерфейсы обеспечивают контекст. К нему нельзя ничего добавить, и из него не может быть ничего удалено.
Модель SADT представляет собой серию диаграмм с сопроводительной документацией, разбивающих сложный объект на составные части, которые представлены в виде блоков. Детали каждого из основных блоков показаны в виде блоков на других диаграммах. Каждая детальная диаграмма является декомпозицией блока из более общей диаграммы. На каждом шаге декомпозиции более общая диаграмма называется родительской для более детальной диаграммы.
Дуги, входящие в блок и выходящие из него на диаграмме верхнего уровня, являются точно теми же самыми, что и дуги, входящие в диаграмму нижнего уровня и выходящие из нее, потому что блок и диаграмма представляют одну и ту же часть системы.
|
