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

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

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

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.

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