русс | укр

Мови програмуванняВідео уроки php mysqlПаскальСіАсемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование


Linux Unix Алгоритмічні мови Архітектура мікроконтролерів Введення в розробку розподілених інформаційних систем Дискретна математика Інформаційне обслуговування користувачів Інформація та моделювання в управлінні виробництвом Комп'ютерна графіка Лекції


СТРУКТУРИ


Дата додавання: 2013-12-24; переглядів: 1494.


Goal

Do (string, int

Do (F, 2034), write(F).

Clauses

reader (“Іванов”,1567).

reader (“Петров”,2034).

do (F,K):-reader (F,K).

 

Змінна F, що задається в цілі вільна на початку роботи програми. Область її дії тільки цільове твердження. Вона має тип string, як вказано в об’яві предикату do для першого аргументу. Другий аргумент предикату константа типу integer - 2034.

Область дії змінних F та К з правила тільки правило. Ці змінні теж вільні на початку роботи програми. Типи змінних F та К з правила визначаються описом предикату do з секції Predicates.

Кожна з локальних змінних розташовується у стеку і існує тільки під час роботи з твердженням. Зв’язок між твердженнями встановлюється під час співставлення цілі і голови правила(умовного твердження) або цілі і факту.

Зіставлення предикату do з цілі із предикатом do із правила, встановлює зв'язок між відповідними вільними змінними і конкретизує змінну К числом 2034.

F цілі --- F правила

2034 цілі --- K правила

При зіставленні константи і вільної змінної, вільна змінна конкретизується константою.

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

Взагалі конкретизація змінної виконується в двох випадках:

Ø При зіставленні предикатів різних тверджень.

Ø При використанні предикату “=”.

 

Предикат „=”

Предикат „=” працює в двох режимах:

Ø для привласнювання змінній значення;

Ø для порівняння значень виразів.

 

Приклад використання предикату „=” для привласнювання.

Завдання: Збільшити число 105 на 1 і результат вивести на екран.

 

Goal

Go (105).

Clauses

Go (K):- К1 = К+1, write(K1). , де К1- вільна перемінна, а К конкретизована змінна.

Приклад використання предикату для порівняння значень виразу. Завдання: Ввести з клавіатури число. Перевірити, чи дорівнює воно 16*2.

Goal

Readln(N),Go(16,N).

Clauses

Go(K, K1):- K1 = K * 2, write(“Дорівнює”). , де К і К1 конкретизовані змінні.

 

Анонімна змінна

Предикат повинний мати стільки аргументів, скільки описано в секції Predicates. Предикат, що має іншу кількість елементів, вважається іншим предикатом.

Якщо у предикаті використовують декілька аргументів, але не всі вони потрібні в певному твердженні, то для непотрібних аргументів використовують анонімну змінну. Анонімна змінна позначається “_”.

Наприклад: Нехай предикат sved містить відомості про табельний номер робітника і його прізвище. Для процедури, необхідно мати тільки табельний номер. Тоді предикат можна записати sved(Tab, _).

Через анонімну змінну не можна передати значення від твердження до твердження. Анонімна змінна розриває ланцюжок зчеплених змінних. Анонімна змінна заощаджує пам'ять стеку.

 

В Пролозі існують стандартні структури і структури користувача. До стандартних структур відносять списки, файли, дерева. Структури: списки, дерева розташовані в оперативній пам’яті. Структури - файли розташовані на зовнішніх носіях. Списки Прологу однодоменні, тобто всі елементи списку одного типу. Структури у яких елементи одного типу називають регулярними.

Приклад списку:

L=['а', 'b', 'с', 'd'] , де базовий елемент списку – тип char.

Структури користувача визначаються за допомогою функтору. Функтор указує на ознаку, за якою збираються об'єкти в структуру.

Наприклад: структура, що задає адресу людини:

Ad = adress („Київ”, „Чарівна”, 25)

(місто, вулиця, будинок)

Вигляд структури схожий на вигляд предикату. Тому треба знати правило, як їх відрізняти.

Структури відрізняють від предикату по місцю опису і по використанню:

Ø структуру описують в Domains, предикат в Predicates;

Ø структуру використовують на місце аргументу предикату, а предикат для утворення тверджень.

3.5. ПРОГРАМА НА ПРОЛОЗІ

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

Секція Constants (константи)

Іменовані константи визначаються в секції Constants ідентифікатором і значенням, що привласнюється ідентифікатору.

Constants

kvartal=4

Т= ”Текст”

Кожна іменована константа записується в новому рядку.

Константа може задаватися виразом:

Constants

kvartal=24

number = 12 / kvartal.

Іменована константа kvartal повинна визначатися раніше запису виразу. Якщо константа задається виразом, то у виразі не можна посилатися на ту ж константу.

У програмі може бути кілька секцій Соnstаnts. Якщо секцій декілька, то вони збираються компілятором в одну.

Ідентифікатор константи глобальний по всій програмі, тому не можна двічі визначати один і той же ідентифікатор.

При запису ідентифікатору констант у секції Constants можна використовувати як великі, так і малі букви. Але при використанні константи у виразі треба записувати ідентифікатор малими буквами, щоб відрізняти константу від змінної.

Секція [Global] Domains (область)

В секції Domains описують структури і типи даних користувача.

Структура визначається у вигляді:

<Ідентифікатор типу структури> =

<функтор>(<тип поля>,...,<тип поля>)

Стандартна структура список визначається:

<Ідентифікатор типу списку> = <тип базового елементу>*

 

Програміст сам обирає ідентифікатор для типу структури, типу поля, функтору. Опис кожного типу розміщується в окремому рядку секції.

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

Тип користувача – визначається через стандартний тип..

Приклад:

Domains

rr, mm, dd = integer

dat = data (rr, mm,dd)

list = integer*

 

В секції Domains об’явлено типи користувача: тип рік, тип місяць і тип день. Ці типи використовуються при визначенні типу структури dat. З опису структури ясно, що структура записується у вигляді: data (2004, 04,21).

В секції об’явлено також тип списку. Такий список записується: [2,5, 35, 8]. Секція Domains може об’являтися глобальною і бути доступною всім модулям програми.

Секція [Global] Database (база даних)

Використовують для опису фактів, які завантажуються в динамічну базу даних. Синтаксис опису фактів такий же як в секції Predicates. В одному модулю предикат повинен об’являтися один раз, незалежно від секції в якій він об’являється. Секції бувають одна неіменована і декілька іменованих.

Секція [Global] Predicates (предикати)

В секції Predicates описують предикати користувача. Стандартні предикати відомі Турбо – системі, тому їх не описують. Користувач при призначенні ідентифікаторів не повинний використовувати зарезервовані слова.

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

Наприклад:

Predicates

find_element /* Предикат не має аргументів */

pas (integer, integer, real) /* Предикат має три аргументи */

 

Функтор предикату записується за правилами запису ідентифікатору. Функтор може починатися, як з великої букви , так і з малої. Два предикати, що мають однаковий функтор, але відрізняються кількістю і (або) типом аргументів вважаються різними.

Наприклад, предикати вказані нижче різні:

Predicates

Zamena()

Zamena(integer, integer)

Zamena(real, string)

Zamena(integer)

Що стосується доменів аргументів, то вони можуть бути стандартними, структурними типами або типами користувача.

 

Секція Clauses (твердження)

В секції розміщуються умовні твердження і факти.

Твердження, що утворюються за допомогою одного предикату повинні розміщуватися підряд. Групу тверджень з одним предикатом називають процедурою.

Правила запису тверджень секції вимагають, щоб:

Ø Факти записувалися перед умовними твердженнями, за винятком вимоги процедури до іншого порядку.

Ø При запису умовного твердження умови, що переходять на інший рядок записують під умовами. Умовне твердження треба виділяти. Перехід на інший рядок можливий в будь якому місці.

Розглянемо приклад.

Завдання: Вивести на екран прізвище студента по введеному № групи. Вибирати перше прізвище, що зустрілося.

Predicates

Student(integer, string)

Go(integer)

 

Goal

Readln(Gr), Go(Gr).

 

Clauses

Student (“Коваленко”, 410 ).

Student (“Василенко”, 410).

Student (“Петренко”, 420).

Student (“Ткаченко”, 420).

Go(Gr):-student(Fam, Gr),

write(Fam, “ “, Gr), Gr=420.

Go(_).

 

Група фактів, яка записана за допомогою предикату Student – є процедура. Факти записані на початку секції Clauses.

Умовне твердження, що записано за допомогою предикату Go і факт Do – теж процедура. Але в процедурі факт записано після умовного твердження. Якщо факт розташувати з початку, то ціль Go спів ставиться з фактом Go і прізвище студента не буде одержано.

 

Секція Goal (ціль)

В секції записується тільки одна ціль. Ціль може записуватися у формі запису тіла правила.

Приклади запису цілі:

1) Goal

Do.

/* Одиночна ціль */

2) Goal /*Кон’юнкція цілей: ціль Do(N), write(N). істина, якщо істині обидві поточні цілі */

 

3) Goal /*Диз’юнкція цілей: ціль буде істина, якщо буде

істинним один з двох наборів цілей */

Find(Fam), write(Fam); /*перший набір цілей */

Write(“Прізвище не знайдено”). /*другий набір цілей */

4. МЕХАНІЗМИ ПРОЛОГУ

4.1 МЕХАНІЗМ УЗГОДЖЕННЯ ЦІЛІ З БАЗОЮ ДАНИХ

Базою даних Прологу вважають умовні твердження і факти. Виконання програми – процес узгодження цілі з базою даних. Ціль вважають узгодженою, якщо вона істина.

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

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

Процес зіставлення цілі з твердженням називають процедурою уніфікації.

Ціль може бути зіставлена з твердженням якщо:

Ø Функтори цілі і твердження однакові;

Ø Кількість аргументів у цілі і твердження однакові;

Ø Типи аргументів, що стоять на відповідних місцях однакові;

Ø Аргументи на відповідних місцях можна зіставити.

 

Аргументи можна зіставити якщо:

v Вони обидва вільні змінні;

v Один аргумент змінна вільна, а другий константа або конкретизована змінна;

v Обидва аргументи однакові константи.

 

Передача параметрів від твердження до твердження завжди виконується при зіставленні поточного цільового твердження та інших тверджень бази даних.

 

Передача можлива через:

Ø вільну змінну, яка зіставляється з константою або конкретизованою змінною;

Ø механізм зчеплення вільних змінних.

Якщо знайдено твердження зіставимо з ціллю, то можливі такі варіанти:

Ø Твердження факт і тоді поточна ціль узгоджена з базою даних;

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

 

Процес доведення істинності умов називають пошуком вглиб.

Після узгодження всіх поточних цілей необхідних для доведення цілі з секції Goal, ціль вважається узгодженою.

 

Розглянемо процес на прикладі: Нехай пасажиру треба з’ясувати час відходу потягів, що йдуть на Київ пізніше заданого часу. Програма одержує номера потягів, що йдуть на Київ пізніше заданого часу .

 

Predicates

Chas (integer, real, string)

oderg_chas

 

Goal

Clearwindow, oderg_chas.

 

Clauses

Chas (46,7.58,”Київ”).

Chas (83, 12.04, “Київ”).

Chas (75, 14.25, “Київ”).

 

Oderg_chas:- write(“Час ? ”), readreal(Ch),

Chas (N, Ch1,_), Ch1>Ch,

write (“ № поїзда ”, N, “ Час ”,Ch1),fail.

Oderg_chas.

 

Розглянемо дерево цілі для програми:

 
 

 

 


 

 


 

 

В прикладі ціль складне твердження:

1. Перша поточна цільgoal стандартний предикат, який очищує вікно істинна;

2. Друга поточна цільgoal істинна, вона вводить час;

3. Третя поточна цільgoal зіставляється з умовним твердженням cina (V). Умовне твердження істинно, якщо істинні умови:

3.1. Перша поточна цільcina істинна. Вона виводить на екран запитання;

3.2. Друга поточна цільcina стандартний предикат “nl”- new line істинна;

3.3. Третя поточна цільcina істинна вона вводить ознаку вагону;

3.4. Четверта поточна цільcina істинна, якщо вірно введено тип вагону і тому ціль зіставляється з фактом.

Вивід: умовне твердження Cina істинне.

4. Четверта поточна цільgoal істинна. Вона виводить на екран ціну білету.

5. П’ята поточна цільgoal Chas (N, Vrem1) має вільні змінні і зіставляється з фактом. Ціль істинна.

6. Шоста поточна цільgoal перевіряє умову Vrem1>Vrem, якщо умова невірна включається механізм звороту(пункт 6.1).

6.1. Звільнюються значення змінних N і Vrem1, які одержано з факту.

6.2. Перелагоджується ціль Chas (N, Vrem1) з наступним фактом.

6.3. Повторюється пункт 6.При вірній умові виконується пункт 7.

7. Сьома поточна цільgoal істинна. На екран виводиться № потягу і час відходу.

8. Восьма поточна цільgoal стандартний предикат “new line” істинна.

9. Дев’ята поточна цільgoal завжди невірна. Стандартний предикат fail завжди невірний.Включається механізм звороту, який передає керування на найближчий предикат, що розташовано ліворуч і має ще не переглянуті розв’язки. Це предикат Chas (N, Vrem1).

9.1. Звільнюються значення змінних N і Vrem1, які одержано з факту.

9.2. Перелагоджується ціль Chas (N, Vrem1) з наступним фактом.

9.3. Повторюються пункти 6-9.

10. Перебір фактів виконується до тих пір, поки будуть розв’язки у предиката Chas(N, Vrem1). По закінченню розв’язків ціль повертає fail. Однак необхідні відомості одержані.

 

4.2. МЕХАНІЗМ ЗВОРОТУ

Часто поточне цільове твердження може бути зіставлено з декількома твердженнями. Такі твердження називають точками розв’язку цільового твердження.

Механізм звороту (backtracking) дозволяє переузгоджувати ціль, якщо попередня точка розв’язку не підходить. Переузгодження може виконуватися двома способами:

Ø Ціль, що зіставлялася з умовним твердженням, може перелагоджуватися з іншим умовним твердженням чи фактом при прямому трасуванні.

Ø Розглядається кон’юнкція цілі в тілі правила чи в секції Goal при пошуку вглиб. Механізм звороту виконує переузгодження попередньої цілі, якщо поточна ціль не узгоджується.

 

В нашому прикладі розглянуто другий варіант.

Як видно з прикладу, при роботі механізму звороту виконуються дії:

Ø У випадку невірного предикату передається керування на найближчий ліворуч предикат, що має ще розв’язки.

Ø Звільнюються змінні, що одержали в цьому предикату значення або після нього.

Ø Предикат перелагоджується і знову узгоджуються цілі, які стоять праворуч нього.

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

 

У Пролозі немає стандартних предикатів для виконання повторюваних операцій. Повторювані операції можна виконати за допомогою механізму звороту. Для цього використовують за відомо невірну умову - стандартний предикат fail. Застосування предикату fail для дій, що повторюються показано в попередньому прикладі.

 

4.3. МЕХАНІЗМ ЗВОРОТУ І ВІДСІК

Часто механізм звороту включається автоматично і шукає такі розв’язки, які непотрібні. Щоб виключити механізм, використовують стандартний предикат !(відсік).

 

Відсік можна також використати щоб:

Ø обмежити нескінченні цикли;

Ø усунути протилежні за змістом твердження;

Ø рішення одержано, завершити породження розв'язків і перевірки;

Ø закінчити роботу процедури при збою( комбінація "!,fail");

 

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

Робота предикату „Відсік”:

Ø При виконанні предикату „Відсік” вилучаються маркери на предикатах, які мають декілька розв’язків і, які стоять в тілі правила ліворуч відсіку.

Ø При виконанні предикату „Відсік” вилучаються маркери на інших твердженнях процедури, що стоять нижче твердження з відсіком і утворенні за допомогою того ж предикату, що і твердження з відсіком.

 

Розглянемо приклад.

Clauses

Calc (X):- X<10, Write(X).

Calc (X):- X<20, Write(X).

Calc (X):- X<30, Write(X).

 

Goal

Calc (5), fail.

 

Дана процедура виведе на екран тричі значення Х тому, що предикат fail включає механізм звороту. Щоб усунути зайві розв’язки запишемо процедуру з використанням відсіку.

Clauses

Calc (X):- X<10, Write(X), !.

Calc (X):- X<20, Write(X), !.

Calc (X):- X<30, Write(X).

Goal

Calc (5), fail.

Ціль узгоджується з першим твердженням, а відсік витирає маркери на 2 і 3 твердженнях. Значення Х буде виведено один раз.

 

4.4. РЕКУРСІЯ

4.4.1. РЕКУРСИВНИЙ МЕТОД РОЗВ’ЯЗКУ ЗАДАЧ

Операції, що повторюються можуть виконуватися також за допомогою рекурсивного метода. Назва „рекурсія” означає повторний рух.

Рекурсивними можуть бути як дані, так і процедури. До рекурсивних даних відносяться списки, рядки, дерева.

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

L = [1, 2, 3, 4, 5] список

L = [2, 3, 4, 5] список

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

 

При утворенні рекурсивних процедур використовують

рекурсивні методи 2-х доменів:

Ø Висхідний метод рекурсії;

Ø Низхідний метод рекурсії.

 

Розглянемо приклади застосування рекурсивних методів.

Задача: визначити факторіал 5.

Застосуємо висхідний метод рекурсії до розв’язку задачі:

Одиницю умножимо на множник двійку. Одержаний добуток умножимо на наступне число 3 Далі дії повторюються поки множник не дорівнюватиме 5.

5! = 1*2*3*4*5

Для реалізації такого методу необхідно мати початкове граничне значення( в прикладі - 1); мати кінцеве граничне значення(в прикладі - 5) та виконати дії, що повторюються, для значень від початкової граничної умови до кінцевої граничної умови ( дії в прикладі - умножити добуток на наступний множник).

Дії розглянуті в прикладі називають фазою одержання рішення висхідного метода рекурсії.

 

Застосуємо низхідний метод рекурсії до розв’язку задач:

1) Розіб’ємо задачу „знайти 5!”на дві задачі. Перша задача: знайти 4!. Друга задача: умножити результат першої підзадачі на 5. Другу задачу не можна розв’язати поки не буде знайдено розв’язок першої. Тому спочатку треба знайти 4!. Але 4! не можна знайти поки не знайдеться розв’язок задачі 3!, тощо. Породження задач припиняється, якщо буде одержано задачу, що розв’яжеться тривіально 1!=1. Таким чином, щоб одержати розв’язок основної задачі 5! треба спочатку розв’язати підзадачі: 1!, 2!, 3!, 4!.

Для розв’язку кожної підзадачі, крім 1!, треба розв’язати дві задачі подібні задачам вказаним для 5!. Перша задача: Знайти факторіал попереднього числа. Друга задача: Умножити результат першої задачі на число.

2) Використовуючи тривіальний розв’язок підзадачі 1!=1 і розв’язав другу задачу(умножити результат на 2), знайдемо розв’язок підзадачі 2! = 1!*2 = 1*2 =2. Дії будемо повторювати до тих пір, поки не буде одержано розв’язок основної задачі.

 

5! = 4!*5 5! = 24*5 = 120

4! = 3!*4 4! = 6*4 = 24

3! = 2!*3 3! = 2*3 = 6

2! = 1!*2 2! = 1*2 = 2

1! = 1 1! = 1

Дії по розбивання задачі на підзадачі називають редукцією. Метод редукції часто використовують для розв’язку будь - яких задач. Метод редукції, що використовують в низхідній рекурсії називають фазою – редукції.

Дії по знаходженню рішення називають фазою одержання рішення.

Таким чином: Висхідна рекурсія має одну фазу – фазу одержання рішення.

Низхідна рекурсія має дві фази: фазу редукції і фазу одержання рішення.

 

4.4.2. РЕКУРСИВНІ ПРОЦЕДУРИ

 

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

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

 

Розглянемо приклади простих рекурсивних процедур, які написано висхідним та низхідним методом.

Завдання: Вивести на екран числа від 0 до 9.

Висхідний метод рекурсії

Predicates

number (integer )

 

Goal

number (0 ).

 

Clauses

number (10). (1)

number (N ):- write (N), N1=N+1, number (N1 ). (2)

 

Предикати, що стоять в тілі правила (2) реалізують фазу одержання рішення. Останнім предикатом при висхідній рекурсії є рекурсивний виклик процедури. Дії правила виконуються до тих пір, поки початкова гранична умова -0 стане дорівнювати граничній кінцевій умові - 10.

 

Низхідний метод рекурсії

Predicates

number (integer )

 

Goal

number (10 ).

 

Clauses

number (0). (1)

number (N ):-N1=N-1, number (N1), write(N1) (2)

 

Фаза редукції – це виконання в тілі правила предикатів N1=N-1 і number(N1). Фаза виконується до тих пір, поки рекурсивний виклик не зіставиться з фактом і стане істинним.

Предикат write(N1) реалізує фазу одержання рішення.

 

4.4.3. ВИСХІДНА РЕКУРСІЯ

Принципи роботи процедури, що написана висхідним методом рекурсії:

1) Висхідна рекурсія вимагає дві граничні умови початкову і кінцеву.

2) Рекурсивна умова процедури, що написана висхідним методом, має останнім предикатом виклик себе. Пролог визначає тип рекурсії за цією ознакою.

3) Висхідний метод рекурсії не зберігає змінні у стеку, якщо в тілі рекурсивної процедури немає предикатів, що мають альтернативні розв’язки. Таку висхідну рекурсію називають простою. Компілятор перетворює просту рекурсію в ітерацію.

4) Рекурсивна процедура, яку написано висхідним методом, і яка має в тілі предикати, що мають альтернативні розв’язки, використовує стек під конкретизовані змінні.

5) Рекурсивна процедура при кожному новому виклику себе зберігає значення своїх змінних у стеці.

6) Вільні змінні в стеку не розташовуються. Вільні змінні цілі і вільні змінні для кожного рекурсивного виклику процедури, що стоять на відповідних місцях, зчіплюються між собою.

7) Після того, як рекурсивний виклик зіставляється з граничною умовою, починається звільнення стека і при поверненні до цілі стек стає порожнім.

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

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

Розглянемо схеми роботи висхідної рекурсії відповідно умовам завдання.

Схема написання та роботи простої висхідної рекурсії №1

Розглянемо схему написання та роботи простої висхідної рекурсії №1 на прикладі.

Завдання: Вивести на екран усі числа від 1 до 10.

 

Predicates

number (integer )

 

Goal

number (0 ).

 

Clauses

number (10). (1)

number (N ):-N1=N+1, write (N1), number (N1 ). (2)

 

В рекурсивній процедурі факт 1 гранична умова, правило два рекурсивна умова.

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

Задамося питанням, щоб було, якби був відсутній факт

number(10)? Цикл відбувався б нескінченно. Тому, щоб уникнути нескінченного циклу необхідна гранична умова.

Значення аргументів рекурсивного виклику обов'язково повинні сходиться до значення аргументу факту. Інакше рекурсивний виклик ніколи не зіставився би з граничною умовою і відбулося зациклювання.

 

Схема написання та роботи висхідної рекурсії №2

Розглянемо програму, в який потрібно значення змінних повертати в ціль.

Завдання: Нехай треба визначити максимальну вагу багажу в пасажирів літака. Відомо, що кожен факт має наступні дані: № місця пасажиру, кількість речей і загальну вагу речей одного пасажиру.

 

Predicates

max (real,real)

bag (integer, integer, real)

 

Goal

bag (_,_,Ves), max (Ves, Res), write(Res).

 

Clauses

Bag(1, 2, 32.8).

Bag(2, 1, 10.4).

Bag(3, 3, 30.0).

 

max (Ves, Res):-bag (_,_,Ves1), Ves1>Ves, max (Ves1, Res).

max (Res, Res).

 

Перший предикат bag з цілі одержує значення ваги з першого факту для порівняння при знаходженні максимуму. Це значення передається в предикат max. Предикат bag з тіла правила одержує значення ваги з поточного факту і порівнює одержане значення ваги з тим, що передається в предикат при виклику процедури. Більше значення ваги стає поточним максимумом.

Змінна третього аргументу Res (результат) під час виконання рекурсії залишається увесь час вільною, тому в стеці для неї не зберігається ніяких значень. Вільні змінні Res кожного рівня рекурсії зчіплюються між собою і змінною Res з цілі. При досягненні граничної умови змінна Res конкретизується значенням другого аргументу і через апарат зчеплення підіймається до цілі. Конкретизація змінної Res виконується за рахунок того, що другим аргументом факту поставлено змінну Res і при зіставленні факту він одержує максимальне значення ваги з рекурсивного виклику.

 

Схема написання та роботи рекурсії №3

Схеми написання та роботи рекурсії №1 і №2 не можна застосовувати при накоплені даних.

Розглянемо приклад програми.

Завдання: Знайти загальну кількість речей у всіх пасажирів літака.

Predicates

kol (integer,integer,integer) /* номер місця, поточна кількість речей, результат*/

bag (integer,integer, real) /*номер місця, кількість речей у одного пасажиру, загальна вага багажу одного пасажиру */

 

Goal

kol (1,0,Res),write(Res).

Clauses

bag (1,2,10.2).

bag (3,1,17.0).

bag (4,1,5.1).

 

kol(N,K,Res):-bag (N,K1,_),K2=K+K1,N1=N+1, !, kol(N1,K2,Res);

N<=4, N1=N+1, !, kol(N1,K,Res);

kol(_,Res,Res).

 

Пролог при кожному зіставленні предикату проглядає твердження секції Clauses з початку. Тому при накопиченні даних необхідно обов'язково керувати вибором факту bag. В завданні керування відбувається номером місця пасажиру. Якщо не керувати вибором факту, при рекурсивних викликах буде розглядатися весь час перший факт.

Початкова гранична умова задається в цілі у предикаті kol. Для номера - 1, для суми - 0. Кінцева гранична умова, факт, що передає результат у вільну змінну, досягається коли N>4.

Процедура kol має дві гілки: за першою гілкою по номеру місця вибирається з факту кількість речей у пасажира і сумується; за другою гілкою пропускається номер місця, яке вільне.

 

Висхідні рекурсивні процедури, що написані за схемами №2, №3 не будуть перетворені компілятором в ітерацію, тому що в тілі процедури є альтернативні розв’язки для предикатів bag.

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


<== попередня лекція | наступна лекція ==>
КОНСТАНТА | ПРЕДИКАТ REPEАТ


Онлайн система числення Калькулятор онлайн звичайний Науковий калькулятор онлайн