Clauses

R(3):-!, с.

R(2):-!, d.

R(1):-!, а, b, с.

D(g).

C(f).

C(e).

B(f).

B(e).

А b c d

Вершина типу “ і ” успішно розв`язувана тільки в тому випадку, коли її вершини сини успішно вирішені. Вершина типу “ або ” успішно розв`язувана, коли хоча б одна з її вершин-синів успішно розв`язувана.

Згідно стратегії пошуку вглиб, яка використовується в Прологу, проводиться послідовний перегляд дерева “ і - або ” зверху - донизу, зліва – направо. Це відповідає виділенню самої лівої підцілі запиту і впорядкуванню зверху - донизу правил програми.

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

Якщо якась з вершин синів вершини типу “ і ” вирішується невдало, тоді обробка інших її вершин-синів закінчується невдало.

Зауважимо, що обробка вершини “ або ” не закінчується, а лише призупиняється. Це пов`язано з тим, що з часом можливе повернення до цієї вершини, і тоді гілки, які ще не аналізувались, можуть знову привести до успіху в цій вершині (бектрекінг).

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

Одним із засобів усунення вказаного недоліку є використання предикату cut. Таким чином відтинається (і іноді досить суттєво) дерево розгалуджень. Розглянемо програму:

а(Х): - b(Х),!, c(Х).

a(Х): - d(Х).

На запит a(Z) програма побудує єдину відповідь Z=e, оскільки вона не буде повертатись до розгалуджень, які виникли до виклику cut (при обробці підцілей a(Z) і b(Z).

Якщо ж ми видалимо предикат cut з першого правила і побудуємо запит a(Z), тоді отримаємо три відповіді Z=e, Z=f, Z=g.

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

Запобігання пошуку з вертанням до наступного твердження

Відсікання можна використати, як спосіб повідомити Vіsual Prolog, що він обрав вірне твердження для деякого предиката. Розглянемо програму:

r(_):- wrіte("Thіs іs a catchall clause.").

Використання відсікання робить предикат r детермінованим. У цьому випадку Vіsual Prolog виконує звернення до r з єдиним цілим аргументом. Припустимо, що зроблено виклик r(l). Система переглядає програму в пошуках відповідності для виклику; знаходить її з першим твердженням, що визначає r. Оскільки є більш ніж одне можливе рішення для даного виклику, Vіsual Prolog проставляє точку вертання біля цього твердження.

Тепер Vіsual Prolog починає обробку тіла правила, проходить через відсікання й виключає можливість вертання до іншого твердження r. Це скасовує точки пошуку вертання, підвищуючи ефективність виконання програми, а також гарантує, що помилкове твердження буде виконано лише, коли жодна з умов не буде відповідати зверненню до r.

Зверніть увагу, що така конструкція схожа на конструкцію case в інших мовах програмування; умова перевірки записується в заголовку правил. По можливості, завжди варто поміщати перевірочну умову саме в заголовок правила, - програма стає ефективнішою і простішою для читання.

Детермінізм і відсікання

Якби предикат r, визначений у попередній програмі, не містив відсікань, то це був би недетермінований предикат (здатний робити множинні рішення за допомогою пошуку з вертанням). Vіsual Prolog виконує перевірку тверджень на недетермінованість, полегшуючи роботу програмістів.

У Пролозі є директива компілятора check_determ. Якщо вставити її в самий початок програми, то Vіsual Prolog буде видавати попередження у випадку виявлення в процесі компіляції недетермінованих тверджень.

Можна перетворити недетерміновані твердження в детерміновані, вставляючи відсікання в тіло правил, що визначають відповідний предикат.

Предикат not - заперечення як неуспіх.

Запишемо фразу "Ваня любить всі ігри крім баскетболу." на Прологу. Першу частину цього твердження виразити легко: " Ваня любить довільне Х, якщо Х - гра ", або ж:

like(wanja,X):-game(X).

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

Якщо Х - баскетбол, тоді "Ваня любить Х" не буде істиною, інакше, якщо Х - гра, тоді "Ваня любить Х".

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

like(wanja, X):- basketball(X),!,fail. % семантично

невірна програма

like(wanja, X):- game(X).

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

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

Пролог система має вбудований предикат not, реалізований подібним чином. Тоді наш приклад можна переписати в такому вигляді:

like(wahja,X):- game(X), not(basketball(X)).

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

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

domaіns

name = symbol

gpa = real

predіcates

honor_student(name)

student(name, gра)

probatіon(name)

honor_student (Name):- student(Name, GPA),

GPA>=3.5, not(probatіon(Name)).

student ("Betty Blue", 3.5).

student ("Davіd Smіth", 2.0).

student ("John Johnson", 3.7).

probatіon ("Betty Blue").

probatіon ("Davіd Smіth").

Дата добавления: 2014-01-04