Процес пошуку розв’язків Пролог-системою на запити
Процес пошуку розв'язку Пролог-системою проілюструємо на прикладі.
Розглянемо таку програму:
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).
/* name - ім‘я */
/* denomination - назва */
/* colour - колір */
/* to_like - любить */
/* berry- ягоди */
/* raspberry - малина */
/* strawberries - суниці */
/* cherry - черешні*/
/* sweety - цукерки*/
/* red - червоний */
/* bilberry - чорниці*/
/* crimson - малиновий */
/* yellow - жовтий */
/* black - чорний */
Слід зазначити, що символ "=" є одночасно стандартним предикатом і оператором. Яким чином Пролог- системою інтерпретується використання цього символу визначається в залежності від того, чи мають терми, які стоять по різні боки від символу "=", конкретні значення, чи є невизначеними змінними.
Тут використано такі предикати (відношення): "любить" {наприклад, любить (оленка, суниці) - "Оленка любить суниці"}, "ягоди" {наприклад, ягоди (суниці) - "суниці - ягоди"}, "колір" {наприклад, колір (черешні, червоний) - "колір черешень - червоний"}, рівності (=).
Співвідношення методу резолюції і пошуку в глибину
Послідовність перебору така:
Якщо вдалося уніфікувати всі літерали верхнього рівня, то виведено порожній диз'юнкт і доведення завершилося успішно. Видаються використані підстановки.
Якщо який-небудь негативний літерал неможливо уніфікувати чи вилучити за допомогою правила резолюції, то треба повернутися і випробувати наступний по порядку підходящий диз'юнкт Хорна з новими підстановками. Якщо таких диз'юнктів нема, то пошук закінчується невдало.
Беремо виведений диз'юнкт (резольвенту) і йдемо зліва направо, уніфікуючи негативні літерали. Якщо черговий літерал уніфікується з неодиничним диз'юнктом, то рухаємося в глибину, щоб вилучити всі негативні літерали в цьому диз'юнкті, точно так, як це робилося для початкового диз'юнкта.
Беремо перший диз'юнкт Хорна, що містить позитивний літерал, який уніфікується з першим негативним літералом цілі, виконуємо уніфікацію і застосовуємо правило резолюції.
Починаємо із запиту, який містить тільки негативні літерали.
Із прикладу видно перевагу диз'юнктів Хорна під час пошуку розв'язків методом резолюції. Вона полягає в наявності "єдиного входу" - позитивного літерала під час пошуку партнера для застосування правила резолюції до негативного літерала. Це приводить до систематичного методу пошуку в глибину зліва направо при спробах застосовувати резолюцію і здійснювати підстановки: цей метод нагадує програмування з бектрекінгом.
Для скорочення записів і наближення їх до вигляду, який використовувався в логіці предикатів, введено для предикатів і констант такі позначення: любить - Р, ягоди - 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 = цукерки).
Пошук розв'язків Пролог-системою здійснюється з використанням механізму повернення. При цьому ланцюжки альтернативних гіпотез досліджуються методом пошуку в глибину, тобто шляхом спуску вниз по вітці до виявлення неуспіху, після чого здійснюється повернення до попереднього вузла і спуск по іншій вітці, і т.д. Разом із тим способи пошуку відповіді Пролог- системою аналогічні методу резолюції.
Процес пошуку розв'язків Пролог-системою на запити.
У реалізаціях Прологу на послідовних машинах використовується стратегія, яка управляє послідовними обчисленнями.
У цьому випадку, якщо задано дві умови, то для одного з них дерево виводу будується повністю до того, як почне опрацьовуватися друга умова.
Описаний алгоритм опрацювання можна реалізувати на дереві спеціального вигляду: І / АБО - дереві
Якщо який-небудь із нащадків І-вершини зазнає неуспіх, то опрацювання останніх її нащадків припиняється і вважаєть ся, що дана вершина зазнає неуспіху. Зазначимо, що опрацювання АБО-вершини не припиняється, а тільки призупиняється. Це пов'язано з тим, що в подальшому можливе повторне звернення до цієї вершини, і тоді вітки, які залишилися неопрацьовані, можуть повторно привести до успіху цієї вершини.
Зазначимо, що повернення назад (backtracing) Пролог-система використовує для пошуку нових шляхів до розв'язку, зокрема для знаходження додаткових фактів і правил, необхідних для обчислення цілі, якщо поточна спроба обчислити ціль виявилася невдалою.
Для ілюстрації описаної стратегії відшукання розв'язку дещо модифікуємо попередній приклад.
Нехай, наприклад, програма містить диз'юнкти:
р(Х) :-q1(Х), q2(Х, У), q3(У).
р(Х) :- q4(2, X), q5(2).
Якщо при обході дерева який-небудь нащадок вершини типу АБО розв'язується успішно, то опрацювання останніх дочірніх вершин призупиняється і вважається, що АБО- вершина розв'язана успішно.
Згідно стратегії пошуку від цілі в глибину, а саме така стратегія використовується в Пролозі, здійснюється послідовний обхід І / АБО - дерева зверху-вниз-зліва-направо.
У кожній своїй вершині І / АБО - дерево має мітку І або мітку АБО. Вершина І успішно розв'язана тільки в тому випадку, коли її вершини - нащадки успішно розв'язані. Вершина типу АБО успішно розв'язана в тому випадку, коли хоча б одна з її вершин-нащадків успішно розв'язана.
Нехай, наприклад, програма має вигляд:
р :- p1, p2, p3.
р :- q4, q5.
Цю програму можна розуміти таким чином. Щоб успішно досягти ціль р, потрібно спочатку довести ціль q1, потім ціль q2 , потім ціль q3: Якщо і q1 і q2, і q3 доведені, то й доведено ціль р. Інакше процедурар терпить неуспіх (ціль р недосяжна, невивідна).
Декларативний і процедурний смисл Пролог-програми.
При процедурному трактуванні Пролог-програми відмічається послідовність кроків, які виконує Пролог-система при опрацюванні запиту.
Процедурна семантика визначає як Пролог-система шукає відповідь на поставлений запит. Таким чином, має значення порядок слідування підцілей у правилі. Зазначимо, що всю множину фраз про одне й те саме відношення (предикат) можна розглядати як процедуру, а запит (або підціль правила) як виклик процедури.
Декларативний смисл стосується відношень, які визначені в програмі, і визначає, що повинно бути результатом роботи програми. Порядок слідування підцілей (умов) у правилі не впливає на декларативний смисл правила.
Пролог-програму можна розглядати як із позиції декларативного підходу, так і з позиції процедурного підходу.
