Son-daughter(X, Y):- parent(Y, X), man(X).

Після уніфікації структур son-daughter(ann, bob) та son-daughter(X, Y) значення змінних будуть X=ann, Y=bob. Тоді початкова ціль буде замінена двома новими: parent(bob, ann) і man(ann). Перша з них досяжна, оскільки її можна уніфікувати з фактом із програми, друга не досяжна – її не можна уніфікувати з жодним фактом чи правилом програми. Ціль man(ann) є неуспішна.

Тепер Пролог-система повертається до початкової цілі son-daughter(ann, bob) (бектрекінг), щоб реалізувати другий варіант виведення цілі, тобто

Son-daughter(X, Y):- parent(Y, X), women(X).

Аналогічно Пролог-система приходить до двох цілей: parent(bob, ann) і women(ann). Оскільки обидві цілі можна уніфікувати з фактами програми, вони досяжні. Таким чином, запит до Пролог-системи є успішний, і вона дасть позитивну відповідь: yes.

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

Розглянемо, наприклад, таку функцію:

якщо Х < 2, то Y = 10;

якщо Х ≥ 2 i Х < 4, то Y = 20;

якщо Х ≥ 4, то Y = 30.

Мовою Пролог цю функцію можна реалізувати таким чином:

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

f(X, 20):- X >= 2, X < 4.

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

Якщо тепер зробити Пролог-системі запит f(0, Y), Y=5, то після досягнення першої підцілі f(0, Y) за першим правилом f(X, 10):- X < 2. змінна Y буде конкретизована значенням 10. Друга підціль Y=5 буде хибною, оскільки 10 не дорівнює 5. Запуститься механізм бектрекінгу, Пролог-система знову повернеться до підцілі f(0, Y) і невдало намагатиметься задовольнити її за другим і третім правилами f(X, 20):- X >= 2, X < 4., f(X, 30):- X >= 4. Зрештою запит f(0, Y), Y=5 закінчиться невдало (результат – No). У ході аналізу роботи програми можна виявити, що намагання Пролог-системи задовольнити підціль f(0, Y) за другим і третім правилами даремні, тому що всі три правила взаємовиключні (якщо виконується перше правило, інші два виконуватися не будуть; X не може одночасно бути меншим за 2 і більшим або рівним 2 і т. д.). Тому в цьому випадку бектрекінг не має сенсу, і його можна заборонити таким чином:

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

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

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

Тепер у випадку запиту f(0, Y), Y=5, після того як за першим правилом змінна Y буде конкретизована значенням 10, а потім підціль Y=5 виявиться хибною, Пролог-система не зможе повернутися далі точки, поміченої в програмі предикатом!. Пролог-система зразу видасть результат запиту (як і в першому варіанті програми – No), не включаючи в роботу даремно друге і третє правила, що підвищить швидкість виконання програми. На декларативний зміст програми введення предиката! не вплинуло, змінився тільки процедурний зміст, тому результати запитів до програми не зміняться, якщо вилучити предикати! з програми.

Якщо застосування предиката! не впливає на декларативний зміст програми, то його називають „зелений cut ”, у протилежному випадку – „червоний cut ”. Фахівці рекомендують конструювати програми таким чином, щоб не використовувати „червоний cut ” (або використовувати якомога менше).

Організація циклів. Рекурсія

 

Циклічні процеси в мові Пролог можна організовувати двома способами – із застосуванням бектрекінгу та за допомогою рекурсії.

Загальний вигляд правила, що виконує повторення за допомогою бектрекінгу, такий:

 

Rule:-

<предикати>,

Fail.

 

Наприклад, наведена нижче програма виводить на екран назви всіх міст, які знаходяться в БД. Щоб увімкнути підтримку кирилиці, необхідної для запуску цієї програми, треба виконати такі дії: вибрати пункт меню Options – Global (.INI)-Environment, потім у вікні Environment перейти на вкладку Fonts і в області Editor Windows клацнути кнопку Change Font, далі у вікні Шрифт у списку Набор символов вибрати Кириллический і OK).

 

Domains

town = string

Facts

Town(town)

Predicates

print_town

Clauses

Town(“Київ”).

Town(“Одеса”).

Town(“Харків”).

print_town:-

Town(X), write(X), nl, fail.

print_town.

Goal

print_town.

 

Процедура, яка реалізує предикат print_town, складається з двох речень. Перше речення town(X), write(X), nl, fail. говорить: “Знайти розв’язок предиката town(X), надрукувати цей розв’язок, перейти на наступний рядок, потім повернутись і пошукати інший розв’язок”. Повернення й пошук іншого розв’язку забезпечує вбудований предикат fail, який завжди має хибне значення. Таким чином він активує бектрекінг. Без другого речення print_town. виконання програми закінчувалося б неуспішно і після виведення на екран назв усіх міст на екрані з’являлося б слово No. Інший цікавий спосіб застосування бектрекінгу для організації циклу полягає у використанні предиката repeat, який визначають таким чином:

 

Repeat.

Repeat:- repeat.

Наприклад, нижчеподана програма виводить на екран усі символи, які вводить користувач, і закінчує роботу у випадку введення символу „.” (крапка).

 

Predicates

Nondeterm repeat

Nondeterm print

Clauses

Repeat.

Repeat:- repeat.

Print:- repeat,

readchar(X), write (X), X=’.’, nl.

Goal

Print.

 

Процедура print виконується таким чином. Спочатку виконується предикат repeat, який нічого не здійснює, потім зчитується з клавіатури в змінну Х деякий символ, далі він виводиться на екран, перевіряється на рівність крапці „.”. За умови, якщо символ дорівнює крапці, відбувається перехід на наступний рядок і процедура закінчується. У противному разі починається бектрекінг і перегляд альтернатив. Ні write (X),ні readchar(X) не породжують нових альтернатив, тому бектрекінг приводить далі назад до предиката repeat, який дозволяє отримати альтернативні розв’язки. Керування переходить знову на початок, зчитується символ і т. д.

У цій програмі предикати repeat і print оголошуються з ключовим словом nondeterm. Це означає, що ці предикати можуть генерувати альтернативні множинні розв'язки. Такі предикати можуть також зазнавати неуспіху і в цьому випадку не породжувати ніяких розв'язків.

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

 

rule:- <predicates>. % нерекурсивне правило

rule:- <predicates>, % рекурсивне правило

Rule.

 

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

 

Domains

chyslo = integer

factorial = integer

Predicates

Factorial(chyslo, factorial)

Clauses

factorial(1, 1):-!.

factorial(N, FactN):- N_1=N-1,

factorial(N_1, FactN_1), FactN=N*FactN_1.

Goal

Factorial(5, N), write(N), nl.

 

Перше правило процедури factorial можна сформулювати так: факторіал числа „1” дорівнює одиниці (тобто 1!=1).

Друге, рекурсивне, правило говорить: число FactN є факторіалом числа N, якщо воно становить добуток числа N і факторіала числа N-1 (тобто N!=N*(N-1)!).

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

 

Предок(X, Z):-

Батько(X, Z).

Предок(X, Z):-

Батько(X, Y), предок(Y, Z).

 

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

· для всіх X і Z X є предком Z, якщо X – батько Z;

· для всіх X і Z X є предком Z, якщо існує такий Y, що X є батьком Y і Y – предок Z.

Як видно, перше правило рекурсивної процедури відображає окремий випадок відношення (предком є батько), а друге – загальний випадок (предком є будь-який родич за висхідною лінією). Це загальний підхід до визначення рекурсивних відношень.