The Templet language preprocessor: a programming tool for process-per-message modeling

Full Text

Мотивация. Для большого числа прикладных задач целесообразно представление кода решаемой задачи в виде совокупности процессов, обменивающихся сообщениями. Например, в области высокопроизводительных вычислений такое разбиение служит для эффективного использования ядер и процессоров. В распределенных вычислениях важен протокол взаимодействия объектов при помощи сообщений. В интеллектуальных многоагентных системах необходимы средства описания процедур обработки сообщений в программных агентах. Системы имитационного дискретно-событийного моделирования обычно в качестве событий рассматривают поступление сообщений в процессы и их обработку. Традиционное применение модели «процесс-сообщение» в средстве программирования состоит в разработке специального языка программирования или библиотеки времени исполнения для имеющегося языка. Очевидным недостатком первого подхода является сложность разработки, а второго - сложность применения. Автором предлагается новый подход, основанный на том, что модель «процесс-сообщение» может быть описана на любом языке программирования с пользовательскими типами данных и процедурной семантикой. Для этого необходимо следовать специальным соглашениям на структуру кода. Использование разработанного универсального препроцессора вместе с предметноориентированным языком позволяет автоматизировать кодирование модели «процесс-сообщение» средствами традиционного языка программирования. В работе рассмотрены архитектура и принцип работы препроцессора. Описан синтаксис предметно-ориентированного языка (DSL) для модели «процесс-сообщение» на основе расширенной нотации Бекуса-Наура (EBNF). Семантика языка показана с использованием диаграмм «сущность-связь» (ER) и вербального описания. Приведён пример описания системы процессов. Рас170 Препроцессор языка Templet: инструмент программирования. . . смотрено применение предлагаемого метода, выполнено сравнение с известными аналогами. Метод. Код программы (например, на языке С++) в терминах модели «процесс-сообщение» можно структурировать следующим образом. Во-первых, это библиотека времени исполнения с базовыми классами «процесс», «сообщение», «диспетчер сообщений» и так далее для передачи структуры потока управления. Во-вторых, «связывающий» код, объединяющий библиотеку времени исполнения и код конкретной задачи. В-третьих, собственно типы данных для сообщений и процедуры их обработки. Таким образом, код в терминах модели «процесс-сообщение» будет иметь блочную структуру. Поэтому для его анализа не требуется знать синтаксис языка, а достаточно уметь определять границы блоков. Очевидным способом определения границ блоков является разметка при помощи комментариев. Например, в фрагменте кода bool Parent::hello() { /*$TET$Parent$hello*/ cout<<"Hello world!"; return true; /*$TET$*/ } тело метода Parent::hello() может быть легко извлечено из кода, если препроцессору известны сигнатуры комментариев. В примере bool Parent:: hello(){...} - связывающий код, а cout<<"Hello world!"; return true; - код конкретной задачи или пользовательский блок. Структуру связывающего кода и блоков пользователя можно описать в компактной форме на языке модели «процесс-сообщение». При этом само описание может быть также встроено в код в форме комментария: /*$TET$templet$!templet!*/ /* *Parent=+hello(). */ /*$TET$*/. С учётом описанных допущений контроль соответствия структуры кода модели «процесс-сообщение» может быть проведён перед компиляцией. Для этого требуется выполнить следующую трансформацию кода программы. Необходимо извлечь пользовательские блоки и описание структуры кода из программы, а затем (если структура изменилась) генерировать код программы в соответствии с новым описанием структуры, помещая в код извлеченные ранее пользовательские блоки. Как компактно представить структуру кода на DSL-языке модели «процесс-сообщение» и выполнить генерацию кода на целевом языке программирования, показано ниже. Для этого рассматриваются два типа объектов модели - канал и процесс. Описание каналов. Канал описывает протокол взаимодействия при помощи сообщений от двух участников - клиента и сервера. Модель каналов представлена на рис. 1. Модель описывает множество типов каналов (сущностей 171 В о с т о к и н С. В. CHANNEL). Каждый тип канала имеет имя (атрибут channel), однозначно идентифицирующее его. Канал может состоять из нескольких состояний (сущностей STATE). Вышеизложенное описывается правилом EBNF: channel = ’~’ ident [’=’ state {’;’ state}] ’.’. Нетерминал ident соответствует имени типа канала channel на ER-диаграмме рис. 1. Состояния STATE описывают последовательность взаимодействия между двумя участниками - клиентом и сервером. Состояния имеют имя (атрибут state); делятся на два множества - состояние клиента и состояние сервера (атрибут cli_or_srv); одно из состояний определяется как начальное (атрибут is_initial). Если состояние является состоянием клиента, то сообщение передаёт клиент, а принимает сервер. Иначе - передаёт сервер, а принимает клиент. Правило EBNF для состояния имеет вид: state = [’+’] ident [ (’?’|’!’) [rules] ]. Здесь начальное состояние обозначено знаком ’+’; состояние клиента обозначено знаком ’?’ (он задаёт вопрос); состояние сервера обозначено знаком ’!’ (он отвечает на вопрос клиента). Нетерминал ident обозначает имя состояния (state). Наконец, правило, представленное сущностью RULE, описывает, в какое состояние new_state будет выполняться переход при отправке сообщения с именем message из текущего состояния. Сущность RULE задаётся правилом rules = ident ’->’ ident {’|’ ident ’->’ ident}. Идентификатор перед знаком ’->’ обозначает сообщение message, идентификатор после знака ’->’ обозначает новое состояние new_state. Рис. 1. ER-модель каналов [Figure 1. ER model of the channels] Пример синтаксиса каналов. Пусть требуется проверить тождество sin2 x+ + cos2 x = 1. Для этого выполним вычисление квадратов синуса и косинуса одновременно (параллельно) в двух процессах. Взаимодействие между управляющим процессом и процессом, вычисляющим функцию, представим каналом ~Link= +Begin ? agrSin2 -> Calc | argCos2 -> Calc; Calc ! result -> End; End. 172 Препроцессор языка Templet: инструмент программирования. . . Это описание имеет следующую интерпретацию. В начальном состоянии Begin управляющий процесс (в роли клиента) посылает сообщение argSin2 (которое заставляет вычислить квадрат синуса от переданного в сообщении значения) или argCos2 (для вычисления квадрата косинуса). Исполняющий процесс в состоянии Calc (в роли сервера) выполняет вычисление и возвращает результат в сообщении result. После этого обработка заканчивается, так как из состояния End нет исходящих сообщений. Для генерации кода сущности, полученные при синтаксическом анализе, дополняются вычисленными сущностями MESSAGE и NEW_STATE. Сущность MESSAGE объединяет все упомянутые в канале сообщения. Сущность NEW_STATE показывает, в каком состоянии state может передаваться сообщение и в какое состояние new_state затем переходит канал. Вычисленные сущности выделены на рис. 1 рамкой. Генерация кода выполняется путём обхода дополненного дерева ER-модели каналов. Описание процессов. Процесс определяет алгоритм обработки сообщений, поступающих по каналам от других процессов, и ответы на сообщения. Модель процессов показана на рис. 2. Модель описывает множество типов процессов (сущностей PROCESS). Каждый тип процесса имеет имя (атрибут process), однозначно идентифицирующее его. Процесс может состоять из нескольких портов (сущностей PORT) и нескольких действий (сущностей ACTION). Вышеизложенное представлено правилом EBNF: process = ’*’ ident [’=’ ((ports [’;’ actions]) | actions) ]’.’. Порт описывает точку подключения канала к процессу. Он характеризуется идентификатором port; типом подключаемого канала channel; ролью процесса во взаимодействии через данный порт cli_or_srv (клиент или сервер); а также действием alt_action, которое запускается при поступлении сообщения в данный порт, если не выполнены (или не указаны) связанные с портом правила RULE. Правила EBNF для порта имеют вид: ports = port {’;’ port}. port = ident ’:’ ident(’?’|’!’)[(rules [’|’ ’->’ ident])| ( ’->’ ident)]. В правилах комбинация имя-тип порта обозначена как ident ’:’ ident. Знак ’?’ показывает, что сообщения в правилах - вопросы от клиента. Знак Рис. 2. ER-модель процессов [Figure 2. ER model of the processes] 173 В о с т о к и н С. В. ’!’ показывает, что поступающие в данный порт сообщения - ответы сервера. Синтаксис правил для порта аналогичен правилам для каналов. Правила для канала имеют следующую интерпретацию. Слева от знака ’->’ записывается имя сообщения message, поступающего в канал, а справа - имя действия action, которое нужно запустить при поступлении данного сообщения. Действия описывают процедуры обработки поступающих в процесс сообщений и выдачу ответных сообщений. Действия имеют уникальные в пределах процесса имена action. Одно из действий может помечаться как начальное is_initial (оно запустится при запуске программы). Действие может иметь связанное действие on_true_action, запускаемое при успешном выполнении. Также может указываться связанное действие on_false_action, запускаемое при неуспешном выполнении. Связанные действия образуют цепочку неделимых (атомарных) операций обработки поступившего сообщения (или начального действия при запуске программы). Правила EBNF для действий имеют вид: actions = action {’;’ action}. action = [’+’] ident ’(’ [args] ’)’ [’->’ ([ident] ’|’ ident) | ident]. Здесь первый идентификатор задает имя действия action; идентификатор, записанный после знака ’->’, задаёт действие on_true_action; идентификатор, записанный после знака ’|’, задаёт действие on_false_action. Сущность ARGUMENT описывает аргумент действия - сообщение message на заданном порте port, которое может считываться или записываться read_ or_write, а затем отправляться получателю. Правило EBNF для аргумента имеет вид args = ident (’?’|’!’) ident {’,’ ident (’?’|’!’) ident}. Первый идентификатор обозначает порт port; знак ’?’ обозначает (в данном контексте) чтение сообщения; знак ’!’ обозначает запись и отправку сообщения. Имя сообщения message указывается после знаков ’?’ или ’!’. Генерация кода, аналогично каналам, выполняется обходом дерева ER-модели процессов. Для генерации кода необходимо вычислить аргумент channel в сущности ARGUMENT (в рамке на рис. 2). При генерации кода для действия должны выполняться следующие правила. А. Действие запускается, если в текущем состоянии подключенных к процессу каналов возможно считать или отправить сообщения, перечисленные как аргумент действия. Б. Сообщения отправляются, если действие было запущено и вернуло признак успешного завершения. В. Если указан атрибут on_true_action, то переход к связанному действию происходит, если действие было запущено и вернуло признак успешного завершения. Иначе, если указан атрибут on_false_action, выполняется переход к данному связанному действию. Поясним использование описаний процессов на примере проверки тождества sin2 x + cos2 x = 1. Управляющий процесс Parent имеет следующий вид: 174 Препроцессор языка Templet: инструмент программирования. . . *Parent= p1 : Link ! result -> join; p2 : Link ! result -> join; +fork(p1!argCos2,p2!argSin2); join(p1?result,p2?result). Порты p1 и p2 связывают процесс Parent с процессами, вычисляющими квадрат тригонометрических функций. В действии fork выполняется формирование и рассылка сообщений со значением переменной x. В действии join выполняется сложение результатов и сравнение суммы с 1. Заметим, что процедура действия join запустится только тогда, когда будут доставлены оба результата (согласно правилу А, приведённому выше). Вычисляющий квадрат синуса или косинуса процесс Child определяется так: *Child= p : Link ? argCos2 -> calcCos2 | argSin2 -> calcSin2; calcCos2(p?argCos2,p!result); calcSin2(p?argSin2,p!result). В определении показано, какое действие (вычисление квадрата косинуса calcCos2 или квадрата синуса calcSin2) нужно запустить при получении сообщений argCos2 или argSin2. Схема работы препроцессора. Рассмотрим работу препроцессора (рис. 3). На этапе 1 из кода извлекаются размеченные блоки. На этапе 2 блок с описанием структуры кода на рассмотренном языке подвергается синтаксическому анализу. Результат анализа (в форме рис. 1 и рис. 2) поступает во внутреннюю базу данных на этапе 3. На этапе 4 выполняется семантический контроль. Контроль семантики канала заключается в проверке уникальности идентификаторов и проверке ссылочной целостности согласно модели рис. 1. Дополнительно выполняется контроль достижимости состояний из начального состояния. Семантический контроль процесса заключается в проверке уникальности идентификаторов согласно модели рис. 2, проверке ссылочной целостности и выполнимости каждого действия. Вывод на этапе 5 дополняет модели рис. 1 и рис. 2 производными сущностями и атрибутами. На последних этапах 6 и 7 из извлеченных блоков и дополненной базы данных генерируется новый код, который замещает собой исходный. Количество строк кода в программе проверки тождества sin2 x + cos2 x = = 1 показано в таблице. Из таблицы видно, что спецификация и остальной пользовательский код занимают незначительную часть общего объема кода. Размер системного кода также невелик (140 строк), то есть механизм исполнения прост для понимания. Количество строк связывающего кода (255 или ∼ 50 %) даёт представление о степени автоматизации программирования препроцессором. Без препроцессора этот код пришлось бы писать вручную. Размер связывающего кода соотносится с размером спецификации как 255/13, то есть объем кодирования сокращается примерно в 20 раз. Связывающий код прост для понимания, так как строится обходом деревьев моделей рис. 1 и рис. 2 без других преобразований. Применение и сравнение с аналогами. Рассмотренный в настоящей работе препроцессор Templet применяется в составе веб-сервиса автоматиза175 176 Всего [Total] Системный код [System code] Код пользователя [User code] Пользователь / система [User code / System code] Спецификация [Code specification] Пользовательские блоки [User blocks] Всего [Total] Библиотека [Run-time library] Разметка блоков [Block mark-up] Связывающий код [Binding code] Всего [Total] Весь код примера [Entire sample code] Назначение фрагмента кода [The function of the code fragment] 7.07 2.63 Доля строк в % от общего кол-ва строк [Percentage of lines from the total size] 9.70 28.28 10.51 51.51 90.30 100 35 13 Кол-во строк [Number of lines] Размер фрагментов кода в примере sin2 x + cos2 x = 1 [Size of a code fragments in the sample sin2 x + cos2 x = 1] 48 140 52 255 447 495 В о с т о к и н С. В. Препроцессор языка Templet: инструмент программирования. . . Рис. 3. Схема взаимодействия подсистем препроцессора [Figure 3. Subsystems of the preprocessor and their interaction] ции параллельных вычислений на суперкомпьютере «Сергей Королёв» Самарского государственного аэрокосмического университета, развернутого по адресу http://templet.ssau.ru [2]. Он позволяет разработать и отладить каркас приложения как последовательную программу на локальной машине, а затем автоматически запустить код на исполнение на суперкомпьютере в параллельном режиме с использованием API POSIX Threads. В текущей реализации также выполняется трансформация кода для исполнения в операционных системах Windows с использованием Windows API. Применение препроцессора Templet не требует от пользователя знаний методов параллельного программирования в Unix или Windows и позволяет сосредоточиться на решении прикладной задачи. Другие варианты генерации кода позволяют добавлять отладочную информацию для работы со специально ориентированным на данную модель отладчиком. Разрабатывается средство визуализации кода на основе пакетов OpenOffice/LibreOffice с использованием графической нотации Templet [3]. Сообщение о препроцессоре впервые представлено в работе [1], основные алгоритмы препроцессора и синтаксис языка разметки зарегистрированы в Роспатенте.1 Концепции, используемые в дизайне языка, в основном соответствуют стилю языково-ориентированного программирования [4, 5]. Применён близкий к алгебраическим конструкциям способ описания процессов в стиле CSP [6]. Идея компактного дизайна, включающего только базовые механизмы абстракции, взята из языка Oberon [7]. В дизайне препроцессора Templet используются несколько подходов к автоматизации программирования. Один из них - метод разметки последовательного кода препроцессорными инструкциями для распараллеливания, который широко распространен, в частности, в стандарте OpenMP [8], российской системе DVM [9, 10]; в системе Cilk [11], в её российском аналоге T++ [12, 13] и других. Но, в отличие от них, в системе Templet контроль структуры ко1 Эталонная реализация языка Templet: свидетельство о гос. регистрации прогр. для ЭВМ № 2014613169 Российская Федерация / С. В. Востокин; правообладатель С.В. Востокин. - Зарегистрировано в Реестре программ для ЭВМ 19.03.2014; опубл. 20.04.2014, ОБПБТ № 4 (90). 177 В о с т о к и н С. В. да реализуется автоматически за счёт генерации кода, а не вручную. Генерирующие макропроцессоры (m4 [14] или современный вариант T4 [15]) используются для автоматизации программирования. Описанная система также относится к классу так называемых активных генераторов, однако является проблемно-ориентированной. Модель системы Templet - это разновидность модели акторов [16-18], но в отличие от специальных языков, например Erlang [19], мы реализуем акторную семантику средствами процедурного языка. Это позволяет использовать системы программирования существующих языков. Система Templet реализует концепцию разработки, управляемой моделями (model-driven development) [20-23]. В области параллельного программирования это важно при автоматическом преобразовании кода для распараллеливания. Особенность нашей модели в том, что она является комбинацией обычного и предметного языков, причём семантика модели представлена на обычном языке. Роль предметного языка в системе Templet - краткое описание каркаса программы. Препроцессор Templet может использоваться в режиме метапрограммирования [21, 24]: исходная программа преобразуется в другую программу, выполняющую более сложные преобразования, чем позволяет препроцессор. Например, так могут быть реализованы глубокий семантический анализ и оптимизация кода. Благодарности. Автор выражает благодарность Самарскому государственному аэрокосмическому университету за поддержку этого исследования. Библиотека времени выполнения препроцессора была реализована для использования на суперкомпьютере «Сергей Королёв» СГАУ при постоянной помощи со стороны обслуживающего персонала. Работа выполнена при государственной поддержке Министерства образования и науки РФ в рамках реализации мероприятий Программы повышения конкурентоспособности СГАУ среди ведущих мировых научно-образовательных центров на 2013-2020 годы.

About the authors

Sergey V Vostokin

S. P. Korolyov Samara State Aerospace University (National Research University)

Email: easts@mail.ru
(Dr. Techn. Sci.; easts@mail.ru), Professor, Dept. of Information Systems and Technology 34, Moskovskoe sh., Samara, 443086, Russian Federation

References

Supplementary files