Новые встроенные средства расширения языка Planning C

Пекунов Владимир Викторович доктор технических наук Инженер-программист, ОАО "Информатика" 153000, Россия, Ивановская область, г. Иваново, ул. Ташкентская, 90 Pekunov Vladimir Viktorovich Doctor of Technical Science Software Engineer, JSC "Informatika" 153000, Russia, Ivanovskaya oblast', g. Ivanovo, ul. Tashkentskaya, 90 pekunov@mail.ru Другие публикации этого автора

В ходе разработки программного обеспечения на C++ и иных производных от него языках нередко возникают проблемы, связанные с необходимостью многократной записи каких-либо достаточно громоздких алгоритмических конструкций, которые невозможно или затруднительно оформить в виде функции или макроса. Примером такой конструкции является, например, цикл с возможностью обработки прерывания (break) после цикла, или вложенный цикл с возможностью выхода по прерыванию на произвольный уровень такого цикла. В таких случаях весьма полезны были бы какие-либо схемы оперативного расширения языка, которые не требовали бы внедрения таких расширений на уровень компилятора (как это делается, например, в проектах, основанных на Clang), а ограничивались бы прямой переработкой исходного текста программы, то есть текстовыми трансформациями. Трансформации могут быть:

а) прямыми вида «текст->текст» (здесь обычно работа идет на уровне текстовых шаблонов с переменными),

б) опосредованными вида «текст->поток лексем->текст» (здесь также могут использоваться текстовые (или записанные с применением некоторой грамматики) шаблоны, либо процедурные описания алгоритмов трансформации),

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

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

В качестве программ-трансформеров упомянем Stratego/XT (^[1], преобразования «текст->абстрактное синтаксическое дерево->текст», причем дерево представляется в текстовой списковой форме), TXL (^[2], подход близок к «текст->поток лексем->текст» с применением шаблонов на базе грамматик), DMS Software Reengineering Tolkit (^[3], используется шаблонный подход «текст->текст», также возможны элементы процедурной обработки на Паскаль-подобном языке) и некоторые отечественные разработки на базе шаблонов «текст->текст» ^[4] и на базе манипуляций с абстрактным синтаксическим деревом исходного текста ^[5].

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

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

В языках Rust ^[6] и Nemerle ^[7] существуют декларативные макросы, выполняющие некоторый код для выражений, соответствующих заданному шаблону, а также процедурно-синтаксические макросы, принимающие поток лексем (читается напрямую или разворачивается в абстрактное синтаксическое дерево) и выполняющие некоторый код, который генерирует замещающий поток лексем.

Язык Scala ^[8] имеет в составе процедурно-синтаксические макросы, фактически работающие с абстрактным синтаксическим деревом аргументов макроса, заменяющие собственный вызов на настраиваемый выходной фрагмент, встраиваемый в дерево программы вместо исходного фрагмента. Как и в PL/1, недостатком данного подхода является ориентированность на близкий к процедурному синтаксис.

Enhanced C# ^[9] содержит LeMP – систему макросов, которые либо используют шаблоны кода с параметрами, либо содержат исполняемый на этапе компиляции код, работающий с абстрактным синтаксическим деревом. Также содержит LLLPG – систему генерации лексических анализаторов на базе regexp-подобных выражений, содержащих встраиваемый C#-код.

Подводя итоги данного краткого обзора, следует отметить, что подходы на основе входных параметризованных шаблонов или входного процедурного синтаксиса не позволяют описывать сложные многозвенные входные конструкции, существенно отличающиеся по синтаксису от исходного языка. В то же время, подходы, ориентированные на работу с абстрактным синтаксическим деревом такие конструкции описать позволяют, но являются достаточно сложными для программирования. Достаточно оптимальным представляется подход, в котором первичное выделение конструкции осуществляется по схеме, схожей с LLLPG (на базе некоторой разновидности регулярных выражений, например, регулярно-логических выражений (см., например, ^{[10, 11]}), позволяющих выйти за рамки регулярных грамматик), а дальнейшая генерация кода выполняется процедурно-синтаксическими макросами по типу реализованных в Rust и PL/1.

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

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

Механизм реализации расширений. Улучшенная схема препроцессинга

Заметим, что вводимые синтаксические конструкции могут потребовать взаимного согласования даже в случае их «разбросанности» по коду программы, например, с целью выбора оптимального алгоритма реализации или для оперативной инициализации некоторых новых вспомогательных переменных/констант. Учитывая, что в Planning C дедуктивные макромодули, которые обычно выполняют оперативный синтез кода, пишутся на языке GNU Prolog, имеет смысл реализовать коллективное согласование макромодулей, реализующих «компиляцию» новых конструкций, через единую базу фактов GNU Prolog. При этом следует учитывать линейный характер анализа программы – необходимо обеспечить возможность конструкциям, идущим выше по тексту, согласовывать свое поведение с конструкциями, идущими ниже по тексту. Наиболее простой реализацией данного процесса может быть многократное выполнение препроцессинга с сохранением единой базы фактов между стадиями.

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

Сканер имеет в своем составе три регулярно-логических выражения ^{[10, 11]}: левый контекст, основное и правый контекст. Текст программы должен просматриваться сканером, который находит фрагменты, подпадающие под конкатенацию вышеупомянутых трех выражений, и, либо заменяет фрагмент, соответствующий основному выражению, вызовом дедуктивного макромодуля (который позднее будет развернут в некий программный код), характерного для языка Planning C, либо, не производя замены, лишь помещает некий дополнительный факт (который прочие макромодули будут учитывать в своей работе) в общую базу фактов. Необходимо сразу заметить, что, хотя синтаксис программы обычно не сводится к регулярным грамматикам, программа вполне может быть разобрана (хотя бы в большинстве случаев) с выделением новых конструкций, с помощью регулярно-логических выражений, которые могут широко использовать различные подключаемые внешние предикаты, выполняющие сложные виды парсинга. В частности, для разбора конструкций, упоминаемых в данной работе, потребовался лишь один такой внешний предикат BAL, определяющий, является ли его аргумент сбалансированным по различного вида скобкам выражением.

Исходя из вышеизложенного, необходимо реализовать в Planning C новую схему препроцессинга:

1. Пусть задано требуемое максимальное количество циклов препроцессинга K. Также задан исходный текст программы.

2. Первая фаза. Анализируется весь текст программы с исполнением директив препроцессора и выполнением макроподстановок в стиле C++.

3. Вторая фаза. Просматривается весь полученный к данному моменту текст программы, обнаруживаются все сканирующие макросы (в стиле Planning C) и директивы, устанавливающие используемые сканеры, режим и порядок их применения. Далее сканирующие макросы применяются к полученному на данный момент тексту программы в режиме парсинга или сканирования (будут рассмотрены далее). Найденные выражения заменяются на обращения к макромодулям или на пустые строки (с генерацией GNU Prolog-факта).

4. Третья фаза. Полученный текст программы просматривается еще раз — собирается таблица именованных констант и осуществляется поиск обращений к макромодулям, для которых выполняются подстановки значений констант в параметры (если параметром макромодуля является выражение, то оно вычисляется). Далее в точках обращений к макромодулям генерируется программный код. Для этого, если тело макромодуля содержит цели, формируется GNU Prolog-программа, в которую включаются библиотечные предикаты (характерные для Planning C), предикаты и цели (поочередно) макромодуля. Сгенерированный код логической программы обрабатывается для каждой цели путем вызова внешнего стандартного интерпретатора GNU Prolog (при этом логическая программа учитывает в своей работе имеющиеся в базе факты и, возможно, пополняет эту базу). Полученный при этом консольный вывод вставляется в тело модуля вместо соответствующей цели. После исключения из тела модуля предикатов получаем готовый к вставке в Planning C-программу код.

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

Управление препроцессингом

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

«#» «preproc_passes» «(» макс_число_стадий «)»

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

а) применение в режиме сканирования. Добавление сканеров в список:

«#» «add_scan» «(» идентификатор_сканера {«,» идентификатор_сканера} «)»

Указание исчерпывающего набора сканеров:

«#» «scan» «(» идентификатор_сканера {«,» идентификатор_сканера} «)»

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

б) применение в режиме парсинга. Добавление сканеров в список:

«#» «add_parse» «(» идентификатор_сканера {«,» идентификатор_сканера} «)»

Указание исчерпывающего набора сканеров:

«#» «parse» «(» идентификатор_сканера {«,» идентификатор_сканера} «)»

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

Сканирующие макросы

сканер = «#» «def_pattern» пробелы идентификатор_сканера [пробелы] «=>»

[пробелы] ((«[» идентификатор_факта «]») | идентификатор_макромодуля) [пробелы] «(» [параметры_макромодуля_или_факта] «)» [пробелы] «{» тело_сканера «}» «;»

параметры_макромодуля_или_факта = параметр {[пробелы] «,» [пробелы] параметр}

параметр = строковая_константа_в_апострофах | XPath_выражение | список

список = «[» [параметр {[пробелы] «,» [пробелы] параметр}] «]»

тело_сканера = [левый_контекст] основное_выражение [правый контекст]

левый контекст = регулярно_логич_выражение ПС

ПС = перевод_строки

правый_контекст = регулярно_логич_выражение ПС

основное выражение = «@» «begin» ПС регулярно_логич_выражение ПС «@» «end» ПС

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

XPath_выражение в параметрах указывается, обычно, либо для вызова каких-либо стандартных функций (например, gid(), выдающую уникальный идентификатор найденного фрагмента, соответствующего основному выражению; random() или randomid(), возвращающие, соответственно случайное число и случайный идентификатор), либо для извлечения значений переменных регулярно-логического выражения ^[10]. При этом, если переменная имеет единственное значение, результатом будет скалярное строковое значение, но если переменная имеет множество значений, результатом станет список таких значений, оформленный по правилам GNU Prolog. Если переменная не имеет значения, результатом будет пустая строка.

Апробация

1. Рассмотрим небольшой пример. Предположим, возникла необходимость ввести в язык Planning C цикл while с обработкой прерывания по break, как это сделано в языке Python. Пусть такой цикл имеет общий вид:

while (условие) {

тело_цикла

}

else

обработчик_прерывания

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

Рис. 1. Начальный фрагмент программы со сканирующим модулем

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

#def_module() while_else(GID, COND, BODY) {

@goal:-brackets_off.

@goal:-

write('bool __break'), write(GID), write(' = false;'), nl,

write('while('), write(COND), write(') {'), nl,

write(' __break'), write(GID), write(' = true;'), nl,

write(BODY), nl,

write(' __break'), write(GID), write(' = false;'), nl,

write('}'), nl,

write('if (__break'), write(GID), write(') '), nl.

};

int main() {

int A^[10];

int k = 0;

while (k < 10) {

cin >> A[k];

if (A[k] == 0) break;

k++;

}

else

cout << "Был введен ноль!" << endl;

return 0;

}

2. С применением предложенной в данной работе схемы в язык Planning C был введен ряд расширений:

а) директивы включения мемоизации функций/процедур (void-функций) с генерацией соответствующего вспомогательного кода;

б) анонимные процедуры и функции с планированием повторного входа (ПППВ и ФППВ), транслирующиеся в наборы вспомогательных лямбда-функций и классических ПППВ/ФППВ;

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

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

Выводы

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

В качестве направления дальнейших исследований по данной теме можно отметить следующие:

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

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