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

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

3.1. СТИЛИ ПРОГРАММИРОВАНИЯ

115

• Ассоциативные системы.Элементы системы —активные данные,пред-

ставляющие собой пары: h

значение

ключ

i. Пары, имеющие одинако-

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

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

в любом стиле (например, в рамках стилей фон Неймановских вычи-

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

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

чтожаются. Легко заметить, что ассоциативная система может рассма-

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

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

чески эквивалентны. Однако эта форма соответствует иному взгляду на

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

работы с базами знаний

• Аксиоматические системы.Если система отождествлений и замен фик-

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

ботаем в фиксированном классе исчислений, и на первый план выхо-

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

Знания и предпочтения записываются в виде аксиом. Таким образом,

формально аксиоматические системы являются частным случаем сен-

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

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

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

система преобразований

В случае наиболее распространенной классической логики и языка ис-

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

сиом можно смотреть как на описание предметной области (либо, что

то же самое, на задание соотношений между данными). Вычислитель-

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

которых является вывод некоторой формулы (что для классической ло-

гики и элементарных формул соответствует выводу истинности либо

ложности некоторого факта; такой вывод уже не назовешь проверкой,

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

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

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

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

поиска вывода планируют сразу эту структуру.

116

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

поскольку он не является элементарной операцией). Программиста в

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

ствимость.

Не все из этих направлений представлены одинаково в экспериментальных

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

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

тях в доказательствах и парадоксом изобретателя (см. [63] или краткий очерк

в Приложении А), прямая реализация аксиоматических систем, несмотря на

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

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

кладных областей.

Аксиоматические системы могут служить иллюстрацией того,как попыт-

ки неоправданного распространения методов за сферу их адекватной при-

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

ний формул исчисления высказываний. Для этой области можно указать кон-

структивное решение, в точности соответствующее потребности и даже до-

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

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

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

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

гается желание распространить “хорошо себя зарекомендовавшую систему”

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

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

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

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

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

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

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

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

тате стремления к распространению в систему включаются инородные эле-

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

антов.Но проблемы неразрешимости все равно дают о себе знать: система не

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

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

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

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

Примерно по такой схеме (с учетом различия моделей вычислений) раз-

3.1. СТИЛИ ПРОГРАММИРОВАНИЯ

117

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

PROLOG

, который, стре-

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

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

идеи логического вывода в системах продукций.

А вот с языком

Рефал

, принадлежащим, как и

PROLOG

, к системам про-

дукций, ситуация прямо противоположна. В. Ф. Турчин, разработчик языка,

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

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

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

шений оказывается эффективным. В результате только за счет этого специ-

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

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

ных. Далее, осознавая, с одной стороны, что для принятого способа задания

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

с другой — что они нужны, Турчин вместо прямолинейного их внедрения в

язык предложил согласованный с моделью вычислений ‘дозированный’ спо-

соб активизации вычисления любых внешних функций. В результате обоб-

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

нынешней версии языка

Рефал-5

В этом отношении поучителен пример функционального языка

LISP

, в

который встроен чужеродный оператор присваивания. В результате появи-

лась возможность писать программы на

LISP

как на императивном языке. К

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

это означает в точности то, что в отличие от

Prolog

а программист все еще в

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

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

тивность

LISP

а отделима от его функциональной сути.

Неимперативные системы должны в современных компьютерах модели-

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

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

граммиста. Наличие одного из таких алгоритмов, достаточно хорошо реали-

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

класса неимперативных систем (как de facto произошло с логическими си-

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

Prolog

). Напротив,

использование конкретных особенностей реализации быстро и практически

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

Prolog

-программами), и поэтому альтернативные реализации просто необ-

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

118

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

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

грамм. К зрелости с точки зрения этого критерия приблизились лишь систе-

мы продукций.

Внимание! Простое комбинирование двух реализаций чаще всего приво-

дит к потере их достоинств при бурном расцвете недостатков.

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

лей в настоящий момент просто нет, рассмотрим практически сложившиеся

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

ровав их список в соответствии с концепциями:

• Программирование от состояний;

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

• Сентенциальное программирование;

• Программирование от событий;

• Программирование от процессов и приоритетов;

• Функциональное программирование;

• Объектно-ориентированное программирование;

• Программирование от переиспользования;

• Программирование от шаблонов.

Это перечисление не претендует на теоретическую полноту и даже на пол-

ную обоснованность. Здесь мы стремимся сосредоточиться на классифика-

ции методов и отвлечься от конкретных частностей выражения (например,

если главное в данном стиле программирования — условия, для нас все рав-

но, на каком они языке задаются, логическом или другом).

§ 3.2. ПРОГРАММИРОВАНИЕ ОТ СОСТОЯНИЙ

Это — пожалуй, самый старый стиль программирования. Он соответ-

ствует теоретическому понятию конечного автомата (изучаемому в курсе

дискретной математики, см., напр., Минский [57] и Приложение А). На этот

3.2. ПРОГРАММИРОВАНИЕ ОТ СОСТОЯНИЙ

119

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

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

томаты.

В общераспространенных языках

Pascal

Ada

есть все средства для

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

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

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

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

языки и, соответственно, языки ассемблера. Имеется много систем, в кото-

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

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

го стиля. Например, в системе

UML

[89, 50] одна из моделей дает возмож-

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

мы.

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

щим образом. Определяются:

• множество так называемых состояний, которые может принимать ко-

нечный автомат;

• переходы между состояниями, которые осуществляются под внешним

воздействием (например,под воздействием перерабатываемых данных).

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

ющих переходы между состояниями. Если же говорить в более ‘теоретиче-

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

hсостояние, внешнее воздействиеi

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

произведено разными способами. Многие из них хорошо изучены теорети-

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

Современные методики программирования от состояний (напр. [81]) ба-

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

автомата. Эти таблицы часто также представляются в виде графов, что осо-

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

зуемы. См., напр., рис. 3.1, где представлены и таблица, и граф.

На таблице состояний или на ее графовом аналоге все действия предпо-

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

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

120

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

a b c d

1 2 3 4 1

2 3 4 1 2

3 4 1 2 3

4 1 2 3 4

Здесь состояния идентифици-

руются порядковыми номера-

ми, а воздействия — буквами.

Рис. 3.1. Таблица состояний. Граф переходов.

выполнено. В зависимости от того, какое из них выполнено, автомат пере-

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

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

Прежде всего, отметим вариацию, отражающую различие автоматов Ми-

ли и Мура в § A.4. Действия в диаграмме состояний и переходов могут ас-

социироваться либо с состояниями (с вершинами графа), либо с переходами.

Ниже Вы увидите примеры, когда при программировании естественно воз-

никают обе эти ассоциации.

Заметим, что естественно рассматривать таблицы состояний и перехо-

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

не может оказаться истинно сразу несколько условий, соответствующих вы-

ходящим ребрам.

Внимание!

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

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

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

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

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

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

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

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

существенны, а какие вставлены лишь для детерминации.

Таблицы переходов и состояний являются естественным способом про-

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

Конечно же, в каждом конкретном примере нужно использовать лишь одну из них! Эти

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

3.2. ПРОГРАММИРОВАНИЕ ОТ СОСТОЯНИЙ

121

некоторой средой (эти глобальные операции сами, как правило, программи-

руются в другом стиле). Для программирования от состояний характерно go

to, и здесь оно на месте.

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

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

ставление программы в виде блок-схемы (см., напр., рис. 3.2), узлы которой

представляют собой состояния. Узлы блок-схемы делятся на пять типов:

a) начальная вершина, в которую нет входов и в которой производится ини-

циализация переменных либо состояния вычислительной системы;

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

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

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

та и затем передают управление по разным адресам;

d) соединения, в которые имеется несколько входов и один выход;

e) выход, попав в который, программа заканчивает работу.

◦

A ∨ B

◦

B ∨C

Рис. 3.2. Блок-схема

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

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

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

122

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

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

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

граммировании (см. книги Котова [44, 45]).

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

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

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

чение переменной,какие существуют зависимости между данными перемен-

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

схема на рис. 3.3.

Заметим, что, операции в программировании от состояний глобальны, а

условия локальны. Проверка условия не изменяет состояния всей системы

(ни одного из ее параметров или характеристик), она лишь ведет нас в то или

иное состояние самой программы.

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

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

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

все потоки в системе, а проверка, открыт ли вентиль, является чисто локаль-

ной операцией. Изменение температуры рабочего вещества в системе опять-

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

сняв показания всего одного датчика.

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

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

чей, и внутренние понятия самой программы. Для системы в целом безраз-

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

ней.Для нее важно, какие изменения в ней самой происходят. Таким образом,

состояние памяти вычислительной системы вполне может рассматриваться

как внешняя характеристика по отношению к программе, которая в ней ра-

ботает.

Необходимость одновременного и согласованного рассмотрения внеш-

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

рактеристики раздробляются и детализируются (например, при соединении

стиля программирования от состояний с присваиваниями), программист на-

чинает путаться, согласованность понятий исчезает и возникают ошибки.

Внимание!

Если пользоваться произвольными таблицами переходов,то надо позаботить-

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

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

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

3.2. ПРОГРАММИРОВАНИЕ ОТ СОСТОЯНИЙ

123

x:=a

y:=a

x:=f(x)

P(x)

x:=f(x)

P(x)

x:=f(x)

P(x)

x:=f(x)

P(x)

x:=f(x)

P(x)

stop(x,y)

x:=f(x)

P(x)

Error

y:=f(y)

P(y)

y:=f(y)

P(y)

y:=f(y)

P(y)

y:=f(y)

P(y)

Рис. 3.3. А что здесь вычисляется?

124

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

операторе типа

case.

В теории данный эффект концептуальной противоречивости проявляется

в неразрешимости большинства естественных свойств схем программ. Од-

нако все основные свойства оказываются разрешимыми, если все функции

одноместные и переменная всего одна (схемы Янова). Как же проинтерпре-

тировать такой теоретический результат?

Поскольку в схеме Янова все присваивания имеют вид

x:=f(x)

, где меня-

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

как глобальное со-

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

мирования от состояний эффективен, если все действия глобальные (или, по

крайней мере, рассматриваются лишь с точки зрения их глобальных эффек-

тов), а присваивания по самой своей природе — локальные действия.

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

ния. Использование схем Янова целесообразно тогда, когда переходов в про-

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

бличного или графового представления лишь затемняет структуру. Если же

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

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

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

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

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

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

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

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

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

автоматному мышлению. В частности, когда сложность алгоритма превыша-

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

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

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

простых примерах.

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

САМЫЙ РАСПРОСТРАНЕННЫЙ СТИЛЬ

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

легче поддаются анализу [44]. Поэтому естественно было выделить такой

класс блок-схем, что и сделали итальянские ученые С. Бем и К. Джакопи-