Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

3.3. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ

125

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

структурированному виду, использовав несколько дополнительных булевых

переменных. Э. Дейкстра подчеркнул, что программы в таком виде, как пра-

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

блок имеет один вход и один выход.Эти наблюдения послужили основой сти-

ля программирования, который, начиная с 70-х гг. XX века, занимает прак-

тически монопольное положение в преподавании и исключительно широко

используется в практике программирования. Этот стиль называется струк-

турным программированием.

В качестве методики структурного программирования Э. Дейкстра пред-

ложил пользоваться лишь конструкциями цикла и условного оператора, из-

гоняя

go to

, как концептуально противоречащее этому стилю.

Поскольку на практике и в основной части данного пособия речь идет

именно о структурном программировании, здесь мы остановимся на данном

стиле лишь бегло, поставив его на то равноправное место, которое он в прин-

ципе занимает среди альтернативных ему друзей-соперников

Структурное программирование основано главным образом на теорети-

ческом аппарате теории рекурсивных функций. Программа рассматривается

как частично-рекурсивный оператор над библиотечными подпрограммами и

исходными операциями. Структурное программирование базируется также

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

ра программы соответствует структуре простейшего математического рас-

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

Средства структурного программирования в первую очередь включаются

во все языки программирования традиционного типа и во многие нетради-

ционные языки. Они занимают основное место в учебных курсах програм-

мирования ([3, 27, 37, 51]).

При структурном программировании присваивания и локальные действия

становятся органичной частью программы. Достаточно лишь внимательно

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

для одной конкретной цели, и не допускать «экономии», при которой ненуж-

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

дует, что оно будет занимать столь же исключительное положение и в будущем и что оно

окажется лучшим средством для решения Ваших конкретных задач.

На самом деле традиционным вычислительным программам соответствует не классиче-

ская, а интуиционистская логика, но структура доказательств и большинство правил вывода

в них совпадают.

126

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

ная в данном месте переменная временно используется совсем под другое

значение. Такая «экономия» запутывает структуру информационных зависи-

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

турой программы.

Структурное программирование естественно возникает в многих классах

задач, прежде всего в таких, где задача естественно расщепляется на подза-

дачи, а информация — на достаточно независимые структуры данных. Для

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

чае, если соблюдается основной его инвариант:

Действия и условия локальны

Необходимой чертой хорошей реализации структурного стиля програм-

мирования является соблюдение согласованности, а в идеале и единства, сле-

дующих компонент программы:

1) Структура информационного пространства. Содержательно любую за-

дачу можно описать как переработку объектов, полный набор которых на-

зывается информационным пространством задачи.

Для структурного стиля программирования требуется следующее. Задача

разбивается на подзадачи, и таким образом выстраивается дерево вложен-

ности подзадач. Информационное пространство структурируется в точ-

ном соответствии с деревом вложенности: для каждой подзадачи оно со-

стоит из ее локальных объектов, определяемых вместе с подзадачей и для

нее, и так называемых глобальных объектов, определяемых как информа-

ционное пространство непосредственно объемлющей подзадачи. Таким

образом, информационное пространство всей задачи (подзадачи самого

верхнего уровня) расширяется по мере перехода к подзадачам за счет их

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

оно имеет общую часть — информационное пространство родительской

подзадачи;

2) Структуры управления. Стиль структурного программирования предпо-

лагает использование строго ограниченного набора управляющих конструк-

ций: последовательность операторов, условные, выбирающие и цикличе-

ские конструкции,все вычислительные ветви которых (для циклов —ите-

В этой системе требований без труда распознается так называемая блочная структура

языков программирования, появившаяся еще в

Algol 60

и ставшая в настоящее время факти-

ческим стандартом.

3.3. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ

127

рации) сходятся в одной точке программы, а также процедуры, вычисле-

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

3) Потоки передачи данных.Разбивая задачу на подзадачи, программист пре-

дусматривает их взаимодействие по данным: одни подзадачи передают

другим данные для переработки;

4) Структуры данных. Данные объединяются в логически связанные фраг-

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

струкций, вводимых для ее решения;

5) “Призраки”. Часто даже сама программа не может быть объяснена через

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

ее связей с внешним миром.Понимание программы возможно лишь после

сопоставления ‘реальных’ внутрипрограммных объектов с ‘идеальными’

внепрограммными. Эти идеальные внепрограммные объекты (призраки)

часто не просто не нужны, но даже вредны для исполнения программы.

Первым обратил внимание на неоходимость введения призраков для логи-

ческого и концептуального анализа программ Г. С. Цейтин в 1971 г. Впо-

следствии в Америке это ‘независимо’ переоткрыли в 1979 г., хотя упомя-

нутая статья Цейтина была опубликована на английском языке в общедо-

ступном издании. Даже название сущностям было дано то же самое...

Для структурного программирования весьма важным является следующее

требование:

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

пространства.

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

1. Необходимо, чтобы структура управления программы была согласова-

на со структурой ее информационного пространства. Каждой структу-

ре управления соответствуют согласующиеся с ней структуры данных

И, кстати, программистам стоит почаще вспоминать, что с точки зрения пользователя ли-

бо заказчика их внутрипрограмные объекты как раз являются такими же ‘призраками’, ко-

торые не имеют никакого отношения к реальной действительности. Так что при переходе от

уровня рассмотрения программы самой по себе к уровню программы как части архитекту-

ры реальной человеко-машинной системы идеальные и реальные объекты порою меняются

местами.

128

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

и часть информационного пространства. Это условие позволяет чело-

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

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

к объектам из общей части их информационных пространств

3. Информационные потоки должны протекать не ортогонально, а соглас-

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

го блока программы, что он имеет на входе и что он дает на выходе. Та-

ким образом, свойства каждого логически завершенного фрагмента

программы должны ясно осознаваться и в идеале четко описываться

в самом тексте программы и в сопровождающей ее документации.

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

а также других, вспомогательных переменных при структурном про-

граммировании строго подчиняется разбиению задачи на подзадачи.

5. Все признаки действуют на своем структурном месте и соответству-

ют идеальным сущностям, которые, согласно парадоксу изобретателя,

должны вводиться для эффективного решения задачи.

Структурное программирование лучше всего описано теоретически, но

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

с точки зрения программиста, другие — с точки зрения теоретика. Так что

даже здесь единой системы взглядов еще нет, хотя, видимо, все основания

для ее формирования уже имеются.

Необходимо помнить, что структурное программирование, как правило,

плохо подходит для описания систем глобальных действий. Это выявилось

уже в теории. А именно, в теореме о структурировании схем программ, до-

казанной Бемом и Джакопини, вводились дополнительные локальные булев-

ские переменные, в совокупности которых, по сути дела, запоминалось со-

стояние программы. Без введения дополнительных переменных невозможно

структурировать даже следующий цикл с двумя выходами (см. рис. 3.4).

В общее употребление структурное программирование вошло после по-

пуляризировавшей его работы Э. Дейкстры, в которой, к сожалению, на ука-

занные нами ограничения не было даже намека, так же,как и на ограничения,

вытекающие из самой теоремы Бема-Джакопини. Применение структурных

Как видим, программа должна составляться после того, как программист хорошенько

подумал, а не до того.

3.3. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ

129

◦

Рис. 3.4. Цикл Бема-Джакопини

переходов, которые ввел в практику и теорию Д. Кнут (откопавший ориги-

нальную работу Бема-Джакопини и четко выделивший ограничения дейкс-

тровского структурного подхода

) избавляет от многих недостатков, прису-

щих методике Дейкстра. Структурные переходы — переходы лишь вперед

и на более высокий уровень структурной иерархии управления, ни в каком

случае не выводящие нас за пределы данного модуля.

Программа 3.3.1

Примеры структурных

goto.*/

...

do {y = f( x ,y);

if(y>0) break;

x=g(x,y);

} while ( x > 0 );

...

{...

{

if (All_Done) goto Success;

}

...

Success: Hurra;}

Структурные переходы в настоящее время также включаются в общераспро-

страненные языки программирования. Их использование понемногу прони-

кает и в учебные курсы.

Так что, применяя теоретический результат, всегда интересуйтесь не только его форму-

лировкой, но и доказательством, желательно в работе авторов.

130

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

Структурные переходы являются паллиативом. Они возникли из-за не-

обходимости выразить мысль, что успех либо неудача глобального процесса

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

и над текущей задачей, и над всей последовательностью вложенных подзадач

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

операторы завершения. Но они в распространенных языках действуют лишь

на один уровень иерархии вверх, а даже теоретически этого недостаточно.

Еще один вопрос — о совместимости структурного программирования с

рекурсиями.Опыт показывает, что процедура,в которой есть ее рекурсивный

вызов внутри цикла, практически почти всегда неправильна, теоретически

же она выходит за рамки примитивной рекурсии (см. курс логики и теории

алгоритмов) и, как следствие, становится практически невычислимой. Что-

бы здесь не попасть впросак, соблюдайте простое правило.

Внимание!

Не используйте рекурсивный вызов процедуры внутри цикла!Рекурсия и ци-

клы должны быть «территориально разделены»!

Хотя данное правило пригодно в подавляющем большинстве случаев, но

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

иска вглубь на дереве.

Программа 3.3.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;

}

Здесь рекурсии вместе с циклом задают обход дерева возможностей и гибель-

ного размножения рекурсивных вызовов не происходит.

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

ритмических языков, в частности, язык

ЯРМО

[25], в котором необходимость многоуровне-

вых средств завершения конструкций была осознана еще в начале 70-х гг.

3.3. СТРУКТУРНОЕ ПРОГРАММИРОВАНИЕ

131

Для стиля мышления при структурном программировании характерно стрем-

ление к локальности и иерархическое разбиение задачи на подзадачи — так

называемое нисходящее программирование. Нисходящее программирование

часто рассматривали (и рассматривают) как общий способ декомпозиции дей-

ствий. Причины тому следующие:

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

вычислений;

• раннее программирование — это поиск способов вычислений, т. е. на-

работка типовых алгоритмов, приемов и методов (рекурсия, динамиче-

ское программирование, поиск в глубину и др.);

• нисходящее построение структур данных стало появляться (оформлять-

ся явно) только тогда, когда сформировалась идея абстракции данных;

• давление теории сложности. Задача программистской оптимизации ча-

ще всего формулируется так: требуется найти минимальное по времени

вычислений решение в заданных ограничениях по памяти (а иногда и

без них).

Последнее сомнительно, т. к. наиболее существенными критическими участ-

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

появления концепции абстракции данных понять это было трудно.

Невозможность при нисходящем структурном программировании увидеть

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

тем более унифицировать несколько формально различных процедур на раз-

ных ветвях в одну общую, показывает необходимость дополнения подхода

средствами, позволяющими “поднять” уровень понятий. Первым выраже-

нием стремления разумно обобщить понятия можно считать привлечение к

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

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

обобщением, а не делением какой-то задачи. Части, выделяемые в виде би-

блиотечных средств, выбираются исходя из их применимости в различных

контекстах. Таким образом, это построение снизу вверх!

Создание глобального контекста, каковым и является восходящее постро-

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

жет применяться программирование от состояний. Если разделение стилей

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

можно избежать эклектического их смешения.

132

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

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

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

(при любой технологии: от данных или от действий);

• затем попытка движения снизу вверх, чтобы спроецировать понятия,

оформившиеся ранее, на абстрактные структуры, допускающие аде-

кватную реализацию;

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

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

§ 3.4. СЕНТЕНЦИАЛЬНОЕ ПРОГРАММИРОВАНИЕ

Теорией, вдохновившей создателей сентенциального программирования,

являются такие формализации понятия алгоритма, как алгоритмы Маркова и

Колмогорова, и логические исчисления с крупноблочными правилами выво-

да (например, метод резолюций).

Схема сентенциального программирования получила две различные реа-

лизации,появившиеся практически одновременно (

Рефал

,Россия,В. Ф.Тур-

чин, 1968,

Prolog

, Р. Ковальски, М. ван Эмден, Великобритания, А. Колмероэ,

Канада, 1971–1974 гг.) и активно используемые до настоящего времени. Обе

они концептуально интересны, и поэтому мы их рассматриваем в соответ-

ствующей главе.

В. Ф. Турчин предложил термин “сентенциальное программирование”,

и он наиболее четко проанализировал методологические особенности этого

стиля на том уровне, на котором это было возможно в 70-х гг. Его анализ лег

в основу нашего рассмотрения, но еще более важно то, что высочайшая науч-

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

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

работы. Поэтому ни один из компонентов анализа Турчина не был отверг-

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

позиций современной теории и практики.

Сентенциальное программирование отличается следующими особенно-

стями.

• Память представляется как единая большая структура данных. Состо-

яние программы (поле зрения) задается как выражение либо совокуп-

ность выражений.

3.4. СЕНТЕНЦИАЛЬНОЕ ПРОГРАММИРОВАНИЕ

133

В некоторых из вариантов сентенциального программирования эти выраже-

ния могут содержать переменные,а в других —нет. Например,в языке

Prolog

поле зрения — конечная система скобочных выражений, подобная

Boss(Commercial)(x,Kovalyov),Father(Mihail,Ivan),

Boss(Formal)(x,YuErshov);

где x — переменная.

• В поле зрения по некоторым правилам может быть выделена активная

часть, т. е. рассматриваемая в данный момент.

Например, в приведенном выше выражении активная часть — первое ско-

бочное выражение

Boss(Commercial)(x,Kovalyov)

На каждом шаге выполнения программы глобальные свойства активной ча-

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

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

а тот, который соответствует условию, выполненному для данного состояния

внутреннего мира программы.

• Каждое действие программы состоит в замене одного выражения на

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

правую.

И левая, и правая части оператора могут при этом содержать переменные,

значения которых станут известны лишь в момент применения оператора.

• Выполняется тот оператор, для которого активная часть выражения по-

лучается из левой части оператора некоторой подстановкой значений

переменных, их конкретизацией либо унификацией

. Полученные при

конкретизации (унификации) значения переменных используются для

конкретизации правой части (а при унификации — и всего поля памя-

ти). Активная часть выражения заменяется на правую часть правила.

Традиционно в сентенциальных языках избегают называть операторы этих языков опе-

раторами. Например, в

Prolog

их называют (различные русские варианты транслитерации и

перевода)

дизъюнктами, предложениями, кл(ау,яу,о)зами

Термин конкретизация обычно употребляется тогда, когда переменные могут содержать-

ся лишь в правилах, но не в рассматриваемом выражении, а унификация — тогда, когда пе-

ременные могут содержаться и в обрабатываемом выражении тоже, и задача согласования

их значений становится симметричной.

134

ГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА

Например, если у нас есть правило

X*(Y+Z)=>X*Y+X*Z

то вся активная часть поля памяти будет проверена на возможность предста-

вления форме

X*(Y+Z)

, при этом переменные

X, Y, Z

получат значения, после

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

ем найденных значений переменных.

При сентенциальном стиле образ мышления программиста подобен вы-

воду предложения по грамматике (отсюда и наименование стиля). Этот стиль

удобен,если перерабатываемые данные естественно представлять в виде слож-

ной структуры единиц, которые достаточно глобально распознаются и доста-

точно регулярно, но глобально, меняются. В отличие от структурного про-

граммирования, когда структурируются и локализуются прежде всего дей-

ствия, здесь делается упор на локальности активной (преобразуемой) части

данных, а действия глобальны.

Такой стиль плохо сочетается со структурной моделью вычислений, но в

принципе сочетаем с операционной моделью вычислений от состояний. Ко-

гда действия глобальны и не смешиваются с распознаванием, то противоре-

чия не возникают. Поэтому, к примеру, оказался успешным язык

SNOBOL

который в начале 60-х гг. прошел полпути к сентенциальному программиро-

ванию. В качестве основного действия в нем было отождествление и замена

по образцу, а структура управления была взята из тогдашних языков про-

граммирования и сответствовала программированию от состояний. Но когда

тот же

SNOBOL

попытались переложить на схему операторов структурного

программирования (в языке

SNOBOL-A

, разработанном в Ленинграде в на-

чале 80-х гг.), сразу исчезла наглядность языкового представления

SNOBOL

машины, и распространения структурный

SNOBOL

не получил. На эту по-

пытку можно было бы не тратить усилий, если бы разработчики обратили

внимание на несочетаемость разнородных стилей, о которой уже было из-

вестно в то время.

Сентенциальный стиль программирования до сих пор обсуждался как

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

вычислений.Однако программировать в сентенциальном стиле можно не толь-

ко на этих языках. Уже сам факт реализации их на фон Неймановской архи-

тектуре доказывает принципиальную возможность моделирования сентен-

циальных примитивов операционными средствами. Поскольку здесь возни-

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

отдельный параграф 13.4.2.