На этом шаге мы рассмотрим теоретические положения, лежащие в основе структурного программирования.
Впервые основные идеи структурного программирования были высказаны Эдсгером Дейкстрой в 1965 году и позже опубликованы в его работе [1]. Основная задача, которую Э.Дейкстра решал, разрабатывая идеи структурного программирования, была задача доказательства правильности программы. Его внимание было сосредоточено на вопросе, "какими должны быть структуры программ, чтобы без чрезмерных усилий мы могли находить доказательство их правильности".
Это особенно важно при разработке больших программных систем. Опыт применения методов структурного программирования при разработке ряда сложных операционных систем показывает, что правильность логической структуры системы поддается доказательству, а сама программа допускает достаточно полное тестирование. В результате, в готовой программе встречаются только тривиальные ошибки кодирования, которые легко исправляются.
Очевидно, что уменьшение трудностей тестирования приводит к увеличению производительности труда программистов. Это следует из того, что на тестирование программы тратится от трети до половины времени ее разработки. Производительность труда программиста обычно измеряется числом отлаженных операторов, которые он может написать за день. Приближенные оценки показывают, что применение методов структурного программирования позволяет увеличить это число в 5-6 раз по сравнению с традиционными способами программирования.
Заметим, между прочим, что при структурном программировании становится излишним вычерчивание блок-схем. Блок-схема вполне структурированной программы настолько тривиально проста, что о программе можно сказать больше по тексту, чем по блок-схеме.
Итак, структурное программирование представляет собой некоторые принципы написания программ в соответствии со строгой дисциплиной и имеет целью облегчить процесс тестирования, повысить производительность труда программистов, улучшить ясность и читабельность программы, а также повысить ее эффективность.
В настоящее время вряд ли существует достаточно простое и краткое определение структурного программирования.
Например, Хоор[2] определяет структурное программирование как "систематическое использование абстракции для управления массой деталей и способ документирования, который помогает проектировать программу".
Структурное программирование можно толковать как "проектирование, написание и тестирование программы в соответствии с заранее определенной дисциплиной" [2].
Х.Миллс,П.Лингер и Б.Уитт в книге [3] использовали такое определение: структуризованная программа - это программа, составленная из фиксированного базового множества первичных программ.
Первичная программа - это простая программа, не имеющая простых подпрограмм, состоящих более чем из одного узла.
Простая программа - это программа, которая:
- имеет один вход и один выход,
- для каждого узла существует путь от входа до выхода, проходящий через этот узел.
Суть дела здесь заключается в том, что если программное обеспечение строится только из первичных и простых программ, то логика и сам ход процесса ее выполнения значительно проясняются благодаря структуризации. Использование таких (готовых) структур дисциплинирует разработчика программ, что в результате приводит к появлению более понятных программ, в которых, следовательно, имеется меньшее число ошибок.
Перейдем к рассмотрению теоретических оснований и методов структурного программирования.
Теоретической основой структурного программирования принято считать принципы, изложенные в классической работе Бома и Джакопини [4]. Эта работа в оригинале на итальянском языке была опубликована в 1965 г., а в английском переводе - в 1966 г.
В соответствии с так называемой "структурной" теоремой, сформулированной и доказанной в этой работе, всякая программа может быть построена с использованием только трех основных типов блоков [4].
- Функциональный блок. Ему в языках программирования соответствуют операторы ввода и вывода или любой оператор (группа операторов) присваивания. В виде функционального блока может
быть изображена любая последовательность операторов, выполняющихся один за другим, имеющая один вход и один выход.
Рис.1. Функциональный блок - Условная конструкция. Этот блок включает проверку некоторого логического условия (P), в зависимости от которого выполняется либо оператор S1, либо оператор S2: If P Then S1 Else S2;.
Рис.2. Условная конструкция - Блок обобщенного цикла. Этот блок обеспечивает многократное повторение выполнения оператора(ов) S, пока выполнено логическое условие P. Аналог блока обобщенного цикла на языке Pascal: While P Do S; .
Рис.3. Циклическая конструкция
Важной особенностью всех перечисленных блоков является то, что каждый из них имеет один вход и один выход.
Кроме того, блоки S, S1, S2, входящие в состав условной конструкции или блока обобщенного цикла, сами могут быть одним из рассмотренных типов блоков, поэтому возможны конструкции, содержащие "вложенные" блоки. Однако какова бы ни была степень и глубина "вложенности", важно, что любая конструкция в конечном итоге имеет один вход и один выход. Следовательно, любой сложный блок можно рассматривать как "черный ящик" с одним входом и одним выходом.
При конструировании программы с использованием рассмотренных типов блоков, эти блоки образуют линейную цепочку так, что выход одного блока подсоединяется к входу следующего. Таким образом, программа имеет линейную структуру, причем порядок следования блоков соответствует порядку, в котором они выполняются. Такая структура значительно облегчает чтение и понимание программы, а также упрощает доказательство ее правильности. Так как линейная цепочка блоков может быть сведена к одному блоку, то любая программа может в конечном итоге рассматриваться как единый функциональный блок с одним входом и одним выходом.
(1) Дал У., Дейкстра Э., Хоор К. Структурное программирование. - М.: Мир, 1975.
(2) Хьюз Дж., Мичтом Дж. Структурный подход к программированию. - М.: Мир, 1980.
(3) Richard C. Linger, Harlan D. Mills, Bertrand I. Witt. Structured Programming: Theory and Practice. Reading, Mass: Addison-Westley, 1979.
(4) Boehm C., Jacopini G. Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules // Communications of the ASM. 1966. 9. P.366-371.
Со следующего шага мы начнем перечислять основные принципы и методы структурного программирования.
