Некоторые аспекты реализации языка FLOGOL как основы интегрированной системы функционально-логического программирования

Заключение

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

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

ЛИТЕРАТУРА

1. Амамия М., Танака Ю. Архитектура ЭВМ и искусственный интеллект. М.: Мир, 1993.

2. Milner R. The Standard ML core language. Polimorphism: The ML/LCF/Hope Newsletter., vol. 2., no.2, October 1985.

3. Burstall R.M., MacQueen D.B., Sannella D.T. HOPE: An Experimental Applicative Language, 1st International LISP Conference, 1980.

4. Кутепов В.П. Организация параллельных вычислений на системах. М.: МЭИ, 1989.

5. Грызунов В.Б. Разработка и реализация системы функционального программирования для ПЭВМ / Автореферат дис.... канд. техн. наук. М., 1990.

6. Kutepov V., Falk V. Integrated tools for functional, logical and data-flow parallel programming and controlling parallel computations on computer systems // Proceed. Internal Conf. "Parallel Computing technolodgies". Novosibirsk, 1991.

7. Кутепов В.П., Фальк B.H. Направленные отношения: теория и приложения // Известия РАН. Техническая кибернетика. № 4, 1994.

8. Кутепов В.П., Фальк В.Н. Направленные отношения: теория и приложения // Известия РАН. Техническая кибернетика. № S, 1994.

9. Арефьев А.А., Кораблин Ю.П„ Кутепов В.П. Язык граф-схем параллельных алгоритмов и его расширения. // Программирование, 1981, №4, С. 14-25.

10. Фальк В.Н. Теоретические модели языков программирования и вопросы их структурной интерпретации. //Автореф. дисс.... канд. техн. наук. М.: МЭИ, 1978.

11. Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты // Кибернетика. 1979. № 1.

УДК 658.512

А.Г. Бенеташвили Некоторые аспекты реализации языка РЪОСОЬ как основы интегрированной системы функционально-логического программирования

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

1. Интегрированная среда функционально-логического программирования

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

компилятор с входного языка программирования FLOGOL [1, 2, 3], генерирующий внутреннее представление программ, интерпретатор и межплатформенный монитор процессов.

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

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

1.1. Компилятор языка FLOGOL

Компилятор языка FLOGOL осуществляет перевод программы из исходного текстового представления во внутреннее представление, проводит лексический и синтаксический анализ, а также типовой контроль исходной программы [4].

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

Синтаксический анализатор осуществляет проверку исходных конструкций языка на соответствие синтаксическим правилам языка FLOGOL.

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

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

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

DOMAIN Combconst

BEGIN

PREDICATE

{CARDINAL К:..} Exist = IF K=0 THEN о

ELSE {K-l} Exist#->;

FUNCTION

{CARDINALK: 1..; 1:1 ,.K}Comp= {1-1 }Exist#"# {K-l}Exist;

{CARDINAL K:..}Copy =...;

{CARDINAL K:..}ldent

{CARDINAL К:..}Сош =...•

{CARDINAL К:..} Gen =...;

END

USES Combconst;

DOMAIN Dirrel BEGIN

RELATION

{RELATION R(#): #}Rev =

({Out(R)}ldent # {ln(R)}Gen A {ln(R)}Copy) A ({Out(R)}ldent # R # (ln(R)}ldent) A ({Out(R)}CoinA (Out(R)} Exist# {ln(R)}ldent);

END

USES Combconst, Dirrel;

DOMAIN {CARDINAL N:l..}Lists BEGIN

OBJECT {CARDINAL l:O..N}Atom:*;

CONSTRUCTOR NIL, CONS(* #*):*;

FUNCTION Car = {Cons} Rev A {2,1} Comp;

Cdr= {Cons}Rev A {2,2}Comp;

SET Atoms - {N}H.Atms;

SET List = Nil I ((Atoms) I List) # List) A Cons;

PREDICATE Eq = {N}H.Equ;

Ne = {N}H.Neq;

Atm = {Atoms} Rev;

FUNCTION Append = {NIL}Rev # -1 ({Cons}Rev # ”) A

(- # Append) A Cons;

WHERE

DOMAIN {K:0..}H BEGIN

SET Atms = IF K>0 THEN {K-l JH.Atms I {K}Atom; PREDICATE Equ = IF K>0 THEN

{K-l }H.Equ I {{K}Atom A -<}Rev;

Neq = IF K>0 THEN

(K-l)H.Neq I {{K-l }H.Atms # (K) Atom I

{K}Atom # {K-l }H.Atms} Rev;

END

END

В данной системе модулей вводятся операции для работы со списками, такие, как Car, Cdr, Append и другие. В модуле Combconst описываются используемые в дальнейшем отношения Comp, Copy, Ident, Coin, Gen. Эти отношения подобны введенным в язык комбинаторным константам, с той разницей, что входные и выходные кортежи данных отношений имеют к элементов, где к > 1.

В модуле Dirrel описывается отношение, инвертирующее входы и выходы любого отношения.

Сами операции работы со списками описываются в модуле Lists, который является головным по отношению к двум ранее описанным модулям.

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

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

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

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

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

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

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

ВнутрЭл 1-п- это определение или описание внутренних элементов домена, т.е. “Сех элементов, следующих после слова WHERE, которые располагаются в Родительском файле.

[ Имя модуля

ВнутрЭл 1

ВнутрЭл 2

ВнутрЭл п

Рис. 1. Структура модуля во внутреннем представлении

Описание элементов домена во внутреннем представлении имеет вид, Представленный на рис. 2.

Арность 2 Имя

Доп. Информация —

Тело

Рис.2. Внутреннее представление элемента домена

"Арность 1" и "Арность 2" обозначают соответственно входную и выходную аРности отношения.

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

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

1.2. Система исполнения функционально-логических программ на языке РЬОСЮЬ

Система исполнения языка НХ)(ЗОЬ, или интерпретатор, осуществляет выполнение функционально-логических программ:

• сканирует внутреннее представление;

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

• порождает параллельные процессы.

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

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

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

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

Необходимо отметить, что сам запрос также проходит синтаксический и лексический анализы.

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

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

Заключение

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

ЛИТЕРАТУРА

1. Фальк В.Н. Теоретические модели языков программирования и вопросы их структурной интерпретации //Автореф. дисс.... канд. техн. наук. М.: МЭИ, 1978.

2. Кутепов В.П., Фальк В.Н. Функциональные системы: теоретический и практический аспекты // Кибернетика. 1979. N 1.

3. Фальк В. Н. Языки схем отношений // Формальные модели параллельных вычислений. Новосибирск: ВЦ СО АН СССР, 1988.

4. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том. 1. Синтаксический анализ. М.: Мир, 1978.

УДК 510.624.

С.В. Астанин, В. Омельницкий Разработка декларативного азыка гибридного типа для представления

знаний

Введение

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

При проектировании языка представления знаний (ЯПЗ) должны приниматься °о внимание следующие соображения:

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

- язык должен быть достаточно прост по синтаксису и семантике;

структуры знаний должны позволять как можно более эффективно Реализовывать процедуры вывода как логического, так и не- логического типа;

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

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