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

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА, ОРДЕНА ОКТЯБРЬСКОЙ РЕВОЛЮЦИИ И ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА

ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И КИБЕРНЕТИКИ

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

ПОПРЫГАЕВ Евгений Владимирович

УДК 519.685

РАЗРАБОТКА ЯДРА СИСТЕМЫ ОБОСНОВАТЕЛЬНОГО ГИПЕРПРОГРАММИРОВАНИЯ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин и систем

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

Мэсква-1991

Работа выполнена на кафедре системного программирования факультета вычислительной математики и кибернетики Московского государственного университета им. М. К Ломоносова

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

профессор Е.А. Еоголев

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

доктор физико-математических наук старший научный сотрудник

Крюков Виктор Алексеевич, кандидат физико-математических наук доцент Гайсарян Сергей Суренович

Ведущая организация: Московский инмэкерно-физический институт

Защита диссертации состоится " ??" 1992 г. в

/У час. _мин. ка заседании Специализированного Совета

Д. 05а 05.38 N4 при Московском государственном университете им. № В. Ломоносова по адресу: 119899, Шсква. Ленинские горы, МГУ, факультет ВМиК, аудитория

С диссертацией можно ознакомиться в библиотеке факультета ВМиК >,СГУ.

Автореферат разослан "__ 169 г.

Учёный секретарь Специализированного

Совета Д. 053.05.38. профессор Н. П. Трифонов

;

i ~ i"5 г 5ртациЯ

- 3 -

Об!цая характеристика работы.

Астуальность проблемы. С развитием вычислительных средств Ъказалась возможной разработка программных инструментов, осуществляю!!;« поддержу отдельных этапов жизненного цикла программ и повышавших производительность и надёжность получаемых продуктов. Уже видится реализуемой, несмотря на её сложность, задача разработки инструментальных систем, поддерживавших Сы весь тазненный цикл , что позволяет говорить об её актуальности.

Система обоснователыгого гиперпрограммирования является системой, претендующей на эту роль. Она базируется на методе обосновательного гиперпрогракмкрования, понимаемое как система-тичешсий процесс определения помечектлх метапеременных на основе правил грамматики заданного йзь:;са с возможностью сеязкзэть с фрагментами програ'-м дополнительнее утверждения (сбоснсзания) для обеспечения статического семантического контроля. Предполагается, что для каждой предметной области целесообразно иметь "свою" такую систему. где кюжло было бы учесть не только специфику данной области, но и предло.'-нть прикладном программистам пркзычяуя для них среду прогрз,летрованил. Тем сам:;м речь идет о целом семействе систем обосновательного гкиерпрсгрРАэтрованкл. число членов ¡второго видится достаточно больинм.

В сег.зи с от."1! является актуальней задача Ен.пелс-:-:не ебцей части всех таь"'х систем, которая, по-видимому, охваг.тг Сазогь'е сперац:;;: их ^уняцчокяроганмл (ведение информационней бэе-п проекта. TKHrjpci.ibütr'i инструментарий и др.). Такуя чзсть скотски удсбпо На31«5£.7Ь .4,7pO!t.

Гельг: д.-'с-сертяиг.олной работы является создание концепции, спеш\1:::-ац":? к реализация ядра се^йства систем обзенор^гельпо-го гиперпрогpri*-орзнкя, сбэспечявй"ощ!Х поддержу разработки и сопровопденил программ ясгикмюЛ кзд^юсти.

Няучигд ног-гзпа. ffeEK-3! научными р:-э".*ь?атгл,и .тс^гтся:

1. Гд-щепц;.;! г семе/отва систем с-бссковатглыгого ггпергрег-рам:-гровання, ре;1лпгу;:"м'о кз^р'-ан^окнгэ и кгструхгитэльну» яз1"«вспезаэ;:с;гг,т! поддерге/ их работы.

2. Разработанное в раках стой концзпцва гсбильнсе ядро, кото-

рое может быть включено в любую систему обосновательного гиперпрограммирования.

Практическая значимость. Реализация ядра на ЭВМ СМ-4, ПЭВМ "Электроника-85" и IBM РС/W/AT позволила существенно упростить производство систем обосновательного гиперпрограммирования (использовано в нескольких аспирантских и студенческих работах). Кроме того, программный пакет работы с программной базой, являющийся существенной частью ядра и обеспечивающий информационную поддержку систем обосновательного гиперпрограммирования, может иметь и самостоятельное применение, например, в трансляторах.

Апробация работы. Результаты работы докладывались на конференции молодых учёных факультета ВМиК МГУ (1Ö89 г.), на Все-сошнрй студенческой конференции "Студент и научно-технический прогресс" (Новосибирск, 1989 г.), на научно-исследовательском семинаре по автоматизации программирования (факультет ВМиК МГУ, 1991 г.).

Публикации. По теме диссертации опубликованы три работы, библиография которых дана в конце.

Структура и объём работы. Диссертация состоит из введения, трёх глав, заключения, списка литератуты и приложения; объём работы без библиографии и приложения 109 страниц.

Краткое содержание работы.

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

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

- 5 -

правил грамматики некоторого языка.

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

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

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

1) инструменты, получающие информацию извне и использующие программную базу как хранилище своих результатов (гиперанализа-

- 6 -

торы, синтаксически-управляемые редакторы);

2) инструменты, как извлекавшее информацию из базы, так и записывайте в неё (верификаторы, модификаторы, конверторы и пр.);

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

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

Программная база и её инструментальное окружение образуют информационно-программную поддержку разработки и сопровождения программ

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

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

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

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

Во второй главе описывается, пожалуй, главная составляйся ядра - пакет работы с программной базой, который называется ИРАСД (Интерфейс Размеченных Атрибутированных Синтаксических Деревьев). Первоначально он был специфицирован на языке программирования Ада и содержал 88 процедур и функций. В работе описана структура пакета Он состоит из двух подпакетов - работы с языковой базой и обработки исключительных ситуаций, и собственно пакета работы с программной базой. Выделение операций над языковой базой в самостоятельный пакет ("Драйвер языко-

вой базы") произведено в силу автономности работы с ней по сравнению с другими частями программной базы.

Пакет ИРАСД предлагает оригинальный способ представления синтаксических деревьев, храня не сами деревья, а их вывод в соответствующих грамматиках. Для этого программная база представляется совокупностью узлов, объединяемых в деревья динамически, где каждый узел есть пара: левая часть, задаваемая помеченной метапеременной, и правая - задаваемая терминалом или цепочкой помеченных метапеременных. Тем самым появляется возможность не только существенно упростить операции по работе с деревьями (добавление, удаление, модификация поддеревьев), но и управлять построением дерева. Для этой цели вся программная база разбита на некоторые области локализации, называемые клетками. Внутри клетки левые части узлов являются уникальными. Одна из клеток называется ведущей и обычно содержит узлы основного дерева програмы. В других клетках находятся лишь модификации тех узлов, которые должны быть изменены, чтобы получить новый вариант программы. Поскольку построение дерева есть каждый раз поиск нужного узла, то задав приоритет клеток, в которых по очереди будет искаться этот узел, можно получить различные версии (в том числе версии версий) программы. При этом важно подчеркнуть, что такой способ хранения семейства программ исключает всякое повторение, поскольку каждая клетка будет содержать лишь те части, которые действительно должны быть другими. Конечно, можно согласиться с тем, что такой способ построения деревьев имеет своей слабой стороной необходимость некоторого перебора узлов перед получением каждого следующего. Но в данном случае есть две возможности сократить эти издержки. Во-первых, программная база - абстрактный тип данных, допускающий различные реализации и, следовательно, возможность постоянного улучшения физического размещения информации. Во-вторых, предполагается, что основная работа будет осуществляться с временными программными базами, быстродействие и сокращённый объём которых сделают время перебора приемлемым.

Шкет ИРАСД содержит и средства, обеспечивающие возможность коллективной работы с программной базой. Предполагается наличие главного лица - администратора программной базы, от-

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

Также внимание в данной главе уделено вопросу реализации пакета ИРАСД. Так как трансляторы с языка Ада в настоящее время труднодоступны и не получили пока широкого распространения (особенно на ПЭВМ), было решено проводить реализацию пакета на другом, более распространённом языке. В силу его близости к исходному языку в качестве инструментального был выбран язык Паскаль. Принципиальным положением было требование максимального соответствия создаваемой реализации стандарту Паскаля для облегчения как переноса пакета на другие версии этого языка (прежде всего на других типах ЭВМ), так и окончательной реализации его на Аде, поскольку, по мнению некоторых иссследовате-лей, стандарт Паскаля полностью покрывается стандартом Ады.

Однако оказалось, что ряд вопросов программирования в стандарте Паскаля либо отражён слабо, либо не отражён вовсе. К их числу относится модульное програмирование. В силу этого в каждой версии языка такие вопросы решались по-своему и в большинстве случаев малосовместимо. Поэтому говорить об одной реализации пакета на Паскале говорить было бы некорректно. Для каждого рассматриваемого типа ЭВМ выбиралась та версия языка, где данные вопросы решались бы максимально близко к их разрешению в Аде. Исходя из этих положений на сегодня можно говорить о трёх реализациях пакета ИРАСД на языке Паскаль: на ЭВМ СМ-4 (ОС РА<ЮС), на ПЭВМ "Электроника-85" (ОС ПРОС-2, Tool Kit Pascal), на IBM PC/XT/AT (МЗ DOS, Turbo-Pascal 5.0). Наиболее близкой к Аде из перечисленных версий Паскаля является последняя. На её

примере и описывается в работе вопросы моделирования пакета Ады на Паскале и, в частности, пакета ИРАСД.

Кроме всего прочего, реализация пакета работы с атрибутированными размеченными синтаксичесикми деревьями может иметь и самостоятельное значение, например, в качестве языка промежуточного представления программ в трансляторах (аналогично языку Б^апа для Ада-программ).

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

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

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

- 11 -

МРАСД (например, 'удаление частей языковой базы).

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

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

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

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

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

2. В рамках этой концепции специфицирован и реализован на ЭВМ СМ-4, ПЭВМ "Электроника-85" и IBM РС/ХТ/АТ пакет работы с программной базой.

3. Разработан и реализован вариант инструментальной надстройки над указанным пакетом.

Основные положения диссертации опубликованы в следующих работах:

1. Попрыгаев Б. В. Моделирование пакета языка Ада на язык« Паскаль ( на прюкре пакета ИРАСД). //Вопросы программного обеспечения ЭВМ. М. , МГУ, 1987. Депонир. в ВИНИТИ 14.12.87 N8693-В87.

2. Попрыгаев Е. В. Пакет работы с программной базой ИРАСД. //Вопросы вычислительной математики и программного обеспечения ЭВМ. Ы. , МГУ. 1988.

3. Жоголев Е. А., Попрыгаев Е. В. Пакет работы с программной базой ИРАСД. Рукопись депонир. в ВИНИТИ 27. 03. 91 *N1338-B91.

Подписано в печать I9.XI.9I г. Форлат 60x84/16. Объём 0,75 п.л. Тира» 100 экз. Заказ * 54. Бесплатно.

Ротапринт НИВЦ МГУ II9899, Мооква, Ленинские гори

s*