WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 |
Российская Академия Наук Институт Системного Программирования УДК 519.682

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

Демаков Алексей Васильевич ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ОПИСАНИЕ ГРАФОВОГО ПРЕДСТАВЛЕНИЯ ПРОГРАММ И МОДЕЛЕЙ Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2006

Работа выполнена в Институте Системного Программирования Российской Академии Наук.

Научный консультант:

доктор физико-математических наук Петренко Александр Константинович

Официальные оппоненты:

доктор физико-математических наук Семёнов Виталий Адольфович кандидат физико-математических наук Головин Игорь Геннадьевич

Ведущая организация:

Институт Прикладной Математики им. М.В.Келдыша РАН

Защита диссертации состоится 22 декабря 2006 года в 15 часов на заседании диссертационного совета Д.002.087.01 при Институте Системного Программирования РАН по адресу:

109004, г. Москва, ул. Б. Коммунистическая, 25, Институт Системного Программирования РАН, конференц-зал.

С диссертацией можно ознакомиться в библиотеке Института Системного Программирования РАН.

Автореферат разослан 21 ноября 2006 г.

Ученый секретарь диссертационного совета кандидат физ.-мат. наук /Прохоров С.П./

Общая характеристика работы

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

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

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

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

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

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

Основные цели работы Основными целями диссертационной работы являлись:

• Разработка метода описания графовых структур данных, применимого для решения таких задач как представление деревьев абстрактного синтаксиса программ в трансляторах языков программирования, описание структуры и обработки объектных моделей документов, обработка сложных структур данных предметной области в прикладных задачах и т.п.

• Реализация инструментальной поддержки этого метода.

• Апробация этого метода и его инструментальной поддержки.

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

Практическая значимость работы Практическая значимость работы подтверждается успешным использованием различных версий языка TreeDL для описания структуры деревьев абстрактного синтаксиса программ в 1995-2005 годах в проектах по разработке:

• Транслятора исполнимого подмножества языка спецификации RSL в язык программирования PROTEL, в рамках проекта по тестированию на основе формальных спецификаций ядра операционной системы, выполненного для компании Nortel, Канада.

• Транслятора спецификационного расширения языка Java в сам язык программирования Java, в рамках проекта по созданию инструментов автоматизированной разработки тестов для программ на платформе Java.

• Транслятора спецификационного расширения языка C# в сам язык программирования C# и модели данных, создаваемой с помощью графического интерфейса пользователя, в рамках проекта по созданию инструментов автоматизированной разработки тестов для программ на платформе.NET.

• Генератора тестов на основе моделей в рамках проекта OTK по созданию методов и инструментов для тестирования оптимизирующих компиляторов.

• Открытого анализатора языка Java в рамках проекта по дальнейшему развитию инструментов автоматизированной разработки тестов для программ на платформе Java.

• Транслятора самого языка TreeDL в языки программирования Java и C#.

Разработанный язык описания структуры данных может использоваться при решении различных задач, в которых используются графовые структуры данных, в частности, при разработке трансляторов языков программирования, при описании структуры и обработки объектных моделей документов, разработке интерфейса пользователя по схеме Model-View-Controller, анализе и обработке моделей и сложных структур данных предметной области в прикладных задачах и т.п.

Апробация работы и публикации По теме диссертации опубликовано 6 работ, представляющих основные научные результаты диссертации.

Основные положения работы обсуждались на • семинаре ВМиК МГУ им. М.В.Ломоносова в 1998 году;

• конференции «Технологии Microsoft в научных исследованиях и высшем образовании» в июне 2003 года;

• семинаре ИСП РАН в 2005-2006 годах;

• семинаре ИПМ им. М.В.Келдыша РАН в октябре 2006 года.

Структура и объем работы Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 99 наименований, и четырех приложений. Основной текст (без приложений) занимает 110 машинописных страниц.

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

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

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

• для текстового представления – контекстно-свободные грамматики и атрибутные грамматики;

• для XML представления – языки описания схем XML документов, задающие структуру (XML Schema, RELAX NG) и контекстные ограничения (Schematron);

• для баз данных – языки описания схем баз данных (SQL).

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

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

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

• С использованием виртуальных методов типов вершин графа.

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

• С использованием шаблона проектирования Посетитель.

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

• С использованием мультиметодов.

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

В работе указаны существенные недостатки первых двух способов.

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

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

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

• Невозможно определить операции, реализация которых зависит не от одного, а от нескольких типов вершин, поскольку выбор метода, который будет вызван, определяется по фактическому типу лишь одного параметра – объекта, у которого метод был вызван.

К недостаткам использования шаблона Посетитель относятся:

• Необходимость изначальной поддержки этого шаблона со стороны типов вершин.

• Фиксированная сигнатура методов, которая затрудняет передачу параметров и возврат результатов.

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

• Необходимость определения методов для всех типов вершин, даже если логически операция определена только на подтипах определенного типа.

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

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

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

Серьёзным препятствием для использования мультиметодов является отсутствие этой возможности в наиболее распространенных в настоящее время объектно-ориентированных языках программирования.

Из обзора сделаны следующие выводы:

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

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

Pages:     || 2 | 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»