Вмонтований предикат fail завжди має хибне значення, але ми могли б форсувати бектрекінг, використавши якийсь інший, завжди хибний предикат типу 10 = 3 + 4, або country(abracadabra) .

Таким чином, будуть надруковані всі країни і процес обробки системою першої фрази закінчиться. Після, почнеться обробка другої фрази того ж предикату print-countries. Вона нічого не робить, а тільки завершає успіхом роботу системи. Кінцеве виведення буде мати вигляд:

england

france

germany

denmark Yes

Якби не було другої фрази, виведення закінчувалось - No, а все інше виведення залишилось без змін.

6.2.Дії типу до і після.

Можливо в попередній програмі треба для наглядності зробити наступні зміни:

1. надрукувати заголовок;

2. надрукувати всі можливі розв'язки запиту;

3. надрукувати в кінці заключне повідомлення.

Тоді нам потрібно в попередню програму внести наступні модифікації в визначенні предикату Print-countries.

print_countries:- write("Some delightful places to live are"),

nl, fail.

print_countries:- country(X), write(X), nl, fail.

print_countries:- write(" And maybe others."), nl.

6.3.Застосування бектрекінгу для реалізації циклів.

repeat.

Розглянемо наступний предикат

repeat:-repeat.

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

predicates

repeat

typewriter

clauses

repeat.

repeat :- repeat.

typewriter :- repeat,

readchar(C),

write(C),

char_int(C,13).

Ця програма показує як працює repeat. Правило typewriter... описує процедуру, яка отримує символи з кейборди і друкує їх на екрані, поки не буде натиснута клавіша ENTER (ASCII кoд 13).

Вона працює так:

1.Виконається repeat (який нічого не робить).

2.Потім читається символ в змінну C.

3.Потім друкується C.

4.Потім перевіряється чи С не дорівнює 13 в коді ASCII.

5.Якщо так, тоді фінішуємо. Інакше, починається бектрекінг і перегляд альтернатив. Ні write ні readchar не генерують альтернативних рішень, тому бектрекінг веде до repeat, котрий дозволяє отримати альтернативні рішення.

6.Тепер обробка може повернутись знову на початок, читати інший символ, друкувати його, перевіряти на рівність 13.

6.4.Рекурсивні процедури.

Інший шлях реаліцації повторення є використання рекурсії. Розглянемо рекурсивну програму обчислення значення факторіалу n!. Яку можна проінтерпретувати наступним чином. Якщо n=1, тоді n!=1 (за рахунок factorial(1,1):-!), інакше n!=n*(n-1)!. Останнє обчислення забезпечується наступною фразою визначення factorial(x,FactX).

predicates

factorial(integer, real)

clauses

factorial(1, 1) :- !.

factorial(X, FactX) :- Y = X-1,

factorial(Y, FactY),

FactX = X*FactY.

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

Попередня рекурсивна програма обчислення факторіалу може бути описана на Паскалі в наступному ітераційному вигляді:

p:=1;

for i:=1 to n do

p:=p*i;

FacN:=p;

або ж використовуючи цикл типу while:

p:=1; i:=1;

while i<=n do

begin p:=p*i; i:=i+1 end;

FacN:=p;

Мал.6.2.

Фрагмент програми, зображений на мал.6.2, можна транслювати в Пролог наступним чином.

predicates

factorial(integer, real)

factorial_aux(integer,real, integer, real)

/* Числа більші за 32767 повинні бути описані як дійсні. */

clauses

factorial(N, FactN):- factorial_aux(N, FactN, 1, 1).

factorial_aux(N, FactN, I, P):- I <= N, !,

NewP = P * I,

NewI = I + 1,

factorial_aux(N, FactN, NewI, NewP).

factorial_aux(N, FactN, I, FactN) :- I > N.

Мал.6.3.

Більш красивіший варіант попередньої програми поданий на мал.6.4.

predicates

factorial(integer,real)

factorial(integer, real,integer, real)

clauses

factorial(N,FactN):- factorial(N,FactN,1,1).

factorial(N, FactN, N, FactN):- !.

factorial(N, FactN, I,P):-NewI = I+1,

NewP = P*NewI,

factorial(N,FactN,NewI,NewP).

мал.6.4.

6.1. Написати рекурсивну і нерекурсивну програми, які обчислюють значення F(M,N) для довільної пари цілих чисел M,N>=0, яке визначається наступним чином:

M+N+1 якщо M*N=0

F(M,N)=

F(M-1, F(M,N-1)) в іншому випадку

6.2. N-те число Фіббоначі визначається наступним чином

0 якщо N=0

F(N)= 1 якщо N=1

F(N-1)+F(M,N-1)) в іншому випадку

Написати рекурсивну і некурсивну програми, які обчислюють N-те число Фіббоначі.

6.3. Найбільший спільний дільник G(M,N) двох цілих чисел M і N можна визначити наступною рекурсивною схемою

M якщо N=0

G(M,N)=

G(N, MOD(M,N)) якщо N0

Написати програму, яка використовує рекурсивно-визначений предикат G(M,N), для визначення найбільшого спільного дільника декількох пар чисел.

7. РЕКУРСИВНІ СТРУКТУРИ ДАНИХ.

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

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

7.1.Структура даних типу дерева.

Серед структур даних типу дерева можна виділити спеціальний клас найбільш вживаних дерев- бінарні дерева. Можна дати наступне рекурсивне визначення бінарного дерева:

1.Пусте дерево- бінарне дерево.

2.Кожний вузел бінарного дерева має не більше одного лівого бінарного піддерева і не більше одного правого бінарного піддерева.

Таку структуру даних в Пролозі можна визначити за допомогою двох предикатів:

treetype = tree(string,treetype,treetype) та empty

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

domains

treetype= tree(string, treetype,treetype);

empty

Наприклад, дерево зображене на мал.7.1

c a t h y

/ \

/ \

m i c h a e l m e l o d y

/ \ / \

/ \ / \

c h a r l e s h a s e l j i m e l e o n o r

Мал.7.1.

може бути описане:

tree('Cathy',tree('Michael',tree('Charles',empty, empty),

tree('Hazel' ,empty, empty)),

tree('Melody', tree('Jim',empty, empty),

tree('eleanor' ,empty, empty)))

Відмітимо, що це не є прологівсьгою фразою; це