Авторефераты по всем темам  >>  Авторефераты по техническим специальностям

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

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

ФОРМАЛЬНАЯ МОДЕЛЬ КОНТЕКСТНО-ЗАВИСИМЫХ ПРОГРАММНЫХ СТРУКТУР И ИХ ПРЕОБРАЗОВАНИЙ В ПРИМЕНЕНИИ К МЕТОДОЛОГИИ 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.

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

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

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

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

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

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

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

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

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

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

Х п. 14 Разработка теоретических основ создания программных систем для новых информационных технологий.

Апробация работы. Основные положения работы докладывались на конференциях "Информатика. Проблемы, методология, технологии" (Воронеж, 2010), "Технологии Microsoft в теории и практике программирования" (Москва, 2010) и УICOOOLPS: Workshop on 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.

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

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

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

Глава 2.

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

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

Значение, коллекции, объектные структуры. Пусть L - фиксированное счетное множество ссылок с выделенным элементом null L и I = * - множество строк (идентификаторов) над некоторым фиксированным алфавитом . Множеством значений называется открытое размеченное объединение следующего вида:

def V = void+ bool : + int : + ident : I + ref : L +...

Для описания структур, составленных из значений мы будем использовать отображения вида D = I V, называемые словарями и кортежи вида V*. Под коллекцией понимается элемент множества def Col = dic : D + seq : V*.

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

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

Множество всех контекстов обозначается C. Пустым контекстом называется def контекст вида C0 = x L. null somenull. Если C l = some z, то l ( ( ) )[ ] ( ) называется внешней идентичностью объектной структуры z.

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

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

C l = some z, tag x met, C l = some z, tag x = met, ( ) ( ) cnt z x = v meta z x = v ( )[ ] ( )[ ], some ref l x X C v X some ref l x X C v X ( ) [ ] ( ) [ ] Любое селекторное выражение имеет единственное значение, поэтому на множестве селекторных выражений можно ввести функцию-вычислитель eval : Se C V.

Пусть C1, C2 - контексты и f : Dom C1 Dom C2 - биективная f функция. Два значения v1,v2 V эквивалентны ( v1 ~ v2 ), если выполняется v1 = v2 = одно из следующих условий: = some ref l1,2,l1 Dom f,l2 = f l1.

( ) v1,v = someu1,2, tag u1,2 ref,u1 = u1, f Контексты C1 и C2 эквивалентны, если Dom С2 Dom С1, f null = null и ( ) f evalC l x ~ evalC f l x при всех l Dom С1, x X.

[ ] ( )[ ] Метаструктура. Выделяется ряд специальных классов объектных структур, отличающихся метаданными и выполняющих различные функции в формировании программной модели. Основным элементом структуры, на основе которого определяются композиционные связи часть-целое, является понятие узла. Объектная структура z называется узлом (запись: NodeC z ) в meta z met"owner " = some ref l [ ] контексте C, если выполняется условие l = some z '.

( ) C z ' = null NodeC z ' ( ) Назначение компонента УownerФ состоит в хранении обратной ссылки на узел-владелец, по отношению к которому данный узел является компонентом.

Объект z называется сущностью ( EntC z ), если он является узлом и содержит в слоте desc список следующего вида (дескриптор).

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

Rng s = s v Rng s.tag v = ref ( ) Для отражения ассоциативных связей, которые могут связывать произвольные узлы модели, вводится понятие адаптера. Сущность z называется адаптером в контексте C ( AdpC z ), если ( ) meta z met"target " = some ref l [ ] .

( ) C l = some z ' z ' = null NodeC z ' ( ) В некоторых случаях требуется ограничить область видимости определенных элементов модели - например, параметры процедуры обычно доступны только внутри этой процедуры и не могут адресоваться извне. Для этой цели определяется специальная разновидность сущностей - связка, определяемая условиями:

meta z met"bnds" = some ref l [ ] meta z met"scope" = some ref l [ ] ( ) C l = some list s и.

( ) C l = some z ' Rng s = s z ' = null EntC z ' ( ) v Rng s.v = ref l ' EntC l ' ( ) ( ) Композиция и ассоциация. Рассмотрим ограничения, которые накладываются на рассмотренные выше структуры. Будем говорить, что узелссылка l является компонентом узла-ссылки l ', а l ' соответственно контейнером l (запись: l C l ' ), если evalC l ' x = some ref l для некоторого [ ] x X \ met"owner ", met"target ".

{ } Если узел l является контейнером для ссылки-адаптера l ' и targetC l ' = l '' null, то имеет место ассоциация между ссылками l и l '' :

def xx l l '' l '' nulll ' : AdpC l ' l ' l = CC ( ) .target l ' l '' C Сформулируем ограничения, касающиеся метаструктуры контекста.

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

z RngC tag z = list.NodeC z (1) ( ) ( ) z RngC tag z = obj.PrimC z EntC z (2) ( ) ( ) ( ) Эти утверждения означают, что в корректном контексте любой список является узлом, а любой объект является либо простым объектом, либо сущностью.

l,l ' l C l '.ownerC l = l ' (3) ( ) l,l ' : NodeC l NodeC l ' ownerC l = l ' l ' null l C l ' (4) ( ( ) ( ) )[ ] м l,l ' : NodeC l ownerC l = l '.l ' * l (5) ( ( ) ) C Эти утверждения характеризуют основные свойства отношения композиции: согласованность с операцией owner, отсутствие узлов, которые являются владельцами самих себя.

ll 'l ''.BinderC l l ' Rng bndsC l l '' С l ' l '' * scopeC l (6) ( ) ( ) C ll 'l ''.BinderC l l ' Rng bndsC l l '' С l ' NodeC l '' (7) ( ) ( ) Утверждение (7) выражает основное свойство связок, состоящее в запрете ассоциации между узлами, не являющимися компонентам соответствующей области видимости, и связанными сущностями.

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

Зависимость. Путем pathC l узла l в контексте С называется такая ownerC ln,ln null ln последовательность ссылок, что l0 = l и ln+1 =.

null Сущность z называется клиентом (запись: ClientC z ), если ( ) meta z met"depAdapters" = some ref l, где C l = somelist s и [ ] ( ) v = ref l ' AdpC l ' ( ) v Rng s.. Клиент l зависит от адаптера ( ) ( ) target l ' = null AdpC targetC l ' C l ', если depAdaptersC l ассоциирован с l '. Кортеж, состоящий из всех ссылокатрибутов, от которых зависит данная ссылка-клиент l обозначается depsC l.

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

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

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

[ ] ( ) ( ) v Rng s.v = ref l '' TmplC 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) на структуру контекста, определяющие его корректность.

ParC l constrC l = somel ' TmplC l ' (8) l :C, l ' (9) p,l '' : p Dom constrC p = somel '' q : p = ref q.q :C, l '' ( ) ( ) Таким образом, результат подстановки сам должен быть реализацией шаблона, заданного операцией constr соответствующего параметра. Правила (11) и (12) выражают свойства, характеризующие отношение наследования:

мl.l <: l (10) + l <:C l ' p : p :C, l.p :C, l ' (11) ( ) Глава 3.

Глава 3 посвящена описанию механизма действий, формализующего преобразования структуры моделей в терминах элементарных операций, таких как создания новых и изменение состояния существующих объектных структур.

Действия. Действия - это объекты предопределенного вида, описывающие элементарные изменения в структуре модели. Выделяются такие действия, как создание списка или объекта с заданной структурой, создание новой реализации заданного шаблона, изменение/добавление/удаление элемента объектной структуры, активация заданного процедурного объекта.

Для описания процедуры выполнения действий вводятся выраженияактиваторы и определяются правила редукции. Активатором называется def элемент множества: A = exec : L L* + halt, где exec k, L символизирует ( ) ( ) выполнение последовательности действий, заданной кортежем ссылок L по отношению к контроллеру k, а halt - останов выполнения. Пара a,C, состоящая из активатора и контекста, обозначается aC.

Отдельный шаг выполнения характеризуется отношением редукции . Ниже представлены некоторые из правил редукции:

Х редукция последовательности действий execC k, execC k, l haltC execC k, l execC ' k, L ' ( ) ( ) ( ) ( ) haltC execC k, l L haltC execC k, l L execC ' k, L ' L ( ) ( ) ( ) Х создание объекта l ::C NewActionDesc evalC l cnt"cnt " = some ref p [ ] evalC l cnt"meta" = some ref q [ ] execC k,l errIfFail C, newinitobj p, q C,exec k, ( ) ( ) ( ) ( ) Х создание экземпляра шаблона l ::C NewInstActionDesc evalC l cnt"template" = some ref p [ ] execC k,l errIfFail C, newinst pC,exec k, ( ) ( ) ( ) Все контексты, порождаемые активатором a из фиксированного контекста C, эквивалентны друг другу.

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

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

Таким образом, преобразования контекста, описываемые посредством механизма действий, сохраняют корректность и ключевые свойства структурных элементов моделей. С точки зрения реализации это означает, что любая последовательность объектов ActionDesc всегда реализуема в терминах элементарных операций (создание объекта/списка и изменение его компонента) и сохраняет корректность контекста. Это условие, в частности, необходимо для правильной реализации системы контроля версий, поскольку состояние модели до и после выполнения любой транзакции должно удовлетворять условиям корректности независимо от того, была эта транзакция выполнена или отменена.

Глава 4.

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

Заключение отражает основные результаты, полученные в ходе диссертационного исследования:

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

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

3. Методика построения языков программирования, которая за счет использования указанных моделей (в частности, контекстнозависимых представлений), позволяет расширить возможности повторного использования в объектно-ориентированных системах.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Седунов А. А. Гибридный объектно-ориентированный метаязык // Труды VI всероссийской научно-практической конференции Технологии Microsoft в теории и практике программирования, Москва, 2009.

2. Седунов А. А., Тюкачев Н. А. Объектно-ориентированный язык спецификаций // Труды всероссийской научно-технической конференции Молодые исследователи - регионам, Вологда, 2009.

3. Седунов А. А. Объектно-ориентированный метаязык // Вестник ВГУ, серия Системный анализ и информационные технологии, 2009, №1.

4. Седунов А. А., Тюкачев Н. А. Построение формальных моделей с применением объектно-ориентированного метаязыка // Вестник ВГТУ, 2009, т. 5, №10 [издание из перечня ВАК].

5. Седунов А. А. Присоединяемые типажи в Java: расширение языка и область применения // Вестник Воронежского государственного университета, серия Системный анализ и информационные технологии, 2010, №[издание из перечня ВАК].

6. Седунов А. А. Расширение функциональности классов с помощью присоединяемых типажей. // Труды X международной конференции Информатика: проблемы, методология, технологии, Воронеж, 2010.

7. Седунов А. А. Язык запросов для внутреннего представления BOOпрограмм // Труды VII всероссийской научно-практической конференции Технологии Microsoft в теории и практике программирования, Москва, 2010.

8. Седунов А. А., Тюкачев Н. А. Расширение языка Java с помощью присоединяемых типажей // Труды всероссийской научно-технической конференции Молодые исследователи - регионам, Вологда, 2010.

9. Седунов А. А. Формализация объектной структуры с помощью систем объектных уравнений // Вестник ВГУ, серия Системный анализ и информационные технологии, 2010, №2 [издание из перечня ВАК].

10. Седунов А. А. Расширение функциональности классов с помощью присоединяемых типажей. // Труды XI международной конференции Информатика: проблемы, методология, технологии, Воронеж, 2011.

11. Седунов А. А. Структура ядра метаязыка в системе LDDпрограммирования // Вестник ВГУ, серия Системный анализ и информационные технологии, 2011, №1 [издание из перечня ВАК].

12. Sedunov Aleksey, Tyukachev Nikolay. An Approach to Modular ObjectOriented Programming in Language-Driven Development Framework // 6th ICOOOLPS Workshop, European Conference on Object-Oriented Programming, Lancaster, UK, 2011.

   Авторефераты по всем темам  >>  Авторефераты по техническим специальностям