1. ПРОГРАМИРАНЕ НА ПОВТАРЯЩИ СЕ ОПЕРАЦИИ
Съществуват два начина за реализиране на правила, които да изпълняват
една и съща задача многократно:
1. Повторение.
2. Рекурсия.
В първия случай се използва възврат(откат)(backtracking)
Във втория – самоизвикване на правилото
# Общият вид на правилото,изпълняващо повторение е:
repetitive_rule:- /* правило за повторение /
< предикати и правила>
fail. /*неуспех/
Конструкцията <предикати иправила> в тялото на правилото означава предикати, които съдържат няколко твърдения, а така също и правилата , определени в програмата .
Вградения пред fail( неуспех ) предизвиква възврат, така че предикатите и правилото се изпълняват веднага .
#Общия вид на правилото, изпълняващо рекурсия е:
recursive_rule:- /*рекурсивно правило */
<предикати и правила >
recursive_rule .
Забележете ,че последното правило в тялото на даденото правило е самото правило recursive_rule .
Рекурсивните правила съдържат в тялото самите себе си .
И двете правила осигуряват еднакъв резултат, макар и алгоритмите за тяхното изпълнение да са различни. Всяко едно от тях в конкретния случай има своите предимства .
РЕКУРСИЯТА , например, може да изиска повече системни ресурси -памет, т.к. при всяко рекурсивно извикване се съхранява новото копие на използваните значения в стек.
Стекът е област от паметта,която основно се използва за предаване на значения(стойности) между правилата.
Тези стойности се съхраняват докато правилото не завърши -или успешно , или неуспешно .
Използването на стек може да бъде оправдано,ако съхраняваните междинни стойности се използват по-нататък , например при обработване на списъци .
ПОВТОРЕНИЕТО не предизвиква допълнително увеличаване на стковата област.
2. ПОВТОРЕНИЕ И ВЪЗВРАТ
Обикновено целта на програмата в PROLOG съдържа една или няколко подцели,които могат да бъдат или факти или правила.
Фактът се изпълнява веднага – резултатът е : или успех,или неуспех в зависимост от това дали фактът от базата е съпоставим с факта от програмата.
Правилото не се изчислява веднага, тъй като то е логическа връзка от подправила. Ако дадено правило в даден момент не може да бъде успешно изчислено, то PROLOG изпълнява възврат с цел търсене на други възможни пътища за изчисления , т.е. алтернативни решения.
Пример за анализ на понятието възврат :
Нека е дадена базата от данни на следните факти :
plays(todor,football).
plays(ivan,soccer).
plays(ivan,volleyball).
plays(todor,basketball).
plays(todor,volleyball).
plays(ivan,baseball).
Целта е да се определи в кой спорт играят едновременно Иван и Тодор.
Твърдението ще има вид:
plays(ivan,G),plays(todor,G).
Целта е съставена от две подцели.
На фигурата е изобразен процесът на възврат.
База факти Цел
plays(ivan,G),plays(todor,G).
plays(todor,soccer).
plays(todor,football).
Неуспех и изпълнение
1 plays(ivan,soccer). G = soccer на възврат
2 plays(ivan,volleyball). G = volleyball
plays(todor,basketball). plays(todor,volleyball).
3 plays(todor,volleyball).
plays(ivan,baseball). Успешно завършване
Изпълнявайки първата подцел след последователното преглеждане на базата от факти променливата G се свързва с константата soccer. След успеха на първата подцел се преминава към удовлетворяване на втората , в която променливата G поради механизма на унификация има същата стойност(G=soccer). Започва процес на удовлетворяване от началото на базата, който завършва с неуспех.
Цялата цел пропада, което води до:
1.Освобождаване на променливата G от стойност.
2.Иницииране на възврат.
Започва процес на преудовлетворяване на първата цел от мястото на указателя за възврат, отбелязан с цифрата 1.
Следващото удовлетворение на първта подцел е твърдението plays(ivan,volleyball).То се отбелязва с указател за възврат(цифрата 2) и PROLOG преминава към удовлетворяване на втората подцел plays(todor,volleyball). По време на търсенето в базата от факти тази цел се удовлетворява (факт 3)и целта като цяло е успешна. Получаваме едно единствено решение
G=volleyball
Механизмът backtracking се инициира автоматически от системата,ако не се използва специални средства за неговото управление.
4. МЕТОДИ ЗА ПОВТОРЕНИЯ.
За управление на процеса на възврат се използват два вградени предиката:
fail (неуспех)
cut (отсичане)
Тези предикати се използват в метода за възврат след неуспех(BCH)
и метода за възврат и отсичане (ВО).
4.1 Методи за възврат след неуспех (ВСН)
Тук ще разгледаме как методът ВСН може да се използва за управление на изчислението на вътрешна цел при търсенето на всички възможни нейни решения .Този метод използва предикатът fail.
Цели: вътрешни
външни
Вътрешни – зададени в самата програма
Външни – задават се в интерактивен режим.
Дадената по-долу програма илюстрира използването на този предикат
Предназначението на програмата е да изброи 10 града от България.
cties(‘Sofia’).
cties(‘V.Tarnovo’).
cties(‘Gabrovo’).
cties(‘Plovdiv’).
cties(‘Varna’).
cties(‘Bansko’).
cties(‘Melnik’).
cties(‘Dipnica’).
cties(‘Montana’).
show_cities:-
write(‘Here are the cities:’), nl,
cities(City),
write(City),nl,
fail.
Целта се задава от монитора:
?show_cities.
Схема на работата на програмата
Цел: cities(City),write(City),nl,fail.
1 cties(‘Sofia’). City = Sofia write(‘Sofia’),nl.
Възврат към
2 cties(‘V.Tarnovo’). маркер 2
City = V.Tarnovo
cties(‘Gabrovo’).
Повтаря се за
cties(‘Plovdiv’). всяко твърдение
.
.
.
Предикатът fail предизвиква неуспешно завършване на правилото, вътрешните унификационни програми изпълняват възврат към точката 1 и процесът се повтаря дотогава, докато не се отработи и последното твърдение от базата данни с факти.
Варианти на ВСН
Разгледаният пример дава изчерпателно решение. В програмата има 10 твърдения и ние получаваме 10 решения.
Добавяйки някои допълнителни ограничения на стойностите на обектите (аргументите) за една или повече променливи на предиката могат да се извличат данни само от отделни твърдения. Програмата за служащите, дадена по-долу илюстрира това.
Твърденията в програмата за служащите съдържат данни както следва:
employee(име, пол, отдел, почасова_ставка).
% База от факти%
employee(‘ИванВасилев’,’М’,’Фин”,350).
employee(‘Тодор Стефанов’,’М’,’Произв’,450).
employee(‘Боряна Лазарова’,’Ж’,’Инф”,500).
employee(‘Живко Христов’,’М’,’Рекл’,450).
employee(‘Симеон Рачев’,’М’.’Инф’,600).
employee(‘Сийка Борисова’,’Ж’,’Рекл’,500).
employee(‘Киро Стоянов’,’М’,’Фин’,500).
employee(‘Диана Петрова’,’Ж’,”Инф”,500).
%Правило за генериране на списък на служителите от мъжки пол%
show_male_part:-
employee(Name,’M’,Dept,Pay_rate),
write(Name),write(‘ ‘),
write(Dept),write(‘ ‘),
write(Pay_rate),write(‘ лв‘),
nl,
fail.
%Правило за генериране на списък на служителите%
% от информационния отдел%
show_data_part:-
employee(Name,_,’Инф’,Pay_rate),
write(Name),write(‘ ‘),
write(Pay_rate),write(‘ лв‘),
nl,
fail.
Ако бихме искали да получим всичките данни, то правилото ще бъде:
show_all:-
employee(Name,Sex,Dept,Pay_rate),
write(Name),write(‘ ‘),
write(Sex),write(‘ ‘),
write(Dept),write(‘ ‘),
write(Pay_rate),write(‘ лв‘),
nl,
fail.
Вариант на правилото show_male_part :
show_male_part:-
employee(Name,Sex,Dept,Pay_rate),
Sex = ‘M’,
write(Name),write(‘ ‘),
write(Dept),write(‘ ‘),
write(Pay_rate),write(‘ лв‘),
nl,
fail.
Meтодът ВСН e удобен за програмиране на приложни задачи по обработката на служебни данни. Типичен пример е създаване на платежна ведомост, извличане на кадрови справки и др.
Упражнения:
1. Програма Заплата.
2. Програма Кадрови справки.
3. Програма за отчет на продажбите в магазин за обувки (размер, цена, модел и др.)
4.2. МЕТОД НА ВЪЗВРАТА И ОТСИЧАНЕТО (ВО)
В някои случаи е необходимо да се осигури достъп към определена част от данните. Например, при обработване на запасните части и материали в склад, които постъпват в различни обеми и различни номенклатури.
Този метод може да се използва за филтрация на данните, извличани от базата данни.
Удобството на този метод става още по явно при голям брой на условията за избор.
Например, методът ВО дава възможност да се изберат всички заявки, фиксирани от 18 до21 ноември, имащи знак “В” в номера на накладната и получени преди Гюро Михайлов да застъпи дежурен. Задавайки инициалите на служителя Г.М. като условие за завършване на прегледа на БД може да се получи необходимата информация.
Тук се използва предоката CUT ( ! ) за управление на търсенето. Този предикат винаги се удовлетворява (изчислява се успешно) и кара вътрешните унификационни програми “да забравят” всичките указатели за възврат, които са били установени по време на опитите за удовлетворяване на текущата подцел.
С други думи CUT “слага бариера”, която забранява да се изпълнява възврат към всичките алтернативни решения на текущата подцел. Той установява бариера, която забранява да се изпълни възврат към всички алтернативни решения на текущата подцел. Всички последващи подцели, обаче, могат да си създават нови указатели за възврат и по този начин да създават условия за търсене на нови решения. Областта на действието на дадения предикат CUT върху тях не се разпространява.
Но ако всичките по-късни цели се окажат неуспешни, то бариерата, която е била установена от предиката CUT, ще застави механизма за възврат да отсече всички решения извън действието на CUT чрез незабавния възврат към други възможни решения извън областта на действието на CUT.
Методът ВО използва предиката FAIL за това, че да се имитира неуспешно изчисление и да се изпълни следващия възврат до тогава, докато не бъде намерено определено условие.
Предикатът CUT служи за отстаняване на всички последващи възврати.
Разглежданият метод може да се поясни с помощта нма простата ситуация, представене в следващата програма. Тази програма формира списък от деца. Нека да предположим, че е необходимо да се направи списък от имената на децата до Диана, включително.
% База от факти %
child(‘Тодор’).
child(‘Бистра’).
child(‘Жоро’).
child(‘Стефан’).
child(‘Лазар’).
child(‘Петър’).
child(‘Диана’).
child(‘Йордан’).
child(‘Симо’).
% Главна цел%
goal:-
write(‘Момчета и момичета’,
nl,nl,
show_some_of_them.
show_some_of_them:-
child(Name),
write(‘ ‘),write(Name),nl,
make_cut(Name),!.
make_cut(Name):-
Name=’Диана’.
Предикатът CUT се използва за да се реализира отсичане в посоченото място. Предикатът FAIL (в примера това е предикатът make_cut (Nаmе) )служи за продължаване на възврата и достъп към последователността от имена в базата од факти до елемента с име Диана.
По такъв начин поставената задача се изпълнява от съответната комбинация на предикатите CUT и FAIL. Тази комбинация се нарича метод на възврата и отсичането.
В програмата за имената предикатът от базата данни е child(person). За този предикат има 9 алтернативни твърдения.
Правилото, което осигурява генерацията на всички мена (а не само някои от тях) има вид:
show_them_all:-
child(Name),
write(Name),nl,
fail.
Това правило се основава на метода връщане след неуспех ВСН. При това, за да се използва предикатът CUT, е необходимо да се определи някакво условие, което може да бъде и просто, както е в нашия пример, но може да бъде и много сложно. В дадения скучай е достатъчно условието Name = ‘Диана’. Правилото, което определя това условие има вид
make_cut(Name):- Name=’Диана’.
Това правило със последващия предикат CUT (!) образува правилото make_cut (извърши отсичане). Сега изпълнението на програмата ще бъде неуспешно, а възвратите ще се повтарят дотогава, докато Name на стане равно на Диана. И в този момент резултатът от изпълнението на правилото make_cut ще бъде успешно, което от своя страна ще извика изпълнението на предиката CUT. По такъв начин, комбинирайки правилото за отсичане с метода за ВЦН може да се получи ОВ-правило.
show_some_of_them:-
child(Name),
write(‘ ‘),write(Name),nl,
make_cut(Name),!.
make_cut(Name):-
Name=’Диана’.
Програмата, която формира списък на децата, включва ОВ-правило. Работата на програмата е показана на фиг.
Цел: child(Name),write(‘ ‘),write(Name),nl, make_cut(Name),!.
child(‘Тодор’). Name = ‘Тодор’ write(‘Тодор’)
child(‘Бистра’). Name = ‘Бистра’
make_cut(‘Тодор’)
child(‘Жоро’).
Повторение за
child(‘Стефан’). останалите твърдения Name = ‘Диана’
child(‘Лазар’). . . . . неуспех и възврат
child(‘Петър’).
child(‘Диана’). Name = ‘Диана’
child(‘Йордан’).
make_cut(‘Диана’).
child(‘Симо’). Правилото е успешно.
Отсичането ( ! ) във
веригата предизвиква
по-нататъшни възврати.
К Р А Й
Работата на програмата може да се измени, ако се промени условието за отсичане. Така например, Name = ‘Бистра’ ще даде списък до името Бистра, включително. Тоз начин на използване на ОВ-правилото се нарича метод на ранжирането на отсичането.
Методът ОВ може да се използва и по друг начин, например за обработка на определени избираеми елементи. Програмата, кочто е изобразена по-долу демонстрира използванвето на ОВ-метода за създаване на списък на избраните от базата елементи.
% База от факти %
child(‘Тодор’).
child(‘Алиса’).
child(‘Диана’).
child(‘Алиса’).
child(‘Бистра’).
child(‘Любо’).
child(‘Алиса’).
% Главна цел%
goal:-
go_and_get_them.
go_and_get_them:-
write(‘Списък на имената’), nl,nl,
child(Name),
Name = ‘Алиса’,
write(Name),nl,
fail.
Както и в програмата, която формира списък на имената на децата, в тази програма child(name) се явява предикат от базата от данни, съдържащ информация, която е необходима за генерация на списъка от имена. Има 7 алтернативни твърдения. Три от тях съдържат името Алиса. Правилото, което избира и отпечатва името Алиса име следния вид:
get_alisa:-
child(Name),
Name =’Алиса’,
write(Name),nl,
fail.
В базата от данни името Aлиса се среща три пъти, поради което в резултат от работата на програмата ще се получи списък от три еднакви имена.
Правилото get_alisa намира всичките три възможни означавания на променливата Name, което и се явява резултат от правилото ОСН. Обаче, при желание може да се изведе само първият срещнат екземпляр на значението на променливата Name. Това се постига чрез въвеждане в правилото на правило за избиране на отсичането:
get_first_alisa:-
child(Name),
Name =’Алиса’,
write(Name),nl,
!,
fail.
В резултат ще бъде получен списък, който се състои от единственото име Алиса.
Внимателният анализ на това правило показва, че предикатът FAIL се използва само веднъж. В комента, когато той получи управление, предикатът
CUT вече е отстранил каквато и да е възможност за възврат, в резултат на което предикатът FAIL се оказва безполезен. Ще отбележим, че методите ВЪЗВРАТ и ОТСИЧАНЕ тук са представени в най-общата форма, модификацията на които, в която и да е конкретна ситуация не е трудно. По такъв начин диапазонът на използване на възврата и отсичането е достатъчно широк.
4.3. Метод на повторението (МП), определян от потребителя
МП както и ВЪЗВРАТ-ОТСИЧАНЕ (ВО), използва възврат. Но в МП-метода изпълнението на възврата винаги е възможно, в отличие от ВО-метода, където възврата се изпълнява само след изкуствено създаден неуспешен резултат.Правилото на рекурсията от общ вид има по-сложна структура и се явява обобщение на тези методи.
Видът на правилото за повторение, определяно от потребителя, е следния:
repeat. %Повтори%
repeat:-repeat.
Първият repeat се явява твърдение, което обявява предиката repeat като истинен. Той не създава подцели, затова даденото правило винаги е успешно. Тъй като, обаче има още един вариант за това правило, то указателят за възврат се установява на ПЪРВИЯ repeat. Вторият repeat – това е правило, което използва само себе си като компонента (третият repeat). Вторият repeat извиква третия и това извикване се изчислява успешно, тъй като първият repeat удовлетворява подцелта repeat. Следователно, правилото repeat винаги е успешно. Предикатът repeat ще се изчислява успешно шпри всеки нов опит той да бъде извикан след възврат. Фактът в правилото ще се използва за изпълнение на всичките подцели на програмата. По такъв начин repeat се явява рекурсивно правило, което никога не бива неуспешно.
Правилото repeat широко се използва като компонент на други правила. Примвр за това може да служи програмата ЕХО, която възприема ред, въведен от клавиатурата и го дублира на екрана. Ако потребителят въведе stop , то програмата приключва своята работа.
Заб: Тази програма е тествана!
goal:-
write_message,
do_echo.
repeat.
repeat:-repeat.
write_message:-
nl, write(‘Въведете, ако обичате, имена’),nl,
write(‘Аз ще ги повтарям’),nl,nl,
write(‘За да ме спрете, въведете stop точка накрая’),nl,nl.
do_echo:-
repeat,
read(Name),
write(Name),nl,
check(Name),!.
check(stop):-
nl,write(‘OK, довиждане!’).
check(_):- fail.
Правилото repeat се явява първо в раздела за твърденията в програмата ЕХО. Второто правило извежда информация за потребителя. Третото правило do_echo е правило за повторение, което повторение се определя от потребителя. Неговата първа компонента е repeat.
do_echo:-
repeat,
read(Name),
write(Name),nl,
check(Name),!.
Твърдението repeat извиква изпълнението на всички идващи след него компоненти. Предикатът read(Name) възприема въведеният от клавиатурата ред, а write(Name) го извежда на екран (моделира се ехо).
Последното подправило check(Name) има две вузможни значения. Едното се определя от подправилото:
check(stop):-
nl,write(‘OK, довиждане!’).
Ако въвежданият от потребителя ред има стойност stop, то правилото ще бъде успешно. При това кърсорът се премества в началото на следващия ред и на екрана се появява съобщението “OK, довиждане!” и процесът на повтаряне приключва. Обърнете внимание на символа за отсичане ( ! ). Той служи за прекратяване на възврата, ако условието check е изпълнено.
Второто значение на check(Name) се определя от подправилото:
check(_):- fail.
Ako значението на реда е различно от stop, то резултатът от изпълнението на правилото ще бъде fail. В този случай ще се извърши възврат към правилото repeat. По такъв начин, do_еchо се явява крайно правило във веригата от повторения, условието за изход от която се определя от предиката check. Благодарение на това, че правилото repeat е компонентно, правилото do_echo става крайно правило за повторение.
В програмата ЕХО правилото за повторение се явява първа компонента на правилото do_echo. Това е твърде гъвкаво средство за програмиране. По долу се дават сведения и за други начини за неговото използване. Правилото за повторение, явявайки се една от компонентите на някакво правило, осигурява циклическо изпълнение на функциите на дадено правило.
По подобен начин в МП правилото може да се използва и повече от едно правило за повторение. По-долу е дадено МП-правило което включва две повторения:
do_twо_things:-
repeat1,
<повтарящо се тяло>,
<условие за изход>,!.
repeat2,
<повтарящо се тяло>,
<условие за изход>,!.
repeat1. % Заб.: Това е тествано%
repeat1:-repeat1.
repeat2.
repeat2:-repeat2.
<правило за условие за изход 1>.
<правило за условие за изход 2>.
По време на определянето на правилата за повторение може вместо името repeat да се използват и някакви други. По-долу се дават някои алтернативи на думата repeat.
loop.
loop:-loop.
loop1.
loop1:-loop1.
iterate.
iterate:-iterate.
recurse.
recurse:-recurse.
Методът МП е твърде ефективен при :
- реализацията на достъп към данни в базата от данни и файлове на диска:
при въвеждане на информация от клавиатурата,
организация на извеждането на екрана;
при формиране на меню.
5. МЕТОДИ ЗА ОРГАНИЗАЦИЯ НА РЕКУРСИЯ
Правилата, които не използват правилата за повторение катъо компоненти са най-общите начини за организация на рекурсивната обработка на данните при програмиране на Пролог. Този метод подхожда за редица приложения, започвайкио с обработката на файлове и завършвайки с математически изчисления.
5.1. ПРОСТА РЕКУРСИЯ
Правило, което съдържа самото себе си като компонента се нарича рекурсивно правило. Рекурсивните правила, както и правилата за повторение, реализират повторно изпълнение на задачата. Те са твърде ефективни, например при обработката за запитвания към базата от данни, а така също и при обтработката на такива структури като списъци.
Пример за рекурсивно правило:
write_string:-
write(‘Ние сме шампиони’),
nl,
write_string.
Tова правило се състои от три компоненти: първите две извеждат стринга ‘Ние сме шампиони’ и премества маркера на нов ред на екрана. Третата е самото правило. Тъй като то съдържа самото себе си, то за да бъде успешно, правилото write_stringтрябва да удовлетворява самото себе си. Това жоди отново към извикване на операцията за извеждане на екрана на стринга и преместване на маркера на нов ред. Процесът продължава безкрайно (безкрайна рекурсия)
В случай на възникване, обаче на безкрайна рекурсия броят на елементите на данните, използван от трекурсивния процес непрекъснато расте и в определен момент от времето стекът ще се препълни. На екрана ще се появи съобщение за грешка. Възникването на такава ситуация в процеса на изпълнението на програмата е нежелателно, тъй като могат да се загубят някои данни.
Избягването на безкрайната рекурсия е възможно. За тази цел следва да се въведе предикат за завършване, който съдържа условие за изход от рекурсията или още гранично условие. Условието за изход от дадената по-горе рекурсия на български език може да изглежда шпримерно така:”Да се извежда дадения стринг дотогава, докато броят на извежданията не стане равен на 7. След това процесът да се прекрати”. Определянето на условието за изход е много важен елемент в програмирането на Пролог.
Програмата “Върни се” демонстрира простото правило за рекурсия, в което е включено и условието за изход.
% Програма : “Върни се” %
% Предназначение: Демонстрира правилото за рекурсия за въвеждане и %
% извеждане на символи от клавиатурата %
goal:-
write_prompt,
read_a_character.
write_prompt:-
write(‘Въведете, ако обичате символи’), nl,nl,
write(‘За да приключите въведете #’),nl,nl.
read_a_character:-
get(Char_data),
Char_data =/= ’#’,
put(Char_data),
read_a_character.
Първата компонента на правилото е вграденият предикат get, който осигурява възприемане на символа. Значението на този символ се присвоява на променливата Char_data. Следващото подправило проверява дали въведеният символ е символът #. Ако не е, то правилото е успешно, символът се извежда на екрана и рекурсивно се извиква read_a_character.
Този процес продължава дотогава, докато вътрешната проверка не открие недопустимия символ #. В този момент обработката се прекратява и програмата завършва своята работа.
5.2. МЕТОД НА ОБОБЩЕНОТО ПРАВИЛО НА РЕКУРСИЯТА
Обобщеното правило на рекурсията съдържа в тялото на правилото самото себе си. Рекурсията ще бъде приключена, ако в правилото е включено условие за изход, гарантиращо завършването на работата. Тялото на правилото се състои от твърдения и правила, определящи задачите, които трябва да бъдат изпълнени.
По-долу в символен вид е дадено общото правило на рекурсията:
<име на рекурсивното правило> :-
<списък от предикати>, (1)
<предикат на условието за изход>, (2)
<списък от предикати>, (3)
<име на рекурсивното правило>, (4)
<списък от предикати>. (5)
Макар и структурата на това правило да е по-сложна от структурата на простото правило, което беше разгледано по-горе, принципите които се използват са едни и същи.
Даденото рекурсивно правило има 5 компоненти
първата компонента е група предикати. Успехът или неуспехът на тези предикати не оказва влияние на рекурсията;
следващата компонента е предикатът за условието за изход. Успехът или неуспехът на този предикат или позволява продължаването на рекурсията, или предизвиква нейното прекратяване;
третата компонента е списък от други прердикати Аналогочно успехът или неуспехът на тези предикати не оказва влияния на рекурсията;
четвъртата компонента е самото рекурсивно правило. Успехът на това правило извиква рекурсията;
петата компонента е списък от предикати, чиито успех или неуспех не оказва влияние върху рекурсията. Петата група получава също значения (ако такива има), които се поместват в стека по време на изпълнението на рекурсията.
Да си спомним, че рекурсивното правило трябва да съдържа условие за изход. В противен случай рекурсията е безктайна и правилото е безполезно. Отговорността за осигуряване на изход от рекурсията изцяло лежи върху програмиста. Правилата, които са построени по посочения начин се явяват обобщени рекусривни правила (ОРП), а методът се нарича ОРП-метод.
Например, нека е необходимо да се генерират целите числа от 1 до 7 .
Нека правилото да е
write_number(Number).
За този пример първата компонента от структурата на общото рекурсивно правило не се използва. Втората компонента, т.е. предикатът за условие за изход, ще бъде Number < 8. Когато значението на Number сатне равно на 8, правилото ще бъде успешно и програмата ще приклшчи своята работа.
Третата компонента оперира с числата. В тази част на правилото числото се извежда на екран , след коерто се увеличава с единица. За увеличеното число ще се използва нова променлива Next_Number. Четвъртата компонента е извикване на самото рекурсивно правило write_number(Next_Number). Петата компонента, която беще дадена в общата структура в разглеждания пример не се използва.
Програмата за генериране на числата използва следното рекурсивно правило.
write_number(8).
write_number(Number):-
Number<8,
write(Number),nl,
Next_Number = Number + 1,
write_number(Next_Number).
Програмата започва с опит да се изчисли подцелта write_number(1) (вж. пълния текст на програмата, даден по-долу)
% Програма: генериране на цифров ред %
% Предназначение: Демонстрира използването на рекурсията за % %генериране на числа във възходящ ред %
goal:-
write(‘По-долу са числата’),
nl,nl,
write_number(1),
nl,nl,
write(‘Готово ! Довиждане !’).
write_number(8).
write_number(Number):-
Number<8,
write(Number),nl,
Next_Number = Number + 1,
write_number(Next_Number).
Отначало тя съпоставя тази подцел с първото правило write_number(8). Тъй като 1 не е равно на 8, то съпоставянето е неуспешно. Програмата отново се опитва да съпостави подцелта, но вече с главата на правилото write_number(Number). Този път съпоставянето е успешно, поради това, че на променливата Number e присвоено значение 1. Програмата сравнява тази стойност с 8; Условието за изход е равенството Number = 8. Тъй като 1 е по-малко от 8, то подправилото е успешно. Следващият предикат извежда стойността, която е била присвоена на Number. Променливата Next_Number получава стойност 2, а стойността на Number се увеличава с единица.
В този момент правилото write_number извиква себе си с нова стойност на параметъра, която е равна на 2 и което е присвоено на Next_Number. Ще отбележим, че не е задължително извикването на правилото да става като се използва същото име на променливата, което е било и в главата на правилото. Това е преди всичко позиция в списъка от параметри, която е съществена при предаването на стойностите. Фактически, ако не се предават значенията на Next_Number, то увеличаването на основното числи ще бъде невъзможно. При рекурсивното извикване на главата на правилото, програмата отново се опитва да изпълни подцелта write_number(8).
Програмата продължава да изпълнява цилъл от съпоставяния, присвоявания и извеждания на стойностите на Number дотогава, докато стойността на Number не стане равно на 8. В този момент подцелта е изпълнена, правилото е успешно и програмата завършва работата си след извеждане на съобщението Готово ! Довиждане !
Важно свойство на рекурсивното правило е неговата разширяемост. Например то може да бъде разширено за пресмятане на сумата от редица от естествени числа.
Програмата “Сума на реда 1” е дадена по-долу и използва правилото за рекурсивно изчисляване на сумата на целите числа от 1 до 7:
S(7) = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
или
S(7) = 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28
Птравилото за рекурсия изпълнява изчисленията по обикновената схема за събиране:
1 начална стойност
+2 следваща стойност
3 частична сума
+3
6 частична сума
и т. н.
Рекурсивното правило има вид:
sum_series(1,1).
sum_series(Number,Sum):-
Number > 0,
Next_munber = Number – 1,
sum_series(Next_number, Partial_Sum),
Sum = Number + Partial_Sum.
Даденото правило има четири компонента и едно допълнително нерекурсивно правило. Да отбележим, че последната компонента от рекурсивното правило – това е правилото Sum с Partial_Sum като променлива. Това правило не може да бъде изпълнено до тогава, докато Partial_Sum не получи някаква стойност.
% Програма: Сума на ред1%
% Предназначение: Демонстрация на използването на рекурсивен% %предикат за намиране на сумата S(N) на реда S, където N е % %положително число%
goal:-
sum_series(7,Sum),
write(‘Сумата на реда е:’),nl,nl,
write(‘ S(7) = ’), write(Sum),nl.
sum_series(1,1). % сума на реда %
sum_series(Number,Sum):-
Number > 0,
Next_munber = Number – 1,
sum_series(Next_number, Partial_Sum),
Sum = Number + Partial_Sum.
Програмата ‘Сума на ред1’ започва с опита да се изпълни подцелта sum_series(7,Sum). Отначало програмата се опитва да съпостави подцелта с подправилото sum_series(1,1). Съпоставянето е неуспешно. След това тя се опитва да съпостави подцелта с sum_series(Number,Sum). Сега съпоставянето е успешно и завършва с присвояване на променливата Number стойността 7. След това програмата сравнява Number със стойност 7 с 0, т.е. проверява се условиетоп за изход. Тъй като 7 е по-голямо от 0, то съпоставянето е успешно и програмата преминава към следващото подправило.
В това правило променливата Next_number получава стойност 6, т.е. значение Number – 1. След това правилото извиква само себе си във вид sum_series(6, Partial_Sum). Следващото правило се явява правилото, коео съдържа свободната променлива Partial_Sum. Тъй като, обаче току що беше извикан рекурсивния процес, затова това правило Sum не може да бъде извикано.
Сега програмата се опитва да съпостави непроменящото се правило sum_series(1,1) със sum_series(6, Partial_Sum). Процесът на съпоставяне е неуспешен, тъй като нито един от параметрите на са съпоставими. Като резултат програмата преминава към следващото правило с глава sum_series(Number,Sum), присвоявайки на променливата Number стойност 6.
Този цикличен процес на съпоставяне продължава дотогава, докатоне се получи sum_series(1, Partial_Sum). Сега това правило се съпоставя със sum_series(1,1), а на Partial_Sum се присвоява значение 1. При съпоставяне на правилото с главата на правилото променливата Sum получава стойност 1. Процесът на съпоставяне продължава по-нататък, в резултат на което Next_number получава стойност 0 (1 – 1 = 0). На следващия етап от съпоставянето променливата Number получава стойност 0 и по условието за изход, правилото се оказва неуспешно. По такъв начин процесът на съпоставяне “прескача” към правилото Sum.
По врме на процеса на съпоставяне променливата Partial_Sum е била свободна, а програмата е запомняла стойностите на Number за по-късното им използване. Но правилото Sum продължава да означава променливата Sum, присвоявайки й последователно стойности 1, 3, 6, 10, 15, 21 и 28. Последното значение на тази променлива е 28.
В разгледаната програма “Сума на ред1” може да се използва модифицирано правило на рекурсията с прилагане на предиката за отсичане ( ! ).
sum_series(1,1) :- !. % сума на реда %
sum_series(Number,Sum):-
Next_munber = Number – 1,
sum_series(Next_number, Partial_Sum),
Sum = Number + Partial_Sum.
Резултатите от работата на тези правила са идентични. Използването на отсичането ( ! ) във втория случай не подобрява работата на рекурсивното правило. Двете правила се разглежат като алтернативни варианти.
Програмата “Факториал” (дадена по-долу) използва рекурсивно правило за изчисляване и извеждане на факториала на дадено цяло число N.
N ! = N*(N-1)*(N-2)* . . . *2*1.
Основната структура на рекурсията за изчисляване на факториала е същата, както и в по-горе разгледания пример, с тази разлика, че за намиране на сумата на реда се извършва полследователно натриюупване на сумата, а тук следва да се извършва последователно умножение. Окончателната стойност на факториала се получава след извличането на съответните променливи от стека, използвани като списък от параметри за последното подправило. То(последното подправило) се извиква след завършване на рекурсията.
% Програма: Факториал %
%Предназначение: Демонстрация на използване на рекурсията за %
% изчисляване на фактириала на положителното число N. Рекурсивната %
% процедура използва предиката ! за забрана на възврата %
% Пример: 7 ! = 7*6*5*4*3*2*1 = 5040 %
goal :-
factorial(7,Result),
write(‘ 7 ! = ‘),write(Result),nl.
factorial(1,1):- !.
factorial(Number,Result) :-
Next_number = Number – 1,
factorial(Next_number, Partial_factorial),]
Result = Number*Partial_factorial.
5.4. Организация на цикли в ARITY/PROLOG
Arity/Prolog не разполага с вградени предикати за организацияна цикли. Главният проблем идва от това, че в PROLOG е недопустимо използуването на класическия оператор за присвояване и организиране на брояч в смисъла на традиционните езици за програмиране. Изразът X := X + 1 няма същата семантика поради специфичния механизъм на унификация в Prolog. Въпреки това съществуват възможности за организация на цикли от известните от конвенционалното програмиране типове. По- долу се разглеждат някои примери.
1. Използуване на предикат (брояч) от вида X1 is X + N. Тук X e началната стойност на променливата на цикъла, а N е нарастванетo й на всяка стъпка. Нека да представим предикат за разпечатване на първите 10 естествени числа:
broj_do_deset:-broj_do_deset(0). %начално присвояване на индекса
broj_do_deset(10):-!. % край на цикъла
broj_do_deset(X):-
X1 is X + 1, % модификация
write(X1),nl, % тяло на цикъла
broj_do_deset(X1). % рекурсивно връщане към правилото broj_do_deset(X)
На въпроса:
?-broj_do_deset.
ще получим разпечатка на всеки ред по едно число от 1 до 10.
2. Използуване предикатите за работа с броячите.
Тъй като съдържимото на броячите е достъпно по време на изпълнение на цялата програма, те могат да се използуват за организиране на цикли на базата на repeat-fail обратна връзка.
Пример:
nowo_broene_do_deset:-
ctr_set(0,1), % Инициализация на брояча
repeat,
ctr_inc(0,Y), % Увеличаване съдържимото с 1
write(Y),nl,
Y == 10. % Проверка за край на цикъла
Първата цел инициализира нулевия брояч и записва в него 1. Предикатът ctr_inc увеличава съдържимото на нулевия брояч с 1 и връща старата му стойност, която с предиката write се отпечатва на екрана. Последната клауза (Y == 10) пропада и обратната връзка се повтаря. Това продължава дотогава, докато Y получи стойност 10.
3. Използуване на вградения предикат repeat.
С помощта на този предикат може да се получи преудовлетворяване на произволен предикат или конюнкция. Да разгледаме, например, как може да се реализира предикатът do, който позволява извършване на някакво действие ( в случая – запис на факти и правила в базата от данни) произволен брой пъти (до въвеждането на стринга “stop”):
do:-
repeat, write(‘>’),
read(X),
action(X).
action(’stop’):-!.
action(X):-
assert(X),nl,fail.
В началото на работата на предиката do се извежда символът за готовност > и програмата чака въвеждане от клавиатурата. След въвеждане на желаната клауза от потребителя тя се подава за обработка на предиката action. Първото правило на предиката е предназначено за излизане от режима на запис в базата при въвеждане на думата ’stop’. Второто правило на предиката action е предназначено за добавяне на въведената клауза в базата от данни чрез използуване на вградения предикат аssert. Вграденият предикат fail предизвиква включване на механизма за възврат по веригата от удовлетворени цели. Тъй като всички предикати, удовлетворени след repeat, не се преудовлетворяват, ПРОЛОГ се връща за преудовлетворяване на самия предикат repeat, при това всички свързани променливи (в дадения случай X) се освобождават. Но repeat винаги се преудовлетворява и затова започва повторно изпълнение на цялата верига от цели, съставяща тялото на предиката do , т.е. PROLOG е отново готов за въвеждане на нова клауза.
В общия случай, ако repeat се използува в конюнкция от цели: …..,цел3, repeat, цел4,…., при пропадане на една от целите, стоящи вдясно от repeat, PROLOG никога не може да се върне обратно през предиката repeat и ще повтаря решенията само за целите, стоящи вдясно от него. Затова при използуване на предиката repeat винаги трябва да се осигури условие за спиране генерирането на решения, в противен случай програмата ще се зацикли.
4. Използуване на предикат за цикъл от типа for.
Предикатът for, даден по-долу позволява дадена клауза да бъде изпълнена зададен брой пъти.
for(X,X,X):-!.
for(Y,X,Y).
for(X,Y,Z):-inc(X,X1),for(X1,Y,Z).
Този предикат е с по-общо използуване в сравнение с формулирания по-горе broj_do_deset, защото може да се използува за изброяване на броя на итерациите за всяка цел. Той е аналог на цикъл по брояч от традиционните процедурни езици. Тук предикатът for има следните променливи:
for(Начало, Край, Индексна_променлива)
Например, за извеждане на числата от 1 до 10 се задава въпроса:
?-for(1,10,X),write(X),fail.
Aкo искаме компютърът да “свирне” 3 пъти:
?-for(1,3,X),put(7),fail.
Този прeдикат е оформен съгласно общите правила за образуване на рекурсивни предикати. Първото правило на клаузата for дефинира края на цикъла. Второто правило остойностява индексната променлива с текущото й значение, а третото правило реализира модификацията на променливата на циkъла и рекурсивното обръщение към предиката for.
З А К Л Ю Ч Е Н И Е
В този раздел бяха разгледани методите за реализиране на повтарящи се изчисления, а именно
метод на възврат след неуспех;
метод на отсичането и възврата;
метод на повторението, определян от потребителя и
обобщено рекурсивно правило.
Сходни статии:
- Динамика на съществуването в обектно ориентираното програмиране В обектно ориентираното програмиране тази страна на динамиката, която може да се нарече динамика на съществуването, е реализирана чрез механизмите за създаване и инициализация на екземпляри на обекти В обектно...
- Интелигентна система за демонстриране методи за търсене в пространствено състояниe Графа може да се опише чрез отношението ”nasl”. Съседството между два възела X и Y може да се изрази чрез предиката: nasl(X,Y). който е в сила,ако Y е непосредствен...
