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

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

4.1.1 Факты.

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

Например:

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

like(john, mary).

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

Например:

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

play(john, mary, badminton).

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

gives(john, book, mary).

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

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

4.1.2 Запросы.

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

Например:

1) ? – like(john, mary).

Yes

2) ? – like(john, ann).

No

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

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

4.1.3 Переменные.

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

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

Например:

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

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

like(john, X)

X = Is there

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

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

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

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

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

4.1.4 Правила.

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

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

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

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

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

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