Використання методу відкату і відсікання

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

– пошуку всіх товаришів по службі;

– пошуку всіх товаришів по службі конкретного працівника;

– з’ясуванню наявності товаришів по службі в конкретного працівника;

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

Один з варіантів реалізації даних вимог може мати вигляд розширеної процедури do_answer()

/* правило 1 */

do_answer("stop") :- write("good bye").

/* правило 2 */

do_answer(X) :- X="all", colleague(Z,Y), write(" ", Z, " -> ", Y), nl, fail, !.

/* правило 3 */

do_answer(X):- frontchar(X,"!",Z), colleague(Z,_),!, write(Z," має товаришів по службі"), nl, fail.

/* правило 4 */

do_answer(X) :- frontchar(X,"< ",Z), colleague(Q,Y), write(" ", Q, " -> ", Y), nl, Q=Z, !, fail.

/* правило 5 */

do_answer(X) :- colleague(X,Y), write(" ", X, " -> ", Y), nl, fail.

Процедура do_answer() складається з п'яти правил. Два з них, перше і п'яте, уже були розглянуті раніше.

Правило 1 забезпечує припинення повтору запитів за рахунок того, що його істинність при узгодженні не викликає відкату до предикату repeat.

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

Правило 2 забезпечує пошук і видачу всіх товаришів по службі за умови, що у відповідь на запит про прізвище вводиться слово “all” (тобто всі). Якщо з клавіатури введене будь-яке інше значення, перша підмета цього правила не погодиться і виконується відкат, що приводить до подальшого пошуку пропозицій, серед заголовків правил процедури do_answer().

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

Розробнику програми заздалегідь відомо, що для обробки слова „all” ніяких інших правил у процедурі do_answer не передбачено, але це невідомо системі, і вона буде переглядати всі правила процедури і проводити їхню уніфікацію.

У цьому випадку має сенс обмежити час і простір пошуку, закінчивши виконання всієї процедури do_answer після обробки слова „all”. З цією метою в дане правило останнім предикатом введено предикат відсікання, що приводить до припинення процедури do_answer, тобто виключенню з подальшого узгодження правил 3, 4 і 5.

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

Нехай, наприклад, із клавіатури введено „!Іванов”. При узгодженні заголовка правила 3 змінна Х уніфікується з рядковою константою „!Іванов” і починається обробка тіла правила.

Перша підмета викликає стандартний предикат frontchar(X,"!",Z) обробки символьних рядків (див. додаток А). Якщо перший символ Х збігається з “!”, то змінна Z приймає значення залишку рядка X, починаючи з другого символу (Z=”Іванов”). Якщо перший символ у Х відмінний від “!”, то перша підмета закінчується невдачею і відбувається відкат до обробки наступного правила процедури.

Друга підмета буде успішна, якщо буде погоджено предикат colleague(Z,_) при якому-небудь значенні Z. Використання анонімної змінної обумовлене характером запиту, у якому потрібно визначити тільки наявність колег, а не їхніх прізвищ. Успішне узгодження другої підмети викликає перехід до предиката відсікання, що встановлює ознаку заборони на відкат в даному місці правила.

Після цього узгодження правила продовжується праворуч від предикату відсікання, і здійснюється вивід на екран повідомлення “Іванов має товаришів по службі”.

Остання підмета викликає стан неуспіху в доведенні правила, що веде до відкату. Але, тому що предикат write() альтернатив не має, то відбувається відкат до предиката відсікання, яким уже встановлена заборона на подальший відкат. Це приводить до того, що на відміну від попередніх прикладів, повторне узгодження предикату colleague() виконуватися не буде. На цьому завершується узгодження даного правила, але не тільки його, але і всієї процедури do_answer(). Причому завершення процедури невдачею веде до того, що невдачею завершиться й остання підмета у предикаті query і, як наслідок, відбудеться відкат до предикату repeat і повторного вводу даних.

Дослідіть процес виконання програми при виключенні предикат fail з правила 3.

Правило 4 реалізує вимогу на обмеження виведеного списку деякою умовою. Як умова виступає прізвище службовця, яким повинний закінчуватися список колег. При цьому прізвище цього службовця вводиться, починаючи із символу, наприклад, ’<’. Вибір цього символу довільний

Перша підмета дасть істинний результат, якщо першим символом Х буде ’<’. Змінна Z у цьому випадку прийме значення залишку рядка X, починаючи з другого символу. В інших випадках, підмета завершиться невдачею, викликаючи невдачу і всього правила. Фактично ця підмета є умовою входу на обробку правила.

Наступні дві підцілі при узгодженні виводять на екран першу пару колег, а четверта – забезпечує повернення до пошуку наступної пари, якщо прізвище першого з колег не збігається з введеним з клавіатури. Як тільки ці прізвища співпадуть, тобто Q=Z стане істиною, виконається відсікання, що не дозволить предикатові fail забезпечити відкат до пошуку нової пари колег, що викликає закінчення виконання даного правила.

Наявність у правилі предиката відсікання не тільки обмежує область пошуку в базі даних заданим прізвищем, але і забезпечує завершення всієї процедури do_answer(). Завершення процедури приводить до повернення до правила query.

Варто особливо звернути увагу на те, що відкат до пошуку альтернативних рішень підмети colleague(Q, Y) у даному правилі, на відміну від правил 2 або 5, виконує не fail, а підмета Q=Z. Тоді, чи потрібний у цьому правилі взагалі предикат fail, а якщо потрібний, то навіщо?

Уся справа в тому, що процедура do_answer() виконується не сама по собі, а викликається як остання мета правила query. Тому, крім функцій пошуку даних у базі, на неї покладена функція керування відкатом до предикату repeat, тобто організація повторень по вводу даних.

Присутність у правилі 4 предиката fail приводить до того, що незважаючи на успішно виконаний запит до бази даних, правило закінчується невдачею. Невдачею завершується і запит з query до процедури do_answer(), що викликає відкат до repeat і повторення вводу даних.

Якщо в правилі 4 не буде предиката fail, то після виконання пошуку в базі правило буде успішно виконаним. Успішним буде і звертання з query до процедури do_answer(), що веде до того, що і правило query стане істинним. Це викликає його закінчення, а разом з цим і закінчення вводу запитів.

Але тому що ознакою закінчення вводу повинен бути ввід слова „stop”, то закінчення роботи програми за іншою вимогою було б помилкою, що і вимагає обов'язкового включення предиката fail у правило 4.

2.10 Відкат і відсікання при реалізації відносин типу „один-до-багатьох”

Облік асоціацій (зв'язків) між об'єктами відносин служить засобом оптимізації запитів у Пролозі. Розглянемо це на прикладі простого відношення

Батько(Ім’я, Дитина),

яке в програмі визначається набором деяких фактів. Між об'єктами даного відношення існує асоціація „один-до-багатьох”. Запит до даної бази може полягати:

– або в пошуку батька конкретної дитини (у цьому випадку має місце простий зв'язок);

– або в пошуку всіх дітей конкретного батька (у цьому випадку має місце складний зв'язок);

Найбільш примітивний спосіб реалізації простого зв'язку полягає в написанні правила, що повинне виконати пошук факту, а потім пройти через предикат відсікання. Для реалізації складного зв'язку необхідний пошук всіх альтернативних рішень у базі даних. Використання нової процедури parent (батько), що враховує вказані зауваження, забезпечить інтерфейс роботи з БД father() .

Причому цей інтерфейс враховує наявний зв'язок між об'єктами відносин БД father() і оптимізує виконання запиту Прологом.

/* програма 2.5 */

domains

nаме, child = symbol

predicates

father(name,child)

parеnt(namе,child)

clauses

father( "іван", "петро").

father( "іван", "павло" ).

father( "петро", "оля" ).

father( "оля" , "борис" ).

/* пошук батька (батька) конкретної дитини */

parent(F,C) :- bound(C), fathеr(F,C),!.

/* пошук усіх дітей конкретного батька */

parent(F,C) :- free(C), fathеr(F,C).

Предикат bound(C) успішний у випадку, якщо змінна С зазначена, а предикат free(C) успішний, якщо змінна С вільна.

Слід зазначити, що два правила процедури є взаємовиключними. А якщо це так, то перевірку в другому правилі стану змінної С можна не виконувати, тому що якщо вона буде зв’язаною, то буде оброблена першим правилом. Однак, якщо ці правила поміняти місцями, то цього робити не можна.