Язык Пролог: стратегии вычислений и встроенные отношения

Стратегии вычислений

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

Последовательные вычисления.

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

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

Если же получен ответ, то для продолжения получения других ответов также нужно выполнить backtracking. Именно эту стратегию мы использовали в примере 1 раздела 3.6.

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

Рассмотрим эти способы.

Использование правила отсечения связано с помещением в правую часть какого-либо правила оператора отсечения в виде знака '|' вертикальной черты. При его выполнении (когда он становится самым левым в запросе) забываются все разветвления до этого места и возврат производится только к последующим разветвлениям. Пусть, например, имеются правила:

P <- A, |, B
P <- C.

Тогда при выполнении оператора отсечения забываются все разветвления при выполнении процедуры A и при выполнении второго правила.

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

книга (книга123456) <-
книга (книга234567) <-
книга (книга345678) <-
. . .
читатель ('Иванов') <-
читатель ('Петров') <-
читатель ('Сидоров'’) <-
. . .
книгаНеВозвращена ('Иванов', книга123456) <-
книгаНеВозвращена ('Сидоров', книга234567) <-
книгаНеВозвращена ('Иванов', книга345678) <-
. . .
оснУслуги (каталог) <-
оснУслуги (справки) <-
допУслуги (абонемент) <-
допУслуги (межбиблАбонемент) <-

общУслуги (X)<- оснУслуги (X)

общУслуги (X) <- допУслуги (X)
 услуги (Читатель, ВидУслуг)<- читатель (Читатель),
                               книгаНеВозвращена
                                      (Читатель, Книга),
                               |, основныеУслуги (ВидУслуг)
								 
 услуги (Читатель, ВидУслуг) <- общУслуги (ВидУслуг)

При выполнении запроса

<- читатель (X), услуги (X, Y)

сначала отождествляется переменная X с читателем Иванов. Затем начинает выполняться второй атом запроса, который должен установить список услуг для данного читателя. При выполнении первого правила с предикатным символом услуги образуется новый запрос:

<- читатель ('Иванов'), книгаНеВозвращена ('Иванов', Книга), |, основныеУслуги (ВидУслуг)

Первый атом этого запроса отождествляется с фактом (удачное вычисление). При вычислении второго атома этого запроса будет сначала найден факт

книгаНеВозвращена ('Иванов', книга123456) <-, и так как следующий атом запроса - оператор отсечения, то после вычисления всего запроса не будет возврата к поиску фактов невозвращения других книг Ивановым и переход к использованию других правил процедуры услуги. Результатом вычисления запроса для Иванова будет список только основных услуг.

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

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

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

Параллельные вычисления.

Различают 2 вида параллельности:

Встроенные отношения

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

Другие встроенные предикаты могут использоваться в правилах программы. Они приведены в табл. 10.2.

Помимо этого используются функторы not для операции отрицания и точка с запятой ';' для обозначения операции дизъюнкции. Так, в примере

<- (not мать (X, Y); Y=ева), |, fail

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

Использование функтора not основано на следующем стандартном определении отношения not X ), где X - целевой предикат:

not X <- X,|,fail
not X <-

В этой конструкции порядок правил программы фиксирорван и не зависит от стратегии (сначала идет правило с отсечением, а затем универсальный факт, и поиск подходящего правила идет только в этом порядке при любой стратегии. Так в вышеприведенном примере при вычислении предиката not мать( X1,Y1) он становится целевым и рассматривается первое правило. При этом обрабатывается сначала предикат мать(X1,Y1), и если найдется интерпретация переменных X1 и Y1, при которой этот предикат имеет истинное значение, то последующее в теле правила отсечение приводит к омене всех разветвлений до этого места (т. е. второе правило не применяется) и значение определяется встроенным предикатом fail, имеющем всегда ложное значение. Если же такой интерпретации переменных X1 и Y1 не найдется, то вычисления в силу ветвления в этой точке переходят ко второму правилу, которым является универсальный факт not X, что приводит к истинному значению предиката not мать (X1,Y1).

Упражнения