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

комитет шормизации

ПРИ МИНИСТЕРСТВЕ СВЯЗИ РОССИЙСКОЙ 5Щ2РА1Щ

ВСЕРОССИЙСКИЙ НАЯНО-ИССЛЕЕОВАТЕЛЬСКО ИНСТИТУТ ПРОБЛЕМ ШЧЕСЖГЕЛЬНОЯ ТЕШЗШ И Ш&ОРЛЯГИЗНЩ

На правах рукописи УЩ 681'.3.06

Гайнер ¡¿ария Львовна

АНАЛИЗ И РАЗРАБОТКА МОДЕЛИ АРШЕКТУга ВЫЧИСЛИТЕЛЬНОЙ СИСГЕШ, ОРИЕНТИРОВАННОЙ НА 'ЯЗЫКИ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Специальность 05.13.13 - Вычислительные иатиш, вошшексы,

системы и сети

АВТОРЕФЕРАТ

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

Москва 1992

Работа выполнена в Научно-исследовательском институте ,! счетного машиностроения ' '

доктор технических наук,_профессор Щерс Артур Львович

доктор технических наук, профессор Клыков Врий Иванович ч/ кандидат физико-математических наук, доцент .

Григорьев Сергей Георгиевич

Ведущая организация - Институт проблем информатики

Российской академии наук \

Заартга состоится " /@ 199^-г. в 14 часов на заседании специализированного совета Д 163.01.01 при Всероссийском научно-исследовательском институте проблем вычислительной техники и информатизации по адресу: 113114, г. Москва, 2-ой Кожевнический пер., д. 4/6.

С диссертацией моасно ознакомиться в научно-техническом архиве ВНИШВТИ.

Автореферат разослан ¿)9 199.¿-г.

Научный руководитель -

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

Ученый секретарь

специализированного совета .

доктор технических наук и? Р.Г. Бияшев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. В настоящее время все более широкое распространение получает направление использования гачнсяительной техники, основанное на применении экспертных систем, обеспечивающих выбор правильных решении в условиях, связанных с анализом большого количества параметров, неоднозначностью задачи и отсутствием единых критериев качества. Одним из наиболее перспективных языков программирования для создания экспертных систем является Пролог, воплощающий принципы логического программирования. Эффективное применение языка Пролог предполагает использование архитектуры ЕЕМ, коренным образом отличающейся от традиционной фон-Неймановской. Такая архитектура основывается на параллелизме, естественно присуцеы логическому программировании. С другой стороны, поскольку в обозримой перспективе по-прехнему будут пнро-ко использоваться ЗЗМ с фон-Неймановской архитектурой, на которых программирование в основном ведется на процедурных языках, актуальной является задача реализация Пролога на ЕВМ с такой архитектурой, в частности, на 11324 и микроЭЗМ.

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

Реализация языка логического программирования Пролог на ЗЗМ с фон-Неймановской архитектурой, в частности, на 8-разрядной учебной ПсШ требует тщательной проработки модели последователь-

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

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

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

Задачами исследования являются:

- построение общей модели программных и аппаратных средств ВС, отражающей различия между уровнями представления выполняемых алгоритмов, а таете между типами языков программирования и систем команд сШ;

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

- построение модели архитектуры абстрактной последовательной Пролог-машины низкого уровня, на которой основывается реализация языка Пролог для учебной ПЗЗМ;

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

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

Научная новизна. Сформулированы требования, которым должна удовлетворять реализация языка Пролог для учебной ПЗЗМ.

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

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

б

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

Практическая значимость исследования определяется использованием разработанной ивдели архитектуры абстрактной Пролог-машины при создании системы автоматизации программирования (САП) ПРОЛОГ для комплекта учебной вычислительной техники (КУВТ) "Корвет". Использование на КУЕТ "Корвет" САП ПРСШОГ позволяет учащимся на практике знакомиться с принципами логического программирования и декларативного представления знаний, что значительно повышает эффективность учебного процесса.

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

Предложенная модель архитектуры абстрактной Пролог-машины мсшет быть использована для реализации языка Пролог на других ЗЗМ, в особенности 5ВМ, по своим техническим характеристикам близкш к "Корвету", при схожих требованиях к реализации.

Реализация результатов исследования. САП ПРОЛОГ, в которой реализованы результаты диссертационной работы, входит в состав инструментального программного обеспечения КУВТ "Корвет", выпускаемого серийно. САП ПРОЛОГ снабяена эксплуатационной документацией и в настоящее время используется во многих учебных заведениях на территории СНГ.

Апробация Работы. Основные результаты диссертационной работы докладывались на семинаре "Моделирование программных средств микропроцессорных систем", г. Москва, 1984 г.I четвертом всесо-

юзном семинаре "Разработка и применение программных средств ПЗЗМ в учебном процессе", Симферополь, 1988 г., пятом всесоюзном семинаре "Разработка и применение программных средств ПЗЗМ в учебном процессе", Ордхонинидзе, 1989 г., шестом всесоюзном семинаре "Разработка и применение программных средств ПсШ в учебном процессе", Москва, 1991 г.

Публикации. Основные результаты работы опубликованы в 4 печатных работах.

Объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и двух приложений, содержит ЦЗ страниц текста, 4 рисунка и I таблицу. Список используемой литературы содержит 48 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Введение содержит общую постановку проблемы и краткую характеристику всей работы. На основе анализа особенностей использования языка Пролог в обучении сформулированы требования, предъявляемые к реализации Пролога для учебной ПЗЗМ.

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

низкого уровня, в которой базовые операции Пролога присутствуют явно, в виде соответствующих команд- Наиболее известной моделью Пролог-малины низкого уровня является абстрактная машина Уоррена ЫШ). Проведен обзор литературы по архитектуре абстрактных ПРолог-машин низкого уровня, реализованных с помопр>ю микропрограммных или аппаратных средств, а таете по методам оптимизации, применяемой в различных реализациях Пролога как на этапе компиляции, так и на этапе выполнения. Рассмотрены также методы расширения Пролога графическими средствами.

В конце главы отмечается, что абстрактные Пролог-машины, создававшиеся ранее, были ориентированы на реализацию с помощью аппаратных или микропрограммных средств в специализированных процессорах, которые должны были использоваться в ВС, предназначав»

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

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

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

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

для реализации процессора более высокого уровня, и указывается, что в сущности она является определенней интерпретатора:

РГ[ = PSj-i = f(?r,.iiPl.i) 1*1,... п где -f(Pt~> Р) обозначает процесс выполнения программы Р на процессоре Рг. Там асе указывается, что кахдый интерпретатор включает в себя блок распознавания возможных действий и блок выполнения действий, а таете, что переход от процессора некоторого уровня к процессору более низкого уровня мохет осуществляться и путем компиляции, причем компилятор во многих случаях берет на себя функции распознавания.

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

usa вдоль вертикальной оси, наиболее проста и генерирует объектную программу наименьшего объема.

В работе рассмотрено применение данной модели к иерархии абстрактных Пролог-машин, а таете к иерархии программно-аппаратных средств Я SU, входящих в КУБГ "Корвет". Применение модели к Пролог-машинам трех уровней показало, что с понижением уровня увеличивается доля статического распознавания (предполагается, что интерпретация производится на машине фон-Неймановского типа), т.е. сами Пролог-машины приближается к фон-Неймановскому типу.

Сформулировано строгое определение реализации языка программирования для некоторого процессора, основанное на рассмотренной модели: Пусть дан язык L , соответствующий процессору ?rL , и процессор Рг2 . Тогда под реализацией языка Li для процессора Ргл понимается создание такого набора программ [р;] (г? i ), выполняемых на процессорах[Рг,}, что для всякого набора данных D и для всякой программы выполняемой на процессоре Р rt , применение процесса (Pi-j , Pj ) к D эквивалентно применению процесса

(Ргг,Р2) к набору данных D , где Р2 - программа, в общем случае однозначно определяемая исходной программой Pj и одной из программ, входящих в набор программ [Pr J , a D включает исходный набор данных D , а также дополнительные данные, однозначно определяемые исходной программой Pt и одной из программ, входящих

Л,

в набор[Рг]. Кратко это можно записать так:

* VPi [ PrJ VЛ j(Pq POfDj ^^(P^JXDug, (Pi, P\) Проведена конкретизация данного определения для таких методов реализации языков, как компиляция, интерпретация, использование промежуточных языков. Показано, что данное определение является обобщением приведенного выше определения интерпретации из литера туры.

п

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

Третья глава посвящена описанию архитектуры абстрактной Пролог-машины низкого уровня. Предлагаемая Пролог-машина во многом аналогична УАЫ и называется модифицированной 1</Ш (М1А11). Основными отличиями ШШ от являются следующие:

I. В МШ1 отсутствуют комаеды индексирования, вместо них ис-

л

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

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

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

следующий образом : для данных структур генерируются•команды get I put и unify специального вида, а команды unify , соответствующие элементам этих структур, не генерируются. В место них в область генерируемого "чистого кода" встраивается структура в том веде, в каком она была бы скопирована в стск. Зго позволяет на этапе выполнения не производить копирование структуры в стек, но работать с ней гак, как будто она была скопирована.

4. Используется метод выполнения встроенных предикатов, работающих с динамическими подцелями (QSSert % retract, call), позволяющий не осуществлять компиляцию их аргументов в команды liVAU. При выполнении предиката assert (аргументом которого может быть -факт, но не правило) производятся обычные действия, связанные с занесением нового клоза в базу данных Пролога, однако вместо ссылки на последовательность команд lilvM формируется ссылка на структуру» являющуюся аргументом assert, и в заголовке представления соответствующего клоза устанавливается специальный признак. Если при выборе клоза обнаружено, что он имеет данный признак и, следовательно, занесен в базу данных Пролога с помощью предиката assert « выбора и интерпретации команд WM, соответствующих данному клозу, не производится, а выполняется унификация соответствующей структуры с вызывающей подцелью. Аргумент предиката retract должен, во-первых, быть фактом, во-вторых, данный факт должен был быть добавлен к базе данных Пролога с помощью предиката assert . При выполнении предиката retract по специальной ссылке в заголовке процедуры находится первый факт, занесенный с помощью предиката a?£erfc, и производится последовательное сопоставление аргумента предиката retract со всеми структурами, занесенными с помощью предиката assert, до тех пор, пока унификация не проГдет успешно. При выполнении предиката СО II , если его

аргументом является структура, аргументы этой структуры помещаются в регистры аргументов A j , после чего производится вызов процедуры, определяемой функтором и числом аргументов данной структуры.

5. В МШМ определены графические встроенные предикаты, позволяющие выводить на экран такие элементарные объекты, как точка, отрезок прямой линии, окружность, прямоугольник,а также выполнять закраску фигуры и очистку экрана. В данных предикатах к моменту ' их выполнения все аргументы должны быть конкретизированы. Для иллюстрации принципов логического программирования графическими примерами введен предикат pcrnt (Х,У,С), для которого допускаются не-конкретизированные аргументы. Если все аргументы конкретизированы, результат эквивалентен истинности факта, что точка с координатами Х,У имеет на экране цвет С. Если координаты Х,У конкретизированы, а дает С - нет, он конкретизируется значением цвета соответствующей точки на экране, если неаонкретизированы значения координат, а цвет конкретизирован, они конкретизируются минимальными значениями координат, имеющих данный цвет.

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

вводе клоза, в котором данный графический объект включается в другой графический объект.

Четвертая глава посвящена реализации Пролог-машины на КУВТ "Корвет". КУВТ "Корвет" представляет собой набор 8-разрядных ПсШ, связанных лекальной информационно-вычислительной сетью. Одна ПЗЗМ, содержащая ЩЦ, называется рабочим местом преподавателя (ИП). Она связана со всеми остальными ПЗЗМ, которые ПОД не имеют и называются рабочими местами учащихся (ГНУ).

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

Реализация проведена в два этапа. На первом этапе в качестве прототипа была перенесена система ПРСШОГ-ЫР с ПсШ Rob о ¿fon 1715, ядром которой является интерпретатор Пролог-машины высокого уровня. На втором этапе была создана программная система, реализующая абстрактную Пролог-машину УМШ. Основными компонентами этой системы в версии для РШ является: компилятор, интерпретатор команд HWAM, текстовый редактор, программа управления меню (последние два относятся к вспомогательным средствам из второй группы). Все указанные выше компоненты располагаются в оверлейных модулях. Блоки синтаксического анализа и предварительной обработки, входящие в состав компилятора, текстовый редактор, программа управления меню, а также блоки интерпретации некоторых

встроенных предикатов .заимствованы из системы ПРОЛОГ-ЫР.

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

"Машина реализации", с помощью которой осуществляется интерпретация ШАМ, включает в качестве основной компоненты процессор языка Паскаль, а таме процессор языка Макроассемблер (без использования макросредств"). Макроассемблер используется, во-первых, для вспомогательных процедур, необходимых для переноса модулей, заимствованных из системы ЙРОЛОГ-МР, во-вторых, для алгоритма унификации термов, связанных с переменными, значения которых не известны на этапе компиляции, а также структур, скопированных в стек. Использование Макроассемблера для алгоритма унификации позволило, с одной стороны, применить нерекурсивный алгоритм унификации (и тем самым избавиться от медленно действующих средств реализации рекурсивных процедур системы Паскаль), а с другой стороны, использовать аппаратный стек микропроцессора для хранения временных данных, используемых в процессе унификации.

Все основные области данных М^йМ представлены в интерпретаторе в виде последовательных ячеек ОЗУ, доступ к которым осуществляется с помощью переменных ссылочного типа. Область программного кода во время выполнения запроса остается фиксированной по размеру, поэтому область одного из стеков МЩ1 может располагаться, непосредственно примыкая к области программного кода. Регистры аргументов и регистры временных переменян* ШЛИ люелгуравпяш^шт яле-

центами массивов. Очввидно, что при представлении регистров ячейками памяти с косвенным доступом доступ к ним по времени оказывается почти таким же, как к постоянным переменным, хранящимся в контексте, однако разделение переменных на постоянные и временные оправдывает себя из-за того, что экономится память в контексте, что особенно важно при рекурсивных вызовах. Аппаратный стек микропроцессора используется, во-первых, при работе блоков интерпретатора, написанных на Паскале, для хранения адресов возврата и параметров процедур (что предусмотрено реализацией Паскаля), во-вторых, при работе блоков, написанных на Макроассемблере, для'хранения служебной информации, используемой при унификации вложенных структур и списков.

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

Особенности реализации Пролог-машины на РЫУ вызваны такими отличиями РМУ от НИ, как отсутствие ГЭД и ре возможность организации оверлейной структуры программ, отсутствие ОС МикроДОС, наличие в базовой конфигурации ПЗУ с интерпретатором языка Бейсик, ненужным для работы Пролог-машины. Для обеспечения возможности функционирования Пролог-машины на РИУ были разработаны дополнительные программные средства, которые позволили создать на базе ЕЛУ абстрактную машину, соответствующую "машине реализации" Про-

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

Пролог-машина, реализованная на ШУ, несколько отличается от Пролог-машины, реализованной на РМП. Во-первых, не реализован ряд встроенных предикатов - в частности, все предикаты, обращающиеся к Г4Д, а также вспомогательные предикаты, выводящие содержимое базы данных Пролога на терминал. Из-за ограничений по памяти не реализованы такие вспомогательные средства, как текстовый экранный редактор и программа управления меню. Редактирование вводимой информации возможно только в пределах одной строки, как в интерпретаторе .Бейсика. С другой стороны, ряд операций, выполняемых нереализованными встроенными предикатами, а также опера- * ций, задаваемых на Ш1 с помощью меню, на РЛУ реализованы в виде так называемых служебных функций, запрос на выполнение которых задается путем ввода однобуквенной команды в момент, когда система ждет ввода с клавиатуры нового клоза на языке Пролог, запроса на выполнение программы на Прологе, либо упомянутой команды. Все параметры для команд задается в диалоговом режиме, в ответ на запрос системы.

Наиболее важными служебными функциями являются прием текстов программ на Прологе с ГЦЦ ВО, компиляция и занесение их в базу данных Пролога, а также передача текстов из базы данных Пролога на ПДЦ Ml (с декомпиляцией), что использует средства локальной сети. Первая функция аналогична предикату consult , вторая - последовательности tell, hsfanj , iold . Другими служебными функциями являются вывод на экран содержимого базы данных

Пролога (аналог предиката 1лд), а также удаление клозов из базы данных Пролога. Последняя функция аналогична предикату геЬгчс^ однако в отличие от данного предиката с помощью нее можно удалать не только факты, но и правила. Особенностью служебных функций по сравнению с аналогичными им встроенными предикатам является то, что юс выполнение производится в моменты, когда Пролог-машина не работает, т.е. выполнения запросов не производится и в ОЗУ не размещены области данных мийм. ?го позволяет эффективно использовать память для буферов, требуемых для приема и передачи информации по сети.

Поскольку смысл функций приема и передачи файлов по сети предполагает, что соответствующие сетевые операции инициализируются со стороны ИУ, но дисциплина работы локальной сети НУБТ "Корвет" не позволяет инициализировать сетевые операции со стороны ИЛУ, для реализации Пролог-машины на ШУ бьш создан новый уровень локальной сети КУНГ "Корвет". Реализация этого уровня основана на организации на РМУ "почтового ящика", в который помещается запрос на выполнение сетевой операции и необходимая информация. Рассылка системы Пролог на РМУ, а также управление обменом файлами между В!П и РМУ осуществляется с помощью специальной программы - диспетчера, работающей на ВН. Диспетчер постоянно в цикле опрашивает все РМУ. Если на каком-либо РЛУ в "почтовом ящике" есть запрос, диспетчер инициализирует требуемую сетевую операцию, после завершения которой опрос возобновляется. С момента подачи заявки на выполнение сетевой операции до завершения сетевой операции на данном ШУ система Пролог не работает, причем период простоя может включать не только время передачи информации по сети для данного Й4У, но и время ожидания выполнения сетевых операций на других ШУ. Поскольку время

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

Программная система, реализующая Пролог-машину для КШГ "Корвет", является законченным программным продуктом, называемым системой автоматизации программирования (САП) ПРОЛОГ. Объем программных средств, лично разработанных автором, составляет 35 Кбайт.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

IСформулированы требования, предъявляемые к реализации языка Пролог на учебной ПсШ класса "Корвет", а также к архитектуре абстрактной Пролог-машины, используемой в реализации.

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

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

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

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

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

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

- методом представления и выполнения динамических подцелей, позволяющим не производить их компиляцию в команды абстрактной машины;

- набором встроенных графических предикатов, позволяющим средствами Пролога создавать параметризуемые графические объекты, выводить их на экран, сохранять на ГЦД, включать в другие объекты.

4. Проведена реализация Пролог-машины на двух типах ПЗЗМ, входящих в КУВТ "Корвет" - рабочем шесте преподавателя (Н4П), содержащем ГЭД, и рабочем месте учащегося (ШУ), не имеющем ПВД. Ядром реализации являются компилятор программ на Прологе в ко-маеды абстрактной Пролог-машины ШАМ и интерпретатор команд данной машины. Реализация Пролог-машины для РМУ' основана на использовании средств школьной локальной сети. Был создан новый уровень сетевых средств КУВТ "Корвет", основанный на использовании "почтового ящика" и позволяющий инициализировать операции приема и-передачи информации по сети со стороны РМУ, который со стороны РМП поддерживается специальной программой - диспетчером.

Разработанные програшы представлены в виде законченного программного продукты, который распространяется на территории СНГ и имеет более IOO установок.

Основные полученные результаты опубликованы в следующих работах:

Г. Либеров A.B., Гайнер МЛ., Субботин Д.М. О переносимости программного обеспечения в микропроцессорных системах. - В кн.: Моделирование программных средств и архитектуры микропроцессорных устройств и систем. Материалы семинара. - Москва, 1984.

2. Гайнер U.JI. О реализации языка Пролог для комплекса учебной вычислительной техники "Корвет". - В кн.: Материалы 1У Всес. семинара "Разработка и применение программных средств П<Ш в учебном процессе". Тезисы докл. - Москва, 1988.

3. Гайнер К.Л., Решеткина Е.Г. Расширение систем программирования КУВТ "Корвёт" графическими средствами. - В кн.: Материалы У Всес. семинара "Разработка и применение программных средств ПсВЛ в учебном процессе". Тезисы докл. - Москва, 1989.

4. Гайнер МЛ. Работа с языком Пролог на КУВГ "Корвет" с использованием нестандартных средств школьной локальной сети. - В кн.: Материалы У1 Всес. семинара "Разработка и применение прог-^ раммных средств ПЭВМ^в учебном процессе". Тезисы докл. - Москва, IS9I.