ПРИЛОЖЕНИЕ F. СИСТЕМА МПРОЛОГ[19]

В этом приложении описывается система МПролог, разработанная в Институте по координации вычислительной техники (SZKI), г. Будапешт. Название системы МПролог отражает тот факт, что в этой системе предусмотрены средства для модульной разработки программ. Кроме того, в ней поддерживается более 200 встроенных предикатов, рассчитанных на различные области применения.

Синтаксис МПролога совместим с синтаксисом Пролога-10 (см. приложение D), и почти все встроенные предикаты Пролога-10 предусмотрены также и в МПрологе.

Пролог доступен на следующих вычислительных комплексах:

Одна из версий МПролога (так называемый мини-МПролог) предназначена для микро- и мини-ЭВМ. Первая реализация этой системы применяется на ЭВМ IBM PC с ОС MSDOS.

Ниже приводится пример сеанса работы с подсистемой разработки программ (PDSS) системы МПролог,

В системе МПролог средства диалоговой разработки программ отделены от интерпретатора и реализованы в подсистеме PDSS, которая исполняет команды первичного ввода, редактирования, выполнения, трассировки и другой обработки модулей МПролога. Подсистема PDSS также позволяет задавать значительное число глобальных параметров, определяющих режимы работы команд. Например, параметр line_length (длина_строки) задает длину выводимых строк при специально форматированном выводе утверждений.

DO $S.MPRO.PDSS

MPROLOG (V1.4) Program Development Subsystem 1.4:4 (

c) 1982 Institute for Coordination of Computer Techniques (SZKI), Budapest.

По команде help выводится общая вспомогательная информация о возможностях PDSS (# означает приглашение системы)[20];

* help Команда; h[elp] [ТЕМА…]

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

Можно получить информацию по следующим темам:

all_global all_symbolic all_visible body bye coded consult declaration delete dynpart edit enter exception_handling execute export face focus global goal help hidden import insert interface list local match_order mode modify module move next nonprolog operator options previous query read rename replace reply reset rungoal savemod selectors set solutions status symbolic trace type untimed untrace visible =

Сведения по конкретной теме, например по теме module, указанной в третьей колонке, можно получить следующим образом:

*help module

Команда: m[odule] [ИМЯ]

Делает модуль ИМЯ текущим модулем. Если ИМЯ опущено, то текущим модулем становится `неименованный_модуль'. После этой команды никакое утверждение не помещается в поле зрения.

Возможности PDSS позволяют разрабатывать несколько модулей. Данный сеанс начинается с команды module, создающей модуль, в который затем будут помещаться определения предикатов.

* module first

MODULE first

* enter hates(ann,john).

PREDICATE hates/2

*?- hates(kate,X).

NO

Команда enter используется здесь для дополнения модуля first новым утверждением. На основе одного этого утверждения ответ на вопрос hates(kate, X) получается отрицательным.

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

*?- likes(X,Y).

Exception -505: undefined predicate In call of likes(_425,_426) Function (h for help)?

* h

 p – enter new PDSS level

 b – backtrace

 a – abandon execution

 с – continue

 f – fail

 s – contents of the stack

 r - redo the broken call

 i – user handled interrupt

 h – help Function (h for help)'

* f

NO

Здесь enter new PDSS level означает выход на новый уровень команд PDSS (аналогично команде break в Прологе-10), backtrace означает вывод списка предшественников ошибочного вызова (аналогично команде backtrace в Прологе для PDP-11 с ОС UNIX).

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

Однако систему МПролог можно заставить вести себя так, как Пролог-система, описанная в книге. Для этого достаточно в качестве обработчика особой ситуации для undefined predicate задать целевое утверждение fail:

*?- newhandler("undefined predicate",fail).

Yes

*?- likes(X,Y).

No

Будем считать, что файл test содержит ту же самую последовательность утверждений, что и в предыдущих приложениях. Тогда мы можем считать содержащиеся в нем утверждения в базу данных. При этом, если параметр auotostate не в состоянии «off» (выключено), то будет выводиться функтор (т. е. имя/число аргументов) читаемых из файла предикатов.

*?- [test]. likes/2

Yes

*?- listing(likes/2).

likes(john,alfred).

likes(alfredjohn).

likes(bertrandjohn).

likes(david,bertrand).

likes(john,ANYBODY):- likes(ANYBODY,bertrand).

Yes

Переменные (в данном случае ANYBODY) записаны прописными буквами как в Прологе-10. Однако в МПрологе предусмотрена особая возможность сохранения символьных имен переменных в пользовательской программе.

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

* type likes/2

likes(john,alfred).

likes(alfred,john).

likes(bertrand,john).

likes(david,bertrand).

likes(john,ANYBODY):- likes(ANYBODY,bertrand).

Второе и четвертое утверждения данного предиката можно просмотреть с помощью команды;

* type likes / 2 CL (2,4)

likes(alfred, john).

likes(david,bertrand).

А все утверждения, включающие bertrand выбираются следующим образом:

* type likes / 2 CL (bertrand)

likes(bertrand, john).

likes(david,bertrand).

likes(john,ANYBODY):- likes(ANYBODY,bertrand).

Получение альтернативных решений для целевого утверждения осуществляется немного иначе, чем в Прологе-10:

*?- likes(john,Who).

WHO = alfred Continue (y/n)?

* y

WHO = david Continue (y/n)?

* у

NO

Новые утверждения можно добавлять как с помощью команды enter, так и путем чтения псевдо-файла user (как в Прологе-10):

*?- [user].

likes(timothy,bertrand).

likes/2+6

* bye

Yes

Команда ввода вопроса (?-) не выдает сведений о времени его выполнения. Эту информацию можно получить путем задания команды execute (в краткой форме ':'):

* :likes(john,X).

(*** CPU time: 0.27 sec, 1 calls, 0 backtracks ***)

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

*?- likes(john,ann)). full stop expected at) Enter the editor (y/n)?

* y

10: likes(john,ann))

*** Enter editor commands

* 10: likes(john,ann)

*** Line 10 replaced ***

* end NO

Команда end закрывает цикл редактирования. Затем делается попытка согласовать отредактированную цель, и в результате получается ответ NO.

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

Сеанс работы с PDSS завершается по команде bye. При этом система предупреждает пользователя о возможности утраты модулей, которые не были записаны в файлы.

* bye

*** The following module(s) have not been saved: ***

first Do you want to exit (y/n)?

* y

Normal exit from MPROLOG PDSS

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

Строки в МПрологе не эквивалентны списку кодов, составляющих их литер. Это означает, что пример из гл. 5 (база данных исторических событий) с вопросом событие(1524,Х) будет работать и ответом будет 'Васко да Гама умер'.

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

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

module dictionary.

export (найти / 3, печ_дерево / 3).

import (меньше / 2).

visible (таблица, подряд), body.

найти(Н, b(H,G,_,_), G):-!.

найти(Н, в(Н1,_,BEFORE,_),G):- меньше(Н,Н1)?найти(Н,ВЕFОRЕ,G).

найти(Н,в(Н1,,_,AFTER),G):- not(меньше(Н,Н1)), найти (H,AFTER,G).

печ_дерево(T,FORM,KEYWORD):- var(T),!.

печ_дерево(в(H,W,L,G),F,K):- печ_дерево(L,F,K), печ_элемент(Н,W,F,K), печ_дерево(G,F,K).

печ_элемент(Н,W,таблица,K):- !, outterm(H), outtab(15), outterm(K),outspaces(l), outterm(W), newline.

печ_элемент(Н,W,подряд,K):- outterm(H), outspaces(l), outterm(K), outspaces(1), outterm(W), outterm(",").

end mod /* dictionary */.

Этот модуль «экспортирует» (т. е. делает доступным для других модулей) предикаты найти/3 и печ_дерево/3, и только эти предикаты данного модуля могут быть использованы вне его. Предикат печ_дерево может выводить на печать заданное дерево в двух возможных форматах в соответствии с аргументом FORM, который может иметь значения таблица и подряд. Эти два имени описаны как видимые, что указывает на то, что они используются не только внутри данного модуля например, как конструктор в-структур. Видимость имени не обязательно обозначает сохранение его символьного представления в другом модуле, однако, если оно используется в другом модуле как видимое имя, то эти два вхождения унифицируются.

Заметим, что конкретное представление дерева скрыто в данном модуле.

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

module index.

export(печ_индекс/0).

import(найти/3, список_кличек/1, печ_дерево/3).

visible(таблица).

body.

печ_индекс:- список_кличек(L),созд_дерево(L, 1, Т, печ_дерево(Т,таблица,": ").

созд_дерево([],_,_):- !.

созд_дерево([NАМЕ|L,N,Т):- найти(NAME,T,N), M is N+1, созд_дерево(L,М,T).

endmod /* index */.

Здесь снова имя таблица задано как видимое, тогда как параметр KEYWORD предиката печ_дерево (здесь он имеет значение ".") заключен в двойные кавычки. Это означает, что символьное представление этого имени должно быть сохранено.

Ядром системы МПролог является интерпретатор. Другой основной компонентой системы является подсистема разработки программ PDSS, которая сама написана на МПрологе и работает под управлением интерпретатора. Подсистема PDSS обеспечивает возможности диалоговой разработки программ.

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

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

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

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

Целые числа могут изменяться в диапазоне от -8 388 607 до 8 388 607. Действительные числа не предусмотрены. Приоритеты операторов могут изменяться от -3000 до 3000.

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

Два основных предиката ввода insymb(X) и interm(X) допускают повторное согласование при возврате. Это означает, что при возвратном ходе выполненные ими действия «отменяются». Например, если первый вводимый символ не совпадает с аааа, то вопрос

? insymb(aaaa).

не согласуется, причем в этом случае аааа сохраняется во входном потоке и может быть считан последующими предикатами ввода[21].

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

предложение:- группа_существительного, группа_глагола.

группа_существительного:- определитель, существительное.

группа_глагола:- глагол.

группа_глагола:- глагол, группа_существительного.

определитель:- insymb(the).

существительное:- insymb(man).

существительное:- insymb(apple).

глагол:- insymb(eats).

глагол:- insymb(sings).

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

fdelclause(EXPR)

исключает первое утверждение, заголовок которого может быть сопоставлен с EXPR, тогда как

fsupclause(EXPR)

только подавляет его. Это означает, что при возвратном ходе это утверждение возвращается на свое место. С помощью этого предиката можно, например, по-другому определить предикат перейти из разд. 7.2:

перейти(X,X).

перейти(X,X):- в_след_комн(Х,Z), перейти(Z,Y).

в_след_комн(Х,Z):- fsupclause(d(X,Z)); fsupclause(d(Z,X)).

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

Имеется большой набор предикатов вывода, позволяющий осуществлять разнообразные виды форматированного вывода. Например, можно задавать границы строк и предельную глубину вывода. Задание глубины вывода полезно при выводе очень сложных термов (или даже бесконечных термов поскольку в МПрологе соответствующих проверок не делается), когда нас интересует только их общая структура. Задание глубины вывода равной N означает, что фактически выводиться будут только первые N уровней терма, а подтермы уровня N+1 будут представлены как (…).

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

ask_the_user:- broken _call(С), outterm("How to continue from: "), outterm(C), outterm("?"), nl, interm(C), ineot.

где broken_call(С) - это стандартный предикат, конкретизирующий переменную С ошибочным целевым утверждением. Выполнив целевое утверждение

newhandler("undefined predicate", ask_the_user)

система будет вызывать ask_the_user (спроси_у_пользователя) всякий раз, когда что-либо окажется неопределенным. Например, определив предикаты плотность и нас как в разд. 2.5, но оставив неопределенным предикат площадь:

плотность(X,Y):- нас(X,Р), площадь(X,A), Y is P/A.

нас(китай,800).

. . .

мы можем наблюдать следующий диалог:

*? плотность(китай,D).

How to continue from площадь(китай,_101)?

* площадь(китай,4).

D = 200

Continue (y/n)?

* y

NO

*? плотность(китай,D).

How to continue from площадь(китай,_101)?

* n.

NO

Другой важный встроенный предикат – это error_protect (Call, Handler), который выполняет целевое утверждение Call в защищенном окружении: когда внутри Call возникает особая ситуация (не обрабатываемая текущим обработчиком особых ситуаций), выполняется Handler.

Средства трассировки МПролога аналогичны тем, что имеются в Прологе-10.

MPROLOG Language Reference Manual

MPROLOG User's Guide /VAX/11-VMS/ MPROLOG User's Guide /VAX/11 – UNIX/ MPROLOG User's Guide /IBM – VM/CMS/ MPROLOG User's Guide /Siemens BS2000/

Getting Started with MPROLOG

Указанная литература может быть получена через институт по координации вычислительной техники (SZKI), г. Будапешт, ВНР.

Примечания:

1

В книге термин «Пролог» употребляется в трех значениях: 1) Пролог – язык программирования с совокупностью синтаксических и семантических правил записи программ; 2) Пролог – программная система (интерпретатор), реализующая язык; эта система и осуществляет диалог с пользователем; 3) Пролог – машина, на которой Пролог-система выполняет (интерпретирует) программы, написанные на языке Пролог. Как правило, из контекста всегда ясно, какое значение используется в каждом конкретном случае. При необходимости явного указания при переводе использовались термины: «язык Пролог», «Пролог-система», «Пролог-машина». - Прим. пepeв.

2

Связь введенного понятия с математической логикой обсуждается в гл. 10. - Прим. ред.

19

The MPROLOG System, SZKI, Budapest, 1986.

© SZKI, Budapest, 1986

© перевод на русский язык, «Мир», 1987 

20

Вспомогательная информация, выдаваемая по команде help, переведена на русский язык.- Прим. ред.

21

Здесь допущена неточность: во входном потоке при возвратном ходе сохраняется не аааа, а то, что прочитано из него до возврата. - Прим. ред.