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

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

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

rule :-

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

fail.

Наприклад, наступна програма друкує назви всіх міст, які знаходяться в базі даних.

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).

Друге, рекурсивне правило говорить:

Число 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.

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