Процес пошуку розв’язків Пролог-системою на запити

Декларативний смисл стосується відношень, які визначені в програмі, і визначає, що повинно бути результатом роботи програми. Порядок слідування підцілей (умов) у правилі не впливає на декларативний смисл правила.

При процедурному трактуванні Пролог-програми відмічається послідовність кроків, які виконує Пролог-система при опрацюванні запиту.

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

Нехай, наприклад, програма має вигляд:
р :- p1, p2, p3.
р :- q4, q5.

Описаний алгоритм опрацювання можна реалізувати на дереві спеціального вигляду: І / АБО - дереві

У кожній своїй вершині І / АБО - дерево має мітку І або мітку АБО. Вершина І успішно розв'язана тільки в тому випадку, коли її вершини - нащадки успішно розв'язані. Вершина типу АБО успішно розв'язана в тому випадку, коли хоча б одна з її вершин-нащадків успішно розв'язана.

Згідно стратегії пошуку від цілі в глибину, а саме така стратегія використовується в Пролозі, здійснюється послідовний обхід І / АБО - дерева зверху-вниз-зліва-направо.

Якщо при обході дерева який-небудь нащадок вершини типу АБО розв'язується успішно, то опрацювання останніх дочірніх вершин призупиняється і вважається, що АБО- вершина розв'язана успішно.

Якщо який-небудь із нащадків І-вершини зазнає неуспіх, то опрацювання останніх її нащадків припиняється і вважаєть ся, що дана вершина зазнає неуспіху. Зазначимо, що опрацювання АБО-вершини не припиняється, а тільки призупиняється. Це пов'язано з тим, що в подальшому можливе повторне звернення до цієї вершини, і тоді вітки, які залишилися неопрацьовані, можуть повторно привести до успіху цієї вершини.

Для ілюстрації описаної стратегії відшукання розв'язку дещо модифікуємо попередній приклад.
Нехай, наприклад, програма містить диз'юнкти:
р(Х) :-q1(Х), q2(Х, У), q3(У).
р(Х) :- q4(2, X), q5(2).

Пошук розв'язків Пролог-системою здійснюється з використанням механізму повернення. При цьому ланцюжки альтернативних гіпотез досліджуються методом пошуку в глибину, тобто шляхом спуску вниз по вітці до виявлення неуспіху, після чого здійснюється повернення до попереднього вузла і спуск по іншій вітці, і т.д. Разом із тим способи пошуку відповіді Пролог- системою аналогічні методу резолюції.

Для скорочення записів і наближення їх до вигляду, який використовувався в логіці предикатів, введено для предикатів і констант такі позначення: любить - Р, ягоди - Q, колір - S дорівнює - R, оленка - а1, оля — а2, малина - b1, суниці - b2, черешні - b3, чорниці - b4, цукерки - b5, малиновий - c1, жовтий - c2, червоний - c3, чорний - c4.

Тоді відповідна множина диз'юнктів матиме такий вигляд:
Р(a1, b1);
Р(a1, b2);
Р(a1, b3);
Р(a1, b5);
Р(а2, х1) V -Р(a1, x1) V -Q(x1) V - S(x1 c3);
Р(а2, x2) V -Р(a1, x2) V - R(х2, b5);
Q(b1);
Q(b2);
Q(bз);
Q(b4);
S(b1, c1);
S(b3, c2);
S(b3, c3);
S(b2, c3);
Б(b4, c4);
- P(a2, x) v Answer (x). Тут під шістнадцятим номером записано диз'юнкт, який відповідає запереченню запиту. Для одержання відповіді на поставлений запит будемо користуватися методом резолюції. Почнемо з диз'юнкта, який породжено запитом. Він може бути уніфікований тільки з позитивними літералами диз'юнктів 5 і 6. Опрацьовуватимемо їх по порядку. Застосувавши правило резолюції до диз'юнктів 16 і 5, одержимо резольвенту
-P(a1, x1) v -Q(x1) v -S(x1, c3) v Answer (x1);  Тепер шукаємо диз'юнкт, який уніфікується з першим літералом диз'юнкта 17. Такими диз'юнктами будуть диз'юнкти 1-4. Опрацьовуватимемо їх по черзі. Застосуємо правило резолюції до диз'юнктів 17 і 1, отримаємо резольвенту
-Q(b1) v -S(b1, c3) v Answer (b1). Продовжуючи резолюційний процес, отримаємо резольвенту
-S(b1, c3) v Answer (b1); (18 i 7). Одержаний диз'юнкт не уніфікується з жодним диз'юнктом. Тому треба повернутися до розгляду іншого диз'юнкта, який добирався до диз'юнкта 17, а саме до диз'юнкта 2. Це дає
-Q(b2) v -S(b2, c3) v Answer (b2); (17 i 2). Відшукуємо диз'юнкти, які уніфікуються з першим предикатом диз'юнкта 20. Для цього є один варіант - диз'юнкт 8. Правило резолюції, застосоване до 20 і дає:
-S(b2, c3) v Answer (b2); (20 і 8). Застосовуючи правило резолюції до 21 і 14, отримаємо порожній диз'юнкт і відповідь
□ v Answer (b2); (21 і 14).
Отже, застосовуючи метод резолюції, на запит "ЗХ любить (оля, X)" отримано відповідь
x = b2 (X = суниці).
Аналогічно можна одержати й інші розв'язки. Так, якщо повернутися назад і до диз'юнкта 17 вибрати диз'юнкт 3 та застосувати правило резолюції, то це приведе до наступного розв'язку
x = b3 (X = черешні).
Нарешті, якщо повернутися на початок до диз'юнкта, який є запереченням запиту (диз'юнкт 16), і продовжити опрацьовувати диз'юнкти, починаючи з шостого, то отримаємо ще один розв'язок
х = b5 (X = цукерки).

Із прикладу видно перевагу диз'юнктів Хорна під час пошуку розв'язків методом резолюції. Вона полягає в наявності "єдиного входу" - позитивного літерала під час пошуку партнера для застосування правила резолюції до негативного літерала. Це приводить до систематичного методу пошуку в глибину зліва направо при спробах застосовувати резолюцію і здійснювати підстановки: цей метод нагадує програмування з бектрекінгом.

Послідовність перебору така:

Починаємо із запиту, який містить тільки негативні літерали.

Беремо перший диз'юнкт Хорна, що містить позитивний літерал, який уніфікується з першим негативним літералом цілі, виконуємо уніфікацію і застосовуємо правило резолюції.

Беремо виведений диз'юнкт (резольвенту) і йдемо зліва направо, уніфікуючи негативні літерали. Якщо черговий літерал уніфікується з неодиничним диз'юнктом, то рухаємося в глибину, щоб вилучити всі негативні літерали в цьому диз'юнкті, точно так, як це робилося для початкового диз'юнкта.

Якщо який-небудь негативний літерал неможливо уніфікувати чи вилучити за допомогою правила резолюції, то треба повернутися і випробувати наступний по порядку підходящий диз'юнкт Хорна з новими підстановками. Якщо таких диз'юнктів нема, то пошук закінчується невдало.

Якщо вдалося уніфікувати всі літерали верхнього рівня, то виведено порожній диз'юнкт і доведення завершилося успішно. Видаються використані підстановки.

Розглянемо таку програму:
domains
name, denomination, colour = symbol predicates
to_like (name, denomination) berry (denomination) colour (denomination, colour) clauses
to_like (olenka, raspberry).
/* 2 */ to_like (olenka, strawberries).
/* 4 */ to_like (olenka, cherry).
/* 7 */ to_like (olenka, sweety). to_like (olya, X) :-
to_like (olenka, X), berry (X), colour (X, red).
/* 1 */ to_like (olya, X) :-
to_like (olenka, X), X = sweety. berry (raspberry).
/* 3 */ berry (strawberries).
/* 5 */ berry (cherry).
berry (bilberry). colour (raspberry, crimson). colour (cherry, yellow). colour (cherry, red). colour (strawberries, red).
/* 6 */ colour (bilberry, black).

Тут використано такі предикати (відношення): "любить" {наприклад, любить (оленка, суниці) - "Оленка любить суниці"}, "ягоди" {наприклад, ягоди (суниці) - "суниці - ягоди"}, "колір" {наприклад, колір (черешні, червоний) - "колір черешень - червоний"}, рівності (=).

Слід зазначити, що символ "=" є одночасно стандартним предикатом і оператором. Яким чином Пролог- системою інтерпретується використання цього символу визначається в залежності від того, чи мають терми, які стоять по різні боки від символу "=", конкретні значення, чи є невизначеними змінними.