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

1. О сущности структурного программирования

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

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

Программное обеспечение и базы данных все более и более стали напоминать мозг человека. Действительно, здесь есть полная аналогия. В одном “полушарии” компьютера хранятся листья образов (программы и данные), а в другом - сами образы, которые представляют собой многоуровневые цепочки произвольной длины, имеющие многочисленные зацикливания. При прохождении дерева образа в строго определенном порядке возникает “пространственный” объект-оригинал образа. Этот процесс может быть многоуровневым, многослойным. Составляя цепочки из кирпичиков, каждый из которых будет деревом образов, мы получим более сложное дерево, получим более сложный образ и т.д. Эта двойственная совокупность цепочек и кирпичиков будет составлять первый уровень иерархии системы, первый слой ее оболочек. Если теперь в качестве кирпичиков использовать образную часть оболочки и начать формировать из этого набора различные образы, то мы получим следующий двойственный слой системы и т.д. В принципе, именно по такому образу и подобию функционируют все иерархические системы. Поэтому можно сказать, что программирование является процессом спектрального разложения образа объекта на две составляющие, из которых первая связывает в строго определенном порядке все элементарные кирпичики образа, а сами кирпичики размещает во втором “полушарии”. Можно сказать, что одно полушарие компьютера отвечает за образное мышление, другое - за абстрактное, так как содержит только первичные данные. Это полушарие составляет самый низкий уровень “интеллекта” компьютера. Полушарие, отвечающее за образное мышление, естественно, составляет более высокий уровень интеллекта компьютера.

Во-первых, это увязывание всех элементов в целостную единую многоуровневую систему.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Внимание!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Однако представление о структурном программировании, как о программировании без использования оператора GOTO, является ошибочным. Например, Хоор определяет структурное программирование как "систематическое использование абстракции для управления массой деталей и способ документирования, который помогает проектировать программу".

Структурное программирование можно толковать как "проектирование, написание и тестирование программы в соответствии с заранее определенной дисциплиной".

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

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

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

Наконец, структурное программирование призвано улучшить эффективность программ.

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

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

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

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

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

2. Условная конструкция. Этот блок включает проверку некоторого логического условия (P), в зависимости от которого выполняется либо один (S₁), либо другой (S₂) операторы:

На языке TP:

if <условие> then <оператор1> else <оператор2>;

3. Блок обобщенного цикла. Этот блок обеспечивает многократное повторение выполнения оператора S пока выполнено логическое условие P:

На языке TP циклы реализуются 2 способами.

Цикл с параметром:

for <параметр> := <нач.значение> to <кон.значение>;

. . begin

<оператор1>

. . <оператор2>

. . ...

. end;

Цикл с предусловием:

. while <условие>

. .begin

<оператор1>

. . <оператор2>

. . ...

. end;

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

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

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

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

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

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

Основные принципы структурного программирования:

Принцип абстрактности.

Принцип формальности.

Принцип разделяй и властвуй.

Принцип модульности.

Принцип открытости