НАУКА и ОБРАЗОВАНИЕ

А. А. Букатов, канд. техн. наук, Ростовский государственный университет

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

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

Введение

В современной технологии программирования существует целый ряд методов разработки программ, в которых вновь создаваемые программы строят путем преобразования некоторых существующих исходных текстов, представленных на том или ином языке программирования или спецификации, в исходные тексты требуемых программ, представленные на требуемом языке программирования. К числу таких методов относятся, например, многие методы синтеза программ по их спецификациям, метод смешанных вычислений [2], методы переконструирования (reengineering) и обратной разработки (reverse engineering) программ [3], методы распараллеливания последовательных программ и пр.

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

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

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

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

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

1. Язык непроцедурного описания преобразований программ

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

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

В качестве формы внутреннего представления программы используется графовая структура, построенная на основе атрибутированного дерева абстрактного синтаксиса программы [9] путем добавления в него дополнительных помеченных дуг, представляющих различные семантические связи между соединяемыми этими дугами синтаксическими объектами (вершинами дерева), и добавления некоторых дополнительных технологических объектов, таких, например, как представленные в специальном виде графы потока управления, и информационных зависимостей программы. Преобразуемые программы в их внутреннем представлении хранятся в специальной объектно-ориентированной (00) БД [10], язык запросов которой предоставляет развитые возможности идентификации объектов путем спецификации абсолютных или относительных путей к этим объектам в графе внутреннего представления программы. Выражения на указанном языке могут использоваться в качестве идентифицирующих выражений компонентов входного и выходного образцов. Это обеспечивает, с одной стороны, выразительные средства описания связей между компонентами многокомпонентных образцов, и с другой стороны, возможность эффективной реализации поиска программных конструкций, сопоставимых с компонентами входного образца.

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

rule имя-правила (параметры-правила): входной-образец

&& условие-применимости

= > выходной-образец end

В отличие от других языков трансформаций программ [1] допускаются составные (многокомпонентные) образцы, а также расширен набор средств, которые могут быть использованы при описании простого образца (компонента составного образца). Описание простого образца включает идентифицирующее выражение на языке запросов к ОО БД (в простейшем случае — это имя синтаксического типа соответствующей программной конструкции), схематическое изображение образца (исходный текст программной конструкции, параметризованной по некоторым вложенным конструкциям) и, возможно, правила вычисления вспомогательных параметров. Каждый из параметров схемы простого образца задается его именем и синтаксическим типом. Если другие компоненты входного или выходного образца идентифицируются путем задания их расположения относительно специфицируемого простого образца (точнее — относительно сопоставленной ему конструкции программы), в описание идентифицирующего выражения включается имя-псевдоним, используемое в дальнейшем для кратких ссылок на конструкцию, сопоставленную с этим образцом. Таким образом, описание простого образца имеет вид: идентифицирующее - выражение [(псевдоним)]: схема-конструкции [; правила – вычисл – спомог - параметров] Здесь и далее квадратные скобки используются как метасимволы, заключающие необязательную конструкцию.

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

(простой-образец [простые-образцы])

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

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

{простой-образец [простые-образцы]}

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

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

2. Примеры непроцедурной спецификации преобразований программ

В данном разделе приводятся примеры непроцедурного описания преобразований программ, применяемых в совершенно различных областях технологии программирования. Первый из этих примеров иллюстрирует применимость предложенного подхода для описания одного из распараллеливающих преобразований программ [11]. Второй пример демонстрирует в упрощенном виде реализацию средствами предложенного языка алгоритма структурного синтеза программ, используемого в ППП ПРИЗ [12] и др.

Описание распараллеливающего преобразования

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

s:=0; ...for i=l to n do s:=s+a[i];

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

rule sum_loop_tr:

(loop_oper (par_loop):

for $i=l to $n do $s:=$s+$a[$i];|

assign_oper(so):$s:=0;|

arr_dcl (adcl):$a:array[1..$n] of $type)

&& precedes(so, loop tr) &

unchanged_between($s, so, loop_tr) & even($n)

=> (after(adcl):$b:array[1..$n/2] of $type) I

instead(par_loop):

for   $i=l   to   $n/2   do   $b[$i]:=$a[2*$i-l]+$a(2*$i];

for  $i=l  to  $n/2  do  $s:=$s+$b[$i])

end

В приведенном правиле составной входной образец содержит три простых образца, сопоставляемых соответственно с преобразуемым оператором цикла, оператором присваивания начального значения переменной—сумматору, и оператором описания суммируемого массива. Имена указанных переменной и массива являются параметрами первого простого образца и подставляются во второй и третий образцы соответственно. Все эти образцы имеют однотипные идентифицирующие выражения, включающие имя синтаксического типа соответствующей программной конструкции (loop_oper, assign_oper, arr_dcl) и имя-псевдоним, предназначенное для обеспечения возможности ссылаться на сопоставленные объекты в предикатах условия применимости правила и в выходном образце. Рассмотренное правило приведено в несколько упрощенном виде: для краткости не указаны синтаксические типы параметров, не учтен случай нечетного значения константы $n. Тем не менее, правило иллюстрирует достаточно высокую выразительность предложенного языка.

Реализация алгоритма структурного синтеза

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

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

(list_of_inputs) module_name —> (list_of_outputs);

а задача ставится следующим оператором:

find (list_of_outputs) by {list_of_inputs) ;

Тогда следующий сценарий реализует упрощенный алгоритм структурного синтеза программ:

scenario struct_synth (probl_stat, mod_seq);

results, inputs, temp, back_tmp, mod_in, mod out:

set of name;

tmp_mod_seq, mod_seq: sequence of name;

rule init_synth:

probl_stat: (find ($list_of_outputs) by

($list_of_inputs))

= > (sequence_to_set {$list_of_outputs, results);

back_tmp : = results; sequence_to_set

($list_of_of_inputs), inputs);

tmp : = inputs); tmp_mod_seq : = mod_seq : = empty)

end;

rule synth_forward: module:($in_list) $m_name —> ($out_list);

sequence_to_set($in_list, mod_in);

sequence_to_set($out_list, mod_out))

&& mod_in c: tmp & mod_out \ tmp 9^0 & results \ tmp *0

= > (tmp : = tmp \j mod_out;

tmp_mod_seq : = tmp_mod_seq I I $m_name) end;

rule cleean_back ($mod_name):

module: ($in_list)$mod_name —> ($out_list);

sequence_to_set ($in_list, rnod_in) ;

sequence_to_set($out_list, mod_out))

&& back_tmp n mod_out Ф 0 = > (back_tmp : = back_tmp и mod_in;

mod_seq : = $mod_name I| mod_seq) end; begin

apply init_synth;

apply all synth_forward;

for all $mod_name from tmp_mod_seq backward apply cleean_back ($mod_name);

end

В этом сценарии правило init_synth используется для инициализации работы алгоритма структурного синтеза программ, состоящей в присваивании начальных значений нескольким переменным типа "множество". Правило synth__forward, многократно вызываемое оператором асинхронного применения applyall, реализует прямой проход планировщика [11], обеспечивающий генерацию последовательности вызова модулей, решающей поставленную задачу. Правило cleean_back, циклически применяемое к элементам последовательности tmp_mod_seq, реализует обратный ход планировщика, обеспечивающий оптимизацию сгенерированной на предыдущем шаге последовательности путем исключения из последовательности вызовов ненужных модулей.

3. Организация системы автоматизации преобразований программ

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

·         выполнение преобразования исходных текстов программ во внутреннее представление этих программ в 00 БД и обратно;

·         поддержку создания правил и сценариев трансформации;

·         автоматическое выполнение трансформаций программ.

Средства преобразования исходных текстов во внутреннее представление и обратно допускают настройку на синтаксис используемых языков программирования, на вид атрибутированных деревьев абстрактного синтаксиса и на состав и способ создания семантических связей между синтаксическими объектами. Синтаксис языка задается L-атрибутной [9] грамматикой, представленной в БНФ-подобном виде. При настройке рассматриваемых средств на требуемый язык программирования правила грамматики компилируются в подпрограммы (функции) на языке Си, выполняющие разбор и порождение соответствующих конструкций. Это позволяет использовать для описания атрибутов нетерминальных символов, правил вычисления атрибутов и правил порождения семантических связей и вспомогательных технологических объектов соответствующие средства языка Си, включающие программные интерфейсы к средствам языка манипулирования данными 00 СУБД [10]. На основе компилируемых правил грамматики строятся также некоторые дополнительные программные структуры, используемые в других подсистемах системы преобразования программ.

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

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

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

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

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

·         проверка корректности совместного (асинхронного) применения всех правил множества;

·         выполнение трансформаций в соответствии с выходными образцами правил.

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

Средства автоматизированного выполнения трансформаций предоставляют программный и интерактивный интерфейсы для выполнения (применения) сценариев, правил и множеств правил трансформации.

Предложенный язык непроцедурного описания преобразований программ и создаваемые средства автоматизации выполнения соответствующих трансформаций могут быть использованы для создания на их базе различных систем преобразования программ. Автор и его коллеги разрабатывают основанную на рассмотренных средствах систему автоматизации распараллеливания последовательных программ [11]. Кроме того, предполагается использовать эти средства для реализации инструментальных систем поддержки каркасного синтеза программ [13] и РД-технологии программирования [14]. Возможно также применение этих средств для построения систем выполнения смешанных вычислений [2], структурного синтеза программ [12], а также других систем преобразований программ, в том числе систем, основанных на совместном использовании нескольких различных методов преобразования программ.

Список литературы

1. Partch H., Steinbruggen R. Program transformation systems // ACM Computer Survey, 1983, v. 15, N 3. P. 199-236.

2. Ершов А. П. Трансформационный метод в технологии программирования // Тез. докладов 1-й Всесоюзной конференции "Технология программирования", Пленарные доклады. Киев, 1979. С. 12-26.

3. Communications of the ACM. Special Issue on Reverse Engineering, v. 37. N 5, 1994.

4. Касьянов В. Н. Трансформационный подход к конструированию и оптимизации программ // Смешанные вычисления и преобразования программ. Новосибирск, 1991. С. 30—43.

5. Markosian L., Ncwcomb P., Brand R., Burston S., Kitz-miller T. Using an Enabling Technology to Reengineer Legacy Systems, Communications of the ACM, 1994, vol. 37, N 5. P. 58—70.

6. Baxter I. D. Design Maintenance System. Communications of the ACM, 1992, vol. 35, N 4. P. 73-89.

7. Фуксман А. Л. Технологические аспекты создания сложных программных систем. М.: Финансы и статистика, 1979. 184 с.

8. Евстигнеев В. А., Спрогис С. В. Векторизация программ (обзор) // Векторизация программ: теория, методы, реализация. М.: Мир, 199L. С. 246-267.

9. Льюис П., Розенкранц Д., Стирнз Р. Атрибутные трансляции // Семантика языков программирования. М.: Мир, 1980. С. 162—195.

10. Bukatov A., Zastavnoy D. High-level navigational language for querying complex data objects and its applications to CASE systems // Proc. of the 3rd Joint Conference on Knowledge-Based Software Engineering Smolenice, Slovakia, Sept. 9—11, 1998 (to be published).

11. Букатов А. А., Лазарева С. А., Жегуло О. А. Непроцедурное описание распараллеливающих преобразований программ // Тез. докладов VII Всероссийской школы-семинара "Современные проблемы математического моделирования", Ростов-на-Дону, 1997. С. 27—29.

12. Кахро М. И., Калья А. П., Тыугу Э. X. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). М.: Финансы и статистика, 1981. 158 с.

13. Горбунов-Посадов М. М. Конфигурации программ. М.: Малип, 1994. 270 с.

14. Абрамович С. М., Литвиненко А. Н. РД-модульность и РД-система программирования // Методы трансляции и конструирования программ. — Новосибирск: ВЦ СО АН СССР, 1986. С. 285-

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 2, 1999

ПРОГРАММИРОВАНИЕ И ОПЕРАЦИОННЫЕ СРЕДЫ

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