Відтинання

Призначення відтинання – динамічне обмеження простору пошуку. Відтинання попереджає нескінченні цикли у випадку успішного узгодження граничної умови і виключає зайві перевірки. Нехай студентові, залежно від набраної у процесі суми балів Z, присвоюється кваліфікація згідно з таблицею

Z>80 M

80>Z>60 S

60>Z>40 B

40>Z>=0 N

(відповідно – „магістр”, спеціаліст”, „бакалавр”, „невдаха”). Запишемо фрагмент найпростішої Пролог-програми:

grade(Z, „M”): -Z>=80,

grade(Z, „S”): -Z<80,S>=60.

grade(Z, „B”): -Z<60,S>=40.

grade(Z, „N”)^ -Z<40.

Під час запиту типу grade (53, G) успіх принесе тільки третя стрічка, причому перші перевірки в другій та третій стрічках є напевно зайвими внаслідок негативного наслідку для попередньої стрічки. Той самий результат можна отримати шляхом:

grade(Z, „M”): -Z>=80.

grade(Z, „S”): -Z>=60.

grade(Z, „B”): -Z>=40.

grade(Z, „N”).

Проте на запит grade (94, G) можна послідовно отримати усі чотири можливих відповіді. Тому кращим буде варіант повної програми:

domains

x = integer

r = symbol

predicates

grade (x, r)

......стр. 71

Clauses

grade (Z, “∙”): -Z < 0 ,!, fail

grade (Z, “-”): -Z > 100 ,!, fail

grade (Z, “M”): -Z >=80 ,!,

grade (Z, “S”): -Z >=60 ,!,

grade (Z, “B”): -Z >=40 ,!,

grade (Z, “N”).

у якому задоволення умовам одного варіанту виключає всі наступні і додатково передбачений захист програми від некоректних даних (два перших твердження). При запиті grade (666, Q) предикат fail зупинить механізм повернення, і на запит буде надана негативна відповідь. Предикат “!” відтинає всі наступні відкати.

У прикладі

Goal

Write (“Children”), n1, n1, /*Заголовок “Діти”*/

Chilist

Clauses

Child (“Тимофій”).

Child (“Борис”).

Child (“Ян”).

Child (“Леонід”).

Child (“Марія”).

Child (“Дар’я”).

......................................

chilist: -

Child (Name),

Write (“ ”, Name), nl,

Cutting (Name),!.

Cutting (Name): -

Name=“Марія”.

будуть виводитися послідовні імена і (за незбігу імен) відбуватимуться відкати – доти, поки не вибереться Марія.

Ще один приклад:

minimum (X,Y,X): -X<=Y, !.

minimum (X,Y,Y): -X>Y, !.

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

Підсумуємо властивості відтинання:

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

2) кон’юнкція цілей, що знаходяться перед відтинанням, призводить не більше ніж до одного рішення;

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

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

likes (“Марія”, X): - likes (“Марія”, X): -

mouse (X), !, fail; animal (X),

animal (X). not mouse (X).

Якщо в програмі є відтинання, то зміна порядку речень може вплинути на її декларативний смисл. Тому застосування not є кращим, проте у цьому випадку існує інша небезпека, яка виникає внаслідок замкненості світу Прологу; те, що не може бути доведеним як істина, вважається хибним. Відтинання, на відміну від інших конструкцій Прологу, інтерпретується процедурно. Тому корисність відтинань деякими авторами заперечується з концептуальних позицій, як порушення чистоти логічного стилю програмування. Безперечно його акуратне використання може підвищити виразність та ефективність програм, виключити перевірку свідомо хибних альтернатив та зменшити потребу у пам’яті, оскільки для повернення знадобиться зберігати менше інформації. Інший шлях до ефективності – мінімізація числа повернень через зміну порядку речень з урахуванням специфіки задачі.

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

repeat,

repeat: -repeat.

(замість repeat можна використовувати loop, iterate,…).

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

execute:-

repeat,

…………..

check (Test), !/

серед інших тверджень –

check (Stop):-

n1, write (“Finish”).

check ( _ ): fail.