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

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

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

165

(даже сами профессионалы им пользуются). Это — подход к разработке про-

грамм по заданным заранее шаблонам. Это скорее целый набор “вырожден-

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

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

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

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

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

ется фрагмент, который можно рассматривать как черный ящик, то ничего,

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

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

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

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

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

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

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

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

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

мой программы. Если образец специально создается для данной программы,

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

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

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

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

ния от образца, получившую название макетирования (см. ниже). В данном

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

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

исключением, чем правилом: чаше всего трудно провести границу между са-

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

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

рования от образцов:

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

кое-что изменить. Точно известно, в каких местах нужно это изменять.

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

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

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

стали включать и в руководства по ООП.

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

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

166

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

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

нение содержательно описанного алгоритма, порождающего програм-

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

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

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

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

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

программа пишется обычным образом. Это один из распространенных

способов работы и профессионалов, и полупрофессионалов, и диле-

тантов.

• Программирование от макета. Разработчики быстро готовят прототип,

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

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

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

няется (например, макет был написан на языке

Prolog

, а окончательная

программа на

Java

). Макет (особенно в системах, поддержиывающих

его представление в графической форме, таких, как

UML

[50]) часто

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

• Предоставляется технологический фрейм:нечто,для чего известны сло-

ты, т. е. позиции (пункты, пустые значения того или иного типа, в

том числе и процедурного) которые требуется заполнить. В результате

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

задана. Это, собственно говоря, и есть программирование от образца в

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

правлений:

– семантические сети искусственного интеллекта;

– фирменная методика и технология,которая погружает один из пред-

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

ментов. Пример

RUP

[88];

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

ном пособии;

– компонентное программирование, например,с использованием

XML

или иного языка разметки (которая задает фрейм), и языка обра-

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

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

167

жаргоне, на парсер и обработчик). Это как раз то, что дает объ-

ектная модель документа.

• Предоставляется технический фрейм, т. е. то, что нужно заполнять. Он,

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

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

ант предыдущего подхода. Вообще говоря, неясно, программирование

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

Forms

из

Oracle

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

зультат — все равно программа.

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

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

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

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

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

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

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

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

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

методологии.

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

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

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

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

поненты, — это все то, что предоставляется шаблоном или фреймом, а пото-

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

условий здесь нет и речи. Именно за счет строгой локализации всего, с чем

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

и качество его работы.

3.9.3. Специализирующее программирование

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

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

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

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

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

168

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

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

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

ющих и оптимизирующих преобразований. Заметим, что в данном случае

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

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

жат общая программа и дополнительные знания.

Эта идея в точности соответствует анализу работы специалиста, овла-

девшего уровнем метода. Он освоил некоторую высокоуровневую структуру

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

частных случаях. Фантастическая производительность и эффективность экс-

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

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

тегию работы в информационной системе.

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

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

форматором не удается. Главная трудность здесь связана с тем, что суще-

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

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

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

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

Это соответствует известным теоретическим результатам о том, что методы,

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

иерархии типов знаний, а проблема унификации и даже конкретизации не-

разрешима уже для понятий второго порядка.

Тем не менее даже частные

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

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

поколения, ученики!

Рассмотрим подход к специализации, принятый в нынешней теории. Он

показывает и возможности, и подводные камни.

Программа, у которой нас интересует лишь результат, а не конкретные

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

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

∀x (A(x) ⇒ ∃y (C(y)&B(x, y))).

Здесь x — входная структура данных программы, y — выходная структура

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

выше первого типа в современных программных системах нет.

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

169

данных, A — условие на вход (предусловие), C — область выходных данных,

B(x, y) — связь вход-выход. C(y)&B(x, y) называется выходным условием

(или постусловием) программы. При специализации программы мы можем

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

Попущения специализации

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

ленному множеству входных данных.

b) Расширить область выходных данных, чтобы дать возможность искать ре-

шение в более либеральных условиях.

c) Ослабить связь между входом и выходом.

Все эти три попущения могут применяться вместе. Частными случаями их

являются добавление входных данных и удаление части выходных данных.

Как показано в работе [61], при специализации у нас возникают следую-

щие основные преобразования:

1. Cпециализация элементарных действий: замена вызова некоторой

процедуры либо метода на вызов более эффективной и лучше подходя-

щей в данном частном случае процедуры.

2. Удаление вариантов и (или) действий, которые стали избыточны из-

за лучше обусловленного условия или более либерально поставленной

цели.

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

достигли удовлетворительного результата намного раньше,и значитель-

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

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

мененная подпрограмма (на сей раз наша, а не заимствованная) может

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

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

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

щие части которого порождают операторы и описания программы, то общая

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

образования доказательств (чистки и нормализации). Но даже теоретически

170

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

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

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

точности и детальности спецификаций, превращающих программу в дока-

зательство. Далее, специализация элементарных действий и следующие три

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

существенно зависит от их порядка. Поэтому задачу специализации необхо-

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

Частный случай специализации, лучше всего исследованный в современ-

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

щем.

Попущение специализации состоит в уточнении (обычно в полной фикса-

ции) части входных данных. Считается, что универсальный алгоритм содер-

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

его специализациям. Все множество таких вычислений записано в неявном

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

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

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

лить из общего решения ту и только ту часть алгоритма, которая относится к

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

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

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

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

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

смотрением программы как функции, отображающей вектор входных дан-

ных в вектор выходных (см. [33]). Если входные данные обозначить как

выходные как

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

обозначить

, то можно

записать

→

Если

, причем значения аргументов из

фиксированы (для

определенности,

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

программу, вычисляющую функцию



(

) =

(

)

Более строго задача смешанных вычислений формулируется следующим обра-

зом.

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

171

Пусть для языка

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

теля

, который для любой программы

и начального состояния памяти

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

(

Иными словами, существует вычислительный автомат, исполняющий про-

граммы на данном языке.

Смешанным вычислением в языке

называется любой частично-опре-

деленный алгоритм

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

и на-

чального состояния памяти

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

стоянию памяти

(

) и к некоторой остаточной программе

(

), где

удовлетворяют следующему равенству:

(

) =

(

)).

(Принцип частичного вычисления).

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

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

стоянии. Смешанное вычисление корректно, если на начальных состояниях

определено отношение частичного порядка

, означающее, что состоя-

ние памяти

является частью

, и

(

) v

всегда, когда определено. Сравните этот подход с подходом к определению

рекурсии в Придожении А!

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

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

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

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

виальны. Мы можем, например, не знать конкретного значения некоторого

поля, но иметь информацию о нем, например, что оно положительно.

Пусть у нас есть отношение пополнения между данными ⊆v

. Напри-

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

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

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

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

жать больше информации, чем исходное данное.

172

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

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

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

данное поле находится в интервале между 0 и 5, то число, подставленное

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

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

ных

, таких, что

, выполнено



и имеются такие данные

что

∪

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

любых полностью заданных, их расширяющих.

Пусть дан класс X частичных данных. Смешанное вычисление является

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



и класса частичных данных X, если есть алгоритм

PEV

(

), опре-

деленный для каждой программы P ∈ P и для каждой пары данных



∈ X, такой, что выполнены равенства:

(

) =

((

PEV

(

)

, (

PEV

(

)

∪ (

PEV

(

)

А вот это математическое определение прочитайте и разберитесь в нем сами!

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

он неконкурентоспособен на мировом рынке, особенно после 30 лет.

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

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

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

чает действий в фон Неймановской модели, сравните наше определение с

описанием теории рекурсивных схем в § A.6. Задача специализации состоит

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

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

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

Пример 3.9.1. Пусть требуется построить программу, вычисляющую функ-

цию λX. X

. Это означает, что программа должна работать для любых зна-

чений X и для конкретного фиксированного значения n. Начнем со следу-

ющей более универсальной программы, реализующей функцию λX, n. X

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

граммы, касающийся существа дела):

Программа 3.9.1

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

173

Y := 1;

while n>0 do

begin if n MOD 2 = 1

then begin Y :=Y * X; n := n - 1 end;

n := n DIV 2; X := X * X

end

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

дующую программу, вычисляющую функцию Y = X

, т. е. частичную про-

грамму для конкретного значения n = 5 и неопределенного значения X:

Y := X; X := X * X; X := X * X; Y := Y * X

(3.1)

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

рию вычисления программы 3.9.1 для n = 5:

{1} Y := 1;

{2} ( n > 0 )

равно

TRUE:

{3} n MOD 2 = 1

равно

TRUE:

{4} Y := Y * X; n := n - 1; n := n DIV 2; X := X * X;

{5} ( n > 0 )

равно

TRUE:

{6} n MOD 2 = 1

равно

FALSE:

{7} n := n DIV 2; X := X * X;

{8} ( n > 0 )

равно

TRUE:

{9} n MOD 2 = 1

равно

TRUE:

{10} Y := Y * X; n := n - 1; n := n DIV 2; X := X * X;

{11} ( n > 0 )

равно

FALSE

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

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

операторами линейной программы (строки 1, 4, 7, 10 истории, в которой

остальные строки отражают вычисления управляющих условий). При этом

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

ным образом, если значения, входящих в них переменных определены (за-

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

татов вычисления самих себя, т. е. выполняются ‘литерально’. Иными сло-

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

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

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

174

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

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

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

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

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

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

Применение этих интуитивных соображений к приведенной выше исто-

рии приводит к следующей частичной истории:

Y := 1;

( n > 0 )

равно

TRUE:

NOT ODD (n)

равно

TRUE: n := n - 1; n := n DIV 2;

( n > 0 )

равно

TRUE:

NOT ODD (n)

равно

FALSE: n := n DIV 2;

( n > 0 )

равно

TRUE:

NOT ODD (n)

равно

TRUE: n := n - 1; n := n DIV 2;

( n > 0 )

равно

FALSE

и следующей остаточной программе

Y := 1 * X; X := X * X; X := X * X; Y := Y * X; X := X * X

(3.2)

очень близкой к программе (3.1).

Первый оператор программы (3.2) отличается от своего прообраза заме-

ной терма

на его значение. Следует заметить, что замена его на

Y:= X

воз-

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

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

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

стичного вычисления. Последний оператор является избыточным. Это мож-

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

стичного вычисления.

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

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

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

Остаточная программа может оказаться короче или длиннее исходной, но она

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

Еще одно замечание.Решение ‘заморозить’

в программе 3.9.1 было про-

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

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

их термы зависели от замороженной переменной