У мові Пролог одним з основних методів управління виконанням програми є рекурсія. Як правило, Пролог-програма є сукупністю рекурсивних або взаємно рекурсивних визначень. Раніше ми уже зустрічалися з рекурсивним визначенням правила "повторити". Зазначимо, що рекурсивним правилом (правилом рекурсії) називають правило, яке містить само себе як компонент. Рекурсивні правила, як і правила повторень, забезпечують повторне виконання задач. Вони досить ефективні при формуванні запитів до бази даних, при обробці таких доменних структур як списки тощо. Рекурсивне правило схематично можна подати так:
<ім’я рекурсивного правила> :-
<список предикатів>,
<предикат умови виходу>,
< список предикатів>,
<ім’я рекурсивного правила>,
<список предикатів>.
У загальному випадку тіло правила містить 5 груп предикатів:
предикати, успіх або невдача будь-якого з них на рекурсію невпливають;
предикат, який визначає умову виходу, успішне виконання його викликає рекурсію, неуспіх цього предиката викликає її зупинку;
список інших предикатів, їх успіх чи неуспіх на рекурсію невпливають;
саме рекурсивне звернення;
список предикатів, успіх чи невдача яких не впливає на рекурсію, в процесі рекурсивного виконання вони "виштовхуються" в стек і викликаються тільки після завершення рекурсії.
Деякі з груп у конкретному випадку можуть бути відсутніми. Проте рекурсивне правило має завжди містити умову виходу, інакше рекурсія нескінченна. Відповідальність за забезпечення завершуваності рекурсивного правила лежить на програмістові.
Розглянемо приклади використання рекурсії.
Нехай потрібно обчислити факторіал цілого числа n. Для визначення факторіала використаємо рекурсивне співвідношення
Введемо предикат fact(X, Y), де Y-факторіал числа X. Перше твердження мовою Пролог запишеться у вигляді факту: fakt ( l , l ) . Для запису другого твердження треба: 1) від n відняти одиницю, одержуючи Z; 2) обчислити факторіал числа Z, одержуючи X1; 3) помножити X1 на n, одержуючи Y.
Таким чином, можна записати таку програму:
/* Програма: Факторіал*/
Domains
chislo, factorial = integer
predicates
fact(chislo, factorial)
clauses
fact(1, 1).
fact(x, Y) : X > 1,
Z = X- 1,
fact(Z, X1),Y = X1*X.
Для цього прикладу перший компонент структури загального правила рекурсії не використовується. Другим компонентом (предикатом умови виходу) є X > 1. Якщо значення X більше за 1, то під ціль X >1 буде успішною і рекурсивно викликатиметься fact. Якщо внутрішні програми уніфікації виявлять, що значення X дорівнює 1, то опрацювання припиняється і виконання програми завершується.
Якщо, наприклад, задати запит fact(5, X), то буде видано X = 120; для fact(10, X)отримаємо X = 24320.
Для цілі fact(5, X) Пролог-система розв’язок шукатиме так.
Спочатку система спробує спів ставити ціль із фактом
fact(1, 1).Співставлення не успішне (1≠5).
Потім система спробує уніфікувати ціль fact (5, X) з головою правила fac t (X,Y) . На цей раз уніфікація завершується успішно з присвоюванням змінній X значення 5. Тоді система спробує довести предикати в правій частині правила. Спочатку перевіриться умова виходу. Оскільки 5 > 1, то підціль успішна і тому Пролог-система переходить до наступної підцілі. Змінній Z присвоюється значення 4, тобто X1. Тоді правило викликає саме себе у вигляді fact(4, X1). Наступною під ціллю є предикат Y = X1*X, який містить вільну змінну X1. Проте оскільки був викликаний рекурсивний процес, то підціль Y = X1*X не викликається. Тепер система спробує уніфікувати предикати fact(1, 1) і fact(4, X1). Предикати не уніфікуються, бо 4≠1. У результаті система переходить до правила, голова якого fact(X, Y). Предикати уніфікуються і змінній X присвоюється значення 4.Цей циклічний процес уніфікування продовжується доти, поки не буде одержано fact(1, X1). Цей предикат уніфікується з fact(1, 1), а X1 присвоюється значення 1. Оскільки для предиката fact існує альтернативне твердження (у вигляді правила), то тут буде поставлено вказівник повернення, який вказуватиме на альтернативний шлях пошуку розв’язку. Тепер система переходить до обчислення предиката Y = X1*X. Предикат успішно обчислюється і буде отримано Y = l*2. Зазначимо, що в процесі уніфікації змінна X1 була вільною, а система запам’ятовувала значення X для наступного використання; зокрема тут було використано X = 2.Предикат Y = X1*X продовжуватиме обчислювати значення змінної Y, присвоюючи їй послідовно значення 2, 6, 24 і 120.Кінцеве значення Y є 120, воно і є розв’язком задачі. Якщо ціль, яка ставиться до програми, зовнішня, то система спробує відшукати інші можливі розв’язки. Тому внутрішні підпрограми уніфікації здійснять повернення до відповідного вказівника (в даному випадку доправила fact(Y, X)) і система намагатиметься довести підціль fact(1, X1)альтернативним способом. Підціль уніфікується з головою правила, але предикат X >1 (умова виходу з циклу) виявляється неуспішним. Отже, інших розв’язків, крім знайденого раніше X = 120, немає. Якщо ж не вказувати умову виходу з циклу (X > 1), то система продовжувала б зменшувати X на одиницю і намагалася б уніфікувати цей предикат з першим фактом fact(1, 1).Теоретично процес мав би продовжуватися нескінченно. Насправді ж через деякий час буде видано повідомлення про переповнення стеку і запропоновано натиснути клавішу "Пробіл". Для того, щоб прослідкувати за процесом виконання програми, доцільно виконати її по кроках із виведенням траси. Наведемо трасу програми Факторіал, якщо ціль зовнішня і має вигляд Goal, fact (3, X). Повідомлення системи подані в одному рядку з відповідним предикатом програми. Для скорочення записів замість назви предиката fact використовується позначення
Як уже зазначалося, цілі, які треба довести, Пролог-система спочатку заносить у певний стек, звідки вони вибираються для доведення. Проілюструємо доведення цілі fact(3, X) із точки зору використання стека. Отже, на початку в стек заноситься ціль fact (3 , X) . Ціль уніфікуватиметься з головою правила fact(X, Y), але спочатку в правилі буде перейменовано змінні:
fact(X2, Y) :Х2 > 1, Z = X2-1, fact(Z, X1), Y = X1*X2.
У результаті уніфікації буде зроблено підстановку
0= {Х2:=3, Y:=X}.
Після уніфікації вміст стека буде таким:
3>1 , 2 = 2, fact(2, X1 ) , Х = Х1*3
Далі система намагатиметься доводити по черзі зліва направо підцілі, які записані в стеку. Перша і друга підцілі успішно доводять ся і вилучаються зі стека. Наступною для доведення вибирається підціль fact(2, X1). Підціль уніфікуватиметься з головою правила fact (X,Y) , в якому спочатку будуть перейменовані змінні, тобто правило набуде вигляду
fact(X3, Y3) :ХЗ > 1, Z = X3-1, fact(Z, X4), Y3 = X4*X3.
Після уніфікації стек матиме вміст:
2> 1, 1 = 1, fact(l, X4 ) , Y3 = X4*2, X = Y3*3;
Підстановка- 0= {ХЗ := 2, X1 := Y3}.Підцілі 2 > 1, 1 = 1 успішні. Наступною є підціль fact(l, X4). Внутрішні програми уніфікації знаходять факт fact(1, 1), який уніфікується з підціллю, підстановка- 0= {Х4 := 1}. Після цього підціль fact(l, X4) також вилучається зі стека. Оскільки для предиката fact є ще альтернативне твердження, то буде поставлено відповідний вказівник для відшукання альтернативних шляхів розв’язку. На цьому етапі доведення стек містить дві підцілі
Y3 = l*2, X = Y3*3,
які успішно обчислюються і вилучаються з стека. Таким чином, знайдено розв’язок Х = 6, його і буде виведено. Нарешті, буде зроблено спробу відшукати інші можливі розв’язки. Механізм повернення назад здійснить повернення до вказівника (він стоїть біля правила fact(X, Y) ) . Вміст стека відновлюється, він знову набуває вигляду
fact (l, X4 ) , Y3 = X4*2, X = Y3*3.
Предикат fact(1, Х4) уніфікується з правилом
fact (X5, Y5) :X5 > l, Z = X5-l, fact(Z, X6 ) , Y5 = X6*X5
(підстановка= {X5 : =1, Y5 := X4}),
а, отже, стек міститиме такі підцілі:
1 > 1, 0 = 0, fact(0, Х6 ) , X4 = X6*1, Y3 = X4*2, X = Y3*3.
Але оскільки уже перша підціль (предикат умови виходу) виявляється неуспішною, то доведення терпить невдачу. Отже, знайдено тільки один розв’язок. На цьому виконання програми завершується. Зазначимо, що в розглянутому прикладі програми організувати рекурсію можна було б взагалі без виконання предиката умови виходу (предиката Х > 1),якщо скористатися предикатом відсікання. В останньому випадку твердження програми досить записати так:
fact (1, 1) :-!.
fact (X, Y) :Z = X-1,
fact(Z, X1), Y = X1*X.
Предикат відсікання можна використати й у другому правилі:
fact (X, Y) :Z = X-1,
fact(Z, X1), !, Y = X1*X.
Приклад 1.
Визначити найбільший спільний дільник(НСД) двох невід’ємних цілих чисел.
Найбільший спільний дільник чисел а і b можна обчислити за алгоритмом Евкліда:
Відповідна програма мовою Пролог матиме вигляд:
/* Програма:НСД*/
Domains
a, b, d = integer
predicates
find_nds
nds (a, b, d)
goal
find_nds.
Clauses
find_nds : -
write("Введіть два числа;"), nl,
write("a="), readint(A),
write("b="),
readint(B),
nds (A, B, D),
write("HCД (" , A, ",", B, ")=", D) .nds(A, B, D):A = B, D=A, !.
nds(A, B, D):A > B, X = A-B, nds(X, B, D), !.
nds(A, B, D):X = B-A, nds(A, X, D).
У програмі використовується внутрішня ціль. Програма пропонує ввести два числа. Після введення чисел буде знайдено найбільший спільний дільник
введених чисел і видано результат. Приклад діалогу з програмою НСД подано на рис. 1.
Рис. 1. Діалог з програмою НСД
Приклад 2.
Розглянемо приклад програми обчислення суми 2+4+6+...+n, де n парне, причому n>2. Програма "Сума парних" розв’язує сформульовану задачу. У програмі використано внутрішню ціль, передбачається введення верхньої межі n з клавіатури на відповідне запрошення.
/* Програма:Сума парних*/
Domains
n, suma = integer
predicates
sum (n, suma)
goal
write("Введіть верхню межу (парне N>=2) "),
readint(N), sum(N, S),
write ("Сума ряду від 2 до ", N, " крок 2:"), nl,
write(" S( " , N, " )=" , S) .
clauses
sum(2, 2).sum(N, S) :N > 2, N1 = N-2,
sum(Nl, S1), S = S1+N.
Як і в попередній програмі, рекурсивне правило можна було б записати
без предиката умови виходу з циклу, а з допомогою предиката відсікання. Приклад діалогу з програмою подано на рис. 2.
Рис. 2. Діалог з програмою "Сума парних"
Приклад 3.
Розглянемо таку задачу. Функція f(n) на множині натуральних чисел визначається таким чином:
f(1)=1,f(3)=3,f(2n)=fn),f(4n+1)=2f(2n+1)-f(n),f(4n+3)=3f(2n+1)-2f(n).
Для заданого значення n обчислити f(n).Функція задається рекурентними формулами. Користуючись за даними формулами, можна послідовно обчислювати:
f(1)=1; f(2)=f(2*1)=f(1)=1; f(3)=3; f(4)=f(2*2)=f(2)=1; f(5)=f(4*1+1)=2f(2*1+1)- f(1)=2f (3)-f(1)=2*3-1=5; f(6)=f(2*3)=f(3)=3; f(7)=f(4*1+3)=3f(2*1+1)-2f(1)=7 і т . д .
Зазначимо, що для обчислення значень функції можна записати алгоритм, який базується на тому, що двійковий запис числа f(n) є записом у зворотному порядку двійкового запису числаn. Доведення цього факту можна провести методом індукції. Проте тут цим фактом користуватися не будемо, а складемо Пролог-програму, яка базується лише на заданих рекурентних співвідношеннях. Шукану програму можна записати у вигляді:
/* Програма: */
Domains
x, y = integer
/* харгумент, узначення функції */
Predicates
f(x, у)
clauses
f(1, 1):-!.
f(3, 3):-!.
f (x, y):-
X mod 2 = 0, X2 = X div 2, f (X2, Y), !.f (X,Y):X mod 4=1, X1= (X-1) div 2, X3 = X1 div 2, X2=X1+1, f (X2,Y1),f(X3,Y2), Y=2*Y1-Y2, !.
f(X Y):-
X mod 4=3, X1= (X-3) div 2, X3=X1 div 2, X2=X1+1, f (X2,Y1),f(X3,Y2), Y=3*Y1-2*Y2.
Приклад діалогу з програмою подано на рис. 3.
Рис. 3. Діалог з програмою "Рекурсивна функція".
Приклад 4.
Обчислити значення функції
Ця функція називається функцією Аккермана. Вона особлива тим, що не тільки значення функції, а й аргументи визначаються рекурсивно.
/* Програма:Функція Аккермана*/
Predicates
a(integer, integer, integer)
clauses
a (N, M, Y) :-M = 0, Y = N+1, !.
a (N, M, Y) :-N = 0, M>0, M1 = M-1,
A (1, M1, Y), !.A (N, M, Y) :-N1= N-1, M1= M-1,
a (N1,M,Y1), a (Y1,M1,Y).
Приклад діалогу з програмою подано на рис. 4.
Рис. 4. Діалог з програмою "Функція Аккермана"
Приклад 5.
Розглянемо ще один приклад (програма "Родина"), в якому використовується рекурсивне визначення правила, але який не пов’язаний, як попередній, з арифметичними операціями. База знань програми описує певну спорідненість. Тут використовуються такі предикати :
father (X,Y)-X є батьком Y;
mother (X, )-X є матір’ю Y;
grandfather (X,Y)-X є дідусем Y;
grandmother (X,Y)-X є бабусею Y;
woman (X)-X є жінкою (жіночої статі);
man (X)-X є чоловіком (чоловічої статі);
parents (X,Y)-X є одним з батьків Y;
ancestor (X,Y)-X є предком Y.
Деякі з предикатів визначаються за допомогою правил.
Правило parents (X,Y) :-
father (X,Y), man (X);
mother (X,Y), woman (X)
виражає твердження
"Для всіх X і Y
X є одним з батьків Y,
якщо X є батьком Y і X є чоловіком
X є матір’ю Y і X є жінкою ".
Зазначимо, що крапка з комою між двома умовами в правилі вказує на диз’юнкцію (АБО).
Звичайно, можна було б обійтися без використання диз’юнкції записавши замість одного два правила.
Правило
grandfather (X,Y) :-father (X,Z),
parents (Z,Y)виражає твердження
"Для всіх X і Y
X є дідусем Y, якщо
X є батьком Z і
Z є одним із батьків Y".
Правило
ancestor (X,Y) :-parents (X,Y)
виражає твердження
"Для всіх X і Y
X є предком Y, якщо
X є одним із батьків Y"
.Предикат "ancestor" у програмі визначається за допомогою двох правил.Перше з них визначає найближчих предків, друге
ancestor (X, Y) :-parents (X, Z), ancestor (Z, Y) - віддалених.
В останньому правилі використовується рекурсивне визначення.
Комментариев нет:
Отправить комментарий