Программирование на языке пролог (ЛП)

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

принадлежит(X,[X |_] ).

принадлежит(X,[_ |Y]):- принадлежит(X,Y).

порождает альтернативные решения. Если мы задаем вопрос

?- принадлежит(а,X).

(обратите внимание, что Xв вопросе является неконкретизированной переменной), то последовательные значения переменной Xбудут представлять частично конкретизированные списки, в которых аявляется первым, вторым, третьим и так далее элементом списка. Убедитесь, что вы понимаете, почему так получается. Другим следствием возврата, допускаемого при выполнении предиката принадлежит, является то, что вопрос

?- принадлежит(а,[а,b,r,а,с,а,d,а,b,r,а]).

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

4.2. Отсечение

Этот раздел посвящен специальному механизму, используемому в программах на Прологе и называемому «отсечением» [8]. Отсечение позволяет указать, какие из сделанных ранее выборов не следует пересматривать при возврате по цепочке согласованных целевых утверждений. Существуют две причины, побуждающие включать в программу такие указания:

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

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

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

Синтаксически использование в правиле отсечения выглядит как вхождение целевого утверждения с предикатом '!', не имеющим аргументов. Как целевое утверждение этот предикат всегда согласуется с базой данных и не может быть вновь согласован. Однако он имеет побочный эффект, который изменяет процесс последующего возврата. Эффект заключается в том, что маркеры некоторых целей становятся недоступными, так что для этих целей нельзя найти новые сопоставления. Рассмотрим, как это происходит на примере. Предположим, что вы заведуете библиотекой и имеете базу данных на Прологе, содержащую информацию о наличии книг, о том, кто и какие книги взял и когда книги должны быть возвращены. Один из вопросов, который мог бы вас интересовать,- это какие виды услуг, предоставляемых библиотекой, доступны каждому из читателей. Некоторые услуги, которые мы могли бы назвать основными, должны быть доступны любому читателю. Они включают пользование каталогом и справочным бюро. С другой стороны, дополнительные услуги, такие как пользование абонементом или получение книг из других библиотек, хотелось бы предоставлять читателю выборочно. Одно из правил могло бы состоять в том, что если читатель не возвратил в указанный срок книгу, то дополнительные виды услуг ему недоступны до тех пор, пока он не вернет книгу. Здесь приведена часть программы, которая использует это правило:

услуги(Читатель,Вид_услуг):-

 книга_не_возвращена(Читатель,Книга),!,основные_услуги (Вид_услуг).

услуги(Читатель,Вид_услуг):-общие_услуги(Вид_услуг).

основные_услуги(пользование_каталогом).

основные_услуги(получение_справок).

дополнительные_услуги (абонемент).

дополнительные_услуги(межбиблиотечный_абонемент).

общие_услуги(X):-основные_услуги(X).

общие_услуги(X):-дополнительные_услуги(X).

книга_не_возвращена('С. Уотзер',книга10089),

книга_не_возвращена('А. Джонс', книга29907).

. . .

читатель('А.Джонс'). читатель('В.Метеск').

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

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

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