2.4. Встроенные предикаты

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

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

Арифметика

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

Арифметические операции реализуются в Прологе с помощью хорошо известных операторов: +, -, *, /, div, mod. Операнды первых четырех из них могут быть как целыми, так и вещественными, последние два определены только для целых операндов. Арифметические выражения строятся в Прологе по правилам, не отличающимся от общепринятых. Вот примеры выражений, не требующие комментариев: (A+B)*C/2, ((3.1*A-12)/(B-1)+2.5)*2 и т.д. Выражения не являются предикатами. Они должны быть частью оператора присваивания, либо операндами сравнений, которые представлены встроенными предикатами особого типа, синтаксис которых отличается от синтаксиса других предикатов. Важной особенностью этих предикатов является то, что они представлены в инфиксной форме:

<аргумент1> <имя предиката> <аргумент2>

Сначала остановимся на операторе присваивания. Это особая конструкция Пролога для рассмотрения которой необходимо ввести понятия конкретизированной и свободной переменных. Конкретизированной называется переменная, которой было присвоено некоторое значение. В большинстве случаев значение переменной присваивается при унификации. Пусть, например, активная цель имеет вид: p(a,Y) и сопоставляется с правилом базы знаний вида: p(X,Y) :- q₁(X,Z), … , q_n(t₁, … , t_m). Наиболее общий унификатор таков: {(X,a)} и поэтому после резолюции образуется список целей: q(a,Z), … . Таким образом, применение унификации позволило определить значение всех вхождений переменной X в приведенное правило, и, следовательно, эта переменная оказалась конкретизированной. Важно помнить, что областью действия конкретизации X является правая часть правила, использованного для резолюции, иначе говоря, список целей q₁(X,Z),…, q_n(t₁, …,t_m). В то же время значения переменных Y и Z остались неопределенными. Такие переменные называются свободными.

Синтаксис оператора присваивания таков:

A = <обобщенный терм>, либо <обобщенный терм> = A,

где A – свободная переменная, а <обобщенный терм> – арифметическое выражение или терм. Обратите внимание, что переменная, которой присваивается значение, может быть расположена как слева, так и справа от знака равенства. Если в операторе используется арифметическое выражение, то переменной присваивается его численное значение. В противном случае переменной присваивается значение терма.

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

Предикаты сравнения

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

<аргумент1> <отношение> <аргумент2>.

Здесь аргументы – это сравниваемые термы, а отношение обозначается обычными синтаксическими знаками: <, <=, =, >, >=. Таким образом, предикат сравнения по виду не отличается от отношений процедурных языков. Отметим, что сравнивать необходимо термы одинаковых типов, например, числа с числами, строки со строками и т.д. Предикаты принимают значение «истина», если для аргументов выполнено соответствующее отношение.

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

Предикаты ввода-вывода

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

Предикаты, имена которых начинаются строкой букв read, предназначены для ввода данных. Например, readint служит для ввода целых, readreal – вещественных чисел, readln – символьную строку и т.д. Вообще говоря, эти предикаты могут вводить данные из разных источников. Но по умолчанию они вводятся с экрана монитора, для чего в большинстве реализаций предусмотрено специальное окно. Аргументами этих предикатов должны быть свободные переменные, число их неограниченно.

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

Рассмотренные предикаты этой группы являются тождественно истинными.

Предикат отсечения

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

p :- p₁, … , p_m, !, p_m+1, … , p_n.

Таким образом, список целей приобрел вид:

p₁, … , p_m, !, p_m+1, … , p_n, …

Предположим также, что в базе знаний после данного правила имеется еще несколько правил и/или фактов для данного предиката, например:

p :- q₁₁, … , q_k.

…

p.

…

p :- q₂₁, … , q_l и т.д.

Пусть цели p₁, … , p_m достигнуты, и предикат отсечения оказался активной целью:

!, p_m+1, … , p_n, …

Так как «!» – это тождественно истинный предикат, данная активная цель будет достигнута, а его побочный эффект отключает механизм возвратов для перебора других вариантов вывода целей p₁, … , p_m, а также выводы первоначальной цели p с помощью правил и фактов, расположенных в базе знаний после правила, содержащего отсечение. В то же время, перебор выводов целей p_m+1, … , p_n, … будет выполнен в полном объеме.

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

Тождественно ложный предикат

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

Примеры

1) Рассмотрим пример использования функторов при моделировании предметной области «Библиотечные каталоги», содержащей сведения о личных библиотеках. Будем считать, что в базу знаний включены имена владельцев библиотек, и данные о книгах: автор, название, издательство, год выпуска. Последние естественно объединить функтором. Таким образом, база знаний должна состоять из фактов, перечисляющих единицы хранения библиотек и их владельцев. Для ее формирования достаточно использовать единственный предикат collection:

collection("Анисимова",

book("Программирование на языке Пролог",

"Клоксин У., Меллиш К.",

"Мир",1987)).

collection("Анисимова",

book("Логика в решении проблем",

"Ковальски Р.",

"Наука",1990)).

collection("Анисимова",

book("Язык программирования Пролог",

"Стобо Дж.",

"Радио и связь",1993)).

collection("Анисимова",

book("Системы продукций",

"Яхно Т.М.",

"АН СССР. Сиб. отделение",1990)).

collection("Братчиков",

book("Синтаксис языков программирования",

"Братчиков И.Л.",

"Наука",1975)).

collection("Братчиков",

book("Введение в МПролог",

"Иванова Г.С., Тихонов Ю.В.",

"МГТУ",1990)).

collection("Братчиков",

book("Принципы искусственного интеллекта",

"Нильсон Н.",

"Радио и связь",1985)).

collection("Братчиков",

book("Реализация экспертных систем",

"Клещев А.С.",

"Препринт ДВО АН СССР",1988)).

collection("Братчиков",

book("Компиляторы",

"Ахо А., Сети Р., Ульман Дж. ",

"Вильямс", 2003)).

2) «ОБЕЗЬЯНА И БАНАН». Построим базу знаний для моделирования поведения обезьяны в следующей ситуации. Обезьяну впускают в комнату, в которой имеется ящик, стоящий у окна, а посередине комнаты к потолку подвешен банан. Обезьяна хочет достать банан, но для этого ей нужно подойти к ящику, перетащить его на середину комнат и залезть на ящик.

База знаний примера:

1. ход( состояние (середина, на-ящике, середина, не-имеет), схватить, состояние(середина, на-ящике, середина, имеет).

2. ход( состояние (Р, на-полу, Р, Н), залезть, состояние(Р, на-ящике, Р, Н).

3. ход( состояние (Р1, на-полу, Р1, Н), подвинуть(Р1,Р2), состояние(Р2, на-полу, Р2, Н).

4. ход( состояние (Р1, на-полу, В, Н), перейти (Р1,Р2), состояние(Р2, на-полу, В, Н).

5. может_завладеть( состояние( _ , _ , _ , имеет)).

6. может_завладеть (С1) :--

ход (С1, Ход, С2), может_завладеть (С2).

Здесь «состояние» – это функтор, определяющий состояние, в котором находится система. Компоненты функтора: расположение обезьяны в комнате, вертикальное расположение обезьяны (на полу или на ящике), расположение ящика в комнате и указание на то, схватила ли обезьяна банан.

В базе знаний используются два предиката. Предикатом «ход» определяются возможные действия обезьяны. Три аргумента предиката задают состояние системы до действия обезьяны, само действие (тоже функтор, в зависимости от действия либо без компонентов, либо с двумя компонентами) и состояние после действия. Предикат «может_завладеть» имеет один аргумент – состояние системы. Цель, представленная этим предикатом, достигается, если при данном состоянии обезьяна, действуя правильно, может схватить банан.

Для правильного понимания семантики базы знаний следует помнить, что все слова, начинающиеся с больших букв, являются переменными (С, С1, Ход и пр.).

Рассмотрим работу алгоритма поиска логического вывода для приведенной базы знаний и следующего вопроса (для сокращения записи обозначим предикат «может_завладеть» через «м_з»):

? м_з ( состояние( у-двери, на-полу, у-окна, не-имеет))

1) Цель может быть унифицирована с (6).

Унификатор: { (С1, состояние( у-двери,

на-полу, у-окна, не-имеет) }.

Теперь имеем следующий список целей:

ход(состояние( у-двери, на-полу, у-окна, не-имеет), Ход, С2), м_з( С2).

2) Первая цель может быть унифицирована с (4).

Унификатор: { (Р1, у-двери), (В, у-окна), (Н, не-имеет),

(Ход, перейти( у-двери, Р2)), (С2, состояние

(Р2, на-полу, у-окна, не-имеет)) }.

Так как первая цель достигнута, остается только вторая цель:

м-з( состояние( Р2, на-полу, у-окна, не-имеет)).

3) Оставшаяся цель может быть унифицирована с (6).

Унификатор: { (С1, состояние( Р2, на-полу, у-окна, не-имеет)) }.

Теперь имеем следующий список целей:

ход( состояние( Р2, на-полу, у-окна, не-имеет), Ход, С2), м-з(С2).

4) Первая цель может быть унифицирована с (2).

Унификатор { (Р2, у-окна), (Р, у-окна), (Н, не-имеет),

(Ход, залезть), (С2, состояние( у-окна,

на-ящике, у-окна, не-имеет)) }.

Так как первая цель достигнута, остается только вторая цель:

м-з(состояние( у-окна, на-ящике, у-окна, не-имеет)).

5) Оставшаяся цель может быть унифицирована с (6).

Унификатор: { (С1, состояние( у-окна, на-ящике, у-окна, не-имеет)) }.

Список целей:

ход(состояние( у-окна, на-ящике, у-окна, не-имеет), Ход, С2), м-з(С2).

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

4) Первая цель может быть унифицирована с (3).

Унификатор { (Р2, у-окна), (Р1, у-окна), (Н, не-имеет),

(Ход, подвинуть(у-окна, Р2)), (С2, состояние( Р2,

на-полу, Р2, не-имеет)) }.

Так как первая цель достигнута, остается только вторая цель:

м-з(состояние( Р2, на-полу, Р2, не-имеет)).

5) Вновь унифицируем с (6).

Унификатор: { (C1, состояние(Р2, на-полу, Р2, не-имеет)}.

Список целей:

ход(состояние( Р2, на-полу, Р2, не-имеет), Ход, С2), м-з( С2).

6) Первую цель унифицируем с (2).

Унификатор: { (Р2, P), (H, не-имеет), (Ход, залезть),

(С2, состояние( Р, на-ящике, Р, не-имеет)) }.

Оставшаяся цель:

м-з(состояние( Р, на-ящике, Р, не-имеет)).

7) Унифицируем с (6).

Унификатор: { (C1, состояние( Р, на-ящике, Р, не-имеет)) }.

ход(состояние( P, на-ящике, Р, не-имеет), Ход, С2), м-з( С2).

8) Унифицируем с (1).

Унификатор: { ( Р, середина), (Ход, схватить), (C2,

состояние(середина, на ящике, середина, имеет))}.

Получили цель:

м-з(состояние(середина, на ящике, середина, имеет)).

Эта цель унифицируется с фактом (5). Цель достигнута, список целей оказывается пустым и, таким образом, вывод получен. Система на поставленный вопрос ответит «ДА».

Проанализируем найденный логический вывод. Нетрудно видеть, что нам достаточно просмотреть последовательность «ходов» обезьяны и подстановки вместо переменных предиката «ход», представленных переменными. Ходы определяются на четных шагах вывода:

2) перейти (у-двери, Р2);

4) (Р2, у-окна), залезть - тупик.

4) (Р2, у-окна), подвинуть (у-окна, Р2);

6) (Р2, Р), залезть;

8) (Р, середина), схватить.

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

1. Обезьяна идет от двери к окну.

2. Обезьяна залезает на ящик, который находится у окна.

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

4. Обезьяна переносит ящик на середину комнаты.

5. Обезьяна залезает на ящик.

6. Обезьяна хватает банан.

3) Вывести на экран монитора целые числа, находящиеся в интервале [M,N].

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

beg – 0-местный предикат, предназначенный для ввода пользователем границ интервала и контроля корректности вводимых границ. Использует встроенный предикат readint.

print(M,N) – 2-местный предикат, осуществляющий вычисление целых чисел, находящихся в заданном интервале, и вывод их на экран. Использует встроенный предикат write. Программа решения задачи такова:

beg :-

write("Введите нижнюю границу интервала: "),

readint(A),

write("Введите верхнюю границу интервала: "),

readint(B),

A<=B, write ("Числа в интервале [",A,",",B,"]:"),

print(A,B),!.

beg:- write("Неверные начальные данные!"), fail.

print (N,M) :- N < M, write(N, ","),

K = N+1, print(K,M).

print(N,_) :- write(N, "."), Nl.

В программе рассматриваются два случая:

a) Границы интервала введены верно (M  N). В этом случае должны выводиться числа, находящиеся внутри интервала. С помощью ответа “Yes” система сообщит, что задание выполнено.

b) Границы интервала введены неверно (M >N). Информация об ошибке должна быть выведена пользователю. С помощью ответа “No” система сообщит, что задание не выполнено.

Первое правило программы для предиката beg осуществляет ввод границ интервала, проверку корректности ввода и вывод и в случае корректности введенных границ вывод на экран последовательности чисел. Если все цели из правой части правила оказались достижимы, оператор отсечения (“!”) блокирует обработку второго правила для beg.

Второе правило выполняется в случае недостижимости цели A<=B из первого правила. С его помощью пользователю выдается информация об ошибке, а встроенный предикат fail инициирует вывод ответа “No”.

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