Содержание к диссертации
Введение
1. Автоматический синтез программ и мобильность программного обеспечения 6
1.1. Прикладное программное обеспечение 6
1.2. Синтезаторы на вычислительных моделях 8
1.3. Обеспечение мобильности систем программирования 14
1.4. Постановка задачи 22
2. Концепции и возможности системы МИС 23
2.1. Функциональные возможности системы 23
2.2. Обзор входного языка 26
2.3. Соотношение систем ПРИЗ и МИС 34
3. Описание реализации 37
3.1. Представление вычислительной модели 40
3.2. Абстрактная машина для языка Утопист 48
3.3. Другие информационные структуры 55
3.4. Архитектура системы 59
4. Обеспечение мобильности системы МИС 68
4.1. Реализация системы МИС 68
4.2. Модель реализации абстрактной машины 72
4.3. Опыт переноса системы МИС 76
Заключение 81
Литература 82
Приложения 86
- Синтезаторы на вычислительных моделях
- Обзор входного языка
- Абстрактная машина для языка Утопист
- Модель реализации абстрактной машины
Введение к работе
Интенсивное развитие программного обеспечения породило проблемы его накопления и использования. В 70-х годах оформилась концепция пакета прикладных программ (ППП): совокупности совместимых модулей для решения определенного класса задач. Поскольку пакет предназначен для решения не одной, а целого класса задач, его функциональное наполнение разрабатывается как совокупность модулей, которые должны быть скомпонованы для решения конкретной задачи. ШШ предоставляет пользователю язык, на котором описывается подлежащая решению задача. Системное наполнение пакета предназначено для обработки описания задачи и формирования расчетной программы.
По характеру решаемых проблем разработка функциональной и системной частей пакета сильно различаются. Разработка функционального наполнения пакета ведется специалистами в конкретной предметной области; как показывает практика, их опыта в большинстве случаев явно недостаточно для создания системной части пакета, при разработке которой решаются задачи, типичные для системного программирования: обработка текстовой информации, ведение библиотек модулей, формирование программ и запуск их на выполнение. Таким образом, разработка ППП требует привлечения системных программистов или использования инструментального средства, облегчающего разработку системной части пакета.
Одним из основных направлений в разработке инструментальных систем для пакетов прикладных программ является предложенный Э.Х. Тыугу подход, основывающийся на автоматическом синтезе программ и реализованный в системах СШІ, ПРИЗ-32 и ПРИЗ ЕС \_2]. Он позволяет создавать пакеты прикладных программ, обладающие гибкими средствами описания модели предметной области, расширяемые в процессе развития. Важным достоинством этого подхода является возможность интегрирования различных пакетов в единую систему.
С появлением в последние годы новых семейств ЭВМ: минимашин серии СМ, многопроцессорных вычислительных комплексов "Эльбрус"— возникла потребность в разработке для них системы автоматического синтеза программ. Была поставлена задача разработать мобильную систему автоматического синтеза.
Целью настоящей диссертации является разработка и реализация мобильного синтезатора программ (системы МИС). В ходе исследований были поставлены и решены следующие задачи:
1) разработаны принципы создания мобильных систем применительно к системам с автоматическим синтезом программ;
2) разработан внутренний язык (абстрактная машина) для представления результатов трансляции с входного языка и синтезированного алгоритма;
3) предложена схема организации базы знаний;
4) разработан метод обеспечения мобильности систем с автоматическим синтезом программ за счет выделения машинно-зависимых компонент и локализации их в небольшом числе модулей.
Данная диссертация выполнена в рамках работ по программе решения научно-технических проблем ГКНТ СССР 0.80.14 (задание 09,22 "Создать и ввести в эксплуатацию систему генерации проблемно-ориентированных пакетов программ для многопроцессорного вычислительного комплекса "Эльбрус-1").
Справки, подтверждающие внедрение результатов диссертации, приведены в приложении I. Основные результаты диссертации докладывались на:
Всесоюзной конференции "Автоматизация производства пакетов программ" в Таллине в 1980 г., заседании рабочей группы по реализации языков программирования Комиссии по системному математическому обеспечению ККВТ в Кишиневе в 1983 г., заседании Комиссии по новой информационной технологии ККВТ в Минске в 1984 г.
Основное содержание работы изложено в публикациях 5, 22-25 .
Изложение в диссертации построено следующим образом.
В первой главе дается обзор систем автоматического синтеза программ и рассматриваются проблемы разработки мобильного программного обеспечения.
Вторая глава посвящена описанию основных концепций и функциональных возможностей системы МИС. Излагаются основные понятия и дается обзор входного языка системы.
В третьей главе рассматриваются наиболее существенные аспекты реализации мобильного синтезатора программ. Описывается организация семантической памяти, абстрактная машина для языка Утопист и архитектура системы в целом.
Четвертая глава посвящена переносу системы МИС на различные ЭВМ.
В заключении приводятся основные результаты, полученные в диссертационной работе.
Личный вклад автора диссертации в разработку системы МИС заключается во введении новых функциональных возможностей и расширении входного языка (см. главу 2), проектировании системы в целом и разработке основных информационных структур (гл. 3) и в разработке и реализации концепции мобильности, рассматриваемой в главе 4.
Синтезаторы на вычислительных моделях
Понятие вычислительной модели было введено Э.Х. Тыугу[б, І], Вычислительная модель - это совокупность объектов, связанных между собой отношениями. Отношения на вычислительной модели являются конструктивно вычислимыми, т.е. при их описании явно указывается, какие из участвующих в отношении объектов являются входные ми, а какие выходными. Если нужно включить в модель алгебраическое уравнение, нужно разрешить его относительно всех входящих в него переменных (во всех рассматриваемых здесь системах это делается автоматически).
Ограничение на вид отношений позволяет синтезировать решение задачи за не более чем полиномиальное время \д. Системы, использующие синтез на вычислительных моделях, формулируют это понятие либо явно (ПРИЗ [2J, СПОРА ІЗ]), либо неявно (различные варианты системы VisiCalc [l4] и система ТК! Solver [_10])# Далее мы вкратце опишем особенности этих систем. Основное внимание при этом будет обращено на следующие вопросы: - назначение системы, - средства формирования базы знаний, - возможности описания объектов, - средства управления вычислениями, - режим работы, - возможности интеграции системы с другими программами. Инструментальная система ПРИЗ
Система предназначена для разработки интеллектуальных пакетов прикладных программ. Она снабжена входным языком, на котором описывается как модель предметной области, так и постановка задачи. Отношения описывают связи между объектами и могут реализовы-ваться либо модулями функционального наполнения пакета, либо уравнениями. Объекты имеют иерархическую структуру, предусмотрены различные типы элементарных компонент. Любой уже описанный объект может использоваться как тип при определении нового объекта, при этом предусмотрены возможности параметризации как типов, так и отношений. Обеспечены средства долговременного хранения моделей, причем-реализовано "прозрачное" использование архива моделей с помощью механизма производных описаний.
Средства задания вычислений на модели включают в дополнение к оператору постановки задачи, запускающему синтез программ, набор традиционных для языка высокого уровня конструкций. Результатом работы транслятора является управляющая программа, содержащая вызовы модулей пакета прикладных программ. Затем происходит сборка программы и ее выполнение. Система может функционировать как в пакетном, так и в диалоговом режиме. Система СПОРА [з] предназначена для использования примерно в тех же областях, что и система ПРИЗ: для разработки интеллектуальных пакетов прикладных программ.
Система снабжена входным языком ДЕКАРТ, который разделяется на две части: средства, предоставляемые администратору системы для описания модели задачи и средства, предоставляемые пользователю пакета для постановки задачи (операторная часть языка). One-раторная часть языка реализуется препроцессором к одному из языков программирования высокого уровня.
Язык строится на основе понятий абстрактного типа данных и абстрактного отображения (отношения в вычислительной модели). Объекты могут быть либо элементарными, либо составными (двухуровневыми). Обеспечена возможность различных представлений одного и того же объекта.
При написании программы на одном из существующих языков программирования пользователь может использовать конструкции операторной части языка ДЕКАРТ для указания модели предметной области и запуска синтезатора программ. Предложения ДЕКАРТа извлекаются из программы, обрабатываются и генерируется программа на языке высокого уровня.
Средства автоматического контроля целостности модели в системе отсутствуют. Контроль целостности возлагается, таким образом, на администратора, составляющего модель предметной области. В системе предусмотрен интерфейс к базе данных.
Обзор входного языка
Язык взаимодействия пользователя с системой МИС сохранил основные черты входного языка системы ПРИЗ. Он разбивается на три части: I. Командный язык, предназначенный для управления работой системы. Он включает следующие средства: - директивы управления семантической памятью, - изменение режимов работы системы, - средства вызова сервисных программ. 2. Язык Утопист, предназначенный для работы с моделью пред метной области. Он состоит из языка описания моделей и языка опи сания вычислений на модели. Синтаксис версии языка Утопист, ис пользуемой в системе МИС, приведен в приложении 2. 3, Язык макроопределений, предназначенный для создания проб лемно-ориентированных входных языков. Вычислительная модель Предметная область описывается на Утописте в виде набора вычислительных моделей. Вычислительная модель — это совокупность объектов, связанных между собой отношениями. Объектом может быть как простая переменная, так и сложная структура, состоящая из связанных между собой подобъектов. Отношение определяет, во-первых, связь между двумя множествами объектов: входными и выходными, и, во-вторых, способ получения значений выходных объектов по значениям входных. Определение объектов в языке описания моделей Описать объект в языке Утопист можно одним из следующих способов: 1. Объект можно определить как элементарный: целый, вещест венный, логический или текстовый. Пример: Angle: real; 2, Объект можно строить из подобъектов, связанных между со бой или с другими объектами отношениями. Пример: Line: (Angle: real; Point: (X,Y: real)); 3. Объект строится как производный от другого объекта, наследуя его структуру и отношения; при этом возможно введение дополнительных отношений. Пример: Vertline: Line rel cos(Angle) = 0; База знаний и параметризация объектов Для создания пакетов прикладных программ важно иметь возможность долговременного хранения моделей. Для этой цели в системе предусмотрена база знаний (архив моделей). База знаний организована как иерархия моделей. Содержимое текущей модели может быть занесено в базу знаний соответствующими директивами.
База знаний или ее часть, указанная специальной директивой, рассматривается как продолжение текущей модели. Это означает, что если объект определяется как производный от некоторого другого объекта, то поиск последнего ведется сначала в текущей модели, а затем в базе знаний. Так, в приведенном выше примере, описание объекта Line может храниться в базе знаний, откуда оно будет извлечено системой и использовано для определения объекта Vertline. Если объект Line хранится в базе знаний как часть модели Geometry, то описанию Vertline должна предшествовать директива use Geometry;
Вообще говоря, в базе знаний разумно хранить универсальные описания. Для этого предусмотрена возможность параметризации описания объекта, обеспечиваемая за счет введения специального описания типа undef (неопределенный). Это позволяет хранить в базе знаний следующее универсальное описание стека: Stack: (Element: undef; Push: rel in Element impl mod (PUSHED; pop: rel out Element impl mod (POPEL) ; Естественно, непосредственно использовать такой объект в процессе вычислений система не позволяет. Однако его можно использовать для описания объекта "стек целых": IntStack: Stack Element type int; Задание отношений Описываемая некоторым отношением связь между объектами может реализовываться двумя способами: 1. Модулем из пакета прикладных программ. Например, Samprel: rel in X out Y impl mod (SUBR); означает, что модуль SUBR вычисляет по входному объекту X выходной объект Y. 2. Алгебраически: отношение rel X я Y = Z; означает, что если известны значения любой пары объектов из тройки X, Y и Z, то можно вычислить значение третьего объекта. Задание отношений в алгебраическом виде особенно удобно на этапе отладки модели предметной области, хотя, вообще говоря,является менее универсальным: так, в приведенном выше примере, если нам заданы Y и Z, система будет считать, что можно вычислить значение х; между тем, если значение Y будет равно нулю, это невозможно и во время выполнения программы будет выдано сообщение о неразрешимом уравнении.
Предоставляемые системой средства описания вычислений разбиваются на две группы. К первой относятся конструкции, использующие семантику вычислительной модели в полном объеме. Таких конструкций две: оператор постановки задачи и оператор применения отношения. Во вторую группу входят конструкции входного языка, использующие семантику вычислительной модели лишь частично: модель используется лишь как описание структуры данных, без учета информации об отношениях.
Основным средством описания вычислений в Утописте является оператор постановки задачи, который имеет вид: compute (1 входные объекты ] -хвыходные объекты?) Обработка такого оператора называется планированием. Планирование вычислений происходит на основе содержащейся в описании модели информации об отношениях; при этом используются как описанные явно отношения, так и структурные отношения между составными объектами и их компонентами. На первом этапе планирования используется только формальная семантика отношений и строится алгоритм решения задачи; способ реализации отношения используется на втором этапе планирования для построения фрагмента программы, решающего поставленную задачу.
Абстрактная машина для языка Утопист
При разработке архитектуры абстрактной машины для языка Утопист (АСМ) были проанализированы следующие факторы: - типы данных, допускаемые языком; - наличие традиционных для языка программирования конструкций; - наличие средств автоматического синтеза программ; - необходимость взаимодействия с библиотекой программ. Организация памяти АСМ имеет память, организованную словами. Слово может содержать целое число, вещественное число или последовательность символов. Переменные представляются в памяти следующим образом: - целая переменная занимает одно слово; - вещественная переменная занимает одно слово; - булевская переменная занимает одно слово: значение false представляется как 0, true— как I; - текстовая переменная занимает некоторое число последовательных слов; например, если в слово помещается 4 символа, для размещения текстовой переменной длиной п символов требуется Гп/4І слов; - составной объект располагается в памяти последовательно в порядке размещения его элементарных компонент. АСМ использует одноуровневую схему адресации. Для вычисления выражений в АСМ используется стек. Например, оператор части действий А :а В + С D; транслируется в следующую последовательность команд абстрактной машины: LOAD В - загрузить В LOAD С - загрузить С LOAD D - загрузить D MULF - перемножить С и D ADDF - прибавить к В STOR А - записать в А Здесь и далее мы будем использовать "ассемблерную" форму записи программ для АСМ; в таком же виде система МИС распечатывает объектный код при вызове соответствующей сервисной программы. Для реализации операторов управления АСМ содержит команды перехода: безусловного и условного (условие определяется значением, находящимся на верхушке стека). Например, фрагмент программы на входном языке while (X Y) do od транслируется в L1 LOAD X - загрузить х LOAD Y - загрузить Y CPLT - сравнить на JMPP L2 - если неверно, завершить цикл ... JMP L1 - повторить цикл
Результатом планирования (в случае, если оно завершилось успешно) является последовательность отношений, которые должны быть применены для решения поставленной задачи. Применяемые отношения могут быть алгебраическими (т.е. реализуемыми уравнением) или процедурными (реализуемыми модулем); процедурные отношения могут содержать подзадачи. Во время трансляции информация об отношениях накапливается в таблице реализаций, где для каждого отношения хранятся: - его тип (процедурное, алгебраическое или подзадача), - для процедурных отношений— имя реализующего отношение модуля; для алгебраических отношений и подзадач— адрес сгенерированной транслятором процедуры, реализующей отношение; - ссылочный номер, присваиваемый отношению, как только оно применяется. По завершении трансляции подготавливаются три таблицы, исполь зуемые при выполнении объектной программы: таблица внутренних процедур, описывающая примененные алгебраические отношения, таблица внешних процедур, описывающая примененные модули, и таблица подзадач, описывающая синтезированные по подзадачам процедуры. Отношения помещаются в таблицы в порядке следования их ссылочных номеров. Для обращения к каждой из этих таблиц имеется соответствующая команда: вызвать внутреннюю процедуру (SUBR), вызвать модуль (CALL), передать модулю сгенерированную по подзадаче процедуру в качестве параметра (LSUB). Операнд команды указывает при этом номер элемента в соответствующей таблице. Применение процедурных отношений Особенностью системы МИС как системы программирования является то обстоятельство, что результатом трансляции является только управляющая часть программы, содержащая обращения к реализующим отношения внешним модулям. Модули хранятся в библиотеке в объектном коде и объединяются с управляющей программой перед началом выполнения программы. Таким образом, во время выполнения программы одна ее часть (а именно та, которая сгенерирована по входному тексту на Утописте) "выполняется" на абстрактной машине, а другая— модули— исполняется непосредственно. При этом мы не можем предполагать, что внешние модули подчиняются принятым в системе МИС соглашениям о связях, поскольку эти соглашения уже зафиксированы во внешних модулях. Предоставляемый абстрактной машиной набор команд не уточняет способа передачи параметров, что обеспечивает необходимую гибкость при реализации АСМ.
Модель реализации абстрактной машины
Мы опишем здесь модель интерпретатора, которая использовалась для реализации АСМ на ЕС ЭВМ, БЭСМ-б и МВК "Эльбрус". Выполнение программы абстрактной машиной происходит в два этапа, которые по аналогии с обработкой программ на реальной ЭВМ мы будем называть загрузкой и выполнением, а реализующие эти этапы программы— соответственно загрузчиком системы МИС и интерпретатором.
Организация данных во время работы интерпретатора показана на рис. 7. Таблица внутренних процедур содержит адреса внутренних процедур в тексте программы для абстрактной машины. Таблица внешних процедур содержит адреса модулей прикладной программы. Таблица подзадач содержит адреса вступлений, которые формируют ся в процессе загрузки и служат для передачи управления интерпретатору в момент, когда прикладной модуль должен вызвать подзадачу. Выполняемый на процессоре загрузочный модуль состоит из интерпретатора, модулей прикладной программы и вступлений к подзадачам. В динамической области (рис. 8) размещаются память абстрактной машины и стек вычислений. Загрузка программы Структура, приведенная на рис. 7, создается загрузчиком системы МИС, который работает следующим образом: 1. На основании таблицы реализаций (см. п. 3.2) создается объектный модуль в соответствии со стандартом данной операционной системы. Этот модуль содержит таблицу внутренних процедур, таблицу внешних процедур, таблицу подзадач и набор вступлений к ним. 2. Вызывается программа операционной системы, ответственная за формирование загрузочного модуля (в терминологии ОС ЕС - связывающий загрузчик, в терминологии МВК "Эльбрус" - комплексатор и т.д.), которая подключает внешние модули и интерпретатор, заполняет адресами таблицу внешних процедур, выполняет перемещение адресных констант в таблице подзадач и формирует готовую к выполнению программу (загрузочный модуль). 3. Загружается интерпретируемый текст, выделяется память для динамической области и вызывается сформированная на предыдущем этапе программа.
Остановимся на особенностях реализации некоторых команд. 1. Управление памятью. В динамической области хранится стек экземпляров памяти. В начале каждого экземпляра имеется заголовок, в котором хранится адрес предыдущего экземпляра и список переданных из вызывающей процедуры параметров. По команде GETM отводится новый экземпляр памяти (его длина вычисляется загрузчиком и передается параметром интерпретатору). По команде FREM из заголовка текущего экземпляра памяти выбирается адрес предыдущего экземпляра. 2. Вызов внутренних процедур. В старших адресах динамической области находится стек вычислений, который расширяется в сторону уменьшения адресов. Вызову внутренней процедуры предшествует команда MARK, по которой в стек заносится слово, содержащее адрес предыдущего маркера, и в регистр маркера стека заносится адрес вершины стека. Параметры внутренней процедуры адресуются относительно этого маркера. При возврате из внутренней процедуры со стека стирается все вплоть до маркера, после чего восстанавливается старое состояние маркера. 3. Взаимодействие с подзадачами. Для каждой из подзадач загрузчик формирует вступление. Это последовательность из нескольких машинных команд, обеспечивающих вызов интерпретатора с передачей ему двух параметров: адреса списка параметров, переданных вызывающей программой, и адреса первой команды интерпретируемого кода подзадачи. Когда в процессе интерпретации выполняется команда LSUB (передать параметр-подзадачу), интерпретатор передает параметром адрес вступления для подзадачи. Таким образом, при вызове подзадачи из пользовательского модуля управление попадает на вступление и из него в интерпретатор, так что интерпретатор должен допускать рекурсивный вызов. Объем интерпретатора на различных системах составляет 300-800 строк. Дяя реализации интерпретатора использовались как ассемблер (ЕС ЭВМ, БЭСМ-6), так и языки более высокого уровня: Эль-76 (Автокод "Эльбрус") для МВК "Эльбрус" и Фортран для НОРД-Ю.
Для переноса системы МИС постановщику передаются: 1. Дистрибутивная лента системы. 2. Описание интерфейса с машинно-зависимыми программами. 3. Описание абстрактной машины. 4. Таблица перекрестных ссылок между программами системы. На дистрибутивной ленте находится один файл, состоящий из 80-байтовых записей в коде ДКОИ, содержащий тексты всех машинно-независимых модулей. Каждому модулю предшествует карта-комментарий специального вида, содержащая имя модуля, что позволяет достаточно просто сформировать текстовую библиотеку для программ системы. Кроме текстов модулей, в файле находится также набор тестовых примеров на языке Утопист, а также вспомогательные программы для формирования модуля инициализации таблицы ключевых слов и таблицы сообщений об ошибках и программа для инициализации архива моделей.
Процесс установки системы состоит из нескольких этапов. В первую очередь требуется прочитать магнитную ленту w сформировать из нее библиотеку текстов системы. В некоторых случаях (например, в минимашинах используется код КОИ-7) требуется также произвести перекодировку текстов. Задача чтения магнитной ленты, хотя и является тривиальной, во всех случаях переноса наталкивалась на трудности: в многих ЭВМ типа БЭСМ-б отсутствуют лентопротяжные механизмы для чтения стандартных магнитных лент; на ЭВМ Н0РД-І0, на которую осуществлялся перенос, вообще не было лентопротяжного механизма, а единственным переносимым носителем были гибкие диски; лентопротяжные механизмы СМ-4 рассчитаны на бобины малого диаметра; системное обеспечение для работы с лентами для МВК "Эльбрус" не было до конца отлажено на момент переноса. За исключением МВК "Эльбрус", во всех случаях для чтения магнитной ленты потребовалась промежуточная ЭВМ.