Передача параметров и возврат значений в предикат.

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

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

Пример 3.4

predicates

like(symbol, symbol).

clauses

like(tom, july).

like(bill, mary).

goal

like(bill, X).

Первый параметр запроса является входным, т.к. имеет значение, равное “bill”, второй параметр – X – свободная переменная, значение которой необходимо уточнить.

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

goal

like(bill, X).

like(Y, X).

like(X, Z).

В Прологе список входных и выходных аргументов для заданного предиката называется потоком параметров. Для предиката с двумя аргументами возможны 4 варианта потоков параметров:

like(i, i).

like(i, o).

like(o, i).

like(o, o).

 

 

i – input

o – output

 

Правила могут возвращать свободную переменную и результаты вычислений. Запрос типа like(X, Y), имеющий поток параметров (о, о), передает в алгоритм поиска две последовательные задачи унификации. Если в базе фактов есть информация, соответствующая запросу, и указан предикат fail, требующий поиска всех возможных альтернатив для переменных X и Y, то Пролог выдаст множество вариантов:

X = tom, Y = july.

X = bill, Y = mary.

При этом после определения значения переменной X Пролог меняет поток параметров:

like(tom, Y), т.е. (i, o).

На 3-ем шаге происходит откат назад: (о, о).

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

goal

cursor(R, C),

R1 = R+1,

cursor(R1, C).

Это – составная цель с последовательным выводом трех подцелей.

При обращении к 1-му предикату поток параметров будет иметь вид (о, о), т.к. переменные R и С – свободные. 2-ая подцель вызывает связанную переменную R, значение которой должно быть определено ранее при вызове 1-го предиката.

Переменная R1 является свободной.

Если же в 1-ом предикате значение переменной R не было найдено, и она осталась свободной переменной, то Пролог выдал бы ошибку и остановил поиск.

После вычисления R1 3-ий предикат вызывается с потоком параметров (i, i).

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

Примечание 1: Предикат not, вызываемый как самостоятельный предикат или как составной элемент правил, не работает, если он вызывается с выходным потоком параметров.

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

init(X):- X = Æ.,

или в процессе унификации как сопоставление цели некоторым фактам в разделе

init(X):- write(X).

goal

X = 5, init(X).

 

Тема 4.

Вычислительная модель Пролога.

Факты, запросы, переменные и правила.

Факты.

Факты характеризуют известные отношения между объектами, заданные в виде предикатов. При этом все объекты и отношения пишутся с маленькой буквы.

Например:

Джону нравится Мэри.

like(john, mary).

Следует соблюдать принятый порядок перечисления аргументов предикатов.

Например:

1) Джон и Мэри играют в бадминтон.

play(john, mary, badminton).

2) Джон дает книгу Мэри.

gives(john, book, mary).

Данные предикаты имеют различные порядки аргументов.

Набор фактов в Прологе – это база фактов (БФ).

 

Запросы.

Запросы – это целевые утверждения в форме предикатов, которые требуется подтвердить или опровергнуть в результате поиска по БФ.

Например:

1)? – like(john, mary).

Yes

2)? – like(john, ann).

No

Во втором случае ответ No, т.к. Пролог не нашел соответствующего факта в БФ, хотя в действительности ничего не известно о том, нравится ли Джону Анна.

Примечание: Ответ No означает, что Пролог не может доказать истинность цели, однако ответ No не тождественен значению False для логической переменной или высказывания.

 

Переменные.

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

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

Например:

1) Что нравится Джону?

2) Есть ли что-либо, что нравится Джону?

like(john, X)

X = Is there

Пролог различает два типа переменных:

ü свободные (free);

ü связанные (instantiated).

Если переменная используется в предикате впервые, то ее значение не определено, и она считается свободной. Пролог ищет в БФ факт, соответствующий запросу и проводит унификацию, т.е. сопоставление свободной переменной какого-либо объекта, определенного из факта. Если такой факт найден, то переменная становится связанной, в том числе для всех последующих предикатов, в которых она встречается. В процессе унификации Пролог просматривает БФ сверху вниз в порядке следования фактов и маркирует первый найденный факт, соответствующий запросу.

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

 

Правила.

Правила – это обобщенные описания множества объектов и их отношений.

Правила используются для указания зависимостей (типа 1:М, М:М) между фактами, где множество допустимых аргументов задается свободными переменными. При этом правила можно представить в виде дерева поиска.

like(john, X):- female(X), like(X, wine),!, ….

Это правило может быть представлено следующей структурой:

Составные цели в правилах образуются объединением нескольких предикатов подцели с помощью логических операторов and, or, not. Пролог последовательно старается подтвердить или опровергнуть составные подцели в порядке их указания. При этом каждая подцель маркируется своим маркером в процессе унификации. Пролог просматривает всю БФ для каждой подцели. Если 1-ая подцель подтверждена (маркер установлен), а 2-ая подцель – нет, то Пролог пытается переопределить 1-ую подцель.

Процесс поиска, в котором Пролог последовательно подтверждает или опровергает составные цели, называется обратным отслеживанием.

Пример 4.1

Backtracking

% facts

m1.1 ® like(mary, food). %f1

m1.2 ® like(mary, wine). %f2

m2.1 ® like(john, wine). %f3

like(john, mary). %f3

? - like(mary, X), like(john, X).

Алгоритм поиска:

Шаг 1:

? - like(mary, X). X = food

Пролог устанавливает маркер m1.1.

Шаг 2:

? - like(john, food). false

Шаг 3:

Откат назад: X®free

? - like(mary, X).

Поиск начинается от маркера m1.1.

X = wine

Предыдущий маркер стирается и устанавливается новый – m1.2.

Шаг 4:

? - like(john, wine).

Yes

Устанавливается новый маркер – m2.1.

Шаг 5

X = wine

Примечание: Если нужно найти другие варианты ответов, то должен использоваться предикат fail, который выполняет откат назад и повторный поиск, начиная с маркеров m1.2 и m2.1 до тех пор, пока не будет просмотрена вся БФ для каждого из составных предикатов.

 

Рассмотренный пример программы использовал программирование с помощью фактов.

Пример 4.2

Рассмотрим пример программирования с помощью правил.

Пусть стоит задача поиска родственных отношений между людьми:

Запишем базу фактов, где будем использовать 3 типа предикатов:

Predicates

родитель(symbol, symbol)

потомок(symbol, symbol)

мужчина(symbol)

женщина(symbol)

% facts

женщина (Нам).

мужчина (Том).

мужчина (Боб).

женщина (Лиз).

мужчина(Пат).

женщина (Энн).

мужчина (Джинн).

родитель(нам, боб);

родитель(том, боб);

родитель(том, лиз);

родитель(боб, энн);

родитель(боб, пат);

родитель(пат, джинн);

 

? – родитель(X, энн), родитель(X, пат).

X=боб.

потомок(X, Y):– родитель(Y, X).

Исходя из дополнительной информации о поле родственников, можно определить новые отношения – “мать” и “сестра”:

Правило, задающее материнство:

мать(X,Y):– женщина(X), родитель(X, Y).

Правило, определяющее термин «сестра»:

сестра (X,Y):– родитель(Z, X), родитель (Z, Y),женщина(X).

? – сестра(X, пат).

X=энн.

Добавим предикат «предок» и зададим его рекурсивное определение. Будем говорить, что некто X и Z являются предком и потомком друг для друга, если между ними существует цепочка людей, связанных между собой отношениями «родитель».

предок (X, Y):– родитель(X, Y).

предок (X, Z):– родитель(X, Y), предок(Y, Z).

? – предок(нам, энн)

Yes.