«ОСНОВАНИЯ ПРОГРАММИРОВАНИЯ УДК 519.682 Непейвода Н. Н., Скопин И. Н. Основания программирования Книга представляет собой первое издание в серии, предназначенной для студентов, готовящихся к работе по современным ...»

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

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

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

А вот с языком Рефал, принадлежащим, как и PROLOG, к системам продукций, ситуация прямо противоположна. В. Ф. Турчин, разработчик языка, понимая безнадежную неэффективность идеи прямого воплощения в языке системы правил алгоритма Маркова, предпринял попытку поиска специального представления перерабатываемых данных, на котором описание соотношений оказывается эффективным. В результате только за счет этого специального представления удалось выделить значимую с прикладной точки зрения область применения идеи: обработка структурно организованных данных. Далее, осознавая, с одной стороны, что для принятого способа задания такой обработки арифметические вычисления оказываются чужеродными, а с другой — что они нужны, Турчин вместо прямолинейного их внедрения в язык предложил согласованный с моделью вычислений ‘дозированный’ способ активизации вычисления любых внешних функций. В результате обобщение без потерь было достигнуто, и эта ситуация сохраняется вплоть до нынешней версии языка Рефал-5.

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

Неимперативные системы должны в современных компьютерах моделироваться императивно. Но конкретный алгоритм построения модели на основе неимперативной системы должен быть как можно лучше упрятан от программиста. Наличие одного из таких алгоритмов, достаточно хорошо реализованного, не означает, что все остальные должны отвергаться для данного класса неимперативных систем (как de facto произошло с логическими системами после взрывообразного распространения языка Prolog). Напротив, использование конкретных особенностей реализации быстро и практически безнадежно портит программы неимперативного стиля (что и произошло с Prolog-программами), и поэтому альтернативные реализации просто необходимы. Именно отсутствие признанных и хороших альтернативных реалиГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА заций является признаком незрелости данного класса неимперативных программ. К зрелости с точки зрения этого критерия приблизились лишь системы продукций.

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

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

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

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

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

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

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

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

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

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

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

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

';

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

§ 3.2.

Это — пожалуй, самый старый стиль программирования. Он соответствует теоретическому понятию конечного автомата (изучаемому в курсе дискретной математики, см., напр., Минский [57] и Приложение А). На этот стиль программирования наталкивает само устройство существующих вычислительных машин, которое представляют собой гигантские конечные автоматы.

В общераспространенных языках C, Pascal, Ada есть все средства для того, чтобы воспользоваться таким стилем, но писать прямо на алгоритмическом языке программы в этом стиле не рекомендуется, поскольку их представление получается ненаглядным, и, соответственно, их модификация затруднена. В значительной степени ориентированы на такой стиль машинные языки и, соответственно, языки ассемблера. Имеется много систем, в которых такие программы автоматически или полуавтоматически генерируются по графовому или табличному представлению, более органичному для такого стиля. Например, в системе UML [89, 50] одна из моделей дает возможность преобразовать диаграмму состояний и переходов в заготовку программы.

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

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

• переходы между состояниями, которые осуществляются под внешним воздействием (например, под воздействием перерабатываемых данных).

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

Современные методики программирования от состояний (напр. [81]) базируются на таблицах состояний, подобных таблице состояний конечного автомата. Эти таблицы часто также представляются в виде графов, что особенно удобно, когда не все возможные переходы между состояниями реализуемы. См., напр., рис. 3.1, где представлены и таблица, и граф.

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

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

Здесь состояния идентифицируются порядковыми номераQ Рис. 3.1. Таблица состояний. Граф переходов.

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

Прежде всего, отметим вариацию, отражающую различие автоматов Мили и Мура в § A.4. Действия в диаграмме состояний и переходов могут ассоциироваться либо с состояниями (с вершинами графа), либо с переходами.

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

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

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

некоторой средой (эти глобальные операции сами, как правило, программируются в другом стиле). Для программирования от состояний характерно go to, и здесь оно на месте.

Исторически первой моделью программирования от состояний, использованной и на практике, и для теоретических исследований, явилось представление программы в виде блок-схемы (см., напр., рис. 3.2), узлы которой представляют собой состояния. Узлы блок-схемы делятся на пять типов:

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

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

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

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

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

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

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

планиравания разработки программ и их документирования. Традиционные блок-схемы являются, в частности, предметом изучения в теоретическом программировании (см. книги Котова [44, 45]).

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

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

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

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

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

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

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

операторе типа case.

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

Поскольку в схеме Янова все присваивания имеют вид x:=f(x), где меняется лишь функция, можно воспринимать переменную x как глобальное состояние среды вычислений, что еще раз подтверждает, что стиль программирования от состояний эффективен, если все действия глобальные (или, по крайней мере, рассматриваются лишь с точки зрения их глобальных эффектов), а присваивания по самой своей природе — локальные действия.

Подводя итоги сказанного, дадим рекомендации по выбору представления. Использование схем Янова целесообразно тогда, когда переходов в программе относительно немного, условия многообразны, и использование табличного или графового представления лишь затемняет структуру. Если же условия однообразны, а переходов много, то лучше подходит графовое представление. Если же граф переходов практически является полным, то лучше всего воспользоваться табличным представлением.

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

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

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

§ 3.3.

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

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

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

Структурное программирование основано главным образом на теоретическом аппарате теории рекурсивных функций. Программа рассматривается как частично-рекурсивный оператор над библиотечными подпрограммами и исходными операциями. Структурное программирование базируется также на теории доказательств, прежде всего на естественном выводе. Структура программы соответствует структуре простейшего математического рассуждения, не использующего сложных лемм и абстрактных понятий. Средства структурного программирования в первую очередь включаются во все языки программирования традиционного типа и во многие нетрадиционные языки. Они занимают основное место в учебных курсах программирования ([3, 27, 37, 51]).

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

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

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

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

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

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

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

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

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

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

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

5) “Призраки”. Часто даже сама программа не может быть объяснена через понятия, которые используются внутри нее. Еще чаще это происходит для ее связей с внешним миром. Понимание программы возможно лишь после сопоставления ‘реальных’ внутрипрограммных объектов с ‘идеальными’ внепрограммными. Эти идеальные внепрограммные объекты (призраки) часто не просто не нужны, но даже вредны для исполнения программы. Первым обратил внимание на неоходимость введения призраков для логического и концептуального анализа программ Г. С. Цейтин в 1971 г. Впоследствии в Америке это ‘независимо’ переоткрыли в 1979 г., хотя упомянутая статья Цейтина была опубликована на английском языке в общедоступном издании. Даже название сущностям было дано то же самое...

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

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

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

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

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

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

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

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

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

переходов, которые ввел в практику и теорию Д. Кнут (откопавший оригинальную работу Бема-Джакопини и четко выделивший ограничения дейкстровского структурного подхода14 ) избавляет от многих недостатков, присущих методике Дейкстра. Структурные переходы — переходы лишь вперед и на более высокий уровень структурной иерархии управления, ни в каком случае не выводящие нас за пределы данного модуля.

Программа 3.3. /*Примеры структурных goto.*/...

do {y = f( x,y);

if(y>0) break;

x=g(x,y);

} while ( x > 0 );

...

{...

if (All_Done) goto Success;

...

Success: Hurra;} Структурные переходы в настоящее время также включаются в общераспространенные языки программирования. Их использование понемногу проникает и в учебные курсы.

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

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

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

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

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

Программа 3.3. int search (ELEMENT x) ELEMENT y; int result; { if (good(x)) { return id(x)} else for(int i=0; i0) return result;

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

В связи с этим стоит помянуть добрыс словом отечественные разработки в области алгоритмических языков, в частности, язык ЯРМО [25], в котором необходимость многоуровневых средств завершения конструкций была осознана еще в начале 70-х гг.

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

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

• раннее программирование — это поиск способов вычислений, т. е. наработка типовых алгоритмов, приемов и методов (рекурсия, динамическое программирование, поиск в глубину и др.);

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

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

Невозможность при нисходящем структурном программировании увидеть тождественность процедур, работающих на разных ветвях декомпозиции, а тем более унифицировать несколько формально различных процедур на разных ветвях в одну общую, показывает необходимость дополнения подхода средствами, позволяющими “поднять” уровень понятий. Первым выражением стремления разумно обобщить понятия можно считать привлечение к разработке структурных программ подхода, получившего название восходящего программирования. К примеру, когда строят библиотеку, занимаются обобщением, а не делением какой-то задачи. Части, выделяемые в виде библиотечных средств, выбираются исходя из их применимости в различных контекстах. Таким образом, это построение снизу вверх!

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

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

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

• сначала сверху вниз для выяснения крупных “строительных блоков” (при любой технологии: от данных или от действий);

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

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

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

§ 3.4.

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

Схема сентенциального программирования получила две различные реализации, появившиеся практически одновременно (Рефал, Россия, В. Ф. Турчин, 1968, Prolog, Р. Ковальски, М. ван Эмден, Великобритания, А. Колмероэ, Канада, 1971–1974 гг.) и активно используемые до настоящего времени. Обе они концептуально интересны, и поэтому мы их рассматриваем в соответствующей главе.

В. Ф. Турчин предложил термин “сентенциальное программирование”, и он наиболее четко проанализировал методологические особенности этого стиля на том уровне, на котором это было возможно в 70-х гг. Его анализ лег в основу нашего рассмотрения, но еще более важно то, что высочайшая научная и общая культура создателя языка позволила ему избежать эффектных, но необоснованных заявлений, которыми кишат многие методологические работы. Поэтому ни один из компонентов анализа Турчина не был отвергнут здесь, хотя, конечно же, он был существенно пересмотрен и дополнен с позиций современной теории и практики.

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

• Память представляется как единая большая структура данных. Состояние программы (поле зрения) задается как выражение либо совокупность выражений.

В некоторых из вариантов сентенциального программирования эти выражения могут содержать переменные, а в других — нет. Например, в языке Prolog поле зрения — конечная система скобочных выражений, подобная Boss(Commercial)(x,Kovalyov),Father(Mihail,Ivan), Boss(Formal)(x,YuErshov);

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

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

Например, в приведенном выше выражении активная часть — первое скобочное выражение На каждом шаге выполнения программы глобальные свойства активной чаBoss(Commercial)(x,Kovalyov).

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

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

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

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

ГЛАВА 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.

ПРОГРАММИРОВАНИЕ ОТ СОБЫТИЙ

§ 3.5.

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

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

• процессы генерации событий отделены от процессов их обработки;

• процессы отработки разных реакций не зависят друг от друга;

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

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

Стиль событийного программирования — это создание для каждого события собственной процедуры-обработчика. Порядок, в котором обработчики описываются в программе, не имеет никакого значения. Более того, они могут, а во многих случаях и должны быть приписаны к разным структурным единицам программы, в рамках которых только и осмыслена реакция на событие. Как следствие, продуктивно разбивать реакцию на событие на части, за которые отвечают такие структурные единицы, и иметь несколько реакций (разных) структурных единиц на одно событие.

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

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

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

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

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

Порождение динамических экземпляров структу рных единиц Генерация событий и активизация реакций:

Рис. 3.5. Схема активизации обработчиков событий

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

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

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

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

В замкнутом относительно средств объектно-ориентированного программирования виде впервые она была реализована в системах Think C++, Think Pascal и Delphi. Именно эту конкретную реализацию сегодня чаще всего называют событийно-ориентированным программированием. Как естественно предположить, в этой объектно-ориентированной системе в качестве структурных единиц программы, способных реагировать на события, выступают классы, а в качестве динамических экземпляров таких структурных единиц — объекты. Обработчиками событий служат методы этих объектов.

До сих пор мы ничего не говорили о том, какие события возможны при программировании в событийно-ориентированном стиле. Исторически этот стиль как определенный “художественный прием” сформировался в области разработки операционных систем, где естественно связывать понятие события с прерываниями. Прерывание — это сигнал от одного из устройств (может быть, и от самого процессора), который говорит о том, что произошло нечто, на что нужно обратить внимание. Когда происходит прерывание, операционная система распознает, какая причина его вызвала, и далее формирует Текст программы (основной), разрабатываемой программистом a) составление последовательного текста программы Библиотечные мод ули Фрагменты, разрабатываемые программистом Рис. 3.6. Две схемы составления программы событие как информационный объект, вызывающий реакцию программной системы. Возможны разные способы реагирования на события, в том числе и передача его для обработки той программе, при выполнении которой возникло прерывание, породившее это событие.

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

В частности, при взаимодействии с пользователем других событий, кроме нажатия на клавишу, перемещения курсора мыши, указания световой кнопки и т. п., не требуется. И не случайно именно те прерывания, которые способна перенаправить операционная система для обработки на уровень пользовательской программы, стали основой для выработки систем событий, реакция на которые задается в событийно-ориентированном стиле. События этого роГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА да можно передать от одного обработчика к другому, не нарушая условий адекватного применения данного стиля: для этого достаточно объявить такое перенаправление события как генерацию нового события. Но требуется также генерация событий, не связанных с прерываниями.

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

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

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

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

В качестве иллюстрации этого тезиса ниже с позиций событийного стиля программирования описываются “взаимоотношения” между синтаксическим анализом и вычислениями семантики программы. Реализация этих взаимоотношений — обычная задача, решаемая при разработке любого транслятора. В событийном описании этой задачи в качестве событий системы естественно рассматривать распознавание во входном потоке (транслируемом тексте) синтаксических единиц, т. е. конструкций языка. Такое событие требует в качестве обработчика семантическую подпрограмму, связанную с распознаваемой конструкцией. Следовательно, выявлены два автономных процесса: синтаксический анализ, задающий генерацию событий, и семантическая обработка, осуществляемая как последовательность вызовов сеПРОГРАММИРОВАНИЕ ОТ СОБЫТИЙ мантических подпрограмм-реакций, упорядоченная событиями.18 Коль скоро есть концептуальное разделение процессов, его можно воплотить в реальной системе в событийном стиле. Это решение влечет за собой следующее:

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

• Для обсуждаемой задачи существенно, что события возникают не в произвольном порядке, их множество имеет вполне определенную структуру. Нисколько не удивительно, что эта структура в точности соответствует синтаксической структуре текста: например, не может возникать событие завершения распознавания конструкции раньше, чем возникнет событие начала конструкции;

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

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

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

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

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

Разумеется, событийное программирование много шире случаев, в которых можно статически определять, когда будет нужно активизировать обработчики, т. е. когда полезно объединение генерации событий с их обработкой и за счет такого объединения растворять события в программе. В частности, и по этой причине его следует рассматривать как самостоятельный стиль. Но интересны и такие случаи, когда объединение, хотя и возможно, но не делается. Конкретный пример — XML/XSL технология, для которой разделение структуры и интерпретации текста считается принципиальным: это позволяет строить ‘съемные’ системы обработки, иметь несколько независимых таких систем для разного назначения. В своей сфере применения в такой многовариантности усматриваются большие преимущества, но, как всегда, перенос принципов данной технологии “куда угодно” чреват уже не раз отмеченной неадекватностью.

ПРОГРАММИРОВАНИЕ ОТ ПРИОРИТЕТОВ

§ 3.6.

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

Он стал основой для формирования самостоятельного стиля программирования от приоритетов.

Этот стиль порожден практическими потребностями. Он предназначен для организации работы многих взаимодействующих процессов, динамически порождаемых и динамически исчезающих. Фундаментальных теоретиСтатическое вычисление некоторых частей программ — очень важный и имеющий в потенциале исключительно широкую область применения прием программирования. Если программист предусматривает, что его программа будет частично вычислена до основного выполнения программы, то он следует еще одному стилю: специализирующему программированию, который рассматривается в § 3.9.3.

ческих исследований в области программирования от приоритетов почти нет.

В частности, в классической работе Хоара [76], в которой рассматривается управление взаимодействующими процессами, предполагается, что программа написана в традиционном структурном стиле, и никаких попыток приспособить ее к обстановке, где есть много процессов, нет. Стиль программирования от приоритетов не реализован систематически в виде законченного языка (в качестве некоторой попытки можно привести проект Joule, см. ???), но часто используется в прикладных языках скриптов для управления процессами или событиями либо в распределенных системах, либо на полуаппаратном уровне (так называемые встроенные программы, являющиеся частью специализированного прибора или устройства).

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

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

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

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

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

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

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

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

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

Стили программирования от событий и приоритетов хорошо совмещаются, взаимно дополняя друг друга, когда целесообразна следующая архиПРОГРАММИРОВАНИЕ ОТ ПРИОРИТЕТОВ тектурная схема разработки программного проекта. В рамках событийного подхода готовятся фрагменты системы, которые отвечают за реакцию на каждое из событий, реализуемую разными обработчиками, а программирование этих обработчиков ведется в стиле программирования от приоритетов.

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

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

Программа 3.6. Демон {Если Поступили экстренные данные То Запоминание экстренных изменений};

Демон {Если Авария То Аварийные действия};

12:

Программа 3.6. a: PRIO 3 {Prepare Data;SLEEP};

b: PRIO 10{Process Changes;SLEEP};

c: PRIO 8 DAEMON IF Extra Data d: PRIO 12DAEMON IF Alert e: PRIO 2 DAEMON IF Idle Видно, что в данном примере все приоритеты задавались статически. Именно к этому стремятся почти во всех случаях современной практики вычислений с приоритетами. Но полной статичности можно добиться лишь в проГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА стейших случаях. Например, если процесс долго ждет своей очереди на исполнение, то естественно постепенно поднимать его приоритет. Но тогда приоритет такого «пользовательского» действия может превзойти приоритет системного процесса, и остается либо статически задавать каждому процессу допустимый максимальный приоритет и мы вновь попадаем в ту же ловушку, либо задавать разным классам процессов приоритеты просто несравнимые по порядку, чтобы ни при каком нормальном исполнении приоритет пользовательского процесса не дорос, скажем, до 109, за которым начинаются приоритеты срочных системных демонов.

Заметим, что назначение приоритетов операционной системой, «сверху», принципиально ничего в данной картине не меняет. С точки зрения пользовательских программ эти приоритеты все равно статические.

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

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

курс математической логики). Поскольку ординалы до 0 имеют хорошую вычислительную модель (см., напр. [63]), можно рассматривать целочисленные приоритеты как конкретную реализацию абстрактного класса таких ординалов.

А в случае реально распределенных или реально параллельных действий проблема приоритетов еще важнее и еще сложнее. Часто управление по приоритетам — единственный шанс справиться со сложностью такой нелинейной во времени системы. Тут уже и линейно упорядоченного множества приоритетов не хватает.

В целом программирование от приоритетов является мощным, но специфическим орудием для описания глобальных совместных, параллельных или распределенных процессов. Его элементы проникают и в традиционные системы программирования в виде обработки исключительных ситуаций в программах. Здесь, как и в событийном программировании с обособленными реакциями, всего два приоритета, которые налагаются на структуру использующей конструкции. Противоречивость этого средства со структурным проПравда, здесь мы отвлекаемся от реальных ограничений, и считаем 1010 столь же легко достижимым числом, как и 10.

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

ФУНКЦИОНАЛЬНОЕ ПРОГРАММИРОВАНИЕ

§ 3.7.

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

Функциональное программирование полностью22 реализовано в ряде достаточно широко используемых систем, например, в языках LISP и ML. Накоплен громадный багаж ценного программного обеспечения на этих языках.

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

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

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

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

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

объект. Основное правило преобразования очень естественно:

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

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

Если запретить самоприменимость, приписав всем переменным и константам типы и разрешив применять функцию лишь к аргументам правильного типа (это обозначается следующим требованием: функция f должна иметь тип ( ), ее аргумент t — тип, и тогда выражение f (t) имеет тип ). В этом типизированном -исчислении зацикливание уже исключается, если его нет в исходных функциях.

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

Основной метод определения новых функций, принятый в программировании — рекурсия.

Пример 3.7.1. Дж. Маккарти в 1960 г. сформулировал определение вычислимости, в котором все функции строятся из исходных при помощи схем типа Mult(x, y) if y = 0 then 0 else Add(Mult(x, Pd(y)), x) (рекурсивные схемы по Маккарти [57]). Здесь Pd — функция, находящая предыдущее натуральное число, Add — функция сложения. А что определяется такой схемой, читатель может разобраться и сам.

Конец примера 3.7.1.

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

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

Дело в том, что логически23 эти функционалы соответствуют абстрактным математическим понятиям, а, как показано Оревковым (см. [63]), применение таких понятий может сократить рассуждение в башню экспонент раз.

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

Поэтому возникает вопрос о том, какие минимальные операции нужны для работы с функциями? Конечно же, это композиция функций (эту операцию не позволяет в общем виде естественно запрограммировать ни C++, ни Pascal, ни Ada, ни Алгол-68).

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

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

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

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

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

Рассмотрим один такой пример.

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

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

Любое расширение указанного нами минимального множества операций над функциями с большой вероятностью ведет в ту же пропасть неэффективности.

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

Это теоретическое рассмотрение в совокупности с другими, подобными ему, приводит к выводу: функциональное программирование и циклы концептуально противоречат друг другу.

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

Наиболее богатый опыт и развитые традиции функционального программирования имеет язык LISP. Методы составления LISP-программ вполне сложились, и можно подвести некоторые итоги. Стиль программирования на LISP’е не удалось погубить даже внедрением совершенно чуждого функциональности присваивания. В то же время, этот стиль оказался гибок по отношению к освоению новых концепций, когда они не противоречат базовым средствам языка: и абстрактные типы данных, и объектная ориентированность вполне успешно прививаются на стройное дерево списочной структуры LISP’а.

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

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

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

ОБЪЕКТНО-ОРИЕНТИРОВАННЫЙ ПОДХОД

§ 3.8.

В современном программировании объектно-ориентированный подход (ООП) является одним из популярнейших. Он превратился в стандарт во многих фирмах и во многих сообществах программистов. Средства для поддержки ООП вошли практически во все профессиональные системы проГЛАВА 3. ПРОГРАММИРОВАНИЕ С ПТИЧЬЕГО ПОЛЕТА граммирования.24 Этот стиль вместе с соответствующими организационными нововведениями позволил резко повысить эффективность коллективной работы программистов.

Конечно же, при этом ООП рекламируется как универсальное средство.

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

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

Пример 3.8.1. Имея тип объектов TPoint, выражающий точки двумерного пространства, мы можем даже и не знать, в какой системе координат представлены эти точки. Важно, что у нас должен быть метод вычисления декартовых координат точки и метод задания точки ее декартовыми координатами.

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

Конец примера 3.8.1.

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

Присваивание функций вместо присваивания данных выводит лишь на второй уровень функциональной абстракции, но каждый из этих уровней дает экспоненциальный выигрыш в выразительных средствах. Правда, этот выигрыш в полной мере проявляется лишь для достаточно больших и сложных Поэтому мы не приводим примеров. В частности, системы Delphi и Visual C++ просто навязывают элементы ООП уже при создании заготовки новой программы, что обучающиеся наверняка уже видели на собственном опыте.

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

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

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

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

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

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

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

ственное, что с гарантией сохраняется — имена понятий. Когда говорят о конкретизации объекта, фактически речь идет о смене ролей. Система программирования, основанная на объектах и их ролях, была реализована в языках SMALLTALK и PLASMA. В последнем из них объекты так и назывались актерами. Эта система и была воспринята ООП. Поскольку система ролей очень хорошо подходит для описания взаимодействия человека и программной системы и для описания поведения программной системы в человеческой среде, ООП оказалось успешным методом проектирования систем по заказу, для нужд непрофессионалов, и позволило повысить производительность труда в данной отрасли программирования порою в десятки раз. Далее, поскольку при изменении задачи меняются роли, ООП позволило быстро перестраивать достаточно сложные программные системы при изменении требований заказчика. Уже эти два преимущества показывают практическую ценность ООП.

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

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

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

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

Очень важной стадией развития ООП является объектно-ориентированное проектирование (дизайн) (ООД). Здесь система описывается с нескольких сторон, сначала со стороны пользователя (диаграммы использования), потом со стороны данных (диаграммы классов) и с других сторон реализации (диаграммы состояний и т. п.) Поддерживать целостность системы описаний и переходить от диаграмм к прототипам программ позволяет система UML (Unied Modelling Language). Это уже не язык программирования, а язык формализованных спецификаций программ.

ТРИ ТЕХНОЛОГИЧЕСКИХ СТИЛЯ ПРОГРАММИРОВАНИЯ

§ 3.9.

Рассмотренные в предыдущих разделах стили программирования относятся к уровню методик (см. сноску 1 на стр. 108). Для следования этим стилям необходимы определенные условия, связанные со спецификой решаемой задачи, выбранного языка или что-либо иное, характеризующее методику данного стиля. Это необходимые, но, разумеется, недостаточные условия, выполнение которых делает возможным адекватное применение стиля. Настоящий параграф посвящен несколько иным стилям, зависящим не столько от языков и от задач, сколько от программного и технологического окружения программиста.

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

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

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

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

стиль специализирующего программирования.

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

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

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

Иногда накопленный опыт может быть перенесен на другие модели без потерь и даже с ощутимыми выгодами, ищите эти возможности!

3.9.1. Программирование от переиспользования Может показаться странным, что в обзоре стилей мы не выделили специально модульное программирование. В самом деле, в программистском обиходе часто употребляется выражение «модульный стиль программирования». Однако если разобраться, то становится очевидным следующее.

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

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

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

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

Стиль от переиспользования характеризуется тем, что при составлении программы стремятся максимально использовать то, что уже сделано — самим программистом, его коллегами или же вообще где-либо. В идеале на смену программированию как кодированию алгоритмов должно прийти программирование как сборка из заранее заготовленных блоков — сборочное программирование. Этот термин введен одним из соавторов в статьях [58, 59, 60]. Г. С. Цейтин отделил это понятие от теоретических рассмотрений и представил его в работе [80] с чисто программистской стороны. Заметим, что практика математики уже давно отказалась от построения новых теорем (соответствующих в информатике программам) и новых понятий (соответствующих абстрактным типам данных) с самого начала. Она весьма профессионально переиспользует ранее полученные результаты. Но в математике из-за концептуального единства системы понятий и строгих критериев обоснованности не возникает проблемы совместимости новых версий, которая зачастую губит попытки не просто переиспользования, но и просто использования старых программ.

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

Рассмотрим две реальные ситуации, которые демонстрируют разработку, не ориентированную и ориентированную на переиспользование. В первой ситуации действует программист, работающий с очень развитой системой, в которой “есть все”. Тем не менее, он пишет свою процедуру лексикографического упорядочивания строк, потому что «легче самому написать, чем найти,

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

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

Вторая ситуация — другая крайность. Программисту на Java потребовалось построить синтаксический анализ. На вопрос о том, как он это делает, получен ответ: «Зачем это знать? У меня есть пакет JavaCC, который все делает, как надо!». Вместе с тем дальнейшие расспросы показали, что этот программист не представляет себе даже того, какого типа метод анализа поддерживает JavaCC, и, следовательно, ничего не может сказать о том, как задание грамматики для данного пакета связано с эффективностью анализа.

Узнав возможные варианты, программист призадумался, но ничего менять не стал. Почему? Ответ простой: «Так ведь все уже работает!». Короче говоря, качество использования готовых компонентов системы зависит от знания о них. Ситуация опять-таки та же самая, что в математике, особенно в прикладной. Квалифицированное использование теоретических результатов требует знания соответствующей теории, а порою и идей доказательств результатов (поскольку в реальной ситуации предположения теории никогда не выполняются точно). Глубина требуемого знания различна: иногда достаточно общего представления, как, например, при использовании математических функций, иногда нужны сведения о принципах реализации, но всегда можно указать необходимый уровень знакомства с переиспользуемым.

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

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

Конечно, переиспользованию способствует применение развитых и выразительных языков. В частности, экранирование в них реализационных деталей позволяет легче переносить программы из одной операционной обстановки в другую (перенос и переиспользование — различные задачи, но в некоторых аспектах они пересекаются). Способствует переиспользованию повышение уровня понятий языка, хотя бы до второго-третьего типа (объектТРИ ТЕХНОЛОГИЧЕСКИХ СТИЛЯ ПРОГРАММИРОВАНИЯ ная ориентированность языка). Иногда ООП помогает также возможностями наследования свойств и методов объектов (но часто в самых критических ситуациях плохо концептуально продуманная концепция наследования столь же сильно и мешает). Все это — зародыши поддержки стиля программирования, нацеленного на переиспользование. Его можно придерживаться или нет в зависимости от ситуации, от собственных склонностей, от уровня знаний о среде программирования, уровня знаний и умений самого программиста (тот, кто способен подняться до уровня метода, склонен к переиспользованию, а тот, кто не может подняться выше тактического планирования, обычно избегает его) и других обстоятельств. С другой стороны, сложившаяся практика в значительной степени препятствует переиспользованию (обстоятельный обзор препятствий, не потерявший актуальности до сих пор, выполнен Г. С.

Цейтиным в уже указанной работе [80]), а уровень систем поддержки еще недостаточно высок и неадекватен общей задаче применения данного стиля.

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

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

a) главная характеристика стиля от переиспользования: предпочтение поиска кандидатов на внедрение в программу самостоятельной разработке;

b) стремление к исследованию существующих кандидатов, к выявлению в них особенностей, полезных или вредных для решаемой задачи;

c) попытки адаптации своего решения для осуществимости внедрения (здесь могут появляться навязанное структурирование данных, конверторы и др.);

d) сопоставление и оценка вариантов внедрения и самостоятельной гипотетической разработки;

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

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

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

a) необходимо уделять особое внимание документированию (лучше всего, самодокументированию) переиспользуемых компонентов;

b) необходим серьезный анализ того, что кандидаты на переиспользование могут быть отнесены к типовым приемам программирования, т. е. имеют достаточно широкую для использования в дальнейшем область применимости; c) нужно прорабатывать варианты не только варианты полного переиспользования компонентов as is, но и частичного их переиспользования в виде шаблонов, готовых фрагментов и т. п., когда требуется настройка компонента (здесь опять прослеживаются связи с программированием от образцов);

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

e) необходима оценка эффактивности применения компонента;

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

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