predicates

f(integer,integer).

clauses

f(X,10):- X < 10,!.

f(X,20):- X >= 10, X < 20,!.

f(X,30):- X >= 20.

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

goal: f(22,Y),

тоді Пролог-система зробить три перевірки, і тільки після цього зв'яже з У значення 30. Але ж наші перевірки взаємовиключні. Тому для підвищення ефективності, ми можемо запропонувати такий варіант програми:

predicates

f(integer,integer).

clauses

f(X,10):- X < 10,!.

f(X,20):- X < 20,!.

f(X,30).

В цьому випадку предикат відтинання міняє і декларативну сторону програми.

Предикат cut по різному діє на складний запит і на множину фраз. Розглянемо випадок, коли предикат відтинання є однією із підцілей складного запиту:

goal: a(X),b(Y),!,c(X,Y,Z)

При виконанні цього запиту Пролог-система пройде через предикат cut тільки в тому випадку, коли підціль а(X) i підціль b(Y) будуть задоволені. Після того, як підціль cut буде оброблена, система не зможе повернутися назад для повторного розгляду підцілей "а" і "b", якщо підціль "с" не задовільниться при поточних значеннях Х і У.

Приведемо ще один приклад використання cut:

predicates

buy_car(symbol, symbol)

car(symbol, symbol,integer)

colors(symbol, symbol)

clauses

buy_car(Model, Color) :- car(Model, Color, Price),

colors(Color, sexy),!,

Price < 25000.

car(maserati, green, 25000).

car(corvette, black, 24000).

car(corvette, red, 26000).

car(porsche, red, 24000).

colors(red, sexy).

colors(black, mean).

colors(green,preppy).

Використання предикату cut говорить про те, що нас спочатку цікавить модель і колір автомобіля, а потім вже ціна.

Для пояснення дії предикату cut повернемося до процесу керування побудови виведення в Пролозі. Нехай прологівська програма має наступний вигляд.

р: - a,b.

p: - c,d.

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

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

Р

а 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(Ціль)