P: - c,d

Цю програму, використовуючи поняття процедури, можна прочитати наступним чином. При виконанні процедури р виконуються процедури a і b. Якщо вони закінчуються успішно, тоді і процедура р вважається успішно завершеною. Якщо це не так, тоді виконуються процедури с і d. Процедура р вважається задоволеною, якщо успішно виконуються процедури с і d. В іншому випадку процедура р закінчується невдало.

Такий алгоритм обробки можна реалізувати на дереві типу “ і ” - “ або ” (мал.4.1), де Ù позначає вузол типу “ або ”, а A позначає вузел типу “ і ”.

 

Р

 

 

а b c d

 

мал.4.1.

 

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

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

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

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

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

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

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

Розглянемо програму:

а(x): - b(x),!, c(x)

a(x): - d(x)

B(c).

B(f)

C(e)

C(f)

D(g)

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

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

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

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

 

4.3.ПРЕДИКАТ 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),