Листинг 3.3.Использование знака равенства для унификации составных объектов

domains

person=person(name, address)

name=name(first, last)

address=addr(city,street))

street=street(number, street_name)

city, state, street_name=string

first, last=string

number=integer

goal

P1=person(name(jim,black),addr(pskov,street(25,mira)),

P1=person(name(_,black),Address),

P2=person(name(jane,black),Address),

write(“P1=”,P1,nl,

write(“P2=”,P2), nl.

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

Замечание2:

Алгоритм унификации очень прост: он рекурсивно исследует два выражения одновременно, и в ходе этого исследования формирует унификатор, но может закончиться и неудачей, если структуры окажутся несопоставимыми. Но при этом есть один маленький нюанс: если переменная согласуется со сложным термом, необходимо произвести проверку того, встречается ли сама эта переменная внутри терма; если встречается, то согласование окончится неудачей, потому что будет невозможно сформировать какой-либо совместный унификатор. Эта операция носит название “проверка вхождения”(occur check). Но к сожалению именно из-за этой проверки сложность всего алгоритма становится квадратично зависимой от размера унифицируемых выражений. Все системы логического программирования просто исключают проверку вхождения и поэтому иногда могут сформироваться противоречивые логические выводы. Это случается крайне редко, но это означит, что унификация, проводимая в логическом программировании не является строго унификацией.

Как проходит процесс унификации?

- Пролог начинает поиск с начала программы.

- Если вызов завершился успешно, то делается попытка доказать следующую подцель.

- Если переменная была связана в предложении, то единственный способ сделать ее снова свободной - это откат.

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

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

3.5.Основные правила поиска с возвратом:

1. подцели проверяются по порядку – сверху вниз

2. предложения проверяются в том порядке, в котором они появляются в программе

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

4. цель доказана, когда соответствующие факты найдены для каждой листьевой вершины дерева целей.

Вызов, который дает множество решений – недетерминированный

Вызов, дающий одно и только одно решение – детерминированный.