На правах рукописи

СЕДУНОВ АЛЕКСЕЙ АЛЕКСАНДРОВИЧ

ФОРМАЛЬНАЯ МОДЕЛЬ КОНТЕКСТНО-ЗАВИСИМЫХ

ПРОГРАММНЫХ СТРУКТУР И ИХ ПРЕОБРАЗОВАНИЙ В

ПРИМЕНЕНИИ К МЕТОДОЛОГИИ LANGUAGE-DRIVEN

DEVELOPMENT

Специальность 05.13.17. — «Теоретические основы информатики»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Воронеж 2012

Работа выполнена в ФГБОУ ВПО «Воронежский государственный университет»

Научный руководитель: кандидат физико-математических наук, доцент Тюкачев Николай Аркадиевич

Официальные оппоненты: доктор технических наук, профессор, зав. кафедрой компьютерных интеллектуальных технологий проектирования Воронежского государственного технического университета Чижов Михаил Иванович доктор физико-математических наук, доцент, зав. кафедрой математического обеспечения ЭВМ Махортов Сергей Дмитриевич

Ведущая организация Таганрогский технологический институт ФГАОУ ВПО "Южный федеральный университет"

Защита состоится 2 июля 2012 года в 12-00 на заседании диссертационного совета Д 212.038.24 при Воронежском государственном университете по адресу:

394006, г. Воронеж, Университетская пл., д. 1, ВГУ, ауд. 226.

С диссертацией можно ознакомиться в научной библиотеке ФГБОУ ВПО «Воронежский государственный университет».

Автореферат разослан 31 мая 2012 г.

Ученый секретарь диссертационного совета Д 212.038.24 Чеботарев А.С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Объект и предмет исследования. Объектом данного исследования являются языки и системы программирования. Предмет исследования составляют средства метапрограммирования, а также методология LanguageDriven Development и объектно-ориентированной разработки программного обеспечения.

Задачи исследования. Для достижения указанной цели поставлены и решены следующие задачи:

1. Анализ основных решений в области языков и систем разработки, поддерживающих элементы метапрограммирования.

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

3. Разработка формальной модели внутреннего представления программ в применении к методологии Language-Driven Development.

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

Для реализации программной системы использованы принципы модульного программирования и объектно-ориентированного программирования с применением паттернов проектирования.

Основные результаты, выносимые на защиту, и их научная новизна.

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

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

3. Методика построения языков программирования (на примере языка представлений и позволяющая расширить возможности традиционного объектно-ориентированного подхода с точки зрения повторного использования программных компонентов и реализации принципа «открытости – закрытости».

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

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

Диссертация соответствует профилю диссертационного совета Д 212.038.24 и паспорту специальности 05.13.17 «Теоретические основы информатики» по следующим областям исследований:

п. 2 «Исследование информационных структур, разработка и анализ моделей информационных процессов и структур»;

п. 14 «Разработка теоретических основ создания программных Апробация работы. Основные положения работы докладывались на конференциях "Информатика. Проблемы, методология, технологии" Implementation, Compilation and Optimization of Object-Oriented Languages, Programs and Systems” (European Conference on Object-Oriented Programming, Lancaster, UK, 2011).

изложено в 12 работах, из них 4 статьи в журналах, рекомендованных ВАК РФ.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка литературы. Общий объем диссертации – 157 страниц.

СОДЕРЖАНИЕ РАБОТЫ

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

В главе 1 приводится обзор существующих подходов к реализации средств метапрограммирования, а также основных вариантов развития объектно-ориентированного подхода. В работе представлен критический анализ ряда языков программирования и описаны их возможные применения в контексте методологии LDD. Кроме того, рассматриваются ключевые реализации программных инфраструктур, предоставляющих средства метапрограммирования, в частности, Meta Programming System (JetBrains, Inc.), Whole Platform и XMF.

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

В завершение главы сформулированы основные требования к языковым возможностям LDD-инфраструктуры и реализуемому ей набору функций.

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

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

фиксированное счетное множество ссылок с выделенным элементом null L фиксированным алфавитом. Множеством значений называется открытое Для описания структур, составленных из значений мы будем использовать отображения вида D= I V, называемые словарями и кортежи Col Объектом и списком называются элементы следующих множеств соответственно. Размеченное объединение списков и объектов называется множеством объектных структур: Dyn obj : Obj + list : List. В частности, null = obj ( null ). На множестве объектных структур определяются функции id : Dyn L, cnt : Dyn Col и meta : Dyn Col, извлекающие из них соответствующей коллекции.

Контексты. Для описанию связей между ссылками и объектными структурами используется понятие контекста. Контекстом называется функция вида f : L Dyn, удовлетворяющая условию f null = some null.

Множество всех контекстов обозначается C. Пустым контекстом называется называется внешней идентичностью объектной структуры z.

Ссылка l L называется замкнутой в контексте C (запись C l ), если l Dom C : ей соответствует объектная структура. Значение называется замкнутым в контексте C, если оно не содержит незамкнутых ссылок: C v tag v ref ( l : v = ref l ).C l. Коллекция называется замкнутой в контексте C, если соответствующая ей функция конечна и все содержащиеся в ней ссылки замкнуты в C. Объектная структура C cnt z C meta z C ( id z ) = Контекст С называется замкнутым, если множество Dom C конечно, любая объектная структура, содержащаяся в его множестве значений контекста, замкнута в нем, а сужение контекста на множество Dom C является биекцией.

Рассмотрим операции доступа к компонентам структур. Пусть X def множество адресных элементов: X = itm : I + met : I + idx :. Кортеж X X* называется селектором. Процедура вычисления селектора основана на следующих правилах вывода в контексте C :

Любое селекторное выражение имеет единственное значение, поэтому на множестве селекторных выражений можно ввести функцию-вычислитель Пусть C1, C2 - контексты и f : Dom C1 Dom C2 - биективная функция. Два значения v1, v2 V эквивалентны ( v1 ~ v2 ), если выполняется Контексты C1 и C2 эквивалентны, если Dom С2 Dom С1, f ( null ) = null и evalC1 l [ x ] ~ evalC2 f ( l )[ x ] при всех l Dom С1, x X.

Метаструктура. Выделяется ряд специальных классов объектных структур, отличающихся метаданными и выполняющих различные функции в формировании программной модели. Основным элементом структуры, на основе которого определяются композиционные связи «часть-целое», является понятие узла. Объектная структура z называется узлом (запись: NodeC z ) в контексте C, если выполняется условие C ( l ) = some z ' Назначение компонента “owner” состоит в хранении обратной ссылки на узел-владелец, по отношению к которому данный узел является Объект z называется сущностью ( Ent C z ), если он является узлом компонентом.

и содержит в слоте «desc» список следующего вида (дескриптор).

Дескриптор, как показано далее, используется для привязки контекстноmeta z [ met" desc "] = some ref l зависимых структур к сущности.

Для отражения ассоциативных связей, которые могут связывать произвольные узлы модели, вводится понятие адаптера. Сущность z meta z [ met" target "] = some ref l = null NodeC ( z ' ) В некоторых случаях требуется ограничить область видимости определенных элементов модели – например, параметры процедуры обычно доступны только внутри этой процедуры и не могут адресоваться meta z [ met" scope "] = some ref l Композиция и ассоциация. Рассмотрим ограничения, которые является компонентом узла-ссылки l ', а l ' соответственно накладываются на рассмотренные выше структуры. Будем говорить, что узелссылка l контейнером l (запись: l C l ' ), если evalC l ' [ x ] = some ref l для некоторого x X \ {met" owner ", met" target "}.

target C l= l '' null, то имеет место ассоциация между ссылками l и l '' :

Сформулируем ограничения, касающиеся метаструктуры контекста.

Будем говорить, что замкнутый контекст C отношению к метаструктуре, если он удовлетворяет свойствам (1) - (8).

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

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

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

Зависимость. Путем path C l узла l в контексте С называется такая l ', если depAdaptersC l ассоциирован с l '. Кортеж, состоящий из всех ссылокатрибутов, от которых зависит данная ссылка-клиент l обозначается depsC l.

Адаптеры позволяют связывать с сущностями контекстно-зависимые метаданные. Пусть e - сущность в контексте C. Локальным дескриптором e указывающих на e и взятых в порядке обратного пути e :

= concat filter ( attrsC li depsC li )( a.target C a e ) Использование операции слияния означает, что один и тот же атрибут не встречается в дескрипторе более одного раза. Гибкое определение локального дескриптора атрибутами, доступными через композиционные связи адаптеров, которые ссылаются на исходную сущность. Тем самым один и тот же объект может обладать различным набором метаданных в зависимости от того, какая ссылка используется для обращения к нему. Для учета ассоциативных связей вводится понятие полного дескриптора. В отличие от локального, полный дескриптор определен для адаптеров, поскольку его структура зависит не только от исходной сущности, но и от ее адаптера: fulldscC l = concat locdscC target C l, extdscC l, где = concat filter ( attrsC li depsC li )( a.target C a target C l ) Реализация и наследование. Отношения реализации и наследования используются для классификации объектов, а также описания объектовпрототипов, используемых для построения других объектов с аналогичной структурой. Наличие механизма прототипов является главным преимуществом рассматриваемой теории по сравнению с существующими альтернативами, поскольку дает возможность абстракции и повторного использования элементов структуры моделей в виде шаблонов.

Сущность z называется шаблонным параметром ( ParC z ), если meta z [ met" constr "] = some ref l C ( l ) = some z ', AdpC ( z ') если все ее связанные сущности являются шаблонными параметрами с попарно различными именами. Шаблон l называется производным, если Рассмотрим контекст C, в котором определены отличные от null ссылки l и l ', причем l l '. Ссылка l ' называется расширением ссылки l, ( l ' C l ), если она имеет ту же структуру, за исключением того, что ссылки на шаблонные параметры могут быть заменены произвольными значениями.

Ссылка l называется экземпляром шаблона в контексте C (запись: l :C l ' ), если l C kerC l ' и evalC l [ met " proto "] = some ref l '.

Сформулируем теперь дополнительные ограничения (9) - (12) на структуру контекста, определяющие его корректность.

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