5.4 Застосування предикату not - заперечення як неуспіх

Розглянемо фразу “Іван любить усі ігри крім баскетболу.” Спробуємо записати її на Пролозі. Першу частину цього твердження виразити легко: “Іван любить довільне Х, якщо Х – гра”, або ж :

like(„Іван”,X):-game(X).

Aлe ж потрібно виключити баскетбол. Це можна зробити, використавши інше формулювання:

Якщо Х – баскетбол, тоді “Іван любить Х” не буде істиною, інакше, якщо Х – гра, тоді “Іван любить Х”.

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

like(”Іван”, X):- basketball(X),!,fail.

like(”Іван”, X):- game(X).

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

Цей приклад показує, що бажано мати унарний предикат not, такий, що not(Ціль) буде істинним у випадку, коли Ціль не є істиною. На Пролозі його можна описати так:

not(P):- P,!, fail;

true.

Пролог-система має вмонтований предикат not, реалізований подібним чином.

Тоді наш приклад можна переписати в такому вигляді:

like(„Іван”, X):- game(X), not(basketball(X))

Наступна программа показує використання предиката not.

Єдине, що варто зазначити: предикат not виконується успішно, коли підціль не є істиною, тобто тоді, коли асоційована з ним підціль не може довести істинність.

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

domains

name = symbol

gpa = real

predicates

honor_student(name)

student(name, gpa)

probation(name)

clauses

honor_student(Name):- student(Name, GPA), GPA>=3.5, not(probation(Name)).

student("Сюрпіта", 3.5).

student("Петров", 2.0).

student("Михайлів", 3.7).

probation("Сюрпіта").

probation("Петров").

На запит honor_student(Name) вона видрукує список студентів, середній бал яких більший або ж дорівнює 3,5 за виключенням студентів Петрова і Сюрпіти, котрі проходять випробувальний термін.

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

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

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

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

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

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

Один з варіантів реалізації даних вимог може мати вигляд розширеної процедури 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() складається з п'яти правил. Два з них, перше і п'яте, уже були розглянуті раніше.

Завдання 6.

Поверніться до файлу lab5.pro і доповніть процедуру 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) обробки символьних рядків (див. додаток 1). Якщо перший символ Х збігається з “!”, то змінна Z приймає значення залишку рядка X, починаючи з другого символу (Z=”Іванов”). Якщо перший символ у Х відмінний від “!”, то перша підмета закінчується невдачею і відбувається відкат до обробки наступного правила процедури.

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

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

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

Завдання 7.

Дослідіть процес виконання програми при виключенні предикат 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.

Завдання 8.

Виконайте програму в покроковому режимі для правила 4. Дослідіть процес виконання відсікання. Повторіть те ж саме без предикату fail. Реалізуйте процедури подібні до процедури do_answer() в індивідуальному завданні.

Розглянуті вище підходи до організації відкатів і відсікання можуть аналогічним способом використовуватися і при формуванні зовнішніх цілей у вигляді складених запитів.

Завдання 9.

Сформуйте зовнішні цілі для запитів, аналогічних до реалізованих у процедурі do_answer() і виконаєте їх при виконанні індивідуального завдання.